c++ - 逻辑/关系表达式优化

Question

我需要优化表单的表达式：

(a > b) || (a > c)

我尝试了几种优化形式，其中一种如下：

(a * 2) > (b + c)

优化不是从编译器的角度来看的。我想将两个 > 减为一个。

这是基于 1 <= (a, b, c) <= 26 的假设

但是，这仅适用于某些情况。我正在尝试做的优化真的可能吗？如果是的话，一个开始会非常有帮助。

Answer 1

答案可能是：您不想优化它。此外，我怀疑是否有任何方法可以更有效地编写此代码。如果您说 a、b 和 c 是 1 到 26 之间的值，那么如果您想获得最佳（大小），则不应该使用整数（您不需要那种精度）。

如果 a > b，则表达式 a > c 无论如何都不会被执行。所以你最多有 2 个（至少 1 个）条件操作，这真的不值得优化。

Answer 2

我很怀疑在大多数情况下这甚至是一种优化。

 a > b || a > c 

将评估为：

 compare a b
 jump not greater
 compare a c
 jump not greater

在哪里

 a * 2 > b + c

给出：

 shift a left 1 (in temp1)
 add b to c (in temp2)
 compare temp1 temp2
 jump if not greater

与性能一样，将您的决定基于实际性能测量（最好基于选择的处理器架构）总是要好得多。

Answer 3

我能想到的最好的就是这个

char a, b, c;
std::cin >> a >> b >> c;

if (((b-a) | (c-a)) & 0x80) {
    // a > b || a > c
}

这样gcc -O2只生成一个条件分支

40072e:       29 c8                   sub    %ecx,%eax
400730:       29 ca                   sub    %ecx,%edx
400732:       09 d0                   or     %edx,%eax
400734:       a8 80                   test   $0x80,%al
400736:       74 17                   je     40074f <main+0x3f>

这利用了输入值的约束，因为这些值不能大于 26，所以当 时减去afromb会给你一个负值a > b，在二进制补码中你知道7在这种情况下会设置位 - 这同样适用于c。然后我OR两者，以便该位7指示是否a > b || a > c，最后​​我们7通过AND与 0x80 进行检查并在其上进行分支。

更新：出于好奇，我计时了 4 种不同的编码方式。为了生成测试数据，我使用了一个简单的线性同余伪随机数生成器。我在一个循环中对它进行了 1 亿次迭代。为简单起见，我假设如果条件为真，我们希望将 5 添加到计数器，否则什么也不做。我g++ (GCC) 4.6.3 20120306 (Red Hat 4.6.3-2)在Intel Xeon X5570 @ 2.93GHz使用-O2优化级别上对其进行计时。

这是代码（注释掉除一个条件变量之外的所有变量）：

#include <iostream>
unsigned myrand() {
    static unsigned x = 1;
    return (x = x * 1664525 + 1013904223);
}

int main() {
    size_t count = 0;
    for(size_t i=0; i<100000000; ++i ) {
        int a = 1 + myrand() % 26;
        int b = 1 + myrand() % 26;
        int c = 1 + myrand() % 26;

        count += 5 & (((b-a) | (c-a)) >> 31);       // 0.635 sec
        //if (((b-a) | (c-a)) & 0x80) count += 5;     // 0.660 sec
        //if (a > std::max(b,c)) count += 5;          // 0.677 sec
        //if ( a > b || a > c) count += 5;            // 1.164 sec
    }
    std::cout << count << std::endl;
    return 0;
}

最快的是对我的回答中的建议进行修改，我们使用符号扩展来生成一个 321s或 32的掩码，0s具体取决于条件是真还是假，并使用它来掩盖5正在添加的内容，以便添加5 或 0。此变体没有分支。时间在每一行的注释中。最慢的是原来的表情( a > b || a > c)。