0.9.0 Tracking Issue

[saik0]

Here's what I think is still left before next release

• Sample data for benchmarking #129
• Add fast counts #167
• Feature: Add select #135
• Perf regression: Iteration #176
• Non-validating deserialize #177
• quantify perf delta for stable
• quantify perf delta for nightly+simd
• manually verify docs
  • rename deserialize_from_unvalidated to deserialize_unchecked_from #199
  • specify None return cases for select #202
• create release notes
• bump direct dependency minor versions #193
• bump rust edition to 2021 #194
• Remove the *_with deprecated methods #200
• remove in place array-array xor operation #205
• Create bench comparison to CRoaring #204 (deferred to next release)

Release notes

• Breaking changes

  • Removed deprecated set ops such as union_with. Use the corresponding operators |=.
  • MSRV increased to 1.56
  • deserialize_from validates inputs. It some cases it can be 4x slower. For workloads that are heavy in deserialization from trusted sources migrate to deserialize_unchecked_from

• Performance optimizations

  • from_sorted_iter and append are exponentially faster. They should be preferred over collect and extend whenever adding monotonically increasing integers to the set as it's about 2-2.5x faster.
  • Other performance optimizations.

    	Min	Mean	Max
    Iteration	6%	57%	125%
    And	0%	7%	22%
    Or	0%	10%	33%
    Sub	0%	9%	39%
    Xor	4%	90%	209%

• New features

  • rank Returns the number of integers that are <= value. rank(u64::MAX) == len()
  • select Returns the nth integer in the set or None if n <= len()
  • union_len intersection_len ... and so on. Compute the cardinality of a set operation without materializing it. Usually about twice as fast as materializing the bitmap.
  • implemented DoubleEndedIterator
  • implemented ExactSizeIterator (on 64 bit targets only)
  • EXPERIMENTAL SIMD feature (requires rust nightly)

    	Min	Mean	Max
    And	0%	34%	141%
    Or	2%	45%	145%
    Sub	0%	51%	168%
    Xor	0%	130%	437%

• Other

  • Added property testing suite for set operations
  • Added many benchmarks and real world datasets

Perf numbers are for pairwise operations on collections of bitmaps from real datasets.
Pairwise as in: B₁ ∩ B₂, B₂ ∩ B₃, ... B_N-1 ∩ B_N

[saik0]

@Kerollmops

Thinking out loud: A major version bump would be a good time to bump rust edition to 2021

Edit: Plus, we've already bumped MSRV to min supported ver for 2021 edition

[saik0]

Here are my benchmark comparisons for v0.8.1 to 49455d4

Environment

Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz. Hyperthreading and frequency scaling disabled. Base Arch Linux install. Linux 5.16.5-arch1-1

Analysis

On rust stable (scalar only)

The good

1. from_sorted_iter and append are exponentially faster
2. iteration can be as much as 125% faster [1]
3. Perf improved for all set ops [1]
   • intersection can be as much as 22% faster
   • union can be as much as 33% faster
   • difference can be as much as 40% faster
   • symmetric difference can be as much as 50% faster

[1] Depends on the dataset. Can be as little as zero

The bad

1. deserialize_into is between 60-400% slower with data validation. We are planning on calling this out.
2. container::len used to be field access, now it must branch on store type. This is a tradeoff we made to make cardinality tracking while flipping bits on bitmaps, which is part of why all the set ops are faster. However it has led to had some unintended downstream effects.
   • RoaringBitmap::len is slower by about 60%.
   • RoaringBitmap::serialize_into is about 10-20% slower
   • Absolute difference for both of the above is on the order of tens of micros per dataset of 200 bitmaps each. I think this is a great trade off given the wins for set ops can be measured in millis and are much more likely to be on hot code paths than serializing for most use cases.

Data

critcmp.zip

Notes

• Difference between old deserialize_into and new deserialize_into_unvalidated is within noise threshold. This is not absent from the data, as previously there was no deserialize_into_unvalidated benchmarks that could be compared automatically. I had to validate this manually.

• is_disjoint being ~15% slower appears to have just been noise. I wasn't able to reproduce this over multiple runs

Analysis for SIMD coming later, but the data is in the zip if you want to peek

[saik0]

SIMD

• intersection can be as much as 140% faster
• union can be as much as 145% faster
• difference can be as much as 168% faster
• symmetric difference can be as much as 437% faster. mostly because Scalar in place xor has poor performance #191

[saik0]

@Kerollmops Time to get rid of union_with() (and others) deprecated in 0.6.7? (April 2021)

[Kerollmops]

Time to get rid of union_with() (and others) deprecated in 0.6.7? (April 2021)

You are right, I created issue #200 about that thank you for the reminder.

Here are my benchmark comparisons for v0.8.1 to 49455d4

I am so much impressed by what you've done and it is only the benchmarks for x64_86 🎉

About the scalar version, you are right: the perf losses aren't much important as they are under the millisecond!
About the SIMD version, that's impressive too! I was sure your work would break the law of physics 🚄 🚀

Once we release the new version of roaring I will create a GitHub release to talk about the work you have done, featuring Meilisearch just for its fame and the indirect help you bring to this project. We are so much awaiting this release of Roaring on the Meilisearch side, just to see those flamegraphs melt 🧊

Meilisearch and other projects intensively using roaring would also gain speed by using the new multi-ops API, however, it can be released in a future version as it will not be breaking!

[saik0]

I am so much impressed by what you've done and it is only the benchmarks for x64_86 🎉

Thanks. I'm curious to see how the array_array SIMD does on other platforms

We are so much awaiting this release of Roaring on the Meilisearch side, just to see those flamegraphs melt

😂

I'm pleased to contribute to OSS again, it's been too long.

Meilisearch and other projects intensively using roaring would also gain speed by using the new multi-ops API, however, it can be released in a future version as it will not be breaking!

That reminds me. I'm going to create a planning ticket for next_version++

[saik0]

@Kerollmops
I kicked out #204. It can wait.

Do you think I should try to do a quick fix for #191 since the theme of this release is: 🚀

[Kerollmops]

Do you think I should try to do a quick fix for #191 since the theme of this release is: 🚀

You can indeed if you have already a good idea of how you would speed this up!

[saik0]

You can indeed if you have already a good idea of how you would speed this up!

Just get rid of the in place operation and force an allocation like we have with union.

[saik0]

@Kerollmops Release notes contains perf from unmerged xor change. AFAICT master is ready to ship as 0.9 once merged

[saik0]

@Kerollmops Updated release notes for #187. Are we ready to bump the version and release?

[Kerollmops]

Yeah, I think we are ready to do so now. You are right that even if there are no breaking changes we should bump the version as we drastically impacted the performances of deserialize_from. I will do this either today or tomorrow.

Thank you for reminding me!