AVX2字节用uint16索引收集到__m256i中

变化的偏移量

一个大问题是gcc(旧的或新的)只为当前的函数实现生成awful code：

lea r10,[rsp+8]
  and rsp,-32
  push QWORD PTR [r10-8]
  push rbp
  mov rbp,rsp
  push r15
  push r14
  push r13
  push r12
  push r10
  push rbx
  sub rsp,40
  movzx eax,WORD PTR [rsi+40]
  movzx r14d,WORD PTR [rsi+60]
  movzx r12d,WORD PTR [rsi+56]
  movzx ecx,WORD PTR [rsi+44]
  movzx r15d,WORD PTR [rsi+62]
  movzx r13d,WORD PTR [rsi+58]
  mov QWORD PTR [rbp-56],rax
  movzx eax,WORD PTR [rsi+38]
  movzx ebx,WORD PTR [rsi+54]
  movzx r11d,WORD PTR [rsi+52]
  movzx r10d,WORD PTR [rsi+50]
  movzx r9d,WORD PTR [rsi+48]
  movzx r8d,WORD PTR [rsi+46]
  mov QWORD PTR [rbp-64],WORD PTR [rsi+36]
  movzx edx,WORD PTR [rsi+42]
  mov QWORD PTR [rbp-72],WORD PTR [rsi+34]
  mov QWORD PTR [rbp-80],WORD PTR [rsi+32]
  mov QWORD PTR [rbp-88],WORD PTR [rsi+30]
  movzx r15d,BYTE PTR [rdi+r15]
  mov QWORD PTR [rbp-96],WORD PTR [rsi+28]
  vmovd xmm2,r15d
  vpinsrb xmm2,xmm2,BYTE PTR [rdi+r14],1
  mov QWORD PTR [rbp-104],WORD PTR [rsi+26]
  mov QWORD PTR [rbp-112],WORD PTR [rsi+24]
  mov QWORD PTR [rbp-120],WORD PTR [rsi+22]
  mov QWORD PTR [rbp-128],WORD PTR [rsi+20]
  mov QWORD PTR [rbp-136],WORD PTR [rsi+18]
  mov QWORD PTR [rbp-144],WORD PTR [rsi+16]
  mov QWORD PTR [rbp-152],WORD PTR [rsi+14]
  mov QWORD PTR [rbp-160],WORD PTR [rsi+12]
  mov QWORD PTR [rbp-168],WORD PTR [rsi+10]
  mov QWORD PTR [rbp-176],WORD PTR [rsi+8]
  mov QWORD PTR [rbp-184],WORD PTR [rsi+6]
  mov QWORD PTR [rbp-192],WORD PTR [rsi+4]
  mov QWORD PTR [rbp-200],WORD PTR [rsi+2]
  movzx esi,WORD PTR [rsi]
  movzx r13d,BYTE PTR [rdi+r13]
  movzx r8d,BYTE PTR [rdi+r8]
  movzx edx,BYTE PTR [rdi+rdx]
  movzx ebx,BYTE PTR [rdi+rbx]
  movzx r10d,BYTE PTR [rdi+r10]
  vmovd xmm7,r13d
  vmovd xmm1,r8d
  vpinsrb xmm1,xmm1,BYTE PTR [rdi+rcx],1
  mov rcx,QWORD PTR [rbp-56]
  vmovd xmm5,edx
  vmovd xmm3,ebx
  mov rbx,QWORD PTR [rbp-72]
  vmovd xmm6,r10d
  vpinsrb xmm7,xmm7,BYTE PTR [rdi+r12],1
  vpinsrb xmm5,xmm5,QWORD PTR [rbp-64]
  vpinsrb xmm6,xmm6,BYTE PTR [rdi+r9],1
  vpinsrb xmm3,xmm3,BYTE PTR [rdi+r11],1
  vpunpcklwd xmm2,xmm7
  movzx edx,BYTE PTR [rdi+rcx]
  mov rcx,QWORD PTR [rbp-80]
  vpunpcklwd xmm1,xmm5
  vpunpcklwd xmm3,xmm6
  vmovd xmm0,edx
  movzx edx,QWORD PTR [rbp-96]
  vpunpckldq xmm2,xmm3
  vpinsrb xmm0,xmm0,BYTE PTR [rdi+rbx],1
  mov rbx,QWORD PTR [rbp-88]
  vmovd xmm4,QWORD PTR [rbp-112]
  vpinsrb xmm4,xmm4,QWORD PTR [rbp-104]
  vpunpcklwd xmm0,xmm4
  vpunpckldq xmm0,xmm0
  vmovd xmm1,BYTE PTR [rdi+rcx]
  vpinsrb xmm1,QWORD PTR [rbp-128]
  mov rbx,QWORD PTR [rbp-120]
  vpunpcklqdq xmm0,xmm0
  vmovd xmm8,BYTE PTR [rdi+rcx]
  vpinsrb xmm8,xmm8,QWORD PTR [rbp-144]
  mov rbx,QWORD PTR [rbp-136]
  vmovd xmm4,edx
  vpunpcklwd xmm1,xmm8
  vpinsrb xmm4,1
  movzx edx,BYTE PTR [rdi+rcx]
  mov rbx,QWORD PTR [rbp-152]
  mov rcx,QWORD PTR [rbp-160]
  vmovd xmm7,edx
  movzx eax,BYTE PTR [rdi+rax]
  movzx edx,BYTE PTR [rdi+rcx]
  vpinsrb xmm7,QWORD PTR [rbp-176]
  mov rbx,QWORD PTR [rbp-168]
  vmovd xmm5,eax
  vmovd xmm2,edx
  vpinsrb xmm5,BYTE PTR [rdi+rsi],1
  vpunpcklwd xmm4,BYTE PTR [rdi+rcx]
  vpinsrb xmm2,1
  vpunpckldq xmm1,xmm4
  mov rbx,QWORD PTR [rbp-184]
  mov rcx,QWORD PTR [rbp-192]
  vmovd xmm6,BYTE PTR [rdi+rcx]
  vpinsrb xmm6,QWORD PTR [rbp-200]
  vmovd xmm3,edx
  vpunpcklwd xmm2,xmm6
  vpinsrb xmm3,1
  add rsp,40
  vpunpcklwd xmm3,xmm5
  vpunpckldq xmm2,xmm3
  pop rbx
  pop r10
  vpunpcklqdq xmm1,xmm2
  pop r12
  pop r13
  vinserti128 ymm0,ymm0,0x1
  pop r14
  pop r15
  pop rbp
  lea rsp,[r10-8]
  ret

基本上它试图完成前面偏移的所有读取,并且只是耗尽寄存器,所以它开始溢出一些然后继续溢出的狂欢,它只是读取大部分16位元素的偏移然后立即将它们(作为64位零扩展值)立即存储到堆栈中.本质上,它将大部分偏移数组(没有扩展为64位)复制到任何目的：它稍后读取溢出值,它当然只能从偏移读取.

在您使用的旧4.9.2版本以及最近的7.2版本中,同样可怕的代码也很明显.

icc和clang都没有任何这样的问题 – 它们都生成几乎相同的非常合理的代码,只需使用movzx从每个偏移位置读取一次,然后使用vpinsrb插入字节,并根据刚读取的偏移量使用内存源操作数：

gather256(char*,unsigned short*): # @gather256(char*,unsigned short*)
  movzx eax,word ptr [rsi + 30]
  movzx eax,byte ptr [rdi + rax]
  vmovd xmm0,eax
  movzx eax,word ptr [rsi + 28]
  vpinsrb xmm0,byte ptr [rdi + rax],1
  movzx eax,word ptr [rsi + 26]
  vpinsrb xmm0,2
  movzx eax,word ptr [rsi + 24]
  ...
  vpinsrb xmm0,14
  movzx eax,word ptr [rsi]
  vpinsrb xmm0,15
  movzx eax,word ptr [rsi + 62]
  movzx eax,byte ptr [rdi + rax]
  vmovd xmm1,word ptr [rsi + 60]
  vpinsrb xmm1,word ptr [rsi + 58]
  vpinsrb xmm1,word ptr [rsi + 56]
  vpinsrb xmm1,3
  movzx eax,word ptr [rsi + 54]
  vpinsrb xmm1,4
  movzx eax,word ptr [rsi + 52]
  ...
  movzx eax,word ptr [rsi + 32]
  vpinsrb xmm1,15
  vinserti128 ymm0,ymm1,1
  ret

非常好. vinserti128两个xmm向量一起有一小部分额外开销,每个向量都有一半的结果,显然是因为vpinserb不能写入高128位.似乎在现代的uarchs上,你正在使用它,这将同时瓶颈2个读取端口和端口5(shuffle)每个周期1个元素.因此,这可能会有大约每32个周期1的吞吐量,并且延迟接近32个周期(主要的依赖链是通过正在进行的xmm寄存器接收pinrb但是列出的内存源延迟该指令的版本只有1个循环1.

我们能否在gcc上接近这32个性能？看来是这样.这是一种方法：

uint64_t gather64(char *array,uint16_t *offset) {
  uint64_t ret;
  char *p = (char *)&ret;
  p[0] = array[offset[0]];
  p[1] = array[offset[1]];
  p[2] = array[offset[2]];
  p[3] = array[offset[3]];
  p[4] = array[offset[4]];
  p[5] = array[offset[5]];
  p[6] = array[offset[6]];
  p[7] = array[offset[7]];
  return ret;
}

__m256i gather256_gcc(char *array,uint16_t *offset) {

  return _mm256_set_epi64x(
    gather64(array,offset),gather64(array +  8,offset + 8),gather64(array + 16,offset + 16),gather64(array + 24,offset + 24)
  );
}

这里我们依靠堆栈上的临时数组一次从数组中收集8个元素,然后我们将其用作_mm256_set_epi64x的输入.总的来说,每8字节元素使用2个加载和1个存储,每个64位元素使用几个额外的指令,因此每个元素吞吐量应该接近1个周期2.

它在gcc中生成“预期”内联code：

gather256_gcc(char*,unsigned short*):
  lea r10,rsp
  push r10
  movzx eax,WORD PTR [rsi+48]
  movzx eax,BYTE PTR [rdi+24+rax]
  mov BYTE PTR [rbp-24],al
  movzx eax,WORD PTR [rsi+50]
  movzx eax,BYTE PTR [rdi+24+rax]
  mov BYTE PTR [rbp-23],WORD PTR [rsi+52]
  movzx eax,BYTE PTR [rdi+24+rax]
  mov BYTE PTR [rbp-22],al
  ...
  movzx eax,WORD PTR [rsi+62]
  movzx eax,BYTE PTR [rdi+24+rax]
  mov BYTE PTR [rbp-17],WORD PTR [rsi+32]
  vmovq xmm0,QWORD PTR [rbp-24]
  movzx eax,BYTE PTR [rdi+16+rax]
  movzx edx,WORD PTR [rsi+16]
  mov BYTE PTR [rbp-24],WORD PTR [rsi+34]
  movzx edx,BYTE PTR [rdi+8+rdx]
  movzx eax,BYTE PTR [rdi+16+rax]
  mov BYTE PTR [rbp-23],WORD PTR [rsi+46]
  movzx eax,BYTE PTR [rdi+16+rax]
  mov BYTE PTR [rbp-17],al
  mov rax,QWORD PTR [rbp-24]
  mov BYTE PTR [rbp-24],dl
  movzx edx,WORD PTR [rsi+18]
  vpinsrq xmm0,rax,BYTE PTR [rdi+8+rdx]
  mov BYTE PTR [rbp-23],WORD PTR [rsi+20]
  movzx edx,BYTE PTR [rdi+8+rdx]
  mov BYTE PTR [rbp-22],WORD PTR [rsi+22]
  movzx edx,BYTE PTR [rdi+8+rdx]
  mov BYTE PTR [rbp-21],WORD PTR [rsi+24]
  movzx edx,BYTE PTR [rdi+8+rdx]
  mov BYTE PTR [rbp-20],WORD PTR [rsi+26]
  movzx edx,BYTE PTR [rdi+8+rdx]
  mov BYTE PTR [rbp-19],WORD PTR [rsi+28]
  movzx edx,BYTE PTR [rdi+8+rdx]
  mov BYTE PTR [rbp-18],WORD PTR [rsi+30]
  movzx edx,BYTE PTR [rdi+8+rdx]
  mov BYTE PTR [rbp-17],WORD PTR [rsi]
  vmovq xmm1,QWORD PTR [rbp-24]
  movzx edx,BYTE PTR [rdi+rdx]
  mov BYTE PTR [rbp-24],WORD PTR [rsi+2]
  movzx edx,BYTE PTR [rdi+rdx]
  mov BYTE PTR [rbp-23],WORD PTR [rsi+4]
  movzx edx,BYTE PTR [rdi+rdx]
  mov BYTE PTR [rbp-22],dl
  ...
  movzx edx,WORD PTR [rsi+12]
  movzx edx,BYTE PTR [rdi+rdx]
  mov BYTE PTR [rbp-18],WORD PTR [rsi+14]
  movzx edx,BYTE PTR [rdi+rdx]
  mov BYTE PTR [rbp-17],dl
  vpinsrq xmm1,QWORD PTR [rbp-24],1
  vinserti128 ymm0,0x1
  pop r10
  pop rbp
  lea rsp,[r10-8]
  ret

当尝试读取堆栈缓冲区时,这种方法将遭受4(非依赖)存储转发停顿,这将使延迟稍微差于32个周期,可能在40年代中期(如果你认为它是最后一个停顿将是一个没有隐藏的).您也可以删除gather64函数并在32字节缓冲区中展开整个事物,最后只有一个加载.这导致只有一个停顿,并且摆脱了将每个64位值一次加载到结果中的小开销,但总体效果可能更差,因为较大的负载似乎有时会遭受较大的转发停顿.

我很确定你可以提出更好的方法.例如,你可以在内在函数中写出clang和icc使用的vpinsrb方法的“长手”.这很简单,gcc应该做对.

重复偏移

如果对多个不同的阵列输入重复使用偏移数组怎么样？

我们可以看一下预处理偏移数组,以便我们的核心负载循环更快.

一种可行的方法是使用vgatherdd有效地加载元素而不会在端口5上出现瓶颈以进行混洗.我们也可以在单个256位加载中加载整个聚集索引向量.不幸的是,最细粒度的vpgather是vpgatherdd,它使用32位偏移加载8个32位元素.所以我们需要4个这样的集合得到所有32个字节元素,然后需要以某种方式混合生成的向量.

实际上,我们可以通过交错和调整偏移来避免组合结果数组的大部分成本,以便每个32位值中的“目标”字节实际上是其正确的最终位置.因此,您最终得到4个256位向量,每个向量具有您想要的8个字节,位于正确的位置,以及您不想要的24个字节.你可以将两对矢量一起vpblend,然后将这些结果一起vpblendb,总共3个端口5 uop(必须有更好的方法来进行这种减少？).

将它们加在一起,我得到类似的东西：

> 4个movups加载4个vpgatherdd索引regs(可以提升)
> 4 vpgatherdd
> 2 vpblendw(4结果 – > 2)
> 1个movups加载vpblendb掩码(可以悬挂)
> 1 vpblendb(2结果 – > 1)

除了vpgatherdds之外,它看起来大概有9个uop,其中3个进入端口5,因此在该端口上有3个循环瓶颈或者如果没有瓶颈则大约2.25个循环(因为vpgatherdd可能不使用端口5).在Broadwell上,vpgather系列比Haswell有了很大的改进,但是对于vpgatherdd,每个元素仍然需要大约0.9个周期,所以那里大约有29个周期.所以我们回到我们开始的地方,大约32个周期.

不过,还有一些希望：

>每个元素0.9个循环用于大多数纯vpgatherdd活动.也许然后混合代码或多或少是免费的,我们大约有29个循环(实际上,移动仍然会与聚集竞争).
> vpgatherdd在Skylake中再次变得更好,每个元素大约0.6个周期,因此当您将硬件升级到Skylake时,这个策略将开始显着帮助. (并且策略可能会比AVX512BW的vpinsrb稍微提前一点,其中带有k寄存器掩码的字节混合是有效的,而vpgatherdd zmm每元素收集吞吐量略高于ymm(InstLatx64).)
>预处理使您有机会检查是否从阵列中读取重复元素.在这种情况下,您可以减少收集的数量.例如,如果偏移中只有一半的元素是唯一的,则只能进行两次收集来收集16个元素,然后pshufb注册以根据需要复制元素. “减少”必须更加通用,但它实际上看起来并不昂贵(并且可能更便宜),因为pshufb在大部分工作中都很普遍.

扩展最后一个想法：您将在运行时调度到一个知道如何进行1,2,3或4次收集的例程,具体取决于需要多少元素.这是相当量化的,但是你可以总是以更细粒度的方式使用标量负载(或者使用更大元素的集合,这些更快)在这些截止点之间进行调度.你很快就会收益递减.

你甚至可以扩展它来处理附近的元素 – 毕竟,你抓住4个字节来获取一个字节：所以如果这3个浪费的字节中的任何一个实际上是另一个使用过的偏移值,那么你几乎可以免费得到它.现在,这需要一个更普遍的减少阶段,但似乎pshufb仍然会做繁重的工作,大部分的努力工作仅限于预处理.

1这是少数SSE / AVX指令之一,其中指令的存储器源形式比reg-reg形式更有效：reg-reg形式在端口5上需要2 uop,这限制了吞吐量每个周期0.5,并给它一个2的延迟.显然,内存加载路径避免了端口5上需要的一个混洗/混合.vpbroadcastd / q也是这样.

2每个周期有两个负载和一个存储器,这将运行得非常接近最大理论性能的不规则边缘：它最大化L1操作吞吐量,这通常会导致打嗝：例如,可能没有任何备用周期从L2接受传入的缓存行.