]> git.proxmox.com Git - mirror_zfs.git/commit
Several B-tree optimizations
authorAlexander Motin <mav@FreeBSD.org>
Fri, 24 Jun 2022 20:55:58 +0000 (16:55 -0400)
committerGitHub <noreply@github.com>
Fri, 24 Jun 2022 20:55:58 +0000 (13:55 -0700)
commitc0bf952c846100750f526c2a32ebec17694a201b
treeeb9d87edafcc23a03e6e489371995c14fe6d6dd2
parentccf89b39fe7f30dd53aec69e04de3f2728c7387c
Several B-tree optimizations

- Introduce first element offset within a leaf.  It allows to reduce
by ~50% average memmove() size when adding/removing elements.  If the
added/removed element is in the first half of the leaf, we may shift
elements before it and adjust the bth_first instead of moving more
elements after it.
 - Use memcpy() instead of memmove() when we know there is no overlap.
 - Switch from uint64_t to uint32_t.  It does not limit anything,
but 32-bit arches should appreciate it greatly in hot paths.
 - Store leaf capacity in struct btree to avoid 64-bit divisions.
 - Adjust zfs_btree_insert_into_leaf() to always result in balanced
leaves after splitting, no matter where the new element was inserted.
Not that we care about it much, but it should also allow B-trees with
as little as two elements per leaf instead of 4 previously.

When scrubbing pool of 12 SSDs, storing 1.5TB of 4KB zvol blocks this
reduces amount of time spent in memmove() inside the scan thread from
13.7% to 5.7% and total scrub time by ~15 seconds out of 9 minutes.
It should also reduce spacemaps load time, but I haven't measured it.

Reviewed-by: Paul Dagnelie <pcd@delphix.com>
Signed-off-by: Alexander Motin <mav@FreeBSD.org>
Sponsored-By: iXsystems, Inc.
Closes #13582
include/sys/btree.h
module/zfs/btree.c