我需要优化表单的表达式:
(a > b) || (a > c)
我尝试了几种优化形式,其中一种如下:
(a * 2) > (b + c)
优化不是从编译器的角度来看的。我想将两个 > 减为一个。
这是基于 1 <= (a, b, c) <= 26 的假设
但是,这仅适用于某些情况。我正在尝试做的优化真的可能吗?如果是的话,一个开始会非常有帮助。
我需要优化表单的表达式:
(a > b) || (a > c)
我尝试了几种优化形式,其中一种如下:
(a * 2) > (b + c)
优化不是从编译器的角度来看的。我想将两个 > 减为一个。
这是基于 1 <= (a, b, c) <= 26 的假设
但是,这仅适用于某些情况。我正在尝试做的优化真的可能吗?如果是的话,一个开始会非常有帮助。
答案可能是:您不想优化它。此外,我怀疑是否有任何方法可以更有效地编写此代码。如果您说 a、b 和 c 是 1 到 26 之间的值,那么如果您想获得最佳(大小),则不应该使用整数(您不需要那种精度)。
如果 a > b,则表达式 a > c 无论如何都不会被执行。所以你最多有 2 个(至少 1 个)条件操作,这真的不值得优化。
我很怀疑在大多数情况下这甚至是一种优化。
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
与性能一样,将您的决定基于实际性能测量(最好基于选择的处理器架构)总是要好得多。
我能想到的最好的就是这个
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,所以当 时减去a
fromb
会给你一个负值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)
。