c++ - 更快的位读取？

Question

在我的应用程序中，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。

score 2 · Accepted Answer

我从之前的评论中看到您正在解压缩 JPEG 中的霍夫曼/算术编码流。

skip()并且value()非常简单，可以内联。编译器有可能将移位寄存器和缓冲区指针一直保留在寄存器中。在此处和在调用者中使用restrict修饰符创建所有指针可能有助于告诉编译器您不会将霍夫曼解码的结果写入位缓冲区，从而允许进一步优化。
每个 Huffman/artimetic 符号的平均长度都很短 - 因此，在 8 次中有约 7 次，您不需要填充 64 位移位寄存器。调查给编译器一个分支预测提示。
JPEG 比特流中的任何符号都长于 32 位是不寻常的。这是否允许进一步优化？
一条繁重的道路的一个非常合乎逻辑的原因skip()是您经常调用它。您一次消耗整个符号，而不是这里的每一位，不是吗？您可以通过计算符号和表格查找中的前导 0 或 1 来实现一些巧妙的技巧。
您可能会考虑安排您的移位寄存器，以便流中的下一位是 LSB。这将避免在value()

score 1 · Accepted Answer

移位 64 位绝对不是一个好主意。在许多 CPU 中，移位是一种缓慢的操作。我建议您将代码更改为字节寻址。这将限制最多 8 位的移位。

在许多情况下，您实际上并不需要它本身，而是检查它是否存在。这可以通过如下代码来完成：

    if (data[bit_inx/64] & mask[bit_inx % 64])
    {
        ....
    }

score 1 · Accepted Answer

1

尝试将此行替换为skip：

m_block  = (m_block << 32) | _byteswap_uint32(*++m_data);

于 2012-08-07T21:42:20.043 回答

score 0 · Accepted Answer

这是我尝试过的另一个版本，它没有提供任何性能改进。

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);
    }   
};

score 0 · Accepted Answer

我不知道这是否是原因以及 _byteswap_uint64 的底层实现是什么样的，但您应该阅读Rob Pike 关于 byteorder 的文章。也许这就是你的答案。

摘要：字节序比它通常被弥补的问题要少。字节顺序交换的实现经常会出现问题。但是有一个简单的选择。

[编辑]我有一个更好的理论。从我下面的评论中粘贴：也许是混叠。64 位架构喜欢将数据按 64 位对齐，当您跨对齐边界读取时，它会变得非常慢。所以它可能是(++m_data)[0]一部分，因为 x64 是 64 位对齐的，当你reinterpret_casta uint32_t*to时uint64_t*，你大约有一半的时间跨越对齐边界。

score 0 · Accepted Answer

bit_reader如果您的源缓冲区不是很大，那么您应该对它们进行预处理，在使用!访问它们之前对缓冲区进行字节交换。

从你那里阅读bit_reader会快得多，因为：

你会保存一些有条件的指令
CPU 缓存可以更有效地使用：它可以直接从内存中读取，这很可能已经加载到 cpu 缓存中，而不是从读取每个 64 位块后将被修改的内存中读取，因此破坏了拥有的好处它在缓存中

编辑

哦等等，你不要修改源缓冲区。但是，将字节交换放入预处理阶段至少应该值得一试。

另一点：确保这些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?

score -2 · Accepted Answer

如果可能的话，最好分多次执行此操作。可以优化多次运行并减少违规。

一般来说，最好这样做

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 中单次加载数据。

在您的情况下，您以流式传输方式执行此操作仅适用于保持低内存和来自慢速数据源的更快响应，但不适用于速度。

c++ - 更快的位读取？

7 回答 7

Related

Reference