roaring-rs icon indicating copy to clipboard operation
roaring-rs copied to clipboard

Consider removing exact size_hint tracking in iterators

Open Dr-Emann opened this issue 1 year ago • 0 comments

See some discussions under https://github.com/RoaringBitmap/roaring-rs/pull/290#pullrequestreview-2335686711

It's not clear that keeping track of the exact size of an iterator is super useful, and it has a definite cost: it may be surprising that my_bitmap.iter().next() (creating an iterator, and visiting only the first value) will visit every container in the bitmap to compute the size_hint field for the iterator (which is never used).

We could either:

  1. Lazily (but exactly) compute the actual remaining size in size_hint: this means the price is only paid when size_hint() is actually called.
  2. Lazily inexactly compute a minimal/maximal remaining size (whatever we can compute in O(1)). This would be a breaking change: currently Iter implements ExactSizeIterator (on 64 bit platforms). However I believe that's more in line with the expectation of what size_hint() is expected to act like.

I think I lean toward option 1 (probably not worth a breaking change to do 2, and it's O(n), but with a tiny per-container cost, so still expected to be fast). What do you think @Kerollmops?

Dr-Emann avatar Oct 16 '24 02:10 Dr-Emann