How do I write a maintainable, fast, compile-time bit-mask in C++?
C++C++11Bit ManipulationC++ Problem Overview
I have some code that is more or less like this:
#include <bitset>
enum Flags { A = 1, B = 2, C = 3, D = 5,
E = 8, F = 13, G = 21, H,
I, J, K, L, M, N, O };
void apply_known_mask(std::bitset<64> &bits) {
const Flags important_bits[] = { B, D, E, H, K, M, L, O };
std::remove_reference<decltype(bits)>::type mask{};
for (const auto& bit : important_bits) {
mask.set(bit);
}
bits &= mask;
}
Clang >= 3.6 does the smart thing and compiles this to a single and instruction (which then gets inlined everywhere else):
apply_known_mask(std::bitset<64ul>&): # @apply_known_mask(std::bitset<64ul>&)
and qword ptr [rdi], 775946532
ret
But every version of GCC I've tried compiles this to an enormous mess that includes error handling that should be statically DCE'd. In other code, it will even place the important_bits equivalent as data in line with the code!
.LC0:
.string "bitset::set"
.LC1:
.string "%s: __position (which is %zu) >= _Nb (which is %zu)"
apply_known_mask(std::bitset<64ul>&):
sub rsp, 40
xor esi, esi
mov ecx, 2
movabs rax, 21474836482
mov QWORD PTR [rsp], rax
mov r8d, 1
movabs rax, 94489280520
mov QWORD PTR [rsp+8], rax
movabs rax, 115964117017
mov QWORD PTR [rsp+16], rax
movabs rax, 124554051610
mov QWORD PTR [rsp+24], rax
mov rax, rsp
jmp .L2
.L3:
mov edx, DWORD PTR [rax]
mov rcx, rdx
cmp edx, 63
ja .L7
.L2:
mov rdx, r8
add rax, 4
sal rdx, cl
lea rcx, [rsp+32]
or rsi, rdx
cmp rax, rcx
jne .L3
and QWORD PTR [rdi], rsi
add rsp, 40
ret
.L7:
mov ecx, 64
mov esi, OFFSET FLAT:.LC0
mov edi, OFFSET FLAT:.LC1
xor eax, eax
call std::__throw_out_of_range_fmt(char const*, ...)
How should I write this code so that both compilers can do the right thing? Failing that, how should I write this so that it remains clear, fast, and maintainable?
C++ Solutions
Solution 1 - C++
Best version is [tag:C++17]:
template< unsigned char... indexes >
constexpr unsigned long long mask(){
return ((1ull<<indexes)|...|0ull);
}
Then
void apply_known_mask(std::bitset<64> &bits) {
constexpr auto m = mask<B,D,E,H,K,M,L,O>();
bits &= m;
}
back in [tag:C++14], we can do this strange trick:
template< unsigned char... indexes >
constexpr unsigned long long mask(){
auto r = 0ull;
using discard_t = int[]; // data never used
// value never used:
discard_t discard = {0,(void(
r |= (1ull << indexes) // side effect, used
),0)...};
(void)discard; // block unused var warnings
return r;
}
or, if we are stuck with [tag:C++11], we can solve it recursively:
constexpr unsigned long long mask(){
return 0;
}
template<class...Tail>
constexpr unsigned long long mask(unsigned char b0, Tail...tail){
return (1ull<<b0) | mask(tail...);
}
template< unsigned char... indexes >
constexpr unsigned long long mask(){
return mask(indexes...);
}
Godbolt with all 3 -- you can switch CPP_VERSION define, and get identical assembly.
In practice I'd use the most modern I could. 14 beats 11 because we don't have recursion and hence O(n^2) symbol length (which can explode compile time and compiler memory usage); 17 beats 14 because the compiler doesn't have to dead-code-eliminate that array, and that array trick is just ugly.
Of these 14 is the most confusing. Here we create an anonymous array of all 0s, meanwhile as a side effect construct our result, then discard the array. The discarded array has a number of 0s in it equal to the size of our pack, plus 1 (which we add so we can handle empty packs).
A detailed explanation of what the [tag:C++14] version is doing. This is a trick/hack, and the fact you have to do this to expand parameters packs with efficiency in C++14 is one of the reasons why fold expressions were added in [tag:C++17].
It is best understood from the inside out:
r |= (1ull << indexes) // side effect, used
this just updates r with 1<<indexes for a fixed index. indexes is a parameter pack, so we'll have to expand it.
The rest of the work is to provide a parameter pack to expand indexes inside of.
One step out:
(void(
r |= (1ull << indexes) // side effect, used
),0)
here we cast our expression to void, indicating we don't care about its return value (we just want the side effect of setting r -- in C++, expressions like a |= b also return the value they set a to).
Then we use the comma operator , and 0 to discard the void "value", and return the value 0. So this is an expression whose value is 0 and as a side effect of calculating 0 it sets a bit in r.
int discard[] = {0,(void(
r |= (1ull << indexes) // side effect, used
),0)...};
At this point, we expand the parameter pack indexes. So we get:
{
0,
(expression that sets a bit and returns 0),
(expression that sets a bit and returns 0),
[...]
(expression that sets a bit and returns 0),
}
in the {}. This use of , is not the comma operator, but rather the array element separator. This is sizeof...(indexes)+1 0s, which also set bits in r as a side effect. We then assign the {} array construction instructions to an array discard.
Next we cast discard to void -- most compilers will warn you if you create a variable and never read it. All compilers will not complain if you cast it to void, it is sort of a way to say "Yes, I know, I'm not using this", so it suppresses the warning.
Solution 2 - C++
The optimization you're looking for seems to be loop peeling, which is enabled at -O3, or manually with -fpeel-loops. I'm not sure why this falls under the purview of loop peeling rather than loop unrolling, but possibly it's unwilling to unroll a loop with nonlocal control flow inside it (as there is, potentially, from the range check).
By default, though, GCC stops short of being able to peel all the iterations, which apparently is necessary. Experimentally, passing -O2 -fpeel-loops --param max-peeled-insns=200 (the default value is 100) gets the job done with your original code: https://godbolt.org/z/NNWrga
Solution 3 - C++
if using only C++11 is a must (&a)[N] is a way to capture arrays. This allows you to write one single recursive function without using helper functions whatsoever:
template <std::size_t N>
constexpr std::uint64_t generate_mask(Flags const (&a)[N], std::size_t i = 0u){
return i < N ? (1ull << a[i] | generate_mask(a, i + 1u)) : 0ull;
}
assigning it to a constexpr auto:
void apply_known_mask(std::bitset<64>& bits) {
constexpr const Flags important_bits[] = { B, D, E, H, K, M, L, O };
constexpr auto m = generate_mask(important_bits); //< here
bits &= m;
}
###Test
int main() {
std::bitset<64> b;
b.flip();
apply_known_mask(b);
std::cout << b.to_string() << '\n';
}
###Output 0000000000000000000000000000000000101110010000000000000100100100 // ^ ^^^ ^ ^ ^ ^ // O MLK H E D B
one really has to appreciate C++`s ability to calculate anything turing computable at compile time. It surely still blows my mind (<>).
For the later versions C++14 and C++17 yakk's answer already wonderfully covers that.
Solution 4 - C++
I would encourage you to write a proper EnumSet type.
Writing a basic EnumSet<E> in C++14 (onwards) based on std::uint64_t is trivial:
template <typename E>
class EnumSet {
public:
constexpr EnumSet() = default;
constexpr EnumSet(std::initializer_list<E> values) {
for (auto e : values) {
set(e);
}
}
constexpr bool has(E e) const { return mData & mask(e); }
constexpr EnumSet& set(E e) { mData |= mask(e); return *this; }
constexpr EnumSet& unset(E e) { mData &= ~mask(e); return *this; }
constexpr EnumSet& operator&=(const EnumSet& other) {
mData &= other.mData;
return *this;
}
constexpr EnumSet& operator|=(const EnumSet& other) {
mData |= other.mData;
return *this;
}
private:
static constexpr std::uint64_t mask(E e) {
return std::uint64_t(1) << e;
}
std::uint64_t mData = 0;
};
This allows you to write simple code:
void apply_known_mask(EnumSet<Flags>& flags) {
static constexpr EnumSet<Flags> IMPORTANT{ B, D, E, H, K, M, L, O };
flags &= IMPORTANT;
}
In C++11, it requires some convolutions, but remains possible nonetheless:
template <typename E>
class EnumSet {
public:
template <E... Values>
static constexpr EnumSet make() {
return EnumSet(make_impl(Values...));
}
constexpr EnumSet() = default;
constexpr bool has(E e) const { return mData & mask(e); }
void set(E e) { mData |= mask(e); }
void unset(E e) { mData &= ~mask(e); }
EnumSet& operator&=(const EnumSet& other) {
mData &= other.mData;
return *this;
}
EnumSet& operator|=(const EnumSet& other) {
mData |= other.mData;
return *this;
}
private:
static constexpr std::uint64_t mask(E e) {
return std::uint64_t(1) << e;
}
static constexpr std::uint64_t make_impl() { return 0; }
template <typename... Tail>
static constexpr std::uint64_t make_impl(E head, Tail... tail) {
return mask(head) | make_impl(tail...);
}
explicit constexpr EnumSet(std::uint64_t data): mData(data) {}
std::uint64_t mData = 0;
};
And is invoked with:
void apply_known_mask(EnumSet<Flags>& flags) {
static constexpr EnumSet<Flags> IMPORTANT =
EnumSet<Flags>::make<B, D, E, H, K, M, L, O>();
flags &= IMPORTANT;
}
Even GCC trivially generates an and instruction at -O1 godbolt:
apply_known_mask(EnumSet<Flags>&):
and QWORD PTR [rdi], 775946532
ret
Solution 5 - C++
Since C++11 you could also use classic TMP technique:
template<std::uint64_t Flag, std::uint64_t... Flags>
struct bitmask
{
static constexpr std::uint64_t mask =
bitmask<Flag>::value | bitmask<Flags...>::value;
};
template<std::uint64_t Flag>
struct bitmask<Flag>
{
static constexpr std::uint64_t value = (uint64_t)1 << Flag;
};
void apply_known_mask(std::bitset<64> &bits)
{
constexpr auto mask = bitmask<B, D, E, H, K, M, L, O>::value;
bits &= mask;
}
Link to Compiler Explorer: https://godbolt.org/z/Gk6KX1
The advantage of this approach over template constexpr function is that it's potentially slightly faster to compile due to rule of Chiel.
Solution 6 - C++
There are some far to 'clever' ideas here. You are probably not helping maintainability by following them.
is
{B, D, E, H, K, M, L, O};
so much easier to write than
(B| D| E| H| K| M| L| O);
?
Then none of the rest of the code is needed.