]> git.ipfire.org Git - thirdparty/haproxy.git/commit
IMPORT: eb32/eb64: use a more parallelizable check for lack of common bits
authorWilly Tarreau <w@1wt.eu>
Sat, 7 Jun 2025 11:12:40 +0000 (13:12 +0200)
committerWilly Tarreau <w@1wt.eu>
Wed, 17 Sep 2025 12:30:31 +0000 (14:30 +0200)
commitc9e4adf608603b1cb9a10f999697097814d6602e
tree5ecef3bd6972e987243d91720a2d1d9da9304a6e
parent6af17d491fb9759adb45d855c5c87b5400b8a63c
IMPORT: eb32/eb64: use a more parallelizable check for lack of common bits

Instead of shifting the XOR value right and comparing it to 1, which
roughly requires 2 sequential instructions, better test if the XOR has
any bit above the current bit, which means any bit set among those
strictly higher, or in other words that XOR & (-bit << 1) is non-zero.
This is one less instruction in the fast path and gives another nice
performance gain on random keys (in million lookups/s):

    eb32   1k:  33.17 -> 37.30   +12.5%
          10k:  15.74 -> 17.08   +8.51%
         100k:   8.00 ->  9.00   +12.5%
    eb64   1k:  34.40 -> 38.10   +10.8%
          10k:  16.17 -> 17.10   +5.75%
         100k:   8.38 ->  8.87   +5.85%

This is ebtree commit c942a2771758eed4f4584fe23cf2914573817a6b.
include/import/eb32tree.h
include/import/eb64tree.h