Thank you for your thoughtful reply. See my comments below.
On Sun, Apr 28, 2024 at 11:10 AM Alex Herbert <alex.d.herb...@gmail.com> wrote:
>
> Hi Gary,
>
> I am in favour of using nomenclature and patterns that will be familiar to
> a Java developer. But only if they match the familiar JDK use patterns. The
> Bloom filter package has some atypical use patterns that have driven the
> current API to where it is. I'll try and describe these below.
>
> On Sun, 28 Apr 2024 at 14:16, Gary Gregory <garydgreg...@gmail.com> wrote:
>
> > Hi Clause, Albert, and all,
> >
> > Since the introduction of lambdas in Java 8, Java has a well-defined
> > terminology around the classic producer-consumer paradigm but (for
> > reasons unknown to me) realized in the functional interfaces *Supplier
> > and *Consumer. In addition, as of Java 5, we have the Iterable
> > interface.
> >
> > In our new Bloom filter package we have new interfaces called
> > *Producer (as opposed to *Supplier), where some of these new
> > interfaces are formally annotated with @FunctionalInterface and some
> > not (for example, BloomFilterProducer).
> >
> > My question is: Why call these "Producers" instead of "Suppliers"? Is
> > the formal Bloom filter literature tied to the "Producer" terminology
> > in a way that would make adapting to the Java term confusing? I know I
> > brought up a similar topic recently, but I would like to revisit it
> > now that I've started to read Claude's blog drafts. Even without
> > making the current "Producers" formal suppliers by extending Supplier,
> > would it be worth using the Java terminology?
> >
>
> Claude is familiar with the literature and can comment on that. I would
> defer to the literature if it is a common term.
>
> There is one notable distinction to JDK suppliers. Suppliers only supply 1
> element and must be repeatedly called to generate more. The Producers in
> the BloomFilter package will supply multiple values. They are invoked using
> a forEach pattern with the intention of supplying all the elements to a
> predicate, not a consumer. If any of those elements is rejected by the
> predicate then the rest of the elements are not supplied. So this is a
> fail-fast bulk supplier.
Ah, this sounds like a special Iterator, fail-fast as you mention, and
Java does not have that in Java 8 at least.
The Producer class suffix still confuses me since this is neither a
factory nor a traditional supplier. If the classes were called
*Iterator and not extend iterator, then it would also be confusing.
The question is whether it would be useful to extend Iterator or if
the class would never be used as a traditional Iterator. I'll that to
an SME ;-)
>
>
> >
> > My second observation is that some might neither be "Producers" or
> > "Suppliers" but instead be extensions of Iterable. For example,
> > BitMapProducer is not a factory for instances of BitMap; the BitMap
> > does not appear in the signatures of BitMapProducer methods. From a
> > strict Java POV, this is (slightly) perplexing.
> >
>
> Iterable was suggested in an earlier API, particular for the IndexProducer.
> IIRC it was rejected on the basis of simplifying the code for the caller in
> the fail-fast case. Otherwise every user of the iterator must implement
> fail-fast loops over the elements. There may have been other reasons so it
> could be worth a check in the mailing list archives. It would require going
> back a few years but it was discussed on the dev list.
>
> The term BitMap refers to a long that holds 64-consecutive indices as
> either present or absent. You can consider the sequential bitmaps
> containing all indices from [0, n) as the serialized state of a Bloom
> filter with n bits. This is essentially a BitSet as you can see from the
> SimpleBloomFilter implementation. This originally wrapped a BitSet; it was
> converted to directly implement the required read/write bit functionality
> on the grounds of performance (no memory reallocation; no index checks).
>
> We do not have a BitMap class since we use a long primitive.
Yes, we do; it's right here: org.apache.commons.collections4.bloomfilter.BitMap
This makes it hard for a non-expert to groke IMO. If we use terms in
class names and discussions that are... what? Mismatched or misnamed.
A rename would
> be to LongProducer causing a name clash with the JDK. Renaming to something
> else is possible but I believe BitMap is a term from the literature.
>
>
> >
> > Instead (forgetting the class name issue for now), we could have:
> >
> > @FunctionalInterface
> > public interface BitMapProducer extends Iterable<LongPredicate> {...}
> >
> > Which would let implementations define:
> >
> > Iterator<LongPredicate> iterator();
> >
> > Instead of:
> >
> > boolean forEachBitMap(LongPredicate predicate);
> >
>
> The BitMapProducer is not iterating LongPredicates. It is iterating longs
> to be accepted by a single LongPredicate. The boolean return allows
> signalling to stop the forEach loop. There is no primitive specialisation
> of Iterator for long. There is a Spliterator.OfLong but that bundles some
> other API that we do not wish to support, namely parallel streaming via
> split and the ability to advance element by element (tryAdvance). Currently
> we only implement the equivalent of the forEachRemaining pattern from
> Spliterator. That accepts a consumer and so fail-fast would be done via
> raising a runtime exception. Given that fail-fast is a key feature of a
> Bloom filter then we do not want this to be implemented via exceptions.
>
> The primary use case for fail-fast is to stop as soon as a bit index is
> found, or not found (case dependent). Consider a Bloom filter that has 20
> indices per hashed item. You have populated the filter with items, each has
> 20 random indices. You then check if a new item is not contained in the
> filter by creating indices for the new item with your hash function and
> checking each index against those already in the filter. If your new
> element has an index not in the filter, then you have not seen this element
> before. This process can be done by creating all the indices by hashing as
> the first step, then comparing each to the filter. Or you can generate
> indices lazily, only creating the next index if the current one is present
> in the filter. This requires fail-fast index iteration and dynamic index
> generation by the hasher. You can walk through this looking at
> the EnhancedDoubleHasher. This is what takes a byte[] (capturing
> information on the item) and creates indices. But it only creates indices
> until it is triggered to stop.
>
> Note that the filter can only tell you with 100% confidence that an item
> has not been observed. It cannot tell you with 100% confidence it has been
> observed, as the random indices created by hashing the item may all be
> present in the collective indices from all items added to the filter. The
> Shape class has the standard computations to create a filter with enough
> bits to control the false-positive rate for the expected number of items
> you wish to store.
OK, it is now clear that this is a fail-fast (or breakable, or some
term) iterator. I'd would like to see the Javadoc clearer for those
classes and forEach* methods. What about something like: "The first
predicate that returns false causes the iteration to stop."?
>
>
> >
> > Same comment for IndexProducer.
> > Same comment for BloomFilterProducer.
> > Is this too much Java-ness?
> >
> > CellConsumer looks like a Predicate, not a traditional Java *Consumer.
> > We have a specialization called LongBiPredicate so I propose we rename
> > and extract CellConsumer as IntBiPredicate.
> >
>
> Cell is a term from the literature. A cell is an index and a count. So
> although you are accepting two int values, they are actually only one cell.
> A rename to CellPredicate would be more appropriate to imitate
> Predicate<Cell> where the Cell is a pair of int primitives.
I agree that reusing the predicate term works here.
>
> In contrast the LongBiPredicate is used to accept two BitMaps that have
> been paired by iterating over two filters with the same shape. This is not
> an extensible design as you can only iterate over a pair of filters, and
> not n filters of the same shape. The use case is in standard set operations
> such as union and intersect which are used to generate metrics used in the
> literature (see the SetOperations class). This could be renamed to
> BitMapBiPredicate. However I think the current name was chosen to be in
> keeping with the JDK j.u.function package.
And that's a good thing :)
>
> Hope that helps set some background.
Absolutely and thank you. I hope you or Clause will take the time to
clarify the Javadoc here and there for non-SMEs! :-) See my suggestion
above.
Gary
>
> Alex
>
>
>
> >
> > TY!
> > Gary
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> > For additional commands, e-mail: dev-h...@commons.apache.org
> >
> >
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
