如何让GCC优化长异或链

Question

我有一个循环：

uint32_t result = 0;

for ( int i = 0; i < CONSTANT; ++i )
{
    result ^= expr;
}
return result;

总体而言，GCC 在这段代码上做得非常出色。它完全展开循环并生成

expr

的最佳代码。然而，它执行了

result

XOR

CONSTANT

次。它可能会累积部分结果并按层次将它们异或在一起。

我怀疑如果我用宏手动展开它，我可以手动完成它（

CONSTANT

并不大），但我想知道为什么它没有看到这个，或者我是否正在做一些阻止它的事情一些神秘的 C++ 语言规则。

Answer 1

在这里积累部分结果可能没有任何好处。如果您使用分而治之的策略（异或偶数与赔率将大小减半，然后重复，每次将操作数数量减半），您最终仍然会做

O(CONSTANT)

工作（一半的工作加上四分之一的工作加上八分之一的工作）工作等，最终执行

CONSTANT - 1

操作）。

以块的形式累积部分结果的行为是相同的。从根本上讲，您必须进行

CONSTANT - 1

异或运算。由于这些是固定宽度寄存器，不会增长任意精度整数，因此每个 XOR 的工作是相同的。除非并行化

expr

工作，否则您不太可能从更复杂的方法中实现任何收益。

Answer 2

对于您的循环，要么

expr

不依赖于

i

，在这种情况下

gcc

应该完全优化循环¹，或者在这种情况下

gcc

可以 still 优化循环（由于循环边界是恒定的，因此可以预先计算整个循环）。

看起来它在后一种情况下失败了，_除非你针对

-march=haswell

进行优化。这看起来真的很奇怪，但我以前就见过这种行为。

无论如何²，您提到

expr

编译为两条指令。为

xor

、循环增量和测试指令添加 3 条指令，您已经为此循环提供了 5 条指令，这甚至超过了高端 x86 CPU 的报废率，因此寻找额外的指令没有任何好处这里的级别并行性（除非您可能正在编译为具有更高宽度的非 x86 架构？）。

---

¹ ...一般而言，无论如何，在

-O3

。

² 我们只能在这里猜测，因为你确实严格保守着

expr

的秘密。

Answer 3

在严格的 XOR 计算中，从技术上讲，输入 XOR 计算的值永远不会超过两个，因为它在逻辑上没有意义，并且只有在超过两个值进行 XOR 时才会告诉我们所有数字的组合奇偶校验位于像 var1 ^ var2 ^ var3 这样的链中，因此从技术上讲，通过使用两个以上，您应该只能知道它的奇偶性，无论结果是偶数还是奇数。

然而，在大多数编程语言中，编译器会自动创建一系列级联的 XOR 运算，一次仅处理其中两个值，然后获取该结果并将其与下一个值进行异或，直到处理完所有值，因此实际上可以存在没有实际的批处理 XOR 链或列表作为表达式，尽管我们可以以这种方式编写它们，并且编译器会处理细节。