如何在 C + + 中编写一个可维护的、快速的、编译时的位掩码？

我有一些或多或少像这样的代码:

#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 做了一件聪明的事情，将其编译成一个单独的 and指令(然后在其他任何地方内联) :

apply_known_mask(std::bitset<64ul>&):  # @apply_known_mask(std::bitset<64ul>&)
and     qword ptr [rdi], 775946532
ret

但是 我试过的所有版本的海湾合作委员会将其编译为一个巨大的混乱，其中包括应该静态 DCE 处理的错误处理。在其他代码中，它甚至将 important_bits等价物作为数据放置在与代码一致的位置！

.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*, ...)

我应该如何编写这段代码，以便两个编译器都能做正确的事情？如果做不到这一点，我应该如何编写它，使其保持清晰、快速和可维护？

9615 次浏览
小开
最佳答案

最好的版本是 :

template< unsigned char... indexes >
constexpr unsigned long long mask(){
return ((1ull<<indexes)|...|0ull);
}

然后

void apply_known_mask(std::bitset<64> &bits) {
constexpr auto m = mask<B,D,E,H,K,M,L,O>();
bits &= m;
}

回到 ，我们可以做这个奇怪的把戏:

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;
}

或者，如果我们被 卡住了，我们可以递归地求解它:

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...);
}

带有所有3 的 Godbolt ——您可以切换 CPP _ VERION 定义，并获得相同的汇编。

实际上，我会尽可能使用最现代的东西。14胜过11，因为我们没有递归，因此有 O (n ^ 2)符号长度(它可以爆炸编译时间和编译器内存使用) ; 17胜过14，因为编译器不必死代码-消除数组，这个数组技巧太丑陋了。

这14个中最令人困惑的是。在这里，我们创建一个包含所有0的匿名数组，同时作为副作用构造我们的结果，然后丢弃该数组。丢弃的数组中有一个数字0等于我们的包的大小，加上1(我们添加这个数字是为了能够处理空包)。

版本的详细说明。这是一个技巧/黑客技巧，事实上，要在 C + + 14中有效地扩展参数包，就必须这样做，这是在 中添加折叠表达式的原因之一。

最好从里到外地理解:

    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.

其余的工作是提供一个参数包，在。

第一步:

(void(
r |= (1ull << indexes) // side effect, used
),0)

在这里，我们将表达式转换为 void，表明我们不关心它的返回值(我们只想要设置 r的副作用——在 C + + 中，像 a |= b这样的表达式也返回它们设置为 a的值)。

然后使用逗号操作符 ,和 0丢弃 void“值”，并返回值 0。所以这是一个值为 0的表达式，作为计算 0的副作用，它在 r中设置了一点。

  int discard[] = {0,(void(
r |= (1ull << indexes) // side effect, used
),0)...};

此时，我们展开参数包 indexes，得到:

 {
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),
}

在 {}。,的这种用法是 没有逗号运算符，而不是数组元素分隔符。这是 sizeof...(indexes)+1 0，它也设置位在 r作为一个副作用。然后，我们将 {}数组构造指令分配给一个数组 discard。

接下来，我们将 discard强制转换为 void——如果您创建了一个变量但从未读取它，大多数编译器都会发出警告。如果您将它强制转换为 void，所有编译器都不会抱怨，这是一种表示“是的，我知道，我没有使用它”的方式，因此它会取消警告。

小开

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;
}

测试

int main() {
std::bitset<64> b;
b.flip();
apply_known_mask(b);
std::cout << b.to_string() << '\n';
}

输出

0000000000000000000000000000000000101110010000000000000100100100
//                                ^ ^^^  ^             ^  ^  ^
//                                O MLK  H             E  D  B

人们真的应该欣赏 C + + 在编译时计算任何可计算的东西的能力。它肯定仍然打击我的心(<>)。

对于 C + + 14和 C + + 17的后续版本，Yakk’s的答案已经很好地涵盖了这一点。

小开

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).

但是，在默认情况下，GCC 不能剥离所有迭代，这显然是必要的。实验上，传递 -O2 -fpeel-loops --param max-peeled-insns=200(默认值是100)可以使用原始代码 https://godbolt.org/z/NNWrga完成工作

小开

因为 C + + 11，你也可以使用经典的 TMP 技术:

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;
}

链接到编译器资源管理器: https://godbolt.org/z/Gk6KX1

这种方法相对于模板 Constexpr 函数的优势在于，由于 切尔规则的存在，编译速度可能会稍微快一些。

小开

我建议您编写一个适当的 EnumSet类型。

基于 std::uint64_t用 C + + 14(以上版本)编写一个基本的 EnumSet<E>非常简单:

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;
};

这使您可以编写简单的代码:

void apply_known_mask(EnumSet<Flags>& flags) {
static constexpr EnumSet<Flags> IMPORTANT{ B, D, E, H, K, M, L, O };


flags &= IMPORTANT;
}

在 C + + 11中，它需要一些卷积，但仍然是可能的:

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;
};

并以下列方式引用:

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;
}

甚至 GCC 也会在 -O1 Godbolt上生成一条 and指令:

apply_known_mask(EnumSet<Flags>&):
and     QWORD PTR [rdi], 775946532
ret
小开

There are some far to 'clever' ideas here. You are probably not helping maintainability by following them.

是

{B, D, E, H, K, M, L, O};

写起来容易多了

(B| D| E| H| K| M| L| O);

?

那么就不需要剩下的代码了。


提交答案