访问数组会减慢我的功能吗？

Question

我有两个功能：

unsigned long long getLineAsRow(unsigned long long board, int col) {
    unsigned long long column = (board >> (7-(col - 1))) & col_mask_right;
    column *= magicLineToRow;
    return (column >> 56) & row_mask_bottom;
}

unsigned long long getDiagBLTR_asRow(unsigned long long board, int line, int row) {
    unsigned long long result = board & diagBottomLeftToTopRightPatterns[line][row];
    result = result << diagBLTR_shiftUp[line][row];
    result = (result * col_mask_right) >> 56;
    return result;
}

我看到的唯一大区别是对 2 维数组的访问。定义如

int diagBRTL_shiftUp[9][9] = {};

我调用这两个函数 10.000.000 次：

getLineAsRow ... time used: 1.14237s
getDiagBLTR_asRow ... time used: 2.18997s

我用 cl (vc++) 和 g++ 测试了它。几乎没有区别。差别真的很大，你有什么建议吗？

Answer 1

_{这些函数做完全不同的事情，但我认为这与问题无关。}

有时这些测试不会显示功能的实际成本。

在这种情况下，主要成本是访问内存中的数组。第一次访问后，它将在缓存中，之后您的函数将很快。所以你并没有真正衡量这个特性。即使在测试中有 10.000.000 次迭代，您只需支付一次价格。

现在如果你批量执行这个函数，批量调用它很多次，那么它就不是问题了。缓存会很温暖。

如果您偶尔访问它，在内存需求高且经常刷新 CPU 现金的应用程序中，这可能是性能问题。但这当然取决于上下文：它被调用的频率等等。

Answer 2

如果不知道生成的汇编代码或您正在访问的哪些全局变量实际上是可以直接编译到代码中的常量，则无法回答导致两个函数的执行时间之间存在差异的问题。无论如何，分析你的功能，我们看到

函数 1
1. 从堆栈中读取两个参数，returns一个值
2. 读取三个全局变量，它们可能是常量也可能不是常量
3. 执行六次算术运算（7-(col-1) 中的两个减法可以合并为一个减法）
函数 2
1. 从堆栈中读取三个参数，returns一个值
2. 读取一个全局变量，它可能是也可能不是常数
3. 解引用两个指针（不是四个，见下文）
4. 做五个算术运算（三个你看到的，两个产生数组索引）

请注意，对二维数组的访问实际上归结为单个内存访问。当您编写 diagBottomLeftToTopRightPatterns[line][row] 时，您的编译器会将其转换为类似 diagBottomLeftToTopRightPatterns[line*9 + row] 的内容。这是两个额外的算术指令，但只有一个内存访问。更重要的是，计算的结果line*9 + row可以循环用于第二次访问二维数组

算术运算速度很快（大约为单个 CPU 周期），从内存中读取可能需要四到二十个 CPU 周期。所以我猜你在函数 1 中访问的三个全局变量都是你的编译器直接内置到汇编代码中的常量。这使得函数 2 有更多的内存访问，使其变慢。

但是，有一件事困扰着我：如果我假设您有一个时钟频率至少为 2 GHz 的正常 CPU，那么您的时间表明您的函数分别消耗超过 200 或 400 个周期。这大大超过预期。即使您的 CPU 在缓存中没有任何值，您的函数也不应该超过大约 100 个周期。所以我建议再看看你是如何为你的代码计时的，我假设你的测量循环中有更多的代码会破坏你的结果。

访问数组会减慢我的功能吗？

Does accessing arrays slow down my function?

c++

arrays

slowdown