在 C++ 中向量化位打包

Question

我正在编写一个工具，用于对 6 个不同字母（例如 >1000000 个字母）的长字符串进行操作，因此我想将每个字母编码为少于 8 位（对于 6 个字母，3 位就足够了）

这是我的代码：

Rcpp::RawVector pack(Rcpp::RawVector UNPACKED, 
                     const unsigned short ALPH_SIZE) {
  const unsigned int IN_LEN = UNPACKED.size();
  Rcpp::RawVector ret((ALPH_SIZE * IN_LEN + BYTE_SIZE - 1) / BYTE_SIZE);
  unsigned int out_byte = ZERO;
  unsigned short bits_left = BYTE_SIZE;

  for (int i = ZERO; i < IN_LEN; i++) {
    if (bits_left >= ALPH_SIZE) {
      ret[out_byte] |= (UNPACKED[i] << (bits_left - ALPH_SIZE));
      bits_left -= ALPH_SIZE;
    } else {
      ret[out_byte] |= (UNPACKED[i] >> (ALPH_SIZE - bits_left));
      bits_left = ALPH_SIZE - bits_left;
      out_byte++;
      ret[out_byte] |= (UNPACKED[i] << (BYTE_SIZE - bits_left));
      bits_left = BYTE_SIZE - bits_left;
    }
  }
  return ret;
}

我正在使用 Rcpp，它是 C++ 的 R 接口。 RawVector 实际上是 char 中的 vector。

这段代码工作得很好——只是它太慢了。我正在一点一点地执行操作，同时我可以以某种方式对其进行矢量化。这里有一个问题——是否有任何库或工具可以做到这一点？ C++ 工具不认可我。

提前致谢！

Answer 1

This code works just perfectly - except it is too slow.

那么您可能想试试 4-bits/letter。用 space 换取时间。如果 4 位满足您的压缩需求（仅大 33.3%），那么您的代码可以处理半字节，这将比 tri-bits.

更快更简单

Answer 2

您需要展开循环，以便优化器可以从中获得有用的东西。它还将摆脱你的 if，这会扼杀任何快速表现的机会。像这样：

int i = 0;
for(i = 0; i + 8 <= IN_LEN; i += 8) {
  ret[out_byte    ] = (UNPACKED[i]         ) | (UNPACKED[i + 1] << 3) | (UNPACKED[i + 2] << 6);
  ret[out_byte + 1] = (UNPACKED[i + 2] >> 2) | (UNPACKED[i + 3] << 1) | (UNPACKED[i + 4] << 4) | (UNPACKED[i + 5] << 7);
  ret[out_byte + 2] = (UNPACKED[i + 5] >> 1) | (UNPACKED[i + 6] << 2) | (UNPACKED[i + 7] << 5);
  out_byte += 3;
} 
for (; i < IN_LEN; i++) {
  if (bits_left >= ALPH_SIZE) {
    ret[out_byte] |= (UNPACKED[i] << (bits_left - ALPH_SIZE));
    bits_left -= ALPH_SIZE;
  } else {
    ret[out_byte] |= (UNPACKED[i] >> (ALPH_SIZE - bits_left));
    bits_left = ALPH_SIZE - bits_left;
    out_byte++;
    ret[out_byte] |= (UNPACKED[i] << (BYTE_SIZE - bits_left));
    bits_left = BYTE_SIZE - bits_left;
  }
}

这将允许优化器对整个事物进行矢量化（假设它足够聪明）。对于您当前的实现，我怀疑任何当前的编译器都能发现您的代码在 3 个写入字节后循环并滥用它。

编辑：有了足够的 constexpr / template 魔法，您也许可以为循环体编写一些通用处理程序。或者只覆盖所有小值（比如为从 1 到 16 的每个位计数编写专门的模板函数）。在 16 位之后按位打包值是多余的。

在 C++ 中向量化位打包

Vectorizing bits packing in C++

c++

bit-manipulation

vectorization

rcpp