Packing heap bits

[eliassjogreen]

An easy memory win, and hopefully in turn performance win would be to move all of the Box<[bool]>s to use some kind of packed representation which should hopefully save ~>8x the memory (With a full "default" heap capacity of 18304 bytes we would shrink it to a mere 2288 bytes).

Doing a quick bit of searching I could find a few appropriate rust crates for creating and using bit-vectors:

• https://github.com/PsiACE/bitsvec

  • SIMD accelerated
  • Sadly #![feature(portable_simd)] which it uses isn't available on stable rust channel
  • Fastest according to own benchmarks
  • Uses SmallVec, might be bad for our use case because we can probably expect to almost always exceed the limit of SmallVec
  • No trait Iterator support :(

• https://github.com/ferrilab/bitvec

  • Most popular, 1.3k gh stars, 100k+ uses

• Roll our own

  • Full control, can optimize for our specific use-case. Yet another of our specialized small_* types
  • More work, reinventing the wheel or just extra fun?
  • SIMD?

[aapoalas]

Absolutely, yeah! One thing to note is that we'll likely want the mark bits to be atomic in the future, so Box<[AtomicU8]> would probably be our packed strategy.

[eliassjogreen]

Right! Sounds like we would need to roll our own then!

[aapoalas]

Done in #902