HomeFreeBSD

radix_tree: redefine the clev field

Description

radix_tree: redefine the clev field

The clev field in the node struct is almost always multiplied by
WIDTH; occasionally, it is incremented and then multiplied by
WIDTH. Instructions can be saved by storing it always multiplied by
WIDTH.

For the computation of slot(), this just eliminates a
multiplication. For trimkey(), where the caller always adds one to
clev before passing it as an argument, this change has the caller, not
the caller, do that. Trimkey() handles it not by adding WIDTH to the
input parameter, but by shifting COUNT, and not 1. That produces the
same result, and it relieves keybarr of the need to test to avoid
shifting by more than 63 bits, since level is always <= 63.

This takes 3 instrutions and 14 bytes out of the basic lookup loop on
amd64.

Reviewed by: kib
Tested by: pho (as part of a larger change)
Differential Revision: https://reviews.freebsd.org/D41226

Details

Provenance
dougmAuthored on Jul 30 2023, 6:20 AM
Reviewer
kib
Differential Revision
D41226: radix_tree: redefine the clev field
Parents
rG64884e0d4ce7: libarchive: merge from vendor branch
Branches
Unknown
Tags
Unknown