c++ - 逐元素 vector 乘法

Question

对于两个 n 元素整数 vectors 的乘法，有什么方法比以下方法更快(就代码所需的时间而言):

{
// code for obtaining two n element int vectors, a and b
}
int temp = 0;  // a temporary variable
for (int ii = 0; ii < n; ++ii)
    temp += a[ii]*b[ii];

编辑:收到了几个不错的想法。我必须检查每一个，看看哪一个是最好的。当然，每个回答都告诉我一些新的东西。

Answer 1

我认为在 C++ 中加快速度的唯一方法是修复“循环携带依赖性”，这意味着每次迭代都必须等到前一个临时值可用于求和。这可以通过展开和使用几个累积变量来实现:

int t0=0, t1=0, t2=0, t3=0;
for (int ii = 0; ii < n; ii += 4) {
    t0 += a[ii]*b[ii];
    t1 += a[ii+1]*b[ii+1];
    t2 += a[ii+2]*b[ii+2];
    t3 += a[ii+3]*b[ii+3];
}
int temp = t0 + t1 + t2 + t3;

现代处理器可以在每个周期执行多个操作，但前提是没有依赖性。在我的系统上，这产生了大约 20% 的改进。注意:n 必须是 4 的倍数，否则您需要添加一个循环“epilog”来完成剩余的元素。测试和测量!我不知道 4 是否是“正确”的展开量。

您可以通过调用特定于处理器的 SIMD 内部函数获得更多改进，但这不是标准的 C++。