CPU缓存对速度的影响

Question

我刚刚写了一个程序来测试CPU缓存对速度性能的影响.

void* foo(void* ptr)
{
    int* r = (int*) ptr;

    for (int i = (r - s); i < N; i += NUM_THREADS)
        *r += num[i];        
    return NULL;
}

void* bar(void* ptr)
{
    int* r = (int*) ptr;
    int idx = r - s;
    int block = N/NUM_THREADS;
    int start = idx * block, end = start + block;

    for (int i = start; i < end; ++i)
        *r += num[i];        
    return NULL;
}

基本上,foo()另一方面,隔行扫描bar()是逐块扫描阵列.

测试结果表明bar()速度更快:

gcc ping-pong.c -std=gnu99 -lpthread -O2  ; ./a.out
1.077037s
0.395525s

那么如何解释这个结果呢？

完整的源代码位于:https://gist.github.com/4617935

更新:删除所有if语句

Answer 1

事实证明一点也不神秘。

我尝试 valgrind 来分析缓存未命中情况，结果如下：

$ valgrind --tool=cachegrind --cachegrind-out-file=profile ./a.out
....
$ cg_annotate profile --auto=yes --show=D1mr --context=1
....
-- line 63 ----------------------------------------
    .  void* foo(void* ptr)
     0  {
     0      int* r = (int*) ptr;
     .  
     0      for (int i = (r - s); i < N; i += NUM_THREADS)
16,388          *r += num[i];
     0      return NULL;
     0  }
     .  
-- line 71 ----------------------------------------

-- line 72 ----------------------------------------
     .  void* bar(void* ptr)
     0  {
     0      int* r = (int*) ptr;
     0      int idx = r - s;
     0      int block = N/NUM_THREADS;
     0      int start = idx * block, end = start + block;
     .  
     0      for (int i = start; i < end; ++i)
 4,098          *r += num[i];
     0      return NULL;
     0  }

foo()如您所见，L1 缓存读取未命中次数是 的 4 倍bar，而 4 正是NUM_THREADS.

正如@Mysticial 的回答

顺序内存访问几乎总是优于非顺序访问。

因为更多的非顺序内存访问意味着更多的缓存未命中。