]> git.ipfire.org Git - thirdparty/haproxy.git/commit
OPTIM: tools: improve hash distribution using a better prime seed
authorWilly Tarreau <w@1wt.eu>
Sat, 12 Aug 2023 15:28:13 +0000 (17:28 +0200)
committerWilly Tarreau <w@1wt.eu>
Sat, 12 Aug 2023 17:04:34 +0000 (19:04 +0200)
commitf0d188f6edc81922849b11031783c69e678fac9f
tree2a56185150e6a99d333daf1f8d5150632019d947
parent58946d44f87e982a83f6ce34f7aefae37425e45c
OPTIM: tools: improve hash distribution using a better prime seed

During tests it was noticed that the current hash is not that good
on 4- and 5- bit hashes. About 7.5% of all the 32-bit primes were tested
as candidates for the hash function, by submitting them 128 arrangements
of N pointers among 40k extracted from haproxy's pools, and the average
fill rates for 1- to 12- bit hashes were measured and compared. It was
clear that some values do not provide great hashes and other ones are
way more resistant.

The current value is not bad at all but delivers 42.6% unique 2-bit
outputs, 41.6% 3-bit, 38.0% 4-bit, 38.2% 5-bit and 37.1% 10-bit. Some
values did perform significantly better, among which 0xacd1be85 which
does 43.2% 2-bit, 42.5% 3-bit, 42.2% 4-bit, 39.2% 5-bit and 37.3% 10-bit.

The reverse value used in the ptr2_hash() was really underperforming and
was replaced with 0x9d28e4e9 which does 49.6%, 40.4%, 42.6%, 39.1%, and
37.2% respectvely.

This should slightly improve the accuracy of the task and memory
profiling, and will be useful for pools.
include/haproxy/tools.h