El 13/06/2025 a las 14:47, Kostas Savvidis via Boost escribió:
On 12 Jun 2025, at 21:56, Joaquin M López Muñoz via Boost <boost@lists.boost.org> wrote:
For branchful lookup, a cost model for mixed lookup would be
P*M*(A*K) + (1-P)*M*C
where P is the percentange of successful lookups and M is an extra cost factor on top of the non-mixed approach due to branch mispredictions.
I agree this effect will affect measurements to the point that you will never be able to be 100% sure. Lets just agree on the obvious consensus: an extra 64bit multiplication cannot affect the running time of any program on modern CPUs.
I finally implemented the change here: https://github.com/joaquintides/bloom/commit/b28e526b9e2994d5470adb6ae502481... There's a measureable effect, at least on microbenchmarks, compare results without * (before) and with * (after): https://github.com/boostorg/boost_bloom_benchmarks/blob/alternative-hash-pro... But, well, it is what it is.
The multiplier is from THE ART OF COMPUTER PROGRAMMING by D. Knuth, volume II, page 108.
I've settled for two multipliers (one for 64-bit and another for 32-bit mode) from Steele and Vigna: https://arxiv.org/pdf/2001.05304 Joaquin M Lopez Munoz