Re: [bloom] Benchmarks with Knuth multiplier-based hash production

From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2025-06-07 09:05:37

El 07/06/2025 a las 10:32, Peter Dimov via Boost escribió:
> Joaquin M López Muñoz wrote:
>> El 07/06/2025 a las 1:33, Peter Dimov via Boost escribió:
>>> Joaquin M López Muñoz wrote:
>>>> Hi,
>>>>
>>>> As per feedback given here:
>>>>
>>>> https://lists.boost.org/Archives/boost//2025/05/259548.php
>>>>
>>>> I've experimented with the  hash production scheme suggested by
>>>> Kostas, where h_{i+1} is calculated as h_i * 6364136223846793005 mod
>>>> 2^64:
>>> Where does this multiplier come from?
>> This is the constant suggested by Kostas. A search on the Internet suggests this
>> is used in connection with so-called PCG algorithms.
> Wikipedia lists it as "MMIX by Donald Knuth", 6364136223846793005 * x + 1442695040888963407 mod 2^64.
>
> This is an LCG multiplier (used with b != 0), so it's not clear whether it would be
> "good" for an MCG (b == 0).
>
> For multipliers my go-to reference is Vigna and Steele,https://arxiv.org/pdf/2001.05304.
>
> For MCG mod 2^64, it gives 0xf1357aea2e62a9c5 as the "good multiplier".

I can use that, but I'm currently more concerned about the potential
impact on performance, which is allegedly independent of the
particular constant chosen.

Joaquin M Lopez Munoz