跳回矢量化余数循环的一些迭代

Question

我手动矢量化循环并一次处理4个项目.项目总数可能不是4的倍数,所以我在主循环结束时留下了一些项目.我认为如果计数大于4并且重做某些项目是安全的,我可以使用相同的主矢量化循环执行剩余项目.例如,如果我需要处理10个项目,我可以在三次迭代中处理0123,4567,6789.我找不到任何对这种技术的引用.它是愚蠢但我不明白怎么样？

#include <stdint.h>
#include <stddef.h>

void inc(int32_t const* __restrict in, int32_t* out, size_t count)
{
    if (count < 4)
    {
        for (size_t i = 0; i < count; ++i)
            out[i] = in[i] + 42;
    }
    else
    {
        typedef int32_t v4i __attribute__ ((vector_size (16), aligned(4)));
        for (size_t i = 0;;)
        {
            for (; i + 4 <= count; i += 4)
            {
                (v4i&)out[i] = (v4i&)in[i] + 42;
            }
            if (i == count)
                break;
            i = count - 4;
        }

    }
}

Answer 1

当您的输入和输出不重叠,并且可以安全地多次重新处理相同的元素时,这个一般的想法很棒.当输出是只写时,通常就是这种情况.例如out[i] = pure_func(in[i])是幂等的,但out[i] += func(in[i])不是.像这样sum += in[i]的减少也不太合适.

当它可用时,它通常比标量清理循环更好.

如果不是这么简单,请参阅@Paul R的评论,以及相关的问题:使用未对齐缓冲区进行矢量化:使用VMASKMOVPS:从未对齐计数生成掩码？或者根本不使用那个insn (TL:DR:实际上使用vmaskmovps通常不好,但是其他的屏蔽和未对齐加载技巧都是.)

你的具体实现(为重叠的最后一个向量重复使用相同的循环)最终会使clang内部循环变得非常糟糕,i+8并且i+4在每个内循环迭代中都是如此.

gcc管理内部循环稍差一点,但它的效率仍然低于gcc7.2 -O3 -mtune=haswell(在Godbolt上的asm输出).内部循环有额外的开销,因为它i每次都会保存旧的i += 4,因为CSE介于它之间和i+4循环条件之间,和/或i = count - 4循环之外.(gcc有时候非常愚蠢地将额外的工作放在内部循环中,而不是在之后重新计算或撤消操作.)

Godbolt编译器资源管理器中的Source + asm(原始版本和改进版本(见下文)).

# Your original source, built with gcc7.2 -O3
# we get here with some registers already set up when count >= 4
.L2:                     # top of outer "loop"
    lea     rcx, [rax+4]
    cmp     rcx, rdx
    ja      .L4

.L17:                    # Inner loop
    movdqu  xmm0, XMMWORD PTR [rdi+rax*4]
    paddd   xmm0, xmm1
    movups  XMMWORD PTR [rsi+rax*4], xmm0
    mov     rax, rcx               # save RAX for use outside the loop!
    lea     rcx, [rax+4]           # 3 uops of loop overhead
    cmp     rcx, rdx
    jbe     .L17

.L4:
    # missed optimization: do rcx-4 here instead of extra work in every inner-loop iteration
    cmp     rax, rdx
    je      .L1             # ret if we're done (whole number of vectors)
    mov     rax, r8
    jmp     .L2             # else back into the loop for the last vector

使用索引寻址模式对SSE2没有特别的影响,但对AVX来说不是一件好事.AVX允许未对齐的内存操作数到任何指令(除外vmovdqa),因此编译器可以在vpaddd xmm0, xmm1, [rdi+rax*4]构建时将负载折叠-march=haswell. 但即使在Haswell上也不能微融合,所以前端仍然是2 uop.

我们可以通过使用来修复clang和gcc的内部循环i <= count - 4.我们知道count >= 4在这一点上,count - 4永远不会包装到一个庞大的数字.(注意,i + 4如果count在类型的最大值的4个范围内,则可以换行并因此创建无限循环.这可能是使得clang如此困难并导致错过优化的原因).

现在我们从gcc7.2和clang5.0获得一个相同的内循环(两者都使用-O3 -march=haswell).(字面相同,即使使用相同的寄存器,也只是一个不同的标签名称.)

.L16:
    vpaddd  xmm0, xmm1, XMMWORD PTR [rdi+rax*4]
    vmovups XMMWORD PTR [rsi+rax*4], xmm0
    add     rax, 4
    cmp     rax, rcx
    jbe     .L16

这是Haswell上的5个融合域uop,因此每1.25个时钟最多可以运行一次,前端瓶颈,而不是加载,存储或SIMD paddd吞吐量.(它可能会在大输入上对内存带宽产生瓶颈,但即使在这种情况下,至少展开一点也是一件好事.)

clang会在自动矢量化时为你展开,并使用AVX2,所以你实际上通过手动矢量化来实现更糟糕的asm,在这种情况下编译器可以轻松地完成它.(除非你使用gcc -O2,不启用自动矢量化).

你实际上可以看到一个clang自动向量化的例子,因为它会对清理循环进行向量化,因为某些原因没有意识到它无法运行count >= 4.是的,它检查是否count > 3并跳转到手动矢量化循环,然后检查它是否是0,然后检查它是否> 32并跳转到清理循环的自动矢量化版本.../facepalm.)

实际上跳回到主循环主要与在C源中展开不兼容,并且可能会使编译器展开失败.

如上所述,展开内循环通常是一个胜利.

在asm中,你当然可以进行设置,这样你就可以在展开的循环之后跳回到最后1或2个向量的内循环,然后可能再次为未对齐的最终向量.

但这对分支预测可能不利.可能会强烈预测循环分支,因此每次跳回循环时都可能会错误预测.单独的清理代码不会有这个问题,所以如果这是一个真正的问题,那么单独的清理代码(复制内部循环体)会更好.

您通常可以将内部循环逻辑包装在一个内联函数中,该函数可以在展开的循环中多次使用,一次在清理/最后未对齐的向量块中.

虽然你的想法在这种情况下不会出现内部循环的影响,如果你仔细地做,内部循环之前/之后的额外指令和额外分支的数量可能比你用更简单的清理方法得到的更多.所以,如果循环体非常大,这可能是有用的,但在这种情况下,它只是一些指令,复制比分支更便宜.

解决相同问题的一种有效方法是使用可能重叠的最后一个向量,因此没有条件分支取决于元素计数是否是整数个完整向量.最终的向量必须使用未对齐的加载/存储指令,因为您不知道它的对齐方式.

在现代x86(英特尔自Nehalem,AMD自Bulldozer以来,请参见Agner Fog的指南)中,在运行时实际对齐的指针上的未对齐加载/存储指令没有任何损失.(与Core2不同,movdqu即使数据实际上是对齐的,也总是较慢.)IDK在ARM,MIPS或其他SIMD架构上的情况如何.

您可以使用相同的想法来处理可能未对齐的第一个向量(如果它实际上是对齐的则不重叠),然后使主循环使用对齐的向量.但是,有两个指针,一个可能相对于另一个指针未对齐.通常的建议(来自英特尔的优化手册)是对齐输出指针(您通过它存储).

您可以而且应该__restrict在两个指针上使用.没有理由不去,除非它实际上可以别名别的东西.如果我只打算做一个,我会在输出指针上使用它,但这两个都很重要.