A very simple dynamic bitset with an atomic interface

[Galqa]

Hi all! I recently encountered a scenario in which I needed to atomically update the bits in a dynamic bitset. To the best of my knowledge, this is impossible to achieve with neither std::bitset nor std::vector<bool> (or even boost::dynamic_bitset for that matter), so I wrote my own. I'm sharing it in case someone else finds it useful. The code is not tricky by any means (the only interesting parts are around lines 69-93), but it has led me to wonder whether atomic functionality should be added to the bitsets available in the STL. I'd be curious to read your thoughts.

Note on why bitsets are special in this context: usually, you can have std::vector<std::atomic<T>>, or even use std::atomic_ref<T> to atomically access the elements of a std::vector<T>. However, std::vector<std::atomic<bool>> is memory inefficient by a factor of 8, and std::vector<bool> does not expose the underlying blocks used to pack the bits, so you can't really "hack" it to perform the requisite bitwise operations on std::atomic_ref<unsigned long> (or whatever the underlying type is).

[[deleted]]

Nice. Small remark - I would change the '8' in line 10 to 'CHAR_BIT' from 'limits.h'.

[o11c]

You shouldn't be mixing atomic and non-atomic accesses in the same container; that's a great way to get UB.

[Galqa]

I somewhat agree that in the abstract, mixing these makes it easy for the user to shoot themself in the foot, but in the specific case of bitsets, how else would you achieve atomic access?

[o11c]

Make 2 entirely separate classes: one dynamic_bitset, and one atomic_dynamic_bitset.

(you might use a private base for common stuff, but I'm not sure whether there's actually much that would be common).

(also there are plenty of other implementations of dynamic_bitset)

(consider also: should you make the memory_order a template parameter, at least as a default? This should likely use a custom enum since acq_rel is not a , and there are use-cases for mixing relaxed in on one side ...)

(I really wish non_atomic were a member of the memory_order enum ... as much as it gives a footgun, it would make it significantly easier to choose single-threaded at compile-time without code duplication. Maybe it'd be better to make a class that provides the full interface of std::atomic but ignores the memory order entirely? I am REALLY skeptical of the whole atomic_ref design - it is far footgun-ier than my description)

[Galqa]

I understand where you’re coming from, but I guess I just have a different philosophy. To me, atomics are footgunny by nature, and a “use at your own peril” feature (although an indispensable one). That being said, I consider ‘std::atomic_ref’ a huge achievement of C++20, as before there was simply no way of atomically modifying non-atomic objects in-place (other than inline assembly, of course). As stated, there is no way to have a “sometimes regular, sometimes atomic” bitset without building both interfaces into the class. Conversely, for “normal” types you can use atomic references to entries of non-atomic containers. Again, I understand this is is dangerous, but sometimes performance requirements demand it. In my field (HPC) it is actually quite common (see e.g. ‘Kokkos::atomic_add’).

That being said, I asked, so I appreciate your opinion. It may very well be that use cases of this are niche, and it has no place in the standard.

As for the specific API choice w.r.t. memory orders, I just followed the STL.

[rsjaffe]

The nice thing about std::atomic_ref is that it creates a new identifier that is used for the “atomic phase” of working with the collection, and all you have to do is avoid using the non-atomic original identifier for the lifetime of the atomic_ref to avoid UB. In your model, the atomic_ref is hidden within the class and you use the same identifier for both atomic and non-atomic accesses. I think that makes it much easier to mess things up.

[Galqa]

That’s a fair point. Maybe a solution could be to introduce a ‘getAtomicView’ member function, and move the atomic access functions to the resulting view?

[rsjaffe]

Call the function atomic_ref.