衡量循环展开的权衡

3
使用Google Benchmark来对以下函数进行基准测试:
int sumElements(int *arr, int count)
{
    int sum = 0;
    for (int i = 0; i < count; ++i) {
        sum += arr[i];
    }
    return sum;
}

int sumElementsUnrolled(int *arr, int count)
{
    int sumA = 0;
    int sumB = 0;
    for (int i = 0; i < count; i += 2) {
        sumA += arr[i];
        sumB += arr[i + 1];
    }
    return sumA + sumB;
}

基准测试结果:

--------------------------------------------------------------
Benchmark                    Time             CPU   Iterations
--------------------------------------------------------------
sumElements                965 ns          963 ns       723250
sumElementsUnrolled        641 ns          641 ns      1091406

我尝试使用Google Benchmark对这些函数进行基准测试,并在-O0和-O1下获得了明显的好处。我在几个地方学到,这可能是由于打破依赖链,如果我理解正确的话,这会导致CPU在执行我的指令时减少流水线停顿。看着-O1下的生成的汇编代码,这是有道理的:展开版本为每个求和变量使用不同的寄存器,打破了依赖链。
问题:
  1. 这个解释正确吗,还是我完全错了?
  2. 如果是这样,我如何在这里测量流水线停顿?运行perf stat显示展开版本的stalled-cycles-backend的速率要高得多,但我不确定这是否相关。
  3. 如果不是这样,那么加速的原因是什么?在CPU级别上打破依赖链会产生什么效果?
基准测试代码非常简单:
#define SIZE 4096

int *initArray(int size)
{
    int *arr = (int*)malloc(size * sizeof(int));
    for (int i = 0; i < size; ++i) {
        arr[i] = rand();
    }
    return arr;
}

void doBenchmark(benchmark::State &s)
{
    int *arr = initArray(SIZE);
    for (auto _ : s) {
        int sum = sumElements(arr, SIZE);
        benchmark::DoNotOptimize(sum);
    }
    free(arr);
}


BENCHMARK(doBenchmark);

我尝试使用perf stat来确定加速的原因。但是我不确定如何解释结果。

获取反转结果 https://quick-bench.com/q/Z679SMuTuf3qzbNYUgH_HMD5bdA - undefined
1
这可以是一个后续问题:反向结果是针对 -O3 的。我在问题中提到了 -O1。 - undefined
7
你使用了手动优化的 -O1,而你手动展开的循环在 -O2 和 -O3 下破坏了编译器的工作。 - undefined
3
永远不要低估编译器对你的帮助。 - undefined
顺便提一下,为什么还在使用“C”风格的编码(malloc和传递“C”风格的数组)? - undefined
显示剩余2条评论
1个回答

2
TL;DR: 就像273K所说的那样,你使用了手动优化的-O1,而你手动展开的循环破坏了编译器使用-O2-O3进行的工作。(主要是因为自动向量化。)
在实际的编译器生成的汇编代码(而不是C++源代码)中,展开循环的一个权衡是更大的指令缓存占用。你无法通过只运行展开循环的微基准测试来衡量这个代价;在重复循环的微基准测试中,像这样的循环或者memcpy的复杂实现看起来很好。实际的代价取决于这个程序中的指令缓存压力。
另一个代价是,如果你的函数需要对所有可能的count值都正确,那么你可能需要更多的清理工作来处理奇数的count(与你的测试用例不同)。例如,展开16次循环会使最坏情况下的清理工作变为15个元素;根据你如何进行清理,这可能对于运行几次展开循环的小问题来说更糟糕。
是的,在存储/重新加载(存储转发延迟)瓶颈非常严重的-O0情况下,手动展开循环有助于解决这个问题(在-O0下进行基准测试通常是没有意义的;瓶颈与正常情况不同。在这种情况下,我认为你意识到了这一点,尽管你没有为任何变量使用register int来让-O0构建仍将它们保留在寄存器中。)
而在-O1情况下,也许可以每个时钟周期允许两个标量加法,而不是一个,或者至少在前端吞吐量上出现瓶颈,而不是每个时钟周期的一个循环迭代受到循环分支吞吐量的瓶颈限制。
但是在启用clang的自动向量化时,当使用-O2 / -O3时,手动展开循环通常会使编译器在自动向量化时表现更差。例如,它们会做一些愚蠢的事情,比如将奇偶元素混洗到向量中以分别向量化sumAsumB。它们并不聪明,只是复杂的机器。
在x86-64上,这个问题的最佳汇编代码涉及到SSE2的paddd(或者AVX2的vpaddd,一次处理32字节)。如果数据在L1d缓存中热点,展开那个循环2次可能会有所帮助,但这意味着标量展开8或16次。(就像我说的,编译器不擅长将标量代码转换为SIMD,尤其是带有多个累加器的情况。尽管有时如果标量展开因子与向量宽度匹配,它也能起作用。我建议保持循环简单)
与GCC不同,clang已经默认对微小的循环进行展开,包括在自动向量化时。有时还会使用多个累加器。
Clang 16 -O2 (Godbolt) 生成了这个内部循环的汇编代码,对于未展开版本来说,它有6个微操作(假设在Intel和AMD CPU上会发生cmp/jcc的宏融合,详情请参考https://agner.org/optimize/),因此Alder Lake可以以每个时钟周期一次迭代的速度运行它(每个时钟周期只执行3个加载操作中的2个,详情请参考https://uops.info/)。
  ... compute a loop bound and zero some regs
.LBB0_5:                                # =>This Inner Loop Header: Depth=1
        movdqu  xmm2, xmmword ptr [rdi + rsi]
        paddd   xmm0, xmm2                         # one vector accumulator
        movdqu  xmm2, xmmword ptr [rdi + rsi + 16]
        paddd   xmm1, xmm2                         # second vector accumulator
        add     rsi, 32
        cmp     rax, rsi
        jne     .LBB0_5             ; } while(i < max);

# Then combine to one vector
        paddd   xmm1, xmm0
# and horizontal sum down to scalar
        pshufd  xmm0, xmm1, 238                 # xmm0 = xmm1[2,3,2,3]
        paddd   xmm0, xmm1
        pshufd  xmm1, xmm0, 85                  # xmm1 = xmm0[1,1,1,1]
        paddd   xmm1, xmm0
        movd    eax, xmm1
  # sum in EAX  for   benchmark::DoNotOptimize(sum);

        cmp     rdx, rcx
        je      .LBB0_8     ; benchmark repeat loop

进一步展开,并/或使用AVX 带非索引寻址模式或对齐指针以允许单uop内存源[v]paddd,可以减少足够的开销,使得我们在每4或5个uop中的2或3个加载+向量相加上达到瓶颈,让Haswell / Ice Lake / Zen在L1d加载吞吐量上达到瓶颈(SIMD向量整数相加吞吐量至少与所有这些CPU的向量加载吞吐量一样高,并且paddd xmm0,[rdi]在所有这些CPU上都是单uop,但不是vpaddd xmm0,xmm0,[rdi + rsi])。

另请参阅预测现代超标量处理器上操作的延迟需要考虑哪些因素,以及如何手动计算它们?

但是要让编译器生成进一步展开的汇编代码,你需要使用像_mm_load_si128这样的内部函数(对齐加载,可以折叠成遗留SSE paddd的内存源操作数,与_mm_loadu_si128不同,它是非对齐加载)。或者可以使用基于配置文件的优化,这样编译器就知道这个循环确实是热点代码,并且会更加积极地进行优化。
正如我猜测的那样,手动展开版本的汇编代码中涉及到了“shufps”指令。它加载了4个向量,并使用4个“shufps”作为2个输入的洗牌操作,从一对向量中获取奇数和偶数元素,并输入到4个“paddd”指令中。
另外请注意,你展开的版本只在循环次数为偶数时才是等效的,因为你没有为奇数元素编写清理代码。而且,“i < count”将会读取超出数组末尾的内容而不是提前停止。在一般情况下,“i < (count - (unroll_factor-1))”将在最后一个“完整”的迭代之后停止,留下一些剩余的元素而不是走得太远。请注意,这个表达式对于“unroll_factor”为1时简化为“i < count”,这对于记忆它是有帮助的。
另请参阅:如何从GCC/clang汇编输出中去除“噪音”?以及Matt Godbolt在CppCon2017的演讲“我的编译器最近为我做了什么?揭开编译器的盖子”。

我可以看到在这里使用-O2展开循环来解决循环依赖链的问题,通过使用两个累加器。但是这里还有另一个依赖关系吗:循环体中的两个加载都写入xmm2吗?或者这个依赖关系不那么重要吗? - undefined
1
@LostCoder:寄存器重命名使这些加载变得独立。这是一个只写访问,因此它启动了一个新的依赖链。请参阅为什么Haswell上的mulss只需要3个周期,与Agner的指令表不同?(使用多个累加器展开FP循环) - 我在那里的答案的第一部分详细介绍了加载到相同寄存器的情况没有虚假依赖(因为movss xmm1, mem会将其零扩展到整个寄存器,所以就像movups一样,不会与旧值合并)。该问题后来进行了一些编辑以提出更多问题。 - undefined

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接