c++ - 优化可变长度编码

Question

我有一个案例需要压缩很多通常很小的值。因此，我使用可变长度字节编码(具体来说是 ULEB128)来压缩它们:

size_t
compress_unsigned_int(unsigned int n, char* data)
{
  size_t size = 0;
  while (n  > 127)
  {
    ++size;
    *data++ = (n & 127)|128;
    n >>= 7;
  }
  *data++ = n;
  return ++size;
}

有没有更有效的方法来做到这一点(也许使用 SSE)？

Edit:压缩后，结果被存储到data中，占用size个字节。然后，在下一个 unsigned int 上调用压缩函数。

Answer 1

您要做的第一件事是针对您当前的代码测试任何可能的解决方案。

我想你可能想尝试摆脱数据依赖，让处理器同时做更多的工作。

什么是数据依赖关系？当数据流经您的函数时，n 的当前值取决于 n 的先前值，即取决于之前的值......这是一长串数据依赖关系。在下面的代码中，n 永远不会被修改，因此处理器可以“跳过”并同时执行几项不同的操作，而无需等待新的 n被计算出来。

// NOTE: This code is actually incorrect, as caf noted.
// The byte order is reversed.
size_t
compress_unsigned_int(unsigned int n, char *data)
{
    if (n < (1U << 14)) {
        if (n < (1U << 7)) {
            data[0] = n;
            return 1;
        } else {
            data[0] = (n >> 7) | 0x80;
            data[1] = n & 0x7f;
            return 2;
        }
    } else if (n < (1U << 28)) {
        if (n < (1U << 21)) {
            data[0] = (n >> 14) | 0x80;
            data[1] = ((n >> 7) & 0x7f) | 0x80;
            data[2] = n & 0x7f;
            return 3;
        } else {
            data[0] = (n >> 21) | 0x80;
            data[1] = ((n >> 14) & 0x7f) | 0x80;
            data[2] = ((n >> 7) & 0x7f) | 0x80;
            data[3] = n & 0x7f;
            return 4;
        }
    } else {
        data[0] = (n >> 28) | 0x80;
        data[1] = ((n >> 21) & 0x7f) | 0x80;
        data[2] = ((n >> 14) & 0x7f) | 0x80;
        data[3] = ((n >> 7) & 0x7f) | 0x80;
        data[4] = n & 0x7f;
        return 5;
    }
}

我通过在 0..UINT_MAX 的紧密循环中执行它来测试性能。在我的系统上，执行时间是:

(Lower is better)
Original: 100%
caf's unrolled version: 79%
My version: 57%

一些小的调整可能会产生更好的结果，但我怀疑除非你去组装，否则你会得到更多的改进。如果您的整数倾向于在特定范围内，那么您可以使用分析来让编译器将正确的分支预测添加到每个分支。这可能会使您的速度提高几个百分点。 (编辑:我从重新排序分支中获得了 8%，但这是一种不正当的优化，因为它依赖于每个数字 0...UINT_MAX 以相同的频率出现的事实。我不推荐这样做。 )

SSE 无济于事。 SSE 旨在同时处理具有相同宽度的多条数据，众所周知，要让 SIMD 加速具有可变长度编码的任何内容是非常困难的。 (这不一定是不可能的，但它可能是不可能的，而且你必须非常聪明才能弄清楚。)