Re: [bloom] Andrzej's feedback

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

El 18/05/2025 a las 19:54, Andrzej Krzemienski escribió:
>
>
> niedz., 18 maj 2025 o 18:52 Joaquin M López Muñoz via Boost 
> <boost_at_[hidden]> napisał(a):
>
>     El 18/05/2025 a las 13:29, Andrzej Krzemienski via Boost escribió:
>     > Hi Everyone,
>     > The following can hardly be called a library review, but I still
>     wanted to
>     > give this feedback.
>
>     > 7. I think that you are missing a precondition for operators &=
>     and |=.
>     > They work under the assumptions that for both filters f1 and f2
>     inserting
>     > the same element renders the same bit pattern in the hash. But
>     this is not
>     > the case when the hashers that I provide to f1 and f2 have the
>     same type
>     > but different initial state:
>     >
>     > filter<T, MyHash> f1(1000, MyHash{1});
>     > filter<T, MyHash> f2(1000, MyHash{2});
>
>     Well, technically the behavior is well defined even if the hashers
>     are not
>     equivalent:
>
>     "[...] changes the value of each bit in the internal array with the
>     result of
>     doing a logical AND operation of that bit and the corresponding
>     one in x."
>
>     Admittedly, doing this with non-equivalent hashers will produce
>     nothing
>     but garbage, so... well, I don't know what I should do here :-)
>
>
> I am pretty sure there is only one right answer here.
>
> While the semantics of the function are specified in terms of setting 
> the bit values, the value that this interface brings to the users is 
> at a higher level. It is this:
> If filter f1 indicates a set S1 of values that are certainly not 
> stored (those for which may_contain() returns false), and filter f2 
> indicates a set S2 of values that are certainly not stored in f2, then 
> the result is a filter whose values certainly not stored are the union 
> of S1 and S2.
>
> This equivalence of specifications (in terms of bits, and in terms of 
> definitely not stored values) is broken when f1 and f2 use different 
> hashes.This is sufficient a reason to call this a precondition: 
> breaking the high-level abstraction/guarantee. Having or not having 
> undefined behavior is irrelevant here.

Not sure I fully agree, but, hey, it's just a precondition
statement in the documentation, so I'll add it.

Thank you,

Joaquin M Lopez Munoz