C - 有一个简单的循环来进行算术计算；探查器显示这是一个瓶颈。如何加快速度？

Question

我的第一篇文章在这里。一个很棒的网站和资源。

我确实进行了一些搜索，并查看了标题相似的问题，但找不到具体的内容。

我正在尝试从我的 C++ 程序使用的 C 天文计算库中删除任何冗余和膨胀。我运行了一个简单的分析器 (VerySleepy)。

这是分析器显示的使用时间最多的代码(除了 C 库函数 sprintf 等):

double swi_echeb(const double x, const double* const coef, const int ncf)
{
    int j = ncf - 1;
    double x2, br, brp2, brpp;
    x2 = x * 2.;
    br = 0.;
    brp2 = 0.;  /* dummy assign to silence gcc warning */
    brpp = 0.;

    for (; j >= 0; --j) {                 // <-- 0.39s
        brp2 = brpp;                      // <-- 0.01s
        brpp = br;                        // <-- 0.32s
        br = x2 * brpp - brp2 + coef[j];  // <-- 3.49s ***
    }                                     // <-- 0.14s

    return (br - brp2) * .5;              // <-- 0.06s
}                                         // <-- 0.05s

这个特定的函数深深地嵌入到其他函数中，我的程序调用的主要“启动”函数被调用了数千次。

您可以看到 3.49 秒的出色语句比所有其他语句时间高得多。我知道有一些方法可以通过在可能的情况下使用乘法来加速 C 算术。但我知道的不多。

喜欢:

1. 将此语句拆分成更小的部分会更好吗？:

   br = x2 * brpp;

   br -= brp2;

   br += 系数[j];

任何其他想法或批评。这段代码不是我写的，尽管我确实将 const 添加到函数参数中，因为我喜欢 const 的正确性。

我以前从未尝试过使用寄存器或其他花哨的技巧来加快速度。有人认为类似的东西可以在这里工作吗？

我知道人们会说，“试试吧!”所以我会的，如果它能帮助任何有类似算术问题的人，我会更新我得到的。

编辑:发布我根据建议测试的结果

按照从最快到最慢的顺序，这是我目前所发现的。 Profiler 是 VerySleepy。编译器是 Visual Studio 2008 Pro Ed。库和我的应用程序的编译选项是:

调试，C7格式，/O2/Ob2/Oi/Ot/Oy/GT/GL/GF/FD/MTd/GS-/Gy/fp:fast/FAs

以下是安德鲁关于“每个循环 4 次迭代”的建议。这是迄今为止最快的。

函数花费的总时间(函数中其他语句的时间未在此处显示)= 2.08 秒

for (; index >= 3; index -= 4) {                    // 0.02s
    brp2    = brpp;
    brpp    = br;                                   // 0.02s
    br      = x2 * brpp - brp2 + coef[index];       // 0.25s
    brp2    = brpp;
    brpp    = br;                                   // 0.13s
    br      = x2 * brpp - brp2 + coef[index - 1];   // 0.33s
    brp2    = brpp;
    brpp    = br;                                   // 0.13s
    br      = x2 * brpp - brp2 + coef[index - 2];   // 0.34s
    brp2    = brpp;
    brpp    = br;                                   // 0.14s
    br      = x2 * brpp - brp2 + coef[index - 3];   // 0.42s
}

for (; index >= 0; --index) {                 // 0.03s
    brp2    = brpp;                           // 0.03s
    brpp    = br;
    br      = x2 * brpp - brp2 + coef[index]; // 0.11s
}

下一个最快的是原始的未更改代码，函数内的总时间为 2.39 秒，同样包括循环外的语句。请注意，这比我原来的帖子要少。我原来的帖子是未优化的代码，但由于每个人都建议这样做，所以我的所有测试随后都尽可能地在 VS08 中进行了优化:

for (j = ncf - 1; j >= 0; j--) {      // 0.02s
    brp2 = brpp;                      // 0.03s
    brpp = br;                        // 0.07s
    br = x2 * brpp - brp2 + coef[j];  // 2.14s
}

在这个原始代码之后，下一个最快的是德鲁预先设置指针并使用它的想法。 在函数内花费的总时间为 2.49 秒，包括循环外语句的时间:

for (; index >= coef; --index) {         // 0.01s
    brp2    = brpp;
    brpp    = br;                        // 0.06s
    br      = x2 * brpp - brp2 + *index; // 2.24s
}

我还尝试了混合使用 Andrew 的循环展开和 Drew 的指针使用，但这花费了 2.39 秒，与未更改的代码相同。

根据结果，循环展开是目前我使用的方法。

Answer 1

这似乎是缓存问题，而不是算术问题。

for (; j >= 0; --j) {
    ...
    ... coef[j];
}

您在这里访问一个数组，并且您正在递减一个索引来这样做。此操作确实会破坏简单循环中固有的缓存友好局部性。

可以往前数吗？即，

for (int i = 0; i <= j; i++) {
    ...
    ... coef[i];
}

你的计算是否有效？