如果被其他函数包围，为什么较慢的函数运行得更快

Question

只需一点c++代码，就可以确认java中的行为。

这是使用Visual Studio 2019 x64版本编译的重现此行为的示例代码。我得到了：

611ms，仅用于增量元素。

对于缓存的增量元素，631ms，因此额外20ms的开销。

但是，当我在每次增量之前添加heavy op时(我选择随机数生成(，得到：

2073ms，仅用于增量元素。

1432ms用于使用缓存的增量元素。

我有英特尔处理器10700K，如果重要的话还有3200RAM。

#include <iostream>
#include <random>
#include <chrono>
#include <cstdlib>

#define ARR_SIZE 256 * 256 * 256 
#define ACCESS_SIZE 256 * 256
#define CACHE_SIZE 1024 
#define ITERATIONS 1000
using namespace std;
using chrono::high_resolution_clock;
using chrono::duration_cast;
using chrono::milliseconds;
int* arr;
int* cache;
int counter = 0;
void flushCache() {
for (int j = 0; j < CACHE_SIZE; ++j)
{
++arr[cache[j]];
}
counter = 0;
}
void incWithCache(int i) {
cache[counter] = i;
++counter;
if (counter == CACHE_SIZE) {
flushCache();
}
}
void incWithoutCache(int i) {
++arr[i];
}
int heavyOp() {
return rand() % 107;
}
void main()
{
arr = new int[ARR_SIZE];
cache = new int[CACHE_SIZE];
int* access = new int[ACCESS_SIZE];
random_device rd;
mt19937 gen(rd());
for (int i = 0; i < ACCESS_SIZE; ++i) {
access[i] = gen() % (ARR_SIZE);
}
for (int i = 0; i < ARR_SIZE; ++i) {
arr[i] = 0;
}

auto t1 = high_resolution_clock::now();
for (int iter = 0; iter < ITERATIONS; ++iter) {
for (int i = 0; i < ACCESS_SIZE; ++i) {
incWithoutCache(access[i]);
}
}
auto t2 = high_resolution_clock::now();
auto ms_int = duration_cast<milliseconds>(t2 - t1);
cout << "Time without cache " << ms_int.count() << "msn";
t1 = high_resolution_clock::now();
for (int iter = 0; iter < ITERATIONS; ++iter) {
for (int i = 0; i < ACCESS_SIZE; ++i) {
incWithCache(access[i]);
}
flushCache();
}
t2 = high_resolution_clock::now();
ms_int = duration_cast<milliseconds>(t2 - t1);
cout << "Time with cache " << ms_int.count() << "msn";

t1 = high_resolution_clock::now();
for (int iter = 0; iter < ITERATIONS; ++iter) {
for (int i = 0; i < ACCESS_SIZE; ++i) {
heavyOp();
incWithoutCache(access[i]);
}
}
t2 = high_resolution_clock::now();
ms_int = duration_cast<milliseconds>(t2 - t1);
cout << "Time without cache and time between " << ms_int.count() << "msn";
t1 = high_resolution_clock::now();
for (int iter = 0; iter < ITERATIONS; ++iter) {
for (int i = 0; i < ACCESS_SIZE; ++i) {
heavyOp();
incWithCache(access[i]);
}
flushCache();
}
t2 = high_resolution_clock::now();
ms_int = duration_cast<milliseconds>(t2 - t1);
cout << "Time with cache and time between " << ms_int.count() << "msn";
}

Answer 1

我认为这类问题很难回答——优化编译器、指令重新排序和缓存都使这很难分析，但我确实有一个假设。

首先，incWithoutCache和没有heavyOp的incWithCache之间的差异似乎是合理的——第二个只是做了更多的工作。

当你介绍heavyOp时，它会变得有趣。

heavyOp + incWithoutCache:incWithoutCache需要从存储器中提取以输出到arr。当内存提取完成时，它可以进行加法运算。由于流水线，处理器可以在增量完成之前开始下一个CCD_ 8操作。

heavyOp + incWithCache:incWithCache不需要在每次迭代中从内存中提取，因为它只需要写出一个值。处理器可以对写入到内存控制器的内容进行排队并继续。它确实执行++counter，但在这种情况下，您总是访问相同的值，所以我认为它可以比incWithoutCache中的++arr[i]更好地缓存。当缓存被刷新时，刷新循环可以被大量流水线处理——刷新循环的每个迭代都是独立的，一次会有很多迭代在运行。

因此，我认为这里的最大区别是，如果没有缓存，对arr的实际写入就无法有效地进行流水线处理，因为heavyOp正在破坏您的流水线，并可能破坏您的缓存。在任何一种情况下，您的heavyOp都需要相同的时间，但在heavyOp + incWithoutCache中，写入arr的摊余成本更高，因为它与写入arr的其他内容(如heavyOp + incWithCache(不重叠。

我认为矢量化理论上可以用于刷新操作，但我在编译器资源管理器上没有看到，所以这可能不是造成差异的原因。如果使用矢量化，可以解释这种速度差异。

我要说的是，我不是这方面的专家，很容易对这一切完全错误。。。但这对我来说是有意义的。