Re: [bloom] Andrzej's feedback

From: Andrzej Krzemienski (akrzemi1_at_[hidden])
Date: 2025-05-18 17:54:45

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.

Regards,
&rzej;