在我的应用程序中，20%的CPU时间都花在通过我的位读取器读取位（skip）上。有没有人知道如何使以下代码更快？在任何给定时间，我都不需要超过 20 个有效位（这就是为什么在某些情况下我可以使用 fast_skip ）。
位以大端顺序读取，这就是需要字节交换的原因。
class bit_reader
{
std::uint32_t* m_data;
std::size_t m_pos;
std::uint64_t m_block;
public:
bit_reader(void* data)
: m_data(reinterpret_cast<std::uint32_t*>(data))
, m_pos(0)
, m_block(_byteswap_uint64(*reinterpret_cast<std::uint64_t*>(data)))
{
}
std::uint64_t value(std::size_t n_bits = 64)
{
assert(m_pos + n_bits < 64);
return (m_block << m_pos) >> (64 - n_bits);
}
void skip(std::size_t n_bits) // 20% cpu time
{
assert(m_pos + n_bits < 42);
m_pos += n_bits;
if(m_pos > 31)
{
m_block = _byteswap_uint64(reinterpret_cast<std::uint64_t*>(++m_data)[0]);
m_pos -= 32;
}
}
void fast_skip(std::size_t n_bits)
{
assert(m_pos + n_bits < 42);
m_pos += n_bits;
}
};
目标硬件为 x64。
我从之前的评论中看到您正在用 JPEG 解压缩霍夫曼/算术编码流。
-
skip()和value()非常简单，可以内联。 编译器有可能在整个寄存器中保留移位寄存器和缓冲区指针。 在此处和调用方中使用restrict修饰符制作所有指针可能会有所帮助，因为它告诉编译器您不会将 Huffman 解码的结果写入位缓冲区，从而允许进一步优化。 - 每个霍夫曼/计时符号的平均长度很短 - 因此，8 次中有 ~7 次，您无需补充 64 位移位寄存器。 研究如何为编译器提供分支预测提示。
- JPEG 比特流中的任何符号长度超过 32 位是不寻常的。 这是否允许进一步优化？
skip()是一条沉重的道路的一个非常合乎逻辑的原因是你经常称呼它。 您正在一次消耗整个符号，而不是这里的每一点，不是吗？ 您可以通过计算符号和表查找中的前导 0 或 1 来做一些聪明的技巧。- 您可以考虑安排移位寄存器，使流中的下一个位是 LSB。 这将避免
value()的变化
移位 64 位绝对不是一个好主意。在许多CPU中，移位是一个缓慢的操作。我建议您将代码更改为字节寻址。这将限制最多 8 位的偏移。
在许多情况下，您真的不需要自己一点，而是检查它是否存在。这可以通过如下代码完成：
if (data[bit_inx/64] & mask[bit_inx % 64])
{
....
}
尝试将这一行替换为skip：
m_block = (m_block << 32) | _byteswap_uint32(*++m_data);
这是否是原因以及_byteswap_uint64的底层实现是什么样子的，但你应该阅读 Rob Pike 关于字节顺序的文章。也许这就是你的答案。
摘要：字节序与其说是一个问题，不如说是人们通常编造的问题。字节顺序交换的实现经常会遇到问题。但有一个简单的选择。
[编辑] 我有一个更好的理论。粘贴自我下面的评论：也许是混叠。64 位架构喜欢将数据对齐 64 位，当您跨对齐边界读取时，它会变得非常慢。所以它可能是最(++m_data)[0]部分，因为 x64 是 64 位对齐的，当你reinterpret_cast一个uint32_t*来uint64_t*时，你大约一半的时间会跨越对齐边界。
如果你的源缓冲区不是很大，那么你应该预处理它们，在使用bit_reader访问它们之前对缓冲区进行字节交换！
从您的bit_reader中读取会快得多，因为：
- 您将保存一些条件指令 CPU缓存
- 可以更有效地使用：它可以直接从内存中读取，这很可能已经加载到CPU缓存中，而不是从读取每个64位块后将被修改的内存中读取，因此，破坏了将其放在缓存中的好处
编辑
哦，等等，你不修改源缓冲区。但是，将byteswap置于预处理阶段至少值得一试。
另一点：确保这些assert()调用仅在调试版本中。
编辑 2
（已删除）
编辑 3
您的代码肯定有缺陷，请检查以下使用场景：
uint32_t source[] = { 0x00112233, 0x44556677, 0x8899AABB, 0xCCDDEEFF };
bit_reader br(source); // -> m_block = 0x7766554433221100
// reading...
br.value(16); // -> 0x77665544
br.skip(16);
br.value(16); // -> 0x33221100
br.skip(16); // -> triggers reading more bits
// -> m_block = 0xBBAA998877665544, m_pos = 0
br.value(16); // -> 0xBBAA9988
br.skip(16);
br.value(16); // -> 0x77665544
// that's not what you expect, right ???
编辑 4
好吧，不，EDIT 3 是错误的，但我无能为力，代码有缺陷。不是吗？
uint32_t source[] = { 0x00112233, 0x44556677, 0x8899AABB, 0xCCDDEEFF };
bit_reader br(source); // -> m_block = 0x7766554433221100
// reading...
br.value(16); // -> 0x7766
br.skip(16);
br.value(16); // -> 0x5544
br.skip(16); // -> triggers reading more bits (because m_pos=32, which is: m_pos>31)
// -> m_block = 0xBBAA998877665544, m_pos = 0
br.value(16); // -> 0xBBAA --> not what you expect, right?
尝试过的另一个版本，它没有提供任何性能改进。
class bit_reader
{
public:
const std::uint64_t* m_data64;
std::size_t m_pos64;
std::uint64_t m_block0;
std::uint64_t m_block1;
bit_reader(const void* data)
: m_pos64(0)
, m_data64(reinterpret_cast<const std::uint64_t*>(data))
, m_block0(byte_swap(*m_data64++))
, m_block1(byte_swap(*m_data64++))
{
}
std::uint64_t value(std::size_t n_bits = 64)
{
return __shiftleft128(m_block1, m_block0, m_pos64) >> (64 - n_bits);
}
void skip(std::size_t n_bits)
{
m_pos64 += n_bits;
if(m_pos64 > 63)
{
m_block0 = m_block1;
m_block1 = byte_swap(*m_data64++);
m_pos64 -= 64;
}
}
void fast_skip(std::size_t n_bits)
{
skip(n_bits);
}
};
如果可能的话，最好分多次进行。可以优化多次运行并减少违规。
一般来说，最好这样做
const uint64_t * arr = data;
for(uint64_t * i = arr; i != &arr[len/sizeof(uint64_t)] ;i++)
{
*i = _byteswap_uint64(*i);
//no more operations here
}
// another similar for loop
这样的代码可以大大减少运行时间
在最坏的情况下，您可以像运行 100k 块一样执行此操作，以将缓存未命中保持在最小值并从 RAM 单次加载数据。
在您的情况下，您以流式传输方式执行此操作，witch 仅适用于保持低内存和来自慢速数据源的更快响应，但不适用于速度。