基于SIMD优化bool数组指针解引用及NAND运算的技术咨询

问题背景 #

给定一个bool类型的位向量T，以及两个与T尺寸相同的索引向量Aidx和Bidx（存储T中的元素索引），需通过以下算法生成新向量T'：

A = T[Aidx]
B = T[Bidx]
T' = A NAND B

C++实现代码 #

#include <cstddef>

#define align 128
#define vsize 1024

struct alignas(align) vec_friendly_idx {
    const static std::size_t size = vsize;
    unsigned short v[size];
};

struct alignas(align) vec_friendly_bool {
    const static std::size_t size = vsize;
    unsigned char v[size];
};

void vecadd3(vec_friendly_bool& __restrict t, const vec_friendly_idx& aidx, const vec_friendly_idx& bidx, vec_friendly_bool& __restrict a, vec_friendly_bool& __restrict b) {
    for (std::size_t i = 0; i != vec_friendly_idx::size; i++) {
        a.v[i] = t.v[aidx.v[i]];
        b.v[i] = t.v[bidx.v[i]];
    }

    for (std::size_t i = 0; i != vec_friendly_idx::size; i++) {
        t.v[i] = !(a.v[i] & b.v[i]);
    }
}

GCC生成的ARM64汇编代码 #

mov     x5, 0
.L2:
        ldrh    w7, [x1, x5, lsl 1]
        ldrh    w6, [x2, x5, lsl 1]
        ldrb    w7, [x0, w7, sxtw]
        ldrb    w6, [x0, w6, sxtw]
        strb    w7, [x3, x5]
        strb    w6, [x4, x5]
        add     x5, x5, 1
        cmp     x5, 1024
        bne     .L2
        movi    v2.16b, 0x1
        mov     x1, 0
.L3:
        ldr     q0, [x4, x1]
        ldr     q1, [x3, x1]
        and     v0.16b, v0.16b, v1.16b
        cmeq    v0.16b, v0.16b, #0
        and     v0.16b, v2.16b, v0.16b
        str     q0, [x0, x1]
        add     x1, x1, 16
        cmp     x1, 1024
        bne     .L3
        ret

核心问题解答 #

Q1：请问有哪些进一步优化该算法的思路？ #

• 向量化索引读取：利用x86-64的AVX2/AVX-512 VGATHER指令、ARM64的NEON GATHER指令（ARMv8.2+）批量读取T[Aidx]和T[Bidx]，替代标量循环，大幅减少迭代次数。
• 合并循环减少内存开销：将当前的两个循环合并为一个，读取一组索引后直接计算NAND并写入T'，避免额外存储A、B数组，节省内存带宽与缓存占用。
• 位打包优化存储：把T的bool值打包为位格式（比如用uint64_t数组，每个元素存64位），降低内存占用、提升缓存命中率，同时NAND运算可通过位操作批量处理（一次处理64/256位）。
• 简化NAND指令序列：NAND等价于~(A & B)，可直接用SIMD的按位与+取反指令替代当前汇编中的and + cmeq + and组合，减少指令数。
• 循环展开：手动展开索引读取与计算循环，降低分支预测开销，提升流水线效率。
• 匹配平台对齐要求：根据目标平台SIMD寄存器宽度调整数据对齐（比如x86-64 AVX2用256位对齐、AVX-512用512位对齐），避免未对齐内存访问的性能损耗。

拓展问题解答 #

Q2：NAND计算已被向量化（仅需64次迭代），但向量索引未被向量化（需1024次迭代）。我原以为gather-collect指令对此会有帮助，是否正确？ #

完全正确。当前的标量索引读取循环是主要性能瓶颈之一，gather指令正是为非连续分散内存读取场景设计的：

• x86-64平台：AVX2的VGATHERDPS/VGATHERQPD、AVX-512的VGATHER系列指令可一次性将多个分散的内存元素加载到SIMD寄存器；
• ARM64平台：ARMv8.2-A及以上的NEON支持GATHER指令（如LD1 {v0.16b}, [x0, v1.16h, sxtw]），可单次从T中读取16个由索引指定的字节，直接替代标量循环的多次ldrb操作；
• 注意事项：gather指令的性能依赖索引的局部性，若索引分散度高会有一定延迟，但相比标量循环仍能带来显著提升；需确保编译器生成gather指令，必要时可手动使用SIMD intrinsics（如x86的_mm256_i32gather_epi8、ARM的vld1q_gather_u8）。

Q3：我考虑过将T中的位打包以加速NAND运算（当前每个字节仅用1位，7位冗余），但担心打包/解包的开销会抵消性能提升，是否如此？ #

是否抵消性能提升取决于T的访问模式和运算规模：

• 收益点：位打包后T的内存占用降至原来的1/8，缓存命中率会大幅提升，尤其是T尺寸较大时，能减少缓存缺失带来的高额延迟；NAND运算可批量处理64/256位数据，单条指令完成多个位的运算，效率远高于逐字节处理。
• 开销点：打包/解包确实需要额外指令（如从打包数组中提取指定位：(T_packed[idx/64] >> (idx%64)) & 1），但如果算法是高频执行的核心逻辑，或后续运算可直接在打包数据上进行，打包的收益会远超过解包开销。
• 建议：若该算法是核心性能热点，建议做原型测试，对比打包前后的执行时间与缓存缺失率（可用perf工具统计）；结合gather指令时，可将索引转换为打包后的位偏移，直接从打包数组中读取对应位，减少解包步骤。

内容的提问来源于stack exchange，提问作者Hugo Sereno Ferreira