c - 我怎样才能加快这个循环(在 C 中)？

Question

我正在尝试在 C 中并行化一个卷积函数。这是对两个 64 位 float 数组进行卷积的原始函数:

void convolve(const Float64 *in1,
              UInt32 in1Len,
              const Float64 *in2,
              UInt32 in2Len,
              Float64 *results)
{
    UInt32 i, j;

    for (i = 0; i < in1Len; i++) {
        for (j = 0; j < in2Len; j++) {
            results[i+j] += in1[i] * in2[j];
        }
    }
}

为了允许并发(没有信号量)，我创建了一个函数来计算 results 数组中特定位置的结果:

void convolveHelper(const Float64 *in1,
                    UInt32 in1Len,
                    const Float64 *in2,
                    UInt32 in2Len,
                    Float64 *result,
                    UInt32 outPosition)
{
    UInt32 i, j;

    for (i = 0; i < in1Len; i++) {
        if (i > outPosition)
            break;
        j = outPosition - i;
        if (j >= in2Len)
            continue;
        *result += in1[i] * in2[j];
    }
}

问题是，使用 convolveHelper 会使代码速度降低大约 3.5 倍(在单线程上运行时)。

关于如何加速 convolveHelper，同时保持线程安全，有什么想法吗？

Answer 1

时域中的卷积变成傅里叶域中的乘法。我建议您获取一个快速 FFT 库(如 FFTW)并使用它。你将从 O(n^2) 到 O(n log n)。

算法优化几乎总是胜过微优化。