更改值与访问 C 中的数组的成本

Question

这个问题因为基于意见而被关闭，所以这是一个澄清我的意思的编辑。

关于更改 double 的值是否会比从数组中检索 double 花费更多或更少的时间，是否有任何方法可以做出有根据的猜测？我知道更快的方法可能是视情况而定，问题是是否有任何方法可以预测在给定情况下更快的方法是什么。或者，如果有任何“良好做法”，应该坚持这样编译器可以进行尽可能多的优化。

此问题基于以下知识：访问给定数据所需的时间取决于它是位于 L1、L2、L3 (...) 还是 RAM 中。由于 L1、L2 中的 space 有限，...我相信重复修改单个变量比修改多个不同的变量一次要快一些。但是，我不知道差异有多大，或者是否有可能 predict/manipulate what data/instructions 将位于 what cache/RAM.

下面是原问题：

操作所花费的时间（据我所知）与存储您正在使用的信息的内存缓存有关。所以我想知道更改 double 2N 次的值而不是将 N double 存储在数组中然后迭代是否更有效在阵列上。这个想法是经常更改的变量将存储在较低级别的缓存中，因此访问它的速度将比存储在数组中的值快一点。数组足够小，整个数组都可以放在 RAM 中，重点是不要释放内存。

两种方案的示例代码如下所示。请注意，此处的计算已简化，以更好地描述问题的本质。实际上数组是二维的，tmp1和tmp2的计算量稍微大一些，但仍然只是对索引的简单依赖：

#define DIM 1000
double states[DIM];
double time_derivatives[DIM];
double ambient_state = 3.0;
    
// Initialize states
for (int pos = 0; pos < DIM; pos++) {
    states[pos] = pos;
}

// Alternative 1
double tmp1;
double tmp2;

// Ends
tmp1 = 1;
tmp2 = 2;
time_derivatives[0] = (ambient_state - states[0]) * tmp1 + (states[1] - states[0]) * tmp2;
tmp1 = DIM;
tmp2 = DIM + 1;
time_derivatives[DIM - 1] = (ambient_state - states[DIM - 1]) * tmp2 + (states[DIM - 2] - states[DIM - 1]) * tmp1;

// Bulk
for (int pos = 1; pos < DIM - 1; pos++) {
    tmp1 = pos + 1;
    tmp2 = pos + 2;
    time_derivatives[pos] = (states[pos - 1] - states[pos]) * tmp1 + (states[pos + 1] - states[pos]) * tmp2;
}
    
// Alternative 2
double flows[DIM + 1];
double tmp1; //Some intermediate, neccesary calculation variable

// Flows at ends
tmp1 = 1;
flows[0] = (states[0] - ambient_state) * tmp1;
tmp1 = DIM;
flows[DIM] = (ambient_state - states[DIM - 1]) * tmp1;

// Flows in bulk
for (int pos = 1; pos < DIM; pos++) {
    tmp1 = pos + 1;
    flows[pos] = (states[pos] - states[pos - 1]) * tmp1;
}
// Compute time derivatives
for (int pos = 0; pos < DIM; pos++) {
    time_derivatives[pos] = flows[pos + 1] - flows[pos];
}

在备选方案 1 中，许多计算在最终的 for 循环中“重复”，因为一次迭代中的 (states[pos + 1] - states[pos]) * tmp1 将等于下一次迭代中的 - (states[pos - 1] - states[pos]) * tmp2。备选方案2中，所有的差值都被计算并存储在数组flows中，从而减少了总的计算量。

问题本质上是，与在数组中存储和访问变量的成本相比，计算操作的成本是多少？是否存在一种情况比另一种更有效的限制情况？

Answer 1

正如一些评论所提到的，通常不可能仅仅通过查看 C 代码来比较两个替代实现（做同样的事情）的性能。首先，现代编译器会施展各种“魔法”来生成性能良好的代码，当代码被执行时，处理器会施展各种魔法来尽可能快地执行代码。因此，您需要成为编译器和处理器方面的极端专家，才能仅通过查看 C 代码来判断性能。

如果您不是极端专家（很少有人是），唯一的选择是衡量两者在实际应用中的表现。

就是说...在我看来，您的备选方案 2 正在做一些奇怪且不必要的事情。例如：

// Flows in bulk
for (int pos = 1; pos < DIM; pos++) {
    tmp1 = pos + 1;
    flows[pos] = (states[pos] - states[pos - 1]) * tmp1;
}
// Compute time derivatives
for (int pos = 0; pos < DIM; pos++) {
    time_derivatives[pos] = flows[pos + 1] - flows[pos];
}

为什么有两个循环？

据我所知，你可以用一个循环来做，比如：

for (int pos = 1; pos < DIM; pos++) {
    tmp1 = pos + 1;
    flows[pos] = (states[pos] - states[pos - 1]) * tmp1;
    time_derivatives[pos-1] = flows[pos] - flows[pos-1];
}

为什么要有流阵列？

据我所知，flows 数组没有任何理由。简单地做：

tmp1 = 1;
flows_prev_loop = (states[0] - ambient_state) * tmp1;
for (int pos = 1; pos < DIM; pos++) {
    tmp1 = pos + 1;
    flows_this_loop = (states[pos] - states[pos - 1]) * tmp1;
    time_derivatives[pos-1] = flows_this_loop - flows_prev_loop;
    flows_prev_loop = flows_this_loop;
}

这样你就有了一个备选方案 3 可以避免多次计算相同的内容而不使用数组。

我有一种感觉，这个替代方案会击败你们两个……但可以肯定的是，您需要衡量

Answer 2

的确，不测量就无法知道，但是运行存在测量错误或未测量未来计算机的风险。

还要记住，您很容易测量错误的东西。程序员的时间通常比机器时间贵很多。猜测——即使猜错了——可能是最好的策略，因为它很快。

所以这是一个快速猜测的基础。

大约 20 年前，我从事 Monte-Carlo 模拟系统的工作，该系统需要大量随机数。我们花了数周时间评估随机数生成器，以选择一个将最小偏差引入我们模型的生成器。然后我们将这些数字存储在一个数组中，并在整个过程中使用该数组。

大约 10 年后，我们有理由重新审视该过程，IIRC，因为我们需要更多的数字。在此过程中，我们注意到数组没有帮助：每次我们需要一个数字时调用 RNG 函数比使用预先生成的数组更快。很多。

随机数生成是一项异常复杂的工作，需要进行大量计算。但这是一个小算法，几乎不是一页代码。

我吸取的教训是计算很便宜，而高速缓存则不然。我一直以此为基础进行猜测。随意做同样的事情。

更改值与访问 C 中的数组的成本

Cost of changing a value vs. accessing an array in C

c

c++

optimization

performance

processing-efficiency