非对齐比特流的快速逐位比较优化方案咨询

我有两个比特流A[1..a]和B[1..b]（a始终小于b），给定B中的索引c，需要判断A是否匹配B[c..c+a-1]（假设c+a-1<=b恒成立）。由于A与B[c..c+a-1]不一定是字节对齐的，无法直接使用memcmp，因此我实现了一个自定义逐位比较的C++函数（代码如下），但该函数成为了应用的性能瓶颈（需在海量输入上反复执行）。现咨询是否存在更快的比较技术？我了解可使用SIMD指令，但认为因B以64位单元编码，提升效果有限。

额外细节：

• A通常较短（约20或30个64位单元），但也可能任意大（始终小于B）；
• 无法假设A的编码格式，可能为uint8_t、uint16_t、uint32_t或uint64_t，因此以void*传入函数；

#include<cstddef>
#include<cstdint>

struct bitstream{

    constexpr static uint8_t word_bits = 64;
    constexpr static uint8_t word_shift = 6;
    const static size_t masks[65];

    size_t *B;

    inline bool compare_chunk(const void* A, size_t a, size_t c)  {

        size_t n_words = a / word_bits; 
        size_t left = c & (word_bits - 1UL);
        size_t right = word_bits - left;
        size_t cell_i = c >> word_shift;

        auto tmp_in = reinterpret_cast<const size_t *>(A);
        size_t tmp_data;

        //shift every cell in B[c..c+a-1] to compare it against A
        for(size_t k=0; k < n_words - 1; k++){
            tmp_data = (B[cell_i] >> left) & masks[right];
            tmp_data |= (B[++cell_i] & masks[left]) << right;
            if(tmp_data != tmp_in[k]) return false;
        }

        size_t read_bits = (n_words - 1) << word_shift;
        return (tmp_in[n_words - 1] & masks[(a-read_bits)]) == read(c + read_bits, c+a-1);
    }

    inline size_t read(size_t i, size_t j) const{
         size_t cell_i = i >> word_shift;
         size_t i_pos = (i & (word_bits - 1UL));
         size_t cell_j = j >> word_shift;
         if(cell_i == cell_j){
             return (B[cell_i] >> i_pos) & masks[(j - i + 1UL)];
         }else{
             size_t right = word_bits-i_pos;
             size_t left = 1+(j & (word_bits - 1UL));
             return ((B[cell_j] & masks[left]) << right) | ((B[cell_i] >> i_pos) & masks[right]);
         }
    }
};

const size_t bitstream::masks[65]={0x0,
                                   0x1,0x3, 0x7,0xF,
                                   0x1F,0x3F, 0x7F,0xFF,
                                   0x1FF,0x3FF, 0x7FF,0xFFF,
                                   0x1FFF,0x3FFF, 0x7FFF,0xFFFF,
                                   0x1FFFF,0x3FFFF, 0x7FFFF,0xFFFFF,
                                   0x1FFFFF,0x3FFFFF, 0x7FFFFF,0xFFFFFF,
                                   0x1FFFFFF,0x3FFFFFF, 0x7FFFFFF,0xFFFFFFF,
                                   0x1FFFFFFF,0x3FFFFFFF, 0x7FFFFFFF,0xFFFFFFFF,
                                   0x1FFFFFFFF,0x3FFFFFFFF, 0x7FFFFFFFF,0xFFFFFFFFF,
                                   0x1FFFFFFFFF,0x3FFFFFFFFF, 0x7FFFFFFFFF,0xFFFFFFFFFF,
                                   0x1FFFFFFFFFF,0x3FFFFFFFFFF, 0x7FFFFFFFFFF,0xFFFFFFFFFFF,
                                   0x1FFFFFFFFFFF,0x3FFFFFFFFFFF, 0x7FFFFFFFFFFF,0xFFFFFFFFFFFF,
                                   0x1FFFFFFFFFFFF,0x3FFFFFFFFFFFF, 0x7FFFFFFFFFFFF,0xFFFFFFFFFFFFF,
                                   0x1FFFFFFFFFFFFF,0x3FFFFFFFFFFFFF, 0x7FFFFFFFFFFFFF,0xFFFFFFFFFFFFFF,
                                   0x1FFFFFFFFFFFFFF,0x3FFFFFFFFFFFFFF, 0x7FFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFF,
                                   0x1FFFFFFFFFFFFFFF,0x3FFFFFFFFFFFFFFF, 0x7FFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF}

1. 预转换A的格式 #

既然A的编码不确定但每次比较时固定，可以提前把A转换成和B一致的64位单元存储格式，同时预计算好A在0~63位所有偏移下的对齐后数据。后续和B比较时，直接用对应偏移的预计算版本对比，避免每次都做类型转换和移位操作。

2. 用SIMD指令批量加速 #

你对SIMD的效果判断有误——现代SIMD（如AVX-512、NEON）一次可处理8个64位整数。针对B的64位单元，可将移位合并后的B块加载到SIMD寄存器，和预计算好的A的SIMD版本做逐位比较，一次性完成多个单元的对比，大幅减少循环次数。

比如用AVX-512时，可通过_mm512_loadu_si512加载B的连续单元，用移位指令组合出对齐块，再用_mm512_cmpeq_epi64和A的预计算数据对比，最后用_mm512_test_epi64_mask快速判断是否存在不匹配单元。

3. 消除分支与减少内存访问 #

原代码中read函数的分支判断会影响流水线效率，可将分支逻辑替换为无分支位运算（比如用掩码合并跨单元比特）。同时预加载B的连续多单元到寄存器，减少重复的内存访问开销。

4. 前置快速过滤 #

对于较长的A，可先对比首尾部分比特（无需完全对齐），若这两部分不匹配直接返回false，跳过中间大量计算，减少无效操作。

5. 编译器优化加持 #

开启最高等级编译器优化（如-O3），给热点函数添加__attribute__((hot))标记，提示编译器做激进优化；同时将masks数组改为constexpr，让编译器直接将掩码值嵌入指令，避免数组访问开销。

内容的提问来源于stack exchange，提问作者AAA