Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Consider removing exact size_hint tracking in iterators #294

Closed
Dr-Emann opened this issue Oct 16, 2024 · 0 comments · Fixed by #295
Closed

Consider removing exact size_hint tracking in iterators #294

Dr-Emann opened this issue Oct 16, 2024 · 0 comments · Fixed by #295
Assignees
Labels
proposal A feature proposal

Comments

@Dr-Emann
Copy link
Member

Dr-Emann commented Oct 16, 2024

See some discussions under #290 (review)

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 Dr-Emann added breaking This change will require a bump of the minor or major version. proposal A feature proposal labels Oct 16, 2024
Dr-Emann added a commit to Dr-Emann/roaring-rs that referenced this issue Oct 16, 2024
This means the price of visting every container is only paid when needed.

Fixes RoaringBitmap#294
Dr-Emann added a commit to Dr-Emann/roaring-rs that referenced this issue Oct 16, 2024
This means the price of visting every container is only paid when needed.

Fixes RoaringBitmap#294
Dr-Emann added a commit to Dr-Emann/roaring-rs that referenced this issue Oct 16, 2024
This means the price of visting every container is only paid when needed.

Fixes RoaringBitmap#294
@Dr-Emann Dr-Emann removed the breaking This change will require a bump of the minor or major version. label Oct 18, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
proposal A feature proposal
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants