带任意偏移量的位串高效相等性测试方案优化问询

场景与问题 #

我拥有超过10^7个令牌序列，每个令牌仅能取4种可能值。为适配内存，将每个令牌用2位编码（1字节可存储4个令牌），替代每个令牌存为char、序列用std::string的方式，最终序列存储在char数组中。

需求是测试两个令牌序列的任意子序列是否完全相等：子序列可从任意偏移开始，长度通常在10至30个令牌之间，且两个子序列长度相同。

当前采用分块比较方案（将最多32个令牌复制到uint64_t再逐块比较），但实际运行速度比std::string的operator==慢两倍以上。尝试过std::memcmp，但子序列可能起始于字节内部（虽为2位的倍数）无法直接使用；boost::dynamic_bitset存储格式匹配，但不支持相等性测试。

优化方案 #

1. 核心优化：替换循环内的低效运算 #

原代码循环中的除法、取模运算（pos / TokenPerBlock、pos % TokenPerBlock）是性能瓶颈，可直接用位运算替代（因为TokenPerBlock=4，是2的幂）：

• pos / 4 等价于 pos >> 2
• pos % 4 等价于 pos & 3

同时，避免循环内的分支判断（原代码中i % TokenPerCompareBlock == 0的分支），利用子序列长度短（10-30个令牌）的特点，直接将所有令牌加载到单个uint64_t中一次性比较。

2. 优化后的代码示例 #

#include <climits>
#include <cstdint>

using Block = char;
constexpr int BitsPerToken = 2;
constexpr int TokenPerBlock = sizeof(Block) * CHAR_BIT / BitsPerToken; // 固定为4
constexpr int TokenMask = TokenPerBlock - 1; // 固定为3

// 位运算优化：从序列的指定位置获取令牌
inline uint8_t getToken(const Block* seq, int pos) noexcept {
    const int blockIdx = pos >> 2;    // 替代 pos / 4
    const int tokenIdx = pos & TokenMask; // 替代 pos % 4
    return (seq[blockIdx] >> (tokenIdx * BitsPerToken)) & 0x03;
}

bool seqEqual(const Block* seqA, int startA, int endA, 
              const Block* seqB, int startB, int endB) noexcept {
    const int len = endA - startA;
    if (len != endB - startB) return false; // 先快速判断长度是否一致

    // 利用uint64_t一次性存储最多32个令牌（覆盖10-30的长度范围）
    uint64_t valA = 0, valB = 0;
    for (int i = 0; i < len; ++i) {
        valA |= static_cast<uint64_t>(getToken(seqA, startA + i)) << (i * BitsPerToken);
        valB |= static_cast<uint64_t>(getToken(seqB, startB + i)) << (i * BitsPerToken);
    }
    return valA == valB;
}

3. 进阶优化：SIMD指令加速 #

如果编译器支持AVX2或NEON等SIMD指令，可以批量加载多字节数据，通过移位和掩码操作对齐两个子序列的起始位，再逐块比较。例如用AVX2的_mm256_loadu_si256一次性加载32字节（128个令牌），对齐后用_mm256_cmpeq_epi8进行批量比较，能进一步提升大序列的比较效率。

原代码慢的原因 #

• 循环内的除法、取模运算延迟远高于位运算；
• 分支判断（i % TokenPerCompareBlock == 0）可能导致分支预测失败，带来额外开销；
• 使用curA +=而非curA |=，加法可能产生不必要的进位运算，而令牌是2位存储，或操作更直接高效。

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