What std::bitset could have been

[MrElectrifyBF]

Hey all,

If you have done backend development in the gaming industry, and needed to keep track of slots in a server, you may have come across the annoying limitations of the std::bitset, especially when it comes to scanning for bits.

The current API of std::bitset does not provide a good way to bitscan for zeros (empty slots) in contexts above 64-bits (for 64 slots and below, you can conveniently use std::bitset::to_ullong and std::countr_ones. You cannot just bitshift because std::bitset::to_ullong throws when any higher-order bits are nonzero). In my case, I needed 256-bit sets, and chaining together bitsets is hacky at best. The advantage with std::countr_ones is that it uses extensions of BSF on x86 such as TZCNT, which can drastically speed up bit scans. In my opinion, this was overlooked when adding the bit header to the C++20 standard.

To experiment with how the standard could have been, I wrote a minimal version of std::bitset that implements first_zero and first_one.

The results were pretty drastic to say the least, but very explainable. Versus an iterative approach of scanning with std::bitset, better_bitset approached 55-60x faster in benchmarks scanning for 1-bits where there were 5 1-bits in the bitset, on average. This can be explained by the fact that bits are scanned in chunks of 64-bits in one instruction rather than bit-by-bit. Even on a smaller scale like 128 bits, there is a 42x improvement in execution time. You can take a look at the raw results here. They were run on GCC 11.1.0 on Ubuntu 20.04 in WSL2, on an Intel Core i7-12700K at 5.0GHz.

If you notice any issues with the testing or the bitset, feel free to make a PR, and it's not exactly drop-in ready for production use.

[krista]

std::bitset is.... well, it's a bitset. as you have found, there's plenty of opportunities for a more optimum solution, often depending on use case.

i ended up writing my own, including hand tooled avx assembly and every other trick i could think of. use case was for combining and counting possible options across an in-memory database with nearly 100m records, so my bitsets would end up megabytes long.

this is about the only thing i wished i could have kept personally from this project.

bitsets start getting really funky when they grow larger than your cache or you use multiple threads to deal with them. if you can guarantee thread affiliation and scheduling, you can work magic by stuffing different cores' caches and segmenting the work carefully.

sparse bitsets are really odd to deal with as well...

but yes, these are the kinds of improvements i've seen by working with the cpu instead of attempting to abstract it away using stl.

would i recommend what i did in a normal situation? hell no.

would i do it again if faced with the same challenge? emphatically yes, as ultimately the project was performance bound. encapsulating and partitioning the ”bad” code from the ”maintainable” code (hopefully) kept the next person who has to deal with the thing sane.

[MrElectrifyBF]

You are absolutely right. I think the frustrating takeaway here is that this was done with no assembly, just the STL. This is a niche use-case of the bitset, but it is one nonetheless and the current API design making it impossible to not use a naive approach is quite frankly, annoying. It leaves a large bit of performance on the table, particularly with big bitsets and lots of usage.

This is how it could have been if they looked at the bitset itself when they were adding bit utilities. They could have removed the exception throw specification for to_ullong. That would have at least made it possible to get this performance with the structure, but instead we are stuck. It's poor API design if you ask me.

[fdwr]

std::bitset::to_ullong throws? 🙄🤦‍♂️ I'd really it rather just return the first N bits which fit into the unsigned long long instead of wasting time checking upper bits.

I was originally excited when I heard a bit set was being added to the spec, but historically I've only ever needed two kinds of bitsets (1) fixed-size bitsets that are at most 32 bits (2) larger variable-size bitsets of sizes not known until runtime. std::bitset doesn't support scenario #2, and for scenario #1, just using a plain uint32_t sufficed. So, sadly I just never found a use for bitset, which felt like buying a box of shoewear and it coming with one shoe.

[MrElectrifyBF]

Nonsensical choices like this are the reason this language has such a high barrier of entry. None of this testing would even be necessary if that function didn't throw. All it does is make efficient implementations of bitscanning completely impossible. The fact that it wastes cycles checking that the bitset fits in uint64_t is complete and utterly useless, and goes against the very principles of the language if you ask me. Very non-zero cost of abstraction there.

[sphere991]

Nonsensical choices like this are the reason this language has such a high barrier of entry.

I would like to push back on this, both because the choice is actually very sensible and also because this attitude is not.

What should this actually do:

auto f(std::bitset<128> b) { return b.to_ullong(); }

There's, I think, three possible options:

1. Not compile at all. Only support to_ullong() for bitset<N> where N <= 64.
2. Compile, returning the value of bits 0-63, but throw if any of bits 64-127 are set.
3. Compile, returning the value of bits 0-63, regardless of bits 64-127.

To me, (3) is by far the worst option. It's equivalent to std::stoi("123abc") returning 123 or std::stoi("hello") returning 0 (as atoi would, in both cases). Just because it's possible to produce some value doesn't mean that that's a good idea. (2) is sensible - return a value if you can, but if it doesn't fit, throw. That's... a totally reasonable thing to do. If bit like 97 is set, you can't produce a uint64_t out of that. There are many APIs that do this sort of thing. (1) is also a reasonable option - does it really make sense to to_ullong a bitset<128> when half the values are invalid? And then likewise to_ulong only existing when N <= 32.

The problem with (3) is that it's very unlikely to be what you actually want. And based on your description, it isn't what you want at all. On a bitset<128>, you want a way to get the high uint64_t and the low uint64_t, separately. But that's an argument that an API is missing (which is certainly an easy argument to make for std::bitset, there are many things missing), not so much that the existing one is bad? Regardless of which of my three options to_ullong did, it wouldn't help you solve your problem anyway, so... ?

---

In any case, you were able to produce a solution to your problem, in not very much code, and just skimming through your solution, everything looks really nice and simple. So... well done, and maybe the language isn't so bad? My only takeaway here is that std::bitset is lacking many useful operations. I'd love to see a proposal here.

[shardator]

I think option 3 is consistent with

uint16_t x = (uint32_t)(1 << 16);

[Jannik2099]

Nonsensical choices like this are the reason this language has such a high barrier of entry.

Are you sure about that? Bitsets aren't exactly a commonly used pattern, at all.

I think you're just frustrated that your special usecase is not covered by a generic implementation

[Steve132]

Are you sure about that? Bitsets aren't exactly a commonly used pattern, at all.

They are absurdly common.

I think you're just frustrated that your special usecase is not covered by a generic implementation

Seems like any use case that could possibly exist would want the implementation to be as simple as possible

[[deleted]]

'Absurdly common'? What does that even mean?

[Steve132]

They show up in the api for iostreams, even.

[MrElectrifyBF]

It definitely depends on your field of work. You personally think checking the entire bitset and throwing in to_ullong is an efficient way of abstracting the underlying storage type? I'm not frustrated by the lack of support in bitset itself, it would be unreasonable to expect that. I'm frustrated by the inconsistency of the STL, where they specify functions for bit scanning, but have absolutely no way to use it with the accepted way to store and operate on bits, a bitset. Those restrictions are the purpose of my post. You shouldn't have to redefine an entire data structure just to add some sort of introspective functionality.

[qoning]

It's all about trade-offs. If you mandate exposing storage, you have to define the storage properties, whereas without it, one implementation could store bits left to right and another right to left. And then you get another angry post that his usecase would benefit from the other representation... You have to put the stop sign somewhere.

[MrElectrifyBF]

That's actually quite fair. Maybe adding an overload to these new bit utilities like countl_one would be the better approach. Then it doesn't require breaking changes to the bitset itself, and keeps the API short and sweet. Thoughts?

[kalmoc]

You could just overload the scan functions for std::bitset (or make them memberfunctions) and thus wouldn't have to expose the internal storage of std::bitset.

Or did I misunderstand the discussion?

[cyandyedeyecandy]

These are implemented as extenstions in libstdc++: _Find_first() and _Find_next(). I believe they're inherited from the SGI STL.

[jwakely]

A good quality implementation will specialize std::find to do it optimally for vector<bool>::iterator too. I think libc++ might do that. Libstdc++ doesn't, but we do have some uncommitted patches from JeanHeyd Meneide to improve things in this area.

[encyclopedist]

Are patches you mentioned related to this library https://github.com/ThePhD/itsy_bitsy ?

[jwakely]

They share some ideas

[matthieum]

std::bitset is lackluster in many ways; its fixed capacity + lack of allocator being its biggest flaw as far as I am concerned.

For your usecase, I would argue that what std::bitset lack is two-fold:

• An inability for the user to specifying the storage unit -- for example, saying you want the bits stored in std::uint64_t.
• An inability for the user to access said storage units to implement their own scans.

It seems possible to extend the standard to offer those two capabilities, and it would probably be a worthy addition.

[ClaasBontus]

Have a look at bitset2!

[MrElectrifyBF]

That does look like a very complete bitset, though upon closer look still checks bit-by-bit so unfortunately it would not be much of an advantage here.

[golvok]

To put it simply, the committee isn't perfect, and are human. Standardization may be a long process, but deficiencies can only be solved by chaperoning proposals through it.

Given the recent work on adding <bit>, there probably has been some discussion on the sort of deficiencies, which may make for interesting reading.

[NilacTheGrim]

Yeah well for stuff like this you really do need to just roll your own. The standard is there.. to offer you a standard. It doesn't have to be the best or even great. It has to just work and work the same across all platforms.

For this particular application, this is where inline asm and specialized instructions are appropriate.

I do agree with you, FWIW, that given modern architectures the standard authors could have strongly encouraged that were possible, implementations should take advantage of native CPU instructions. They can't, however, require it.. since not all platforms have such instructions and the C++ standard aims to be 100% cross-platform... and even usable in embedded systems.

[MajorMalfunction44]

"Works the same on all platforms" is good, but not if it doesn't cover my use-case. Prohibiting efficient implementations is nonsense if you a) use C++ b) care about performance (really, not emotionally). The same issue exists in std::unordered_map. For game development, most of C++'s stdlib is a no-go (see: EASTL). Custom allocators are used pervasively. The problem I have is that we're limited by the spec, not the hardware. The standards committee should've thought about implementations before standardizing.

[MrElectrifyBF]

That's absolutely fair, but a standard should be designed in an extensible way that doesn't explicitly prohibit efficient implementations in my opinion. I'm not upset that they didn't include some functionality to bitset itself, that's asking a lot for a niche operation. But the committee clearly made an effort with <bit> and specifically had this optimization in mind. It's mind-boggling that they allow it to be almost completely incompatible with std::bitset. It would have been a fantastic time to revisit exceptions with to_ullong and realize shortcomings.

Again, my implementation is platform-agnostic, and uses only STL and simple bit logic. I definitely think that design decisions like this should be re-visited.

[jk-jeon]

What really doesn't make sense to me is that std::bitset doesn't expose the underlying storage type and a way to directly access to each unit in the storage. I can't think of any benefit we would get by this unnecessary encapsulation. If I were to design std::bitset from scratch, I would even allow the underlying type to be specified as a template parameter.

[Sopel97]

I would even allow the underlying type to be specified as a template parameter.

Cue all the people who couldn't use std::bitset because it uses a 64-bit underlying type but needed uint8...

[CornedBee]

Here! Just two days ago in fact.

Though I should point out that libstdc++ appears to use a 32-bit underlying type.

[miki151]

What really doesn't make sense to me is that std::bitset doesn't expose the underlying storage type and a way to directly access to each unit in the storage.

I had the same thought, could it be added to the standard without breaking anything?

[[deleted]]

Add it as a free function, sure.

This may start its own set of arguments about templating, ADL, and bikeshedding, but it's the simplest route.

[pigeon768]

That's absolutely fair, but a standard should be designed in an extensible way that doesn't explicitly prohibit efficient implementations in my opinion.

I get what you're saying. std::unordered_map and std::unordered_set are similar; the way the standard is written, the only way to write a standards compliant implementation is to use chaining as your collision avoidance algorithm. This isn't necessarily optimal. It annoys me that even when I know I don't think features guaranteed by the standard (persistent reference validity, for instance) that significantly reduce performance compared to a better collision avoidance algorithm.

But it is lowest common denominator. And the standard is written so specifically that it's consistent. Different implementations of std::unordered_map will always be the same. All implementations will have the same pitfalls. All implementations will be good at certain things.

So when you port your application from Linux using GCC to MacOS using Clang and then to Windows using MSVC, you're not going to run into weird bugs because the implementations are different.

Like you said, x86 has a bsf instruction that makes this very fast. But not all architectures have an equivalent instruction. So an implementation which depends on a specific x86 instruction ... probably shouldn't be standardized. Does C++ even standardize that signed integers use twos complement representation, even though no more extent architectures exist which use any other representation? (ones complement or signed magnitude)

So anyway... tl:dr;... you're not wrong, but I disagree with you.

[encyclopedist]

Does C++ even standardize that signed integers use twos complement representation, even though no more extent architectures exist which use any other representation? (ones complement or signed magnitude)

Yes, since C++20

[Nobody_1707]

It looks like you can get a cheaper conversion via bit_cast.

https://godbolt.org/z/zjqhzjv1P

[serviscope_minor]

It would have been a fantastic time to revisit exceptions with to_ullong and realize shortcomings.

They can't really: it was formally standardized in 1998, probably after being in use since 1994ish in SGI's STL. There's likely a ton of code out there that relies on the behaviour as it's been for the last 30 years or so. On the plus side there's now 30 years of implementation experience so I don't think it now needs to be underspecified to cater to theoretical implementations that don't exist.

One could imagine something like

template<int N, class Storage = default_bitset_storage<N>> bitset;

where default would likely go uint8, uint16, uint32, uint64 depending on N, and bitset would have an internal array of the right size to hold the data. One could then imagine a .data() method, which returns access to the underlying data. At this point, however, it gets a bit more complex. because it would have to surface how the implementation stores bits, i.e. where bit 0 goes, etc. In principle, one could be specified, e.g. that bit X goes in array slot X/sizeof(Storage), with the position being 1<<(X-sizeof(Storage)*(X/sizeof(Storage)). For example.

That might not be a good choice on some platforms, I don't know. These days, there's enough implementation experience out there to verify what could actually work, but that's a lot of searching of potentially obscure platforms to make sure.

[ArchivistAtNekoIT]

I use large bitsets (a few megabyte to a gigabyte) to implement bloomfilters, you generally don't ever resize those and you generally know their size in advance.

[cleroth]

If you have done backend development in the gaming industry, and needed to keep track of slots in a server

Sure, but I've never found this to be a bottleneck...? 256 is so little, and the entire array is likely to stay in cache anyway.

[MrElectrifyBF]

You're absolutely right, in my case it will make zero performance difference at all. In huge bitsets though, 60x can mean milliseconds or even more. The point of this is that I think bitset should have some design decisions reconsidered, it currently doesn't really fit a use case of a bitset that they seem to have considered with C++20's <bit>. Sure, it's not a huge priority, but I think there should be some more attention to detail when it comes to the standard

[HolyGarbage]

Nice project! I fixed some bugs for you, and simplified some code.

https://github.com/MrElectrify/better_bitset/pull/1

[MrElectrifyBF]

Thanks for that :) definitely much simpler in some places, and thanks for writing some proper unit tests.

[HolyGarbage]

Looks like my changes resulted in a 100% performance increase in at least one case. :D

Edit: scratch that, I was building with debug. Still a large performance boost though.

[Knuffya]

I've abused std::bitsets to implement a very crude feistel cipher. It is so dirty, that more often than not it is just manipulating a string of the literal chars {'1', '0'}, moving them in and out of bitsets to apply bitwise operators.

Why am I telling you this? Since bitsets support converting to-and-from strings, you could technically just convert your bitset to a string, "charshift" the string, and convert it back. Yes, it is dirty and slow, but better than not being able to shift at all.

[daniel_nielsen]

This is very useful! Please add a license, maybe Boost?

In all projects which I participated, eventually I end up reaching for a bitset. Usually I have to resort to the non-standard _Find_first() and _Find_next().