基于SIMD优化ASCII字符串7位二进制Blob编码的技术疑问

我希望将ASCII字符串编码为7位二进制Blob，以此节省12.5%的内存占用，同时追求最快的编码速度——也就是处理大字符串时的延迟最小化。

普通C实现 #

void ascii_pack(const char* ascii, size_t len, uint8_t* bin) {
  uint64_t val;
  const char* end = ascii + len;

  while (ascii + 8 <= end) {
    memcpy(&val, ascii, 8);
    uint64_t dest = (val & 0xFF);

    // 编译器会自动展开循环
    for (unsigned i = 1; i <= 7; ++i) {
      val >>= 1;
      dest |= (val & (0x7FUL << 7 * i));
    }
    memcpy(bin, &dest, 7);
    bin += 7;
    ascii += 8;
  }

  // 收尾处理：不足8字节时直接复制，不进行打包
  while (ascii < end) {
    *bin++ = *ascii++;
  }
}

SSE2 SIMD实现及疑问 #

我尝试用SSE2指令集加速该算法，写出了如下实现，现在有两个疑问：

1. 能否优化实现中的顺序内部循环？
2. 处理大字符串时，这个实现能否提升吞吐量？

// 算法逻辑：并行处理两个uint64_t整数，和ascii_pack的单整数逻辑一致
void ascii_pack_simd(const char* ascii, size_t len, uint8_t* bin) {
  __m128i val;

  __m128i mask = _mm_set1_epi64x(0x7FU);  // 两个uint64_t掩码

  // 循环中每次加载16字节，但会额外预留16字节空间
  // 因为我们会向bin写入完整的16字节而非14字节，为避免越界写，提前一轮结束循环
  const char* end = ascii + len - 32;
  while (ascii <= end) {
    val = _mm_loadu_si128(reinterpret_cast<const __m128i*>(ascii));
    __m128i dest = _mm_and_si128(val, mask);

    // 编译器会自动展开循环
    for (unsigned i = 1; i <= 7; ++i) {
      val = _mm_srli_epi64(val, 1);                          // 同时右移两个整数
      __m128i shmask = _mm_slli_epi64(mask, 7 * i);    // 生成对应位的掩码
      dest = _mm_or_si128(dest, _mm_and_si128(val, shmask));  // 合并当前7位数据
    }

    // dest中包含两个7字节的打包结果，复制到bin中
    _mm_storeu_si128(reinterpret_cast<__m128i*>(bin), dest);
    memmove(bin + 7, bin + 8, 7);
    bin += 14;
    ascii += 16;
  }

  end += 32;  // 恢复end的原始位置
  DCHECK(ascii < end);
  ascii_pack(ascii, end - ascii, bin);
}

问题解答 #

1. 内部顺序循环的优化方案 #

当前内部循环的核心是逐次右移并提取7位数据，完全可以用无循环的SIMD指令组合替代，消除循环带来的分支和迭代开销：

• 预先计算好所有需要的移位后的掩码，不需要在循环中每次计算_mm_slli_epi64(mask, 7*i)
• 一次性生成所有右移1到7位的val副本，然后分别掩码后合并到dest中

示例优化后的核心代码片段：

__m128i val = _mm_loadu_si128(...);
__m128i dest = _mm_and_si128(val, mask);

// 预生成所有右移后的val版本
__m128i val_r1 = _mm_srli_epi64(val, 1);
__m128i val_r2 = _mm_srli_epi64(val, 2);
__m128i val_r3 = _mm_srli_epi64(val, 3);
__m128i val_r4 = _mm_srli_epi64(val, 4);
__m128i val_r5 = _mm_srli_epi64(val, 5);
__m128i val_r6 = _mm_srli_epi64(val, 6);
__m128i val_r7 = _mm_srli_epi64(val, 7);

// 预计算所有掩码
__m128i mask_7 = _mm_slli_epi64(mask, 7);
__m128i mask_14 = _mm_slli_epi64(mask, 14);
__m128i mask_21 = _mm_slli_epi64(mask, 21);
__m128i mask_28 = _mm_slli_epi64(mask, 28);
__m128i mask_35 = _mm_slli_epi64(mask, 35);
__m128i mask_42 = _mm_slli_epi64(mask, 42);
__m128i mask_49 = _mm_slli_epi64(mask, 49);

// 一次性合并所有位段
dest = _mm_or_si128(dest, _mm_and_si128(val_r1, mask_7));
dest = _mm_or_si128(dest, _mm_and_si128(val_r2, mask_14));
dest = _mm_or_si128(dest, _mm_and_si128(val_r3, mask_21));
dest = _mm_or_si128(dest, _mm_and_si128(val_r4, mask_28));
dest = _mm_or_si128(dest, _mm_and_si128(val_r5, mask_35));
dest = _mm_or_si128(dest, _mm_and_si128(val_r6, mask_42));
dest = _mm_or_si128(dest, _mm_and_si128(val_r7, mask_49));

这种方式完全消除了循环，所有操作都是并行的SIMD指令，能大幅降低延迟，同时编译器可以更好地调度指令。

另外，当前实现中memmove(bin +7, bin +8,7)的开销也可以优化：不需要先写入16字节再移动，而是直接将dest中的两个7字节块分别写入到bin和bin+7的位置，避免内存拷贝操作。例如：

// 直接提取低7字节和高7字节（注意SIMD寄存器的字节顺序）
_mm_storel_epi64(reinterpret_cast<__m128i*>(bin), dest); // 存低8字节，我们只需要前7个
_mm_storeh_epi64(reinterpret_cast<__m128i*>(bin+7), dest); // 存高8字节，只需要前7个

2. 大字符串场景下的吞吐量提升潜力 #

当前的SSE2实现理论上能提升吞吐量，但现有版本的瓶颈会限制实际收益：

• 潜力：SSE2同时处理两个64位块，原本普通实现每处理8字节输出7字节，SIMD版本每处理16字节输出14字节，理论上吞吐量可以接近2倍。
• 现有瓶颈：
  1. 内部循环的迭代开销（即使编译器展开，依然有依赖链：每次右移依赖上一次的val值）
  2. memmove操作带来的额外内存读写开销，这会严重拖慢速度
  3. 内存访问的对齐问题：_mm_loadu_si128和_mm_storeu_si128是不对齐访问，相比对齐访问会有轻微开销，若能保证输入输出内存对齐，可换成_mm_load_si128和_mm_store_si128优化。

优化后的SIMD版本（消除循环、移除memmove）在大字符串场景下，吞吐量应该能达到普通实现的1.5~2倍，完全能满足低延迟的需求。

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