指针向量与值向量对大内存块和小内存块的性能损失

Question

我进行了一个小测试以确定访问指针向量与值向量的行为。事实证明，对于小内存块，两者的性能都一样好，但是，对于大内存块，则存在显着差异。

如何解释这种行为？

对于下面的代码，在我的电脑上执行，D=0 的差异约为 35%，而 D=10 的差异不明显。

int D = 0;
int K = 1 << (22 - D);
int J = 100 * (1 << D);

int sum = 0;
std::vector<int> a(K);
std::iota(a.begin(), a.end(), 0);
long start = clock();
for (int j = 0; j < J; ++j)
    for (int i = 0; i < a.size(); ++i)
        sum += a[i];
std::cout << double(clock() - start) / CLOCKS_PER_SEC << " " << sum << std::endl;

sum = 0;
std::vector<int*> b(a.size());
for (int i = 0; i < a.size(); ++i) b[i] = &a[i];
start = clock();
for (int j = 0; j < J; ++j)
    for (int i = 0; i < b.size(); ++i)
        sum += *b[i];
std::cout << double(clock() - start) / CLOCKS_PER_SEC << " " << sum << std::endl;

Answer 1

从全局内存获取数据很慢，因此 CPU 有一小部分非常快的内存来帮助内存访问跟上处理器。在处理内存请求时，您的计算机将尝试通过在您请求的位置周围请求一大堆它们并将它们存储在缓存中来尝试加速对内存中单个整数或指针的未来请求。一旦快速内存已满，每当请求新内容时，就必须摆脱它最不喜欢的位。

您的小问题可能完全或大部分适合缓存，因此内存访问非常快。大问题无法放入此快速内存中，因此您遇到了问题。该向量存储为 K 个连续的内存位置。当您访问 int 的向量时，它会加载 int 和他附近的一些值，这些值可以立即使用。但是，当您加载 int* 时，它会加载一个指向实际值的指针以及其他几个指针。这会占用一些内存。然后，当您使用 * 取消引用时，它会加载实际值，并可能加载附近的一些实际值。这会占用更多内存。您不仅需要执行更多的工作，而且还需要更快地填满内存。实际增加的时间会有所不同，因为它在很大程度上取决于体系结构、操作（在本例中为 +）和内存速度。此外，您的编译器将非常努力地工作以最大程度地减少延迟。

指针向量与值向量对大内存块和小内存块的性能损失

Vector of pointers vs vector of values performance penalty for large vs small memory blocks

c++

pointers

vector