通过 avx 指令向量化间接访问

Question

我最近被介绍了向量指令（理论上）并且对如何使用它们来加速我的应用程序感到兴奋。

我想改进的一个方面是一个非常热的循环：

__declspec(noinline) void pleaseVectorize(int* arr, int* someGlobalArray, int* output)
{
    for (int i = 0; i < 16; ++i)
    {
        auto someIndex = arr[i];
        output[i] = someGlobalArray[someIndex];
    }

    for (int i = 0; i < 16; ++i)
    {
         if (output[i] == 1)
         {
             return i;
         }
    }

    return -1;
}

但是，当然，所有 3 个主要编译器（msvc、gcc、clang）都拒绝对此进行矢量化。我可以理解为什么，但我想得到确认。

如果我必须手动矢量化它，它将是：

(1) VectorLoad "arr", 这带来了 16 个 4 字节整数，让我们说到 zmm0

(2) 16个内存从zmm0[0..3]指向的地址加载到zmm1[0..3]，从zmm0[4..7]指向的地址加载到zmm1[4..7]所以等等

(3)比较zmm0和zmm1

(4) 向量 popcnt 到输出中找出最高有效位并基本上除以 8 得到匹配的索引

首先，向量指令可以做这些事情吗？就像他们可以执行这种“收集”操作，即从指向 zmm0 的地址加载？

以下是 clang 生成的内容：

0000000000400530 <_Z5superPiS_S_>:
  400530:       48 63 07                movslq (%rdi),%rax
  400533:       8b 04 86                mov    (%rsi,%rax,4),%eax
  400536:       89 02                   mov    %eax,(%rdx)
  400538:       48 63 47 04             movslq 0x4(%rdi),%rax
  40053c:       8b 04 86                mov    (%rsi,%rax,4),%eax
  40053f:       89 42 04                mov    %eax,0x4(%rdx)
  400542:       48 63 47 08             movslq 0x8(%rdi),%rax
  400546:       8b 04 86                mov    (%rsi,%rax,4),%eax
  400549:       89 42 08                mov    %eax,0x8(%rdx)
  40054c:       48 63 47 0c             movslq 0xc(%rdi),%rax
  400550:       8b 04 86                mov    (%rsi,%rax,4),%eax
  400553:       89 42 0c                mov    %eax,0xc(%rdx)
  400556:       48 63 47 10             movslq 0x10(%rdi),%rax
  40055a:       8b 04 86                mov    (%rsi,%rax,4),%eax
  40055d:       89 42 10                mov    %eax,0x10(%rdx)
  400560:       48 63 47 14             movslq 0x14(%rdi),%rax
  400564:       8b 04 86                mov    (%rsi,%rax,4),%eax
  400567:       89 42 14                mov    %eax,0x14(%rdx)
  40056a:       48 63 47 18             movslq 0x18(%rdi),%rax
  40056e:       8b 04 86                mov    (%rsi,%rax,4),%eax
  400571:       89 42 18                mov    %eax,0x18(%rdx)
  400574:       48 63 47 1c             movslq 0x1c(%rdi),%rax
  400578:       8b 04 86                mov    (%rsi,%rax,4),%eax
  40057b:       89 42 1c                mov    %eax,0x1c(%rdx)
  40057e:       48 63 47 20             movslq 0x20(%rdi),%rax
  400582:       8b 04 86                mov    (%rsi,%rax,4),%eax
  400585:       89 42 20                mov    %eax,0x20(%rdx)
  400588:       48 63 47 24             movslq 0x24(%rdi),%rax
  40058c:       8b 04 86                mov    (%rsi,%rax,4),%eax
  40058f:       89 42 24                mov    %eax,0x24(%rdx)
  400592:       48 63 47 28             movslq 0x28(%rdi),%rax
  400596:       8b 04 86                mov    (%rsi,%rax,4),%eax
  400599:       89 42 28                mov    %eax,0x28(%rdx)
  40059c:       48 63 47 2c             movslq 0x2c(%rdi),%rax
  4005a0:       8b 04 86                mov    (%rsi,%rax,4),%eax
  4005a3:       89 42 2c                mov    %eax,0x2c(%rdx)
  4005a6:       48 63 47 30             movslq 0x30(%rdi),%rax
  4005aa:       8b 04 86                mov    (%rsi,%rax,4),%eax
  4005ad:       89 42 30                mov    %eax,0x30(%rdx)
  4005b0:       48 63 47 34             movslq 0x34(%rdi),%rax
  4005b4:       8b 04 86                mov    (%rsi,%rax,4),%eax
  4005b7:       89 42 34                mov    %eax,0x34(%rdx)
  4005ba:       48 63 47 38             movslq 0x38(%rdi),%rax
  4005be:       8b 04 86                mov    (%rsi,%rax,4),%eax
  4005c1:       89 42 38                mov    %eax,0x38(%rdx)
  4005c4:       48 63 47 3c             movslq 0x3c(%rdi),%rax
  4005c8:       8b 04 86                mov    (%rsi,%rax,4),%eax
  4005cb:       89 42 3c                mov    %eax,0x3c(%rdx)
  4005ce:       c3                      retq
  4005cf:       90                      nop

Answer 1

你的工作怎么会想法是接近的，除非你想有一个位扫描/找到一集位（86 BSF或TZCNT比较位的），而不是人口数（数位设置的）。

AVX2 / AVX512vpgatherdd确实使用了带符号的 32 位缩放索引向量。它几乎不值得在 Haswell 上使用，在 Broadwell 上改进，在 Skylake 上非常好。（http://agner.org/optimize/，并查看x86 标签 wiki中的其他链接，例如英特尔的优化手册，其中有一个关于收集性能的部分）。相比之下，SIMD 比较和位扫描非常便宜；单 uop 和完全流水线。

gcc8.1 可以自动矢量化您的集合，如果它可以证明您的输入不与您的output函数 arg重叠。内联后有时可能，但对于非内联版本，您可以使用int * __restrict output. 或者，如果您创建output一个本地临时文件而不是函数 arg。（一般规则：通过非_restrict指针存储通常会抑制自动向量化，特别是如果它char*可以为任何东西设置别名。）

gcc 和 clang 从不矢量化搜索循环；只有在进入循环之前可以计算行程计数的循环。但ICC 可以；它标收集并存储结果（即使output[]是本地，因此不会有这样做的运行功能的副作用），然后使用SIMD填充比较+位扫描。

__restrict版本的编译器输出。请注意，gcc8.1 和 ICC 在针对 Skylake-AVX512 进行调整时默认避免 512 位向量。512 位向量可以限制 max-turbo，并且在它们处于管道中时始终关闭端口 1 上的向量 ALU，因此使用 AVX512 或 AVX2 与 256 位向量是有意义的，以防万一大程序的一小部分。（编译器不知道这个函数在你的程序中是超级热的。）

如果 output[]是本地的，更好的代码生成策略可能是在收集时进行比较，因此早期命中会跳过其余的负载。完全标量的编译器（clang 和 MSVC）都错过了这种优化。事实上，它们甚至存储到本地数组，即使 clang 大多不会重新读取它（将结果保存在寄存器中）。在第一个循环内使用比较编写源代码将有助于获得更好的标量代码。（根据来自聚集的缓存未命中与来自非 SIMD 搜索的分支错误预测，标量可能是一个很好的策略。特别是如果前几个元素中的命中很常见。当前的聚集硬件无法利用来自于非 SIMD 搜索的多个元素相同的缓存线，因此硬限制仍然是每个时钟周期加载 2 个元素。

编译器可以将__restrict您的代码版本自动矢量化为这样的东西。（gcc 管理gather 部分，ICC 管理SIMD 比较部分）

;; Windows x64 calling convention: rcx,rdx, r8,r9
; but of course you'd actually inline this
; only uses ZMM16..31, so vzeroupper not required

vmovdqu32   zmm16, [rcx/arr]   ; You def. want to reach an alignment boundary if you can for ZMM loads, vmovdqa32 will enforce that

kxnorw      k1, k0,k0      ; k1 = -1.  k0 false dep is likely not a problem.
  ; optional: vpxord  xmm17, xmm17, xmm17   ; break merge-masking false dep
vpgatherdd  zmm17{k1}, [rdx + zmm16 * 4]    ; GlobalArray + scaled-vector-index
; sets k1 = 0 when done

vmovdqu32   [r8/output], zmm17

vpcmpd      k1, zmm17, zmm31, 0    ; 0->EQ.  Outside the loop, do zmm31=set1_epi32(1)
                                   ; k1 = compare bitmap
kortestw    k1, k1
jz         .not_found      ; early check for not-found

kmovw       edx, k1

           ; tzcnt doesn't have a false dep on the output on Skylake
           ; so no AVX512 CPUs need to worry about that HSW/BDW issue
tzcnt       eax, edx       ; bit-scan for the first (lowest-address) set element
                           ; input=0 produces output=32
      ; or avoid the branch and let 32 be the not-found return value.
      ; or do a branchless kortestw / cmov if -1 is directly useful without branching
ret

.not_found:
   mov eax, -1
   ret

您可以使用内在函数自己完成此操作：

英特尔的指令集参考手册（http://felixcloutier.com/x86/index.html 上的HTML 摘录）包括每条指令的 C/C++ 内在名称，或在https://software.intel.com/sites 中搜索它们/登陆页面/内在指南/

我将output类型更改为__m512i. 如果您没有手动矢量化调用者，您可以将其改回数组。 您肯定希望此函数内联。

#include <immintrin.h>

//__declspec(noinline)  // I *hope* this was just to see the stand-alone asm version
                        // but it means the output array can't optimize away at all

//static inline
int find_first_1(const int *__restrict arr, const int *__restrict someGlobalArray, __m512i *__restrict output)
{
    __m512i vindex = _mm512_load_si512(arr);
    __m512i gather = _mm512_i32gather_epi32(vindex, someGlobalArray, 4);  // indexing by 4-byte int
    *output = gather;  

    __mmask16 cmp = _mm512_cmpeq_epi32_mask(gather, _mm512_set1_epi32(1));
       // Intrinsics make masks freely convert to integer
       // even though it costs a `kmov` instruction either way.
    int onepos =  _tzcnt_u32(cmp);
    if (onepos >= 16){
        return -1;
    }
    return onepos;
}

所有 4 个 x86 编译器都产生与我建议的类似的 asm（在 Godbolt 编译器资源管理器中查看），但当然它们必须实际实现set1_epi32(1)向量常量，或者使用（广播）内存操作数。实际上铿锵使用{1to16}从比较恒定的广播负载： vpcmpeqd k0, zmm1, dword ptr [rip + .LCPI0_0]{1to16}。（当然，当内联到循环中时，他们会做出不同的选择。）其他人使用mov eax,1/ vpbroadcastd zmm0, eax。

gcc8.1 -O3 -march=skylake-avx512 有两个冗余mov eax, -1指令：一个kmov用于为聚集提供 a ，另一个用于返回值的东西。愚蠢的编译器应该保留它并为1.

他们都使用 zmm0..15 ，因此无法避免vzeroupper. （xmm16.31 不能通过 legacy-SSE 访问，因此如果您使用的唯一宽向量寄存器是 y/zmm16..31 ，则vzeroupper解决的 SSE/AVX 转换惩罚问题不存在）。vzeroupper 可能仍然存在微小的优势，例如当 ymm 或 zmm regs 的上半部分已知为零时更便宜的上下文切换（如果您的程序+库不包含 SSE 指令，使用 VZEROUPPER 有用吗？）。如果你无论如何都要使用它，没有理由避免 xmm0..15。

哦，在 Windows 调用约定中，xmm6..15 是保留调用的。（不是 ymm/zmm，只是低 128 位），所以如果 xmm0..5 regs 用完，zmm16..31 是一个不错的选择。