为什么g ++将计算推入热循环？

Question

我有一个非常奇怪的编译器行为,其中G ++将计算拉入热循环,严重降低了生成的代码的性能.这里发生了什么？

考虑这个功能:

#include <cstdint>

constexpr bool noLambda = true;

void funnyEval(const uint8_t* columnData, uint64_t dataOffset, uint64_t dictOffset, int32_t iter, int32_t limit, int32_t* writer,const int32_t* dictPtr2){
   // Computation X1
   const int32_t* dictPtr = reinterpret_cast<const int32_t*>(columnData + dictOffset);
   // Computation X2
   const uint16_t* data = (const uint16_t*)(columnData + dataOffset);
   // 1. The less broken solution without lambda
   if (noLambda) {
        for (;iter != limit;++iter){
            int32_t t=dictPtr[data[iter]];
            *writer = t;
            writer++;
        }
   }
   // 2. The totally broken solution with lambda
   else {
        auto loop = [=](auto body) mutable { for (;iter != limit;++iter){ body(iter); } };
        loop([=](unsigned index) mutable {
            int32_t t=dictPtr[data[index]];
            *writer = t;
            writer++;
        });
   }
}

这里的问题是,G ++莫名其妙地喜欢拉计算X1和X2成热的主循环,降低了性能.以下是详细信息:

该函数简单地遍历数组data,在字典中查找值dictPtr并将其写入目标内存位置writer. data并dictPtr在函数的开头计算.它有两种口味:一种带有lambda,一种带有lambda.

(注意,这个函数只是一个更复杂的代码的最小工作示例.所以请不要在这里评论lambda是不必要的.我知道这个事实,在原始代码中,它是必要的,不幸的是.)

使用最新的g ++(尝试过的8.1和7.2,与你提供的Godbolt链接中可以看到的老g ++相同的问题)编译高优化级别(-O3 -std=c++14)的问题如下:

解决方案2.(noLambda=false)为循环生成非常糟糕的代码,甚至比"天真"解决方案更糟糕,因为它假设将超级热循环之外的计算X1和X2拉入到超级热主循环,使我的CPU慢了大约25%.

https://godbolt.org/g/MzbxPN

.L3:
        movl    %ecx, %eax          # unnecessary extra work
        addl    $1, %ecx
        addq    $4, %r9             # separate loop counter (pointer increment)
        leaq    (%rdi,%rax,2), %rax # array indexing with an LEA
        movzwl  (%rax,%rsi), %eax   # rax+rsi is Computation X2, pulled into the loop!
        leaq    (%rdi,%rax,4), %rax # rax+rdx is Computation X1, pulled into the loop!
        movl    (%rax,%rdx), %eax   
        movl    %eax, -4(%r9)
        cmpl    %ecx, %r8d
        jne     .L3

当使用通常的for循环(noLambda=true)时,代码更好,因为X2不再被拉入循环,但X1仍然是!:

https://godbolt.org/g/eVG75m

.L3:
        movzwl  (%rsi,%rax,2), %ecx
        leaq    (%rdi,%rcx,4), %rcx
        movl    (%rcx,%rdx), %ecx # This is Computation X1, pulled into the loop!
        movl    %ecx, (%r9,%rax,4)
        addq    $1, %rax
        cmpq    %rax, %r8
        jne     .L3

你可以尝试通过用(一个参数)替换循环中的dictPtr(计算X1)来循环中的X1 dictPtr2,指令将消失:

https://godbolt.org/g/nZ7TjJ

.L3:
        movzwl  (%rdi,%rax,2), %ecx
        movl    (%r10,%rcx,4), %ecx
        movl    %ecx, (%r9,%rax,4)
        addq    $1, %rax
        cmpq    %rax, %rdx
        jne     .L3

这最终是循环,因为我想拥有它.一个简单的循环,可以加载值并存储结果,而不会将随机计算拖入其中.

那么,这里发生了什么？将计算引入热循环很少是一个好主意,但G ++似乎在这里这么认为.这让我失去了真正的表现.lambda加剧了整个局势; 它导致G ++将更多的计算引入循环.

是什么让这个问题如此严重,这是一个非常简单的C++代码,没有花哨的功能.如果我不能依赖我的编译器为这样一个简单的例子生成完美的代码,我将需要在我的代码中检查所有热循环的汇编,以确保一切尽可能快.这也意味着可能有大量的程序受此影响.

Answer 1

您使用无符号32位类型作为数组索引(在第21行).这会强制编译器在循环的每个步骤中考虑是否可能溢出其可用范围,在这种情况下,它需要返回到数组的开头.您看到的额外代码与此检查有关!至少有三种方法可以避免编译器采用这种过于谨慎的方法:

1. 在第21行使用64位类型的索引.现在编译器知道你永远不会包围数组,并生成与没有lambda相同的代码.
2. 在第21行使用带符号的32位类型作为索引.现在编译器不再关心溢出:有符号溢出被认为是UB,因此被忽略.我认为这是对标准解释的一个错误,但意见不同.
3. 通过添加一行'int32_t iter = 0;'来清楚编译器是否永远不会发生溢出 在函数的开头,并从声明中删除它.显然,这并不能解决您的问题,但它说明了溢出分析是如何导致生成额外代码的.

在循环开始之前你并没有抱怨代码,但是你遇到了同样的问题.只需创建它并限制int64_t,你就会发现它变得更短,因为编译器不再考虑阵列溢出的可能性.

所以回顾一下:不是X1和X2的计算被移动到循环中导致大小膨胀,而是使用了错误类型的数组索引变量.

Answer 2

恭喜你,你发现了一个gcc bug.主要解决方案是使用"miss-optimization"关键字在GCC的bugzilla上报告.你的MCVE已经是bug的很好的测试用例了,所以编写一个不需要太长时间.复制/粘贴代码和一些描述.此问答的链接以及http://godbolt.org/上代码的链接也很好.

有时候微妙的微架构理由会使用"额外"指令,例如 - xor调整目标popcnt/ lzcnt或bsf 避免对英特尔CPU的错误依赖,但事实并非如此.这很糟糕; 的movl %ecx, %eax内循环可以是使用一个无符号类型比指针更窄的结果,但即使这样,可以更有效地完成; 这也是一个错过的优化.

我没有查看GCC的GIMPLE或RTL转储(内部表示)以了解更多详细信息.计算值的唯一用途是在循环内部,因此我可以想象编译器的程序逻辑的内部表示可能在转换时丢失循环内部/外部之间的差异.通常情况下,不需要在循环中的东西被提升或沉没在循环之外.

但不幸的是,gcc mov在循环中留下额外的指令来设置循环外的代码并不罕见.特别是当它可能需要循环外的多个指令才能获得相同的效果.在优化性能而不是代码大小时,这通常是一个不好的权衡.我没有像我想的那样查看Profile-Guided Optimization的asm输出,看看gcc知道哪些循环真的很热并且展开它们的代码.但不幸的是,大多数代码都是在没有PGO的情况下构建的,因此没有代码生成-fprofile-use仍然非常重要.

但是,这个问题的核心不是如何尽可能快地得到这个特定的例子.相反,我对编译器如何在如此简单的代码片段中产生这样的去优化感到非常恼火.我现在的主要问题是:我对编译器失去了信心,所以我想了解这是怎么发生的,所以我可以重新获得它.

对gcc不信任!这是一个非常复杂的机器,通常会产生良好的结果,但很少产生最佳效果.

这个案例是我看到它的优化器制作的最明显和最简单的错误选择之一(并且非常令人失望).通常,错过的优化会更加微妙(并且依赖于微架构细节,如寻址模式选择和uops /执行端口),或者至少不那么明显是微不足道的避免.(提升一条指令而不改变整个循环的任何寄存器分配.)

但许多循环瓶颈在内存上,而不是uop吞吐量.现代CPU通过编译器(特别是JIT编译器)生成的浪费指令来设计.这就是为什么像这样的遗漏优化通常不会对宏观尺度产生很大影响,以及为什么它们重要的情况(例如视频编码器或矩阵乘法)通常仍然使用手写asm块.

通过以类似于你想要的asm结构的方式实现你的源代码,通常可以把gcc手工制作成好的asm.(就像这种情况:在一个位置或更低位置计算设置位的有效方法是什么？,并且看看为什么这个C++代码比用于测试Collat​​z猜想的手写程序集更快？,有关帮助编译器与用手写的asm击败编译器.)

但是当你的编译器像这样脑力下降时,你无能为力.好吧,除了寻找变通方法,或者避免unsigned整数比指针更窄的东西,其他一些答案已经指出这些指针很重要.

有趣的是,最糟糕的情况(循环中的2个额外LEA指令,加上使用额外的循环计数器)只发生在你的if (noLambda).

如果你制作2个独立版本的函数并删除它if,那么nolambda版本会产生一个很好的干净循环(但是错过了聚集的自动矢量化,这在编译时会是一个胜利-march=skylake)

我把你的代码放在Godbolt编译器资源管理器上.(同样有趣的是,用于-funroll-loops查看哪些部分在每次展开的循环迭代中重做,哪些部分只在循环内部重复一次.)

# gcc7.2:  the nolamba side of the if, with no actual if()
.L3:
    movzwl  (%rsi,%rax,2), %ecx
    movl    (%rdx,%rcx,4), %ecx
    movl    %ecx, (%r9,%rax,4)   # indexed store: no port 7
    addq    $1, %rax             # gcc8 -O3 -march=skylake uses inc to save a code byte here.
    cmpq    %rax, %r8
    jne     .L3

在Intel Sandybridge系列中,这解码为5 uops.(cmp/jcc的宏融合将该对转换为1 uop.其他指令都是单uop; movzwl是纯负载,不需要ALU端口).

该商店在SnB/IvB上进行了非层压(对于4宽发布阶段来说是一个额外的优势,这是主要的前端瓶颈之一),但可以在HSW/SKL上保持融合.它不能使用端口7(因为它被索引),这意味着HSW/SKL将限制为每个时钟2个存储器操作,而不是3个.

瓶颈:

• 每个时钟4个融合域uop的前端发布带宽.循环是5微秒,并且每1.25可以发出近1次迭代.(4个非多重循环并不完美,但至少有5个 uops 在Haswell/Skylake处理得很好.可能不是Sandybridge.)

• 加载/存储执行端口:Haswell和更高版本可以每个时钟运行2个加载+ 1个存储,但仅当存储避免索引寻址模式时,存储地址uop才能在端口7上运行.

lambda版本得到第二个循环计数器(指针增量)和一个愚蠢的movl %ecx, %eax,但LEA指令不在循环中.

但这不是额外的计算本身,而是可能会损害你的循环的总uop吞吐量.如果字典大多数在缓存,Haswell或更高版本的CPU中保持热

我打算写更多,但我没有完成.现在发布是因为通用的早期/中期部分显然是问题的真正含义.不要盲目信任gcc.

并且不要指望它会在大多数时间内制作出最佳代码.通过调整C源(有时甚至更多),您通常可以获得10%或20%.有时gcc似乎没有线索,比如lea在展开时没有明显的原因使用额外的s,而不是在寻址模式中使用位移.我认为它的寻址模式成本模型必须不准确,至少对于-march=haswell/ -march=skylake.