HomeFreeBSD

btree: Implement faster binary search algorithm

Description

btree: Implement faster binary search algorithm

This implements a binary search algorithm for B-Trees that reduces
branching to the absolute minimum necessary for a binary search
algorithm. It also enables the compiler to inline the comparator to
ensure that the only slowdown when doing binary search is from waiting
for memory accesses. Additionally, it instructs the compiler to unroll
the loop, which gives an additional 40% improve with Clang and 8%
improvement with GCC.

Consumers must opt into using the faster algorithm. At present, only
B-Trees used inside kernel code have been modified to use the faster
algorithm.

Micro-benchmarks suggest that this can improve binary search performance
by up to 3.5 times when compiling with Clang 16 and up to 1.9 times when
compiling with GCC 12.2.

Reviewed-by: Alexander Motin <mav@FreeBSD.org>
Reviewed-by: Brian Behlendorf <behlendorf1@llnl.gov>
Signed-off-by: Richard Yao <richard.yao@alumni.stonybrook.edu>
Closes #14866

Details

Provenance
Richard Yao <richard.yao@alumni.stonybrook.edu>Authored on May 26 2023, 5:03 PM
GitHub <noreply@github.com>Committed on May 26 2023, 5:03 PM
Parents
rGbb736d98d133: Fix inconsistent definition of zfs_scrub_error_blocks_per_txg
Branches
Unknown
Tags
Unknown

Event Timeline

GitHub <noreply@github.com> committed rG677c6f845794: btree: Implement faster binary search algorithm (authored by Richard Yao <richard.yao@alumni.stonybrook.edu>).May 26 2023, 5:03 PM