Experimental bitset that might be more efficient for large sparse sets

[AshleyRoll]

Hi,

I've been experimenting with a modified bitset that:

• now have a bitset_simple and bitset_summarised and a
  bitset is a compile time choice between them based on NumBits
  This choice is purely arbitrary and would need performance tuning and
  probably would be different on different platforms.
• modified to allow different storage types for different platforms
  where word sizes may vary. Defaults to uint32_t
• Implemented iterators for both options, for_each is now implemented
  in terms of the iterators. Could be deleted and ranged for used in the
  rest of the implementation.
• The bitset_summarised uses a bitset_simple to store both its bits
  and a summary set containing a bit for each storage element. The
  summary bit is set when any bits are set in that storage location.
  This allows optimised traversal and logical AND/OR operations for
  large but generally sparse bit sets.

This is a proof of concept, additional work on characterising the
performance would be needed before decided if it could be adopted.

https://github.com/AshleyRoll/compile-time-init-build/tree/experiment/bitset

I was inspired to play with this when I heard Luke mention Run Length Encoding the bitset
in his EmBO++23 talk

I started thinking about RLE and it would need to allow dynamic sizes for it to be worth while
storage wise, but this is difficult, especially in an embedded environment. So it would likely
end up with some compromised "max length" data storage.

This is a sort of mid-way between the existing bitset and a RLE version. There is a fixed size, and
we trade a little more size to have a summary of elements with bits set to speed things up (hopefully).

I've not got any way to meaningfully measure performance impact, I'm sure this has some pros and cons
and it might just all wash out until a certain size of set where the additional processing overhead might be offset.

More a though experiment than anything, perhaps something useful there. perhaps not.

[elbeno]

Hi Ashley, thanks for doing this! Sorry for the delayed response... Luke and I have been discussing, and I think we will want an RLE bitset. FYI we were able to open source a few more repos lately and the STL-like stuff (including bitset) has moved to https://github.com/intel/cpp-std-extensions now. Luke is busy opening issues to track his ideas...

[elbeno]

I would say though that I'd like to get an rle_bitset in CIB first and not rush to include it in stdx. We might end up with a somewhat different interface than on the standard bitset, and the first use case is for indexed message handling.

[elbeno]

See #375

[lukevalenty]

I started thinking about RLE and it would need to allow dynamic sizes for it to be worth while
storage wise, but this is difficult, especially in an embedded environment. So it would likely
end up with some compromised "max length" data storage.

Our RLE bitset will use a shared table of data that is built at compile time, the RLE bitset instances will contain a constexpr pointer to this shared table along with an offset and length. Only the offset and length need to be stored in each RLE bitset instance since the shared data table address is known statically. This means each RLE bitset instance can consume a total of 32 bits....16 bits each for the offset and length.

[AshleyRoll]

Hi @lukevalenty and @elbeno

Thanks for the comments. I realised that this was not going to be very useful for CIB, mostly it was just me getting some ideas out of my head, thanks for indulging me :)

If you're not already working on the RLE, I would be keen to give it a go, I've done a Huffman string compression and there is a lot of machinery in that which might be reused for RLE. I did it for my CppCon talk a few years ago. https://github.com/AshleyRoll/squeeze

I don't think the Huffman encoder itself is that useful here as it requires quite a bit of overhead so needs quite a large amount of data to be worthwhile.

[lukevalenty]

That would be great if you wanted to implement RLE bitsets! I think it will be a fun feature to implement.

Run length encoding shouldn't require Huffman at all...it should be fairly straightforward. If you want to take this on, we should collaborate on the design. Minimizing processing time, storage, and fitting into a statically allocated memory model will require some careful design.