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.49s的突出声明比所有其他声明时间高得多.我知道有可能在可能的情况下使用乘法除法来加速C算术.但我不仅仅知道更多.

喜欢:

1. 将这个陈述分成更小的部分会更好吗？:

   br = x2 * brpp;

   br -= brp2;

   br += coef[j];

任何其他想法或批评.我没有编写这段代码,虽然我确实将const添加到函数参数中,因为我喜欢const-correctness.

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

我知道人们会说,"试试吧!" 所以我会,并且会更新我得到的内容,如果它可以帮助任何有类似算术问题的人.

编辑:发布结果我已经从建议测试

从最快到最慢,这是我到目前为止所发现的.Profiler非常好.编译器是Visual Studio 2008 Pro Ed.库和我的应用程序的编译选项是:

Debug, C7 format, /O2 /Ob2 /Oi /Ot /Oy /GT /GL /GF /FD /MTd /GS- /Gy /fp:fast /FAs

以下是Andrew关于进行"每循环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
}

在这个原始代码之后,下一个最快的是Drew提前设置指针并使用它的想法.在函数内部花费的总时间是2.49秒,包括循环外语句的时间:

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

我也尝试了安德鲁的循环展开和Drew的指针使用的混合,但这需要2.39秒,与未改变的代码相同.

根据结果​​,循环展开是迄今为止我的使用方式.

Answer 1

我要尝试的第一件事就是以4的步长迭代,即:j + = 4(或者在你的情况下,j - = 4)并半循环.这样做的原因是它将帮助编译器进行SSE优化并批量从主内存到缓存的内存访问.请注意,如果循环计数不能被4整除,则必须满足最后几个元素.例如:

// Disclaimer: I have not tested this code!
for (; j >= 3; j -= 4) {              
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef[j]; 
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef[j-1]; 
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef[j-2]; 
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef[j-3]; 
}                          
// if (j % 4) != 0 before the loop operation, 
// handle 1, 2 or 3 remaining elements here

我要尝试的第二件事是在计算之前立即将coeff [j]预加载到寄存器中.原因是浮点计算是流水线的,这意味着错误位置的内存访问会对性能产生负面影响.计算本身可以非常快,但可能需要14条指令才能将数据从缓存排入FPU.再加上来自主内存的访问,它可能会变得更糟.例如,尝试这个(也可以尝试使用和不使用 - = 4展开)

// Disclaimer: I have not tested this code!
register double coef1, coef2, coef3, ceof4;
for (; j >= 3; j -= 4) {           
    coef1 = coef[j];    // Preloads the 4 sequential coeffs from 
    coef2 = coef[j-1];  // main memory to cache (if available)
    coef3 = coef[j-2];  
    coef4 = coef[j-3];  
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef1; 
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef2; 
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef3; 
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef4; 
} 

在这种情况下,如果可能的话,变量double x2,br,brp2,brpp,coef1,coef2,coef3,coef4应该是寄存器.

最后,使用上面的内容,您可以应用SSE/SSE2优化吗？确保在GCC编译器中启用了这个(我已经习惯了VS,所以等效的是启用释放模式,调试符号关闭,优化开启,SSE2开启)并在没有连接调试器的情况下对代码进行基准测试.仅此一点就会对性能产生巨大影响.

让我们知道结果.性能调优是试错!

祝你好运,

Answer 2

这似乎是一个缓存问题,而不是算术问题.

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

你在这里访问一个数组,并且你正在递减索引.此操作确实可以破坏简单循环中固有的缓存友好位置.

是否有可能向前推进？也就是说,

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

你的计算是否有效？

Answer 3

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

有一个非常容易的注册技巧,任何人都可以做. 为最近的CPU构建项目. 这段代码是否需要从1995年开始在计算机上运行？2000？2005年？如果程序可以依赖于较新的CPU,那么它可以指望拥有更多的寄存器.

此外,整数索引是不必要的.你可以改为j直接指向double感兴趣的指针. 如果您的优化编译器尚未执行此操作,这可能会有所不同.

double swi_echeb(const double x, const double* const coef, const int ncf)
{
    const double *j = &coef[ncf - 1];
    // (stuff...)

    while (true) { 
        // (stuff...)

        br = x2 * brpp - brp2 + *j;
        if ( j == coef )
            break;
        --j;
    }  
}