c - 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() 逐 block 扫描数组。

测试结果表明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 缓存读取未命中率是 bar 的 4 倍，而 4 恰好是 NUM_THREADS。

正如@Mysticial 所回答的那样

Sequential memory access is almost always going to out-perform non-sequential access.

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