随机内存写入比随机内存读取慢？

Question

我正在尝试计算 sequential/random 内存 read/write 的内存访问时间。这是代码：

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>

#define PRINT_EXCECUTION_TIME(msg, code)                                       \
  do {                                                                         \
    struct timeval t1, t2;                                                     \
    double elapsed;                                                            \
    gettimeofday(&t1, NULL);                                                   \
    do {                                                                       \
      code;                                                                    \
    } while (0);                                                               \
    gettimeofday(&t2, NULL);                                                   \
    elapsed = (t2.tv_sec - t1.tv_sec) * 1000.0;                                \
    elapsed += (t2.tv_usec - t1.tv_usec) / 1000.0;                             \
    printf(msg " time: %f ms\n", elapsed);                                     \
  } while (0);

const int RUNS = 20;
const int N = (1 << 27) - 1;
int *data;

int seqR() {
  register int res = 0;
  register int *data_p = data;
  register int pos = 0;

  for (register int j = 0; j < RUNS; j++) {
    for (register int i = 0; i < N; i++) {
      pos = (pos + 1) & N;
      res = data_p[pos];
    }
  }

  return res;
}

int seqW() {
  register int res = 0;
  register int *data_p = data;
  register int pos = 0;

  for (register int j = 0; j < RUNS; j++) {
    for (register int i = 0; i < N; i++) {
      pos = (pos + 1) & N;
      data_p[pos] = res;
    }
  }

  return res;
}

int rndR() {
  register int res = 0;
  register int *data_p = data;
  register int pos = 0;

  for (register int j = 0; j < RUNS; j++) {
    for (register int i = 0; i < N; i++) {
      pos = (pos + i) & N;
      res = data_p[pos];
    }
  }

  return res;
}

int rndW() {
  register int res = 0;
  register int *data_p = data;
  register int pos = 0;

  for (register int j = 0; j < RUNS; j++) {
    for (register int i = 0; i < N; i++) {
      pos = (pos + i) & N;
      data_p[pos] = res;
    }
  }

  return res;
}

int main() {
  data = (int *)malloc(sizeof(int) * (N + 1));
  assert(data);

  for (int i = 0; i < N; i++) {
    data[i] = i;
  }

  for (int i = 0; i < 10; i++) {
    PRINT_EXCECUTION_TIME("seqR", seqR());
    PRINT_EXCECUTION_TIME("seqW", seqW());
    PRINT_EXCECUTION_TIME("rndR", rndR());
    PRINT_EXCECUTION_TIME("rndW", rndW());
  }

  return 0;
}

我使用 gcc 6.5.0 和 -O0 来防止优化，但得到的结果是这样的：

seqR time: 2538.010000 ms
seqW time: 2394.991000 ms
rndR time: 40625.169000 ms
rndW time: 46184.652000 ms
seqR time: 2411.038000 ms
seqW time: 2309.115000 ms
rndR time: 41575.063000 ms
rndW time: 46206.275000 ms

很容易理解顺序访问比随机访问快得多。但是，随机写入比随机读取慢而顺序写入比顺序读取快对我来说没有意义。什么原因可能导致这种情况？

此外，我可以肯定地说 seqR 的内存带宽是 (20 * ((1 << 27) - 1) * 4 * 1024 * 1024 * 1024)GB / (2.538)s = 4.12GB/s 吗？

Answer 1

听起来很正常。所有 x86-64 CPUs（以及大多数其他现代 CPUs）都使用 write-back / write-allocate 缓存，因此写入在提交到缓存之前需要读取一次，并且最终 write-back.

with -O0 to prevent optimization

自从您对所有本地人使用 register 以来，这是极少数没有使您的基准变得毫无意义的情况之一。

不过，您可以只在数组上使用 volatile 来确保这些访问中的每一个都按顺序发生，但是让优化器如何实现这一点。

Am I safe to say memory bandwidth for seqR is (20 * ((1 << 27) - 1) * 4 * 1024 * 1024 * 1024)GB / (2.538)s = 4.12GB/s?

不，你的分子中有一个额外的因子 2^30 和 10^9。但是你做错了，无论如何都接近正确的数字。

正确的计算是 RUNS * N * sizeof(int) / time 字节每秒，或者除以除以 10^9 GB/s。或者除以 2^30 得到基数 2 GiB/s。内存大小通常以 GiB 为单位，但您可以选择带宽； DRAM 时钟速度通常为 1600 MHz，因此 base-10 GB = 10^9 对于 GB/s 中的理论最大带宽当然是正常的。）

所以 4.23 GB/s 以 base-10 GB 为单位。

是的，你首先初始化了数组，所以定时运行都没有触发 page-faults，但我可能在 CPU 变暖后仍然使用第二个运行最大涡轮增压，如果还没有的话。

但请记住这是 un-optimized 代码。那就是你的 un-optimized 代码运行有多快，并没有告诉你你的内存有多快。它可能 CPU 绑定，而不是内存。

特别是其中有一个冗余的 & N 以匹配 rndR/W 函数的 CPU 工作。硬件预取可能能够跟上 4GB/s，但它仍然没有在每个时钟周期读取 1int。

随机内存写入比随机内存读取慢？

Random memory write is slower than random memory read?

performance

x86-64

cpu-cache

memory-bandwidth