c - 优化慢循环

Question

代码看起来像这样，并且内部循环要花费大量时间：

#define _table_derive                  ((double*)(Buffer_temp + offset))
#define Table_derive(m,nbol,pos)        _table_derive[(m) + 5*((pos) + _interval_derive_dIdQ * (nbol))]
char *Buffer_temp=malloc(...);

for (n_bol=0; n_bol<1400; n_bol++)  // long loop here
    [lots of code here, hundreds of lines with computations on doubles, other loops, etc]

    double ddI=0, ddQ=0;

    // This is the original code
    for(k=0; k< 100; k++ ) {
            ddI += Table_derive(2,n_bol,k);
            ddQ += Table_derive(3,n_bol,k);
    }
    ddI /= _interval_derive_dIdQ;
    ddQ /= _interval_derive_dIdQ;
    [more code here]
}

oprofile告诉我，大多数运行时都用在这里（第二列是时间的百分比）：

129304  7.6913 :for(k=0; k< 100; k++) {
275831 16.4070 :ddI += Table_derive(2,n_bol,k);
764965 45.5018 :ddQ += Table_derive(3,n_bol,k);

我的第一个问题是：我可以依靠oprofile来指示代码缓慢的正确位置（我在-Og和-Ofast中尝试过，并且基本上是相同的）。

我的第二个问题是：为什么这个非常简单的循环比sqrt，atan2和之前的数百行计算要慢？我知道我没有显示所有代码，但是有很多代码，对我来说这没有意义。

我尝试了各种优化器技巧来矢量化（不起作用）或展开（起作用），但是获得的收益很小，例如：

    typedef double aligned_double __attribute__((aligned(8)));
    typedef const aligned_double* SSE_PTR;
    SSE_PTR TD=(SSE_PTR)&Table_derive(2,n_bol,0);   // We KNOW the alignement is correct because offset is multiple of 8

    for(k=0; k< 100; k++, TD+=5) {
        #pragma Loop_Optimize Unroll No_Vector
        ddI += TD[0];
        ddQ += TD[1];
    }

我检查了优化器的输出：
“ -Ofast -g -march = native -fopt-info-all = missed.info -funroll-loops”
在这种情况下，我会“展开9次循环”，但是如果我尝试向量化，我会得到（简而言之）：
“无法强制ref对齐”，
“向量对齐可能无法达到”，
“对未对齐的访问进行矢量化处理”，
“访问的未知对齐方式：*（prephitmp_3784 +（（sizetype）_1328 +（long unsigned int）（n_bol_1173 * 500）* 2）* 4）”

有什么办法可以加快速度吗？

附录：
感谢所有评论，我将在此处尝试回答：


是的，我知道代码很丑陋（不是我的），并且您还没有看到真正的原始代码（这是一个极大的简化）
由于C代码位于库中，因此我受困于此数组，并且大型数组一旦由C处理和修改，就将传递给调用方（IDL，Python或C）。
我知道使用一些strucs而不是将char *转换为复杂的多维double *会更好，但是请参见上文。最初编写此编时，结构可能不是C规范的一部分（只是在开玩笑……也许）
我知道，对于矢量化程序而言，拥有数组结构要比结构数组好，但是，叹气……参见上文。
（在调用程序中）存在一个实际的外部循环，因此该单片阵列的总大小约为2Gb
照原样，无优化运行大约需要15分钟，而我重写了一些代码（更快的atan2，在数组内部进行了一些手动对齐）后又花了1分钟，然后我使用了-Ofast和-march = native
由于硬件的限制变化，我试图更快地跟上数据流的速度。
我尝试使用Clang时，增益很小（几秒钟），但是我看不到获得诸如-fopt-info之类的优化报告的选项。我是否必须将程序集视为知道发生了什么的唯一选择？
该系统是具有500Gb RAM的惊人的64核，但我无法插入任何OpenMP编译指示来并行化上述代码（我已经尝试过）：它读取文件，将其完全解压缩到内存（2Gb）中，按顺序对其进行分析（如“ + =”之类），然后将一些结果发送给调用IDL / Python。所有这些都在一个核心上（但是其他核心都非常忙于实际的采集和后处理）。 :(
没用，谢谢您的出色建议：删除ddQ + = ...似乎将时间百分比转移到了上一行：376280 39.4835：ddI + = ...
这使我们更好：将两者都删除（因此删除整个循环）可以节省……一无所有！！！因此，我想正如Peter所说，我不能相信探查器。如果我分析无环编，我会得到更均匀的时序分布（以前只有1s以上的3行，现在大约10行，所有简单的变量都没有意义）。


我想内环从一开始就是个红鲱鱼。我将使用手动计时重新开始优化。谢谢。

Answer 1

我的第一个问题是：我可以依靠oprofile来指示正确的
代码慢的地方

不完全是。据我了解，周期经常被用于等待输入（或其他执行资源）的指令，而不是缓慢产生输入或释放任何其他执行资源的指令。
但是，在您的oprofile输出中，很可能实际上是最后一个循环。这个外循环中还有其他内循环吗？
您是否配置了缓存未命中？除周期外，还有许多有趣的事物的计数器。
还请注意，要真正了解性能，您需要查看汇编（而不是C）上的配置文件注释。奇怪的是，一次添加比另一次添加更多的时间，但这可能只是将insns映射到源代码行的问题。

回复：性能来自注释掉循环：
因此，如果没有该内部循环，该程序将不会运行得更快？如果外循环已经触及到该内存，也许您只是在高速缓存未命中时遇到瓶颈，而内循环又再次触及了该内存？尝试perf record -e L1-dcache-load-misses ./a.out然后perf report。或等效的oprofile。
也许内部循环的微指令被卡住，等待发布，直到外部循环中的慢速内容退役。现代Intel CPU中的ReOrder Buffer（ROB）大小约为200 uops，大多数insns解码为单个uop，因此乱序窗口约为200条指令。
注释掉内部循环还意味着在外部循环运行时，外部循环中任何循环承载的依赖链都没有时间来完成。从吞吐量到延迟，删除该内部循环可能会导致外部循环的瓶颈发生质的变化。

回复：使用-Ofast -march=native快15倍。好的，那很好。未优化的代码太可怕了，不应被视为任何形式的“基准”或任何性能指标。如果要与某物进行比较，请与-O2比较（不包括自动矢量化，-ffast-math或-march=native）。
尝试使用-fprofile-generate / -fprofile-use。 profile-use包含-funroll-loops，因此我假设在有可用的概要分析数据时，该选项最有效。
回复：自动并行化：
您必须使用OpenMP编译指示或像-floop-parallelize-all -ftree-parallelize-loops=4这样的gcc options专门启用它。如果存在非平凡的循环承载依赖关系，则可能无法进行自动并行化。该Wiki页面也很旧，可能无法反映自动并行化的最新技术。我认为OpenMP暗示要并行化哪些循环是比让编译器进行猜测更为明智的方法。没有-fprofile-use。


我尝试使用Clang时，增益很小（几秒钟），但是我看不到获得诸如-fopt-info之类的优化报告的选项。我是否必须将程序集视为知道发生了什么的唯一选择？

您可以将clang manual says用于clang -Rpass=inline有关内联的报告。 The llvm docs say矢量化传递的名称为loop-vectorize，因此您可以使用-Rpass-missed=loop-vectorize或-Rpass-analysis=loop-vectorize告诉您导致矢量化失败的语句。
查看asm是了解其是否会严重自动向量化的唯一方法，但是要真正判断编译器的工作，您必须知道如何自己编写高效的asm（这样您就知道它可以完成的工作。）请参阅< aa>，以及http://agner.org/optimize/标签Wiki中的其他链接。
我没有尝试将您的代码放在x86上以使用不同的编译器进行尝试，但是如果您的示例使asm代表了从完整源代码中看到的内容，则可以发布链接。

自动向量化

for(k=0; k< 100; k++ ) {
        ddI += Table_derive(2,n_bol,k);
        ddQ += Table_derive(3,n_bol,k);
}

这应该自动矢量化，因为2和3是连续的元素。如果将表拆分为多个表，则将获得更好的缓存局部性（针对此部分）。例如将每组5个元素中的元素2和3保持在一个数组中。将一起使用的其他元素分组到表中。 （如果存在重叠，例如另一个循环需要元素1和3，那么可能分解了无法自动矢量化的元素？）
回复：问题更新：您不需要为此使用SSE自动矢量化的数组结构。 16B向量恰好包含两个double，因此编译器可以将[ ddI ddQ ]向量与addsd累加。对于AVX 256b向量，它必须执行vmovupd / vinsertf128来从相邻结构中获得这对double，而不是单个256b加载，但这并不是一件大事。但是，内存局部性是一个问题。您所触摸的缓存行中每5个double仅使用2个。

只要您将CPU定位为具有双精度矢量的CPU，它甚至应该即使没有-ffast-math也会自动矢量化。 （例如x86-64或带有-msse2的32位）。
gcc喜欢为可能未对齐的数据制作大量序言，使用标量，直到到达对齐的地址为止。这会导致代码code肿，尤其是。带有256b向量和小元素。不过，使用double应该还不错。仍然尝试clang 3.7或clang 3.8。 clang自动矢量化具有未对齐负载的可能未对齐的访问，而在运行时对齐数据则不会产生额外的开销。 （gcc会针对极少数情况下的数据不对齐进行优化，因为即使在对齐数据上使用时，未对齐的加载/存储指令在旧CPU（例如Intel pre-Nehalem）上也较慢）

如果无法证明每个char甚至都是8B对齐的，则您的double数组可能会击败自动矢量化器。就像@JohnBollinger评论的那样，这确实很丑。如果您有5个double的结构体数组，请以这种方式声明！
如何将其编写为结构数组：
保留“手动”多维索引，但将基本1D数组设置为double或更好的struct类型的数组，因此编译器将假定每个double是8B对齐的。
您的原始版本还引用了每次访问数组时的全局Buffer_temp。 （或者它是本地的？）任何可能使用别名的存储都将需要重新加载基本指针。 （C的别名规则允许char*为任何别名，但是我认为在取消引用之前将对象强制转换为double*可以避免这种情况。无论如何，您都不会存储到内部循环内部的数组中，但是我假设您位于外部数组。）

typedef struct table_derive_entry {
    double a,b,c,d,e;
} derive_t;

void foo(void)
{
    // I wasn't clear on whether table is static/global, or per-call scratch space.
    derive_t *table = aligned_alloc(foo*bar*sizeof(derive_t), 64);            // or just malloc, or C99 variable size array.

    // table += offset/sizeof(table[0]);   // if table is global and offset is fixed within one call...

// maybe make offset a macro arg, too?
#define Table_derive(nbol, pos)     table[offset/sizeof(derive_t) + (pos) + _interval_derive_dIdQ / sizeof(derive_t) * (nbol))]


    // ...        
    for(k=0; k< 100; k++ ) {
         ddI += Table_derive(n_bol, k).b;
         ddQ += Table_derive(n_bol, k).c;
    }
    // ...
}
#undef Table_derive

如果_interval_derive_dIdQ和offset并非总是5 * 8B的倍数，那么您可能需要声明double *table = ...;并将Table_derive修改为类似

#define Table_derive(nbol, pos)   ( ((derive_t *)(double_table + offset/sizeof(double) + _interval_derive_dIdQ / sizeof(double) * (nbol)))[pos] )

FP部门：

ddI /= _interval_derive_dIdQ;
ddQ /= _interval_derive_dIdQ;

您可以将double inv_interval_derive_dIdQ = 1.0 / _interval_derive_dIdQ;提升到循环之外吗？乘法比除法便宜得多。如果延迟很重要，或者sqrt也需要div单位。