有序数的有效稳定和

Question

我有一个很长的浮点正数列表（std::向量

for (auto v : vec) { sum += v; }

我想我可能有一些数值稳定性问题，因为接近向量sum的末尾将比v大得多。最简单的解决方案是以相反的顺序遍历向量。我的问题是：这是否与正向情况一样有效？我会丢失更多缓存？

还有其他智能解决方案吗？




Answer 1

最简单的解决方案是以相反的顺序遍历向量。我的问题是：这和正向情况一样有效吗？我会有更多的缓存丢失？

是的，它很高效。您硬件中的分支预测和智能缓存策略已针对顺序访问进行了调整。您可以安全地积累您的向量：

#include <numeric>

auto const sum = std::accumulate(crbegin(v), crend(v), 0.f);

Answer 2

我想我会有一些数值稳定性问题

因此，请进行测试。现在你有一个假设的问题，也就是说，没有问题。

如果你测试，假设变成了一个实际的问题，那么你应该担心实际修复它。

也就是说，浮点精度可能会引起问题，但您可以先确认它是否真的对您的数据有影响，然后再将其优先于其他所有内容。

...我会有更多的缓存丢失？

1000个浮点数是4Kb，它可以放在现代大众市场系统的缓存中（如果你想使用另一个平台，请告诉我们它是什么）。

唯一的风险是预取器在向后迭代时不会帮助您，但当然您的向量可能已经在缓存中。在您在完整程序的上下文中分析之前，您无法真正确定这一点，因此在您拥有完整程序之前不必担心它。

还有其他智能解决方案吗？

不要担心可能会成为问题的事情，直到它们真正成为问题。最多值得注意的是可能存在的问题，并对代码进行结构化，以便以后可以用经过仔细优化的解决方案替换最简单的解决方案，而无需重新编写其他所有内容。

Answer 3

我对您的用例进行了基准测试，结果（见附加图像）指向了向前或向后循环不会产生任何性能差异的方向。

您可能还想在硬件编译器上进行测量。

使用STL执行求和，速度与手动循环数据一样快，但更具表现力。

使用以下方法进行反向累积：

std::accumulate(rbegin(data), rend(data), 0.0f);

而对于远期累积：

std::accumulate(begin(data), end(data), 0.0f);