我意识到我在这方面非常缺乏知识(用一种奇特的方式说我不了解杰克)。
是否有关于如何以及何时使用它们的文档?
除了所有基于twidling的无分支代码(不会涵盖所有内容,如FP)之外,您还可以获得专门用于创建无分支代码的指令,这些指令将是x86下的SETcc
、FCMOVcc
和CMOVcc
,它们根据比较中的条件标志执行操作。
一个真正简单的例子是(是的,这个例子太简单了,人们可能永远不会写这样的东西,这只是为了清楚地证明一点):
bool CheckZero(int x)
{
if(x == 0)
return true;
return false;
//OR we can use: return (x == 0) ? true : false;
}
现在,一个简单的x86编译器可能会将其编译为:
MOV EAX,[ESP + 4]
TEXT EAX,EAX
JE _TRUE
XOR EAX,EAX
RETN 4
_TRUE:
MOV EAX,1
RETN 4
一个优化的x86编译器会将其分解为以下无分支代码(或类似代码):
MOV ECX,[ESP + 4]
XOR EAX,EAX
TEST ECX,ECX
SETE AL
RETN 4
这里可以找到一个更复杂的例子。
然而,这是编译器将执行的操作,而不是您应该担心的操作(至少在不分析编译器输出的情况下不会担心)。但是,如果代码必须是无分支的,C++就不能提供足够的控制,所以需要使用(内联)汇编。
不久前我写了三元逻辑模拟器,这个问题对我来说是可行的,因为它直接影响我的解释器执行速度;我被要求以尽可能快的速度模拟大量的三元逻辑门。
在二进制编码的三进制系统中,一个trit被打包为两个比特。最高有效位表示负,最低有效位表示正。情况"11"不应发生,但必须正确处理并威胁为0。
考虑inline int bct_decoder( unsigned bctData )
函数,它应该将我们格式化的trit返回为正则整数-1、0或1;正如我所观察到的,有4种方法:我称它们为"cond"、"mod","math"one_answers"lut";让我们调查他们
第一个是基于jz|jnz和jl|jb的条件跳跃,因此是第二个。它的性能一点也不好,因为它依赖于一个分支预测器。更糟糕的是,它是变化的,因为不知道是否会有一个或两个先验分支。这里有一个例子:
inline int bct_decoder_cond( unsigned bctData ) {
unsigned lsB = bctData & 1;
unsigned msB = bctData >> 1;
return
( lsB == msB ) ? 0 : // most possible -> make zero fastest branch
( lsB > msB ) ? 1 : -1;
}
这是最慢的版本,在最坏的情况下可能涉及2个分支,这是二进制逻辑失败的地方。在我的3770k上,随机数据平均产生约200MIPS。(此处和之后-每次测试是在随机填充的2mb数据集上进行1000次尝试的平均值)
下一个依赖于模运算器,它的速度介于第一和第三之间,但速度明显更快——600 MIPS:
inline int bct_decoder_mod( unsigned bctData ) {
return ( int )( ( bctData + 1 ) % 3 ) - 1;
}
下一个是无分支方法,它只涉及数学,因此涉及数学;它根本不假设跳转指令:
inline int bct_decoder_math( unsigned bctData ) {
return ( int )( bctData & 1 ) - ( int )( bctData >> 1 );
}
这做了应该做的事,表现得非常好。相比之下,性能估计为1000 MIPS,比分支版本快5倍。分支版本可能由于缺乏本机2位签名int支持而速度减慢。但在我的应用程序中,它本身就是一个非常好的版本。
如果这还不够,那么我们可以继续前进,吃一些特别的东西。下一种方法叫做查找表方法:
inline int bct_decoder_lut( unsigned bctData ) {
static const int decoderLUT[] = { 0, 1, -1, 0 };
return decoderLUT[ bctData & 0x3 ];
}
在我的例子中,一个trit只占用2个比特,所以lut表只有2b*4=8个字节,值得一试。它适合缓存,在1400-1600 MIPS下工作速度极快,这就是我的测量精度下降的地方。这是快速数学方法的1.5倍加速。这是因为您只需要预先计算结果和单个AND
指令。遗憾的是,缓存很小,(如果你的索引长度大于几位)你根本无法使用它
所以我想我回答了你的问题,关于分支/无分支代码是什么样子的。答案要好得多,有详细的样本、真实世界的应用程序和真实的性能测量结果。
http://hbfs.wordpress.com/2008/08/05/branchless-equivalents-of-simple-functions/
我认为(尽管我只知道我在页面上读到了什么)这是一种在没有分支的情况下获得if功能的方法(基于单词branchless if;),这是有意义的)。不知道更多。
感谢谷歌先生。