原理

字符查找

Looking for an index of an element in array via SIMD. A fast way
16个8位字符打包成128位__m128i ARR = _mm_setr_epi8(1,2,3...)
设置被比较数字的vector__m128i N = _mm_set1_epi8(3)
比较并得到按bit的mask，__m128i cmp = _mm_cmpeq_epi8(ARR, N); int mask = _mm_movemask_epi8(cmp);
_tzcnt_u32返回尾部最小有效零位的个数，也就是第一个满足条件的字符的位置

Bitwise MSB Radix Sort on AVX-512
基于bit的MSB基数排序，从高位开始每bit做比较像快排一样做左右划分，这样不需要额外的空间去做基数归类
simd排序有个麻烦的点是怎样搬动比较key之外的数据，这里的做法是看成kv并打包在一起，如果v是64位指针kv就是128位，512位的vector可以放4个，如果v是32位的位置kv是64位放8个
每次拿vector中所有key中的一位进行比较得到一个mask， testAndCount(bitMaskVec, keyPayload, sortBits, popcnt)
然后关键点是mask_compressstoreu这个指令，通过sortBits，把keyPayload符合条件的位对应的数据写到d + writePos[0]，这样就实现了搬动数据
但是感觉一位一位排序似乎效率有点低，把simd的优势又还回去了？

Bitonic_sorter
双调排序，适合并行度比较大的场景，双调序列是先单调递增然后单调递减的序列，将双调序列等分然后两个子序列一一比较得到min和max序列又都是双调序列。排序算法是先从原子一级级组成一整个双调序列，然后再一级级拆散最后就是排序好的
复杂度是n*logn^2，但并行度很好
simd算法详见A Novel Hybrid Quicksort Algorithm Vectorized using AVX-512 on Intel Skylake

Fast Quicksort Implementation Using AVX Instructions
假设一次操作4个数，VBROADCASTSS (pivot), P (设置pivot)
VMOVDQU (in), D (取数组成向量)
VPCMPGTD D, P, C (向量和pivot比较)
VMOVMSKPS C, r (生成按bit的mask)
SHL $4, r VPERMILPS permTableLesser(, r), D, L VPERMILPS permTableGreater(, r), D, G (用mask查表得到两个向量内位置list，然后用vpermilps指令从源向量取数到目标寄存器，完成了partition这一步)
permTableLesser这种表是预先构建好的，因为mask寄存器只有16种可能对应的位置都是确定的
POPCNT r, r0 MOV $4, r1 SUB r0, r1 (计算partition后两边各有几个数)
VMOVDQU L, (Lptr) VMOVDQU G, (Gptr) (寄存器写回内存比如数组里面)
LEA (Lptr, r0, 4), Lptr LEA (Gptr, r1, 4), Gptr (移动数组指针)
256位的AVX2增加了VPGATHERQQ指令，这样源向量里面可以存kv然后VPGATHERQQ只取出key来比较
AVX512增加了VCOMPRESSPS指令，直接通过mask写无需查表
存kv始终是个痛点，放一起会减少向量里面的记录数，A Novel Hybrid Quicksort Algorithm Vectorized using AVX-512 on Intel Skylake 给的一个解决办法是value单独放一个等长的数组，根据mask partition的时候也给value数组操作一次