求一个数组中元素的最大值和最小值

G-Spider

10# gxqcn 呵呵，是有点，我测试了一下我的这个：

liangbch

对于64bit 整数比较，没有和PMINUD,PMAXUD 类似的指令. 我想，只能使用CMOVcc系列指令了。

gxqcn

也许，传说中的 AVX 指令可完美解决该问题吧。

liangbch

在许多情况下，并不是执行的指令数越多越耗时。程序的运行时间除了和在运行路径中执行的指令数有关，还和分支预测，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倍多。

1. void getMaxMin1(DWORD *pData,int len,DWORD *min,DWORD *max)
2. {
3. int i;
4. *min=~0;
5. *max=0;
6. for (i=0;i<len;i++)
7. {
8. if ( pData[ i ] > *max)
9. *max=pData[ i ];
10. if (pData[ i ]< *min)
11. *min=pData[ i ];
12. }
13. }
15. void getMaxMin2(DWORD *pData,int len,DWORD *min,DWORD *max)
16. {
17. int i;
19. if (len % 2 ==0 )
20. {
21. if ( pData[0] > pData[1] )
22. {
23. *max= pData[0];
24. *min= pData[1];
25. }
26. else
27. {
28. *max= pData[1];
29. *min= pData[0];
30. }
31. i=2;
32. }
33. else
34. {
35. *max= *min= pData[0];
36. i=1;
37. }
39. for (;i<len;i+=2)
40. {
41. if ( pData[ i ] > pData[ i+1] )
42. {
43. if ( pData[ i ]> *max)
44. *max=pData[ i ];
46. if ( pData[ i+1]< *min)
47. *min=pData[ i+1];
48. }
49. else
50. {
51. if ( pData[ i ] < *min)
52. *min=pData[ i ];
54. if ( pData[ i+1]> *max)
55. *max=pData[ i+1];
56. }
57. }
58. }

复制代码

gxqcn

请教一下：“CPU 的分支预测”的原理或表现是什么？我一直不太清楚。 它倾向于“为真”还是“为假”？还是依据该处指令先前执行的结果？

mathe

根据以前执行的结果,如果以前执行的结果大部分情况跳转,那么就预测跳转. 不过进行预测需要消耗用于预测的寄存器(存放统计数据),而预测寄存器数目有限(比如20个左右).所以不是所有的跳转都会预测,只会预测执行频率高的那些跳转

gxqcn

谢谢 mathe 的专业且权威的解答。

gxqcn

我在想，分支预测可能对循环的执行有很大好处吧？

G-Spider

18# gxqcn 我想，对于循环，如果在循环内(计算指令较多)或循环外把握好数据预取的距离，用数据预取可能会有较大的收益。

gxqcn

对数据预取我不太熟，但也说明了cache很重要。 所以有些算法会特意去读取CPU的L1/L2 cache的大小。