HomeFreeBSD

radix_trie: simplify ge, le lookups

Description

radix_trie: simplify ge, le lookups

Replace the implementations of lookup_le and lookup_ge with ones
that do not use a stack or climb back up the tree, and instead
exploit the popmap field to quickly identify the place to resume
searching if the straightforward indexed search fails.

The code size of the original functions shrinks by a combined 160
bytes on amd64, and the cumulative cycle count per invocation of
the two functions together is reduced 20% in a buildworld test.

Reviewed by: alc, markj
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D40936

Details

Provenance
dougmAuthored on Jul 19 2023, 2:43 PM
Reviewer
alc
Differential Revision
D40936: radix_trie: simplify ge, le lookups
Parents
rGe38c634b77de: vfs: Add a parenthese to vn_lock_pair() asserts to silence gcc
Branches
Unknown
Tags
Unknown