Introducing the most important speed-up to date 🚀

Hey folks,

Before I start the note on the new release, I'll just introduce what roaring-rs is. It is a Rust idiomatic port of the Roaring Bitmap data structure introduced by Daniel Lemire, G. Ssi-Yan-Kai and O. Kaser. The data structure simply defines better-compressed sets of bits, faster and memory-efficient data structures for performing operations on sets, i.e. intersections, unions... and so on.

So, about this new version of roaring-rs, it is a bit special because it's the version that introduces the most performance improvements in a while and on the most topics. Most of this amazing work was done by @saik0, a new contributor to the crate 🎉. @schmidek implemented DoubleEndedIterator on the bitmap iterators 💪

Breaking changes

• Removed deprecated set ops such as union_with. Use the corresponding operators |=.
• Minimum supported Rust version (MSRV) increased to 1.56.
• deserialize_from validates inputs. In 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 lower or equal to a given 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 proper 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

Version 0.8.1

• Fix the Sub::sub implementation of the internal Store type (Thanks to @kolstae).

Version 0.8.0

• Change the insert_range API to accept the idiomatic RangeBounds<u32> (thanks to @oliverdding and @tomjw64).
• Improve the internal Pairs Iterator type.
• Modify the from_sorted_iter and append methods to return a Result (Thanks to @MarinPostma).

Version 0.7.0

• Introduce a new non-panicking push method (thanks @MarinPostma).

Version 0.6.7

• Replace set ops literal methods (intersect_with...) by the Rust std ops traits (BitAnd...)

Version 0.6.6

• remove redundant slicing (thanks to @zyctree).
• Optimize the BitAnd/Assign and BitOr/Assign operations.

Version 0.6.5

• Improve unions between array stores by writing into a new allocation instead of inserting.
• Improve the RoaringBitmap::deserialize_from method by fetching bigger batches of bytes at a time.
• Remove the local retain_mut function we introduced (#85) by an external library that does it for us (thanks to @upsuper).

Version 0.6.4

• Improve the bitmap intersect and differences operation again.

Version 0.6.3

• Improve the bitmap intersect and differences operation.
• Introduce Treemap serialization (thanks to @vorot93).

Version 0.6.2

• Improve the bitmap to_array conversion (thanks to @damnMeddlingKid).
• Fix a deserialization bug (thanks to @detailyang).
• Add RoaringBitmap::push/append/from_sorted_iter and RoaringTreemap::push/append/from_sorted_iter (thanks again to @zommiommy).
• Add RoaringBitmap::insert_range and RoaringTreemap::insert_range (thanks again to @domodwyer).