如何优化一个简单的循环？

Question

循环很简单

void loop(int n, double* a, double const* b)
{
#pragma ivdep
    for (int i = 0; i < n; ++i, ++a, ++b)
        *a *= *b;
}

我正在使用英特尔 C++ 编译器，目前正在使用 #pragma ivdep 进行优化。有什么方法可以使其性能更好，比如同时使用多核和矢量化，或其他技术？

Answer 1

假设a指向的数据不能与b指向的数据重叠，给编译器优化代码的最重要信息就是事实。

在旧的 ICC 版本中，"restrict" 是向编译器提供关键信息的唯一干净方式。在较新的版本中，有一些更简洁的方法可以提供比 ivdep 更强的保证（实际上 ivdep 对优化器的承诺比它看起来更弱，通常没有预期的效果） .

但如果 n 很大，整个事情将由缓存未命中决定，因此没有任何局部优化可以帮助。

Answer 2

我假设 n 很大。您可以通过启动 k 个线程并为每个线程提供 n/k 个元素来在 k 个 CPU 上分配工作负载。为每个线程使用大块连续数据，不要进行细粒度交错。尝试将块与缓存行对齐。

如果您计划扩展到多个 NUMA 节点，请考虑将工作负载块显式复制到节点，线程运行开启，然后复制回结果。在这种情况下，它可能并没有多大帮助，因为每个步骤的工作量都非常简单。你必须运行测试一下。

Answer 3

手动展开循环是一种优化代码的简单方法，以下是我的代码。原始 loop 耗时 618.48 毫秒，而 loop2 在我的 PC 中耗时 381.10 毫秒，编译器是带有选项“-O2”的 GCC。我没有Intel ICC来验证代码，但我认为优化原理是一样的。

同样，我做了一些实验，比较了两个程序对两个内存块进行异或的执行时间，一个程序是借助 SIMD 指令进行矢量化，而另一个是手动循环展开。如果您有兴趣，请参阅 here。

P.S。当然 loop2 只在 n 为偶数时有效。

#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

#define LEN 512*1024
#define times  1000

void loop(int n, double* a, double const* b){
    int i;
    for(i = 0; i < n; ++i, ++a, ++b)
        *a *= *b;
}

void loop2(int n, double* a, double const* b){
    int i;
    for(i = 0; i < n; i=i+2, a=a+2, b=b+2)
        *a *= *b;
        *(a+1) *= *(b+1);
}


int main(void){
    double *la, *lb;
    struct timeval begin, end;
    int i;

    la = (double *)malloc(LEN*sizeof(double));
    lb = (double *)malloc(LEN*sizeof(double));
    gettimeofday(&begin, NULL);
    for(i = 0; i < times; ++i){
        loop(LEN, la, lb);
    }
    gettimeofday(&end, NULL);
    printf("Time cost : %.2f ms\n",(end.tv_sec-begin.tv_sec)*1000.0\
            +(end.tv_usec-begin.tv_usec)/1000.0);

    gettimeofday(&begin, NULL);
    for(i = 0; i < times; ++i){
        loop2(LEN, la, lb);
    }
    gettimeofday(&end, NULL);
    printf("Time cost : %.2f ms\n",(end.tv_sec-begin.tv_sec)*1000.0\
            +(end.tv_usec-begin.tv_usec)/1000.0);

    free(la);
    free(lb);
    return 0;
}

Answer 4

这个循环绝对是 vectoriz编译器。但要确保该循环实际上是矢量化的（使用编译器'-qopt-report5、汇编输出、Intel (vectorization) Advisor，无论其他技术）。另一种矫枉过正的方法是使用 -no-vec 选项（这将禁用 ivdep 驱动和自动矢量化）创建 性能基线 ，然后将执行时间与其进行比较。这不是检查矢量化存在的好方法，但它对于下一个项目符号的一般性能分析很有用。

如果循环实际上还没有被向量化，请确保你推动编译器自动向量化它。为了推动编译器，请参阅下一个项目符号。请注意，即使循环已成功自动矢量化，下一个项目符号也可能有用。

要推动编译器对其进行矢量化，请使用：(a) restrict 关键字到 "disambiguate" a 和 b 指针（有人已经建议它你）。 (b) #pragma omp simd（与 ivdep 相比，它具有更便携和灵活得多的额外好处，但也有一个缺点，即在英特尔编译器版本 14 和之前的旧编译器中不受支持对于其他循环更多 "dangerous")。再次强调：given bullet 可能看起来与 ivdep 做同样的事情，但根据不同的情况，它可能是更好、更强大的选项。
给定循环具有细粒度迭代（每次迭代的计算量太少）并且总体上不是纯粹的计算限制（因此 effort/cycles 花费 CPU load/store 数据 from/to cache/memory 与执行乘法所花费的 effort/cycles 相比，如果不更大的话）。展开通常是稍微减轻此类缺点的好方法。但我建议通过使用 #pragma unroll 明确要求编译器展开它。事实上，对于某些编译器版本，展开会自动发生。同样，您可以使用 -qopt-report5、循环汇编或 Intel（矢量化）Advisor 检查编译器何时执行此操作：
在给定的循环中，您处理 "streaming" 访问模式。 IE。你是连续 loading/store 数据 from/to 内存（缓存子系统对大 "n" 值没有多大帮助）。因此，根据目标硬件、多线程的使用（在 SIMD 之上）等，您的循环最终可能会成为内存带宽限制。一旦成为内存带宽限制，您就可以使用循环阻塞、非临时存储、主动预取等技术。所有这些技术都值得单独写一篇文章，尽管对于 prefetching/NT-stores，您可以使用英特尔编译器中的一些编译指示。
如果 n 很大，并且您已经准备好应对内存带宽问题，您可以使用 #pragma omp parallel for simd 之类的东西，这将同时线程并行化和向量化循环。然而，此功能的质量仅在非常新的编译器版本 AFAIK 中才变得不错，因此您可能更愿意半手动拆分 n。 IE。 n=n1xn2xn3，其中 n1 - 是要在线程之间分配的迭代次数，n2 - 用于缓存阻塞，n3 - 用于矢量化。重写给定循环，使其成为 3 个嵌套循环的最内层循环，其中外层循环有 n1 次迭代（并且应用了#pragma omp parallel for），下一级循环有 n2 次迭代，n3 - 是最内层的（其中应用了#pragma omp simd）。

一些包含语法示例和更多信息的最新链接:

展开：https://software.intel.com/en-us/articles/avoid-manual-loop-unrolling
OpenMP SIMD pragma（不是那么新鲜和详细，但仍然相关）：https://software.intel.com/en-us/articles/enabling-simd-in-program-using-openmp40
restrict vs. ivdep
NT 存储和预取：https://software.intel.com/sites/default/files/managed/22/a3/mtaap2013-prefetch-streaming-stores.pdf

注意1：很抱歉，我没有在这里提供各种代码片段。至少有 2 个合理的理由不在这里提供它们： 1. 我的 5 个项目符号几乎适用于很多内核，而不仅仅是你的。 2. 另一方面，pragmas/manual 重写技术的具体组合和相应的性能结果将因目标平台、ISA 和编译器版本而异。

注 2：关于您的 GPU 问题的最后评论。想想你的循环与简单的行业基准，如 LINPACK 或 STREAM。事实上，您的循环最终可能会变得与其中一些非常相似。现在想想 x86 CPUs，尤其是 LINPACK/STREAM 的 Intel Xeon Phi 平台特性。它们确实非常好，并且在高带宽内存平台（如 Xeon Phi 2nd gen）上会变得更好。所以理论上没有任何单一的理由认为 你给定的循环 没有很好地映射到 x86 硬件的至少一些变体（请注意，我没有为 [=33 说类似的话=]宇宙中的任意内核).

如何优化一个简单的循环？

How to optimize a simple loop?

c++

optimization

multicore

simd

vectorization