10# gxqcn
呵呵，是有点，我测试了一下我的这个：
对于64bit 整数比较，没有和PMINUD,PMAXUD类似的指令. 我想，只能使用CMOVcc系列指令了。
也许，传说中的 AVX 指令可完美解决该问题吧。
在许多情况下，并不是执行的指令数越多越耗时。程序的运行时间除了和在运行路径中执行的指令数有关，还和分支预测，cache命中率等因素有密切的关。有时这类因素往往占主导地位。今天终于找到一个例子，说明分支预测失败的影响有多大。下面给出两个求数组最大最小值函数。
在第一个例子中，数组的每一个元素对应2次比较。在每次比较中，两个分支执行的几率并不相同。“if”语句条件为真几率非常小，按照算法导论中的算法，if语句条件为真次数仅为log2(n)，n为数组元素的个数。在这种情况下，CPU 的分支预测和取指机构总是预取条件为假的那个分支的指令，预测失败的几率非常低，故CPU的效率很高。
在第二个例子中，数组的每一个元素对于1.5次比较，执行的指令数比第一个函数少。但是，在平均情况下，第一个比较语句 "if ( pData[ i ] > pData[ i+1 ] )"条件为真的概率为50%，这时CPU的分支预测将不起作用，无论预取那个分支的指令，预测失败的概率总是50%。测试结果显示查找32M个数据，第一个函数需要0.048秒，第二个函数却需要0.098秒，是第一个函数执行时间的2倍多。void getMaxMin1(DWORD *pData,int len,DWORD *min,DWORD *max)
{
int i;
*min=~0;
*max=0;
for (i=0;i<len;i++)
{
if ( pData[ i ] > *max)
*max=pData[ i ];
if (pData[ i ]< *min)
*min=pData[ i ];
}
}
void getMaxMin2(DWORD *pData,int len,DWORD *min,DWORD *max)
{
int i;
if (len % 2 ==0 )
{
if ( pData > pData )
{
*max= pData;
*min= pData;
}
else
{
*max= pData;
*min= pData;
}
i=2;
}
else
{
*max= *min= pData;
i=1;
}
for (;i<len;i+=2)
{
if ( pData[ i ] > pData[ i+1] )
{
if ( pData[ i ]> *max)
*max=pData[ i ];
if ( pData[ i+1]< *min)
*min=pData[ i+1];
}
else
{
if ( pData[ i ] < *min)
*min=pData[ i ];
if ( pData[ i+1]> *max)
*max=pData[ i+1];
}
}
}
请教一下：“CPU 的分支预测”的原理或表现是什么？我一直不太清楚。
它倾向于“为真”还是“为假”？还是依据该处指令先前执行的结果？
根据以前执行的结果,如果以前执行的结果大部分情况跳转,那么就预测跳转.
不过进行预测需要消耗用于预测的寄存器(存放统计数据),而预测寄存器数目有限(比如20个左右).所以不是所有的跳转都会预测,只会预测执行频率高的那些跳转
谢谢 mathe 的专业且权威的解答。
我在想，分支预测可能对循环的执行有很大好处吧？
18# gxqcn
我想，对于循环，如果在循环内(计算指令较多)或循环外把握好数据预取的距离，用数据预取可能会有较大的收益。
对数据预取我不太熟，但也说明了cache很重要。
所以有些算法会特意去读取CPU的L1/L2 cache的大小。