Cache命中:性能优化实记之Cache命中对CPU运行性能的影响

情景描述

先上代码:

  • code1:
void Graph::shufle(int cnt) {
    for (int i = 1; i<cnt; i++) {
        unsigned int swid = fastrand() % (cnt-i)  ;
        std::swap(iCons[cnt - i], iCons[swid]);
        std::swap(jCons[cnt - i], jCons[swid]);
        std::swap(dCons[cnt - i], dCons[swid]);
        std::swap(wCons[cnt - i], wCons[swid]);
    }
}
  • code2
// 作用为快速取得随机数
unsigned int g_seed = 0;
unsigned int fastrand() {
    g_seed = (214013 * g_seed + 2531011);
    return g_seed;
}
  • code3
// 与代码2的区别在于取值范围变为了65535
unsigned int fastrand() {
    g_seed = (214013 * g_seed + 2531011);
    return (g_seed >>16) & &7FFF;
}

实际效果:

  • cnt : 107403264
  • code2 timeuse : 3489 ms
  • code3 timeuse : 984 ms

分析

两种代码实现结果相差接近3.5倍,起初怀疑是取模造成的。怀疑在-O3的编译器优化下,较小的值取模往往可以直接返回该值本身。将code1中swap去掉后发现,就算是code2方法,光产生随机数只需要69ms。因此排除取模为性能瓶颈。

我们可以注意到,code3产生的数往往是小于65535的,而i是依次递减的。因此,对于code3而言,访问的内存总是在前65535个地址中,以及依次移动的cnt-i。而code2产生的随机数对cnt-i取模后,该数取值范围很大很大,因此总是造成cache miss,因此比code2慢3.5倍。