Constant time len

[saik0]

Fixes #45 Closes #105

[saik0]

I'm not sure what the right approach to testing this is.

[Kerollmops]

I'm not sure what the right approach to testing this is.

Do you mean benchmarking the constant length or checking that select which uses len() is valid? You already added tests for the select method so... Nothing more to do.

However, checking that the length is valid is maybe a little bit complex, we could maybe add an iter().count() == .len() after all of our proptests or something?

[saik0]

However, checking that the length is valid is maybe a little bit complex

This is what I meant. I'm trying to think of a clean way to debug_assert that each time the len changes we compare it against the computed len

[Kerollmops]

This is what I meant. I'm trying to think of a clean way to debug_assert that each time the len changes we compare it against the computed len

Wouldn't it be ok to directly do debug_assert_eq!(self.iter().count(), self.len())? As the macro expansion is done at compile-time, therefore the call to iter/count is only done for debug builds.

I just hope that we haven't implemented the count method on our iterator to only call self.len() 😂

[Kerollmops]

I just checked in the playground and the macro expansion indeed works like that: it didn't panic when compiling in release.

[saik0]

I just hope that we haven't implemented the count method on our iterator to only call self.len()

Of course it does. Why should it recompute the cached len?

Edit: It's an exact size iterator whose size hint is initialized by RoaringBitmap::len I believe ExactSizeIterator overrides count to return the exact size

[Kerollmops]

Of course it does. Why should it recompute the cached len?

Ok so we should trick by doing a fold instead.

[saik0]

Of course it does. Why should it recompute the cached len?

Ok so we should trick by doing a fold instead.

We'd probably have to wrap it in a black_box. LLVM is very clever.

[saik0]

Thinking we should assert invariants #197 before we merge this to be sure we didn't introduce a regression