找回密码
 欢迎注册
楼主: liangbch

[原创] 求一个数组中元素的最大值和最小值

[复制链接]
发表于 2010-12-15 23:28:57 | 显示全部楼层
10# gxqcn
呵呵,是有点,我测试了一下我的这个:
cachemem.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-12-16 01:37:58 | 显示全部楼层
对于64bit 整数比较,没有和PMINUD,PMAXUD  类似的指令. 我想,只能使用CMOVcc系列指令了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-12-16 07:46:39 | 显示全部楼层
也许,传说中的 AVX 指令可完美解决该问题吧。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-12-16 21:00:14 | 显示全部楼层
在许多情况下,并不是执行的指令数越多越耗时。程序的运行时间除了和在运行路径中执行的指令数有关,还和分支预测,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. }

  14. void getMaxMin2(DWORD *pData,int len,DWORD *min,DWORD *max)
  15. {
  16.     int i;
  17.    
  18.     if (len % 2 ==0 )
  19.     {
  20.         if ( pData[0] > pData[1] )
  21.         {
  22.             *max= pData[0];
  23.             *min= pData[1];
  24.         }
  25.         else
  26.         {
  27.             *max= pData[1];
  28.             *min= pData[0];
  29.         }
  30.         i=2;
  31.     }
  32.     else
  33.     {
  34.         *max= *min= pData[0];
  35.         i=1;
  36.     }
  37.    
  38.     for (;i<len;i+=2)
  39.     {
  40.         if ( pData[ i ] > pData[ i+1] )
  41.         {
  42.             if ( pData[ i ]> *max)
  43.               *max=pData[ i ];
  44.             
  45.             if ( pData[ i+1]< *min)
  46.               *min=pData[ i+1];
  47.         }
  48.         else
  49.         {
  50.             if ( pData[ i ] < *min)
  51.               *min=pData[ i ];
  52.             
  53.             if ( pData[ i+1]> *max)
  54.               *max=pData[ i+1];
  55.         }
  56.     }
  57. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-12-17 07:30:17 | 显示全部楼层
请教一下:“CPU 的分支预测”的原理或表现是什么?我一直不太清楚。
它倾向于“为真”还是“为假”?还是依据该处指令先前执行的结果?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-12-17 09:37:14 | 显示全部楼层
根据以前执行的结果,如果以前执行的结果大部分情况跳转,那么就预测跳转.
不过进行预测需要消耗用于预测的寄存器(存放统计数据),而预测寄存器数目有限(比如20个左右).所以不是所有的跳转都会预测,只会预测执行频率高的那些跳转
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-12-17 10:09:24 | 显示全部楼层
谢谢 mathe 的专业且权威的解答。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-12-17 10:10:57 | 显示全部楼层
我在想,分支预测可能对循环的执行有很大好处吧?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-12-17 10:19:37 | 显示全部楼层
18# gxqcn
我想,对于循环,如果在循环内(计算指令较多)或循环外把握好数据预取的距离,用数据预取可能会有较大的收益。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-12-17 10:27:34 | 显示全部楼层
对数据预取我不太熟,但也说明了cache很重要。
所以有些算法会特意去读取CPU的L1/L2 cache的大小。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 16:45 , Processed in 0.046868 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表