在现代x86硬件上编写位流的最快方式

Question

在x86/x86-64上写位流最快的方法是什么?(codeword <= 32bit)

通过写位流，我指的是将可变位长符号连接到连续内存缓冲区中的过程。

目前我有一个标准的容器与一个32位的中间缓冲区写入

void write_bits(SomeContainer<unsigned int>& dst,unsigned int& buffer, unsigned int& bits_left_in_buffer,int codeword, short bits_to_write){
    if(bits_to_write < bits_left_in_buffer){
        buffer|= codeword << (32-bits_left_in_buffer);
        bits_left_in_buffer -= bits_to_write;
    }else{
        unsigned int full_bits = bits_to_write - bits_left_in_buffer;
        unsigned int towrite = buffer|(codeword<<(32-bits_left_in_buffer));
        buffer= full_bits ? (codeword >> bits_left_in_buffer) : 0;
        dst.push_back(towrite);
        bits_left_in_buffer = 32-full_bits;
    }
}

有没有人知道任何好的优化，快速指令或其他信息，可能是有用的?

Cheers，

Answer 1

我曾经写过一个非常快的实现，但是它有几个限制:当您写入和读取比特流时，它可以在32位x86上工作。我在这里没有检查缓冲区限制，我分配了更大的缓冲区，并不时地从调用代码中检查它。

unsigned char* membuff; 
unsigned bit_pos; // current BIT position in the buffer, so it's max size is 512Mb
// input bit buffer: we'll decode the byte address so that it's even, and the DWORD from that address will surely have at least 17 free bits
inline unsigned int get_bits(unsigned int bit_cnt){ // bit_cnt MUST be in range 0..17
    unsigned int byte_offset = bit_pos >> 3;
    byte_offset &= ~1;  // rounding down by 2.
    unsigned int bits = *(unsigned int*)(membuff + byte_offset);
    bits >>= bit_pos & 0xF;
    bit_pos += bit_cnt;
    return bits & BIT_MASKS[bit_cnt];
};
// output buffer, the whole destination should be memset'ed to 0
inline unsigned int put_bits(unsigned int val, unsigned int bit_cnt){
    unsigned int byte_offset = bit_pos >> 3;
    byte_offset &= ~1;
    *(unsigned int*)(membuff + byte_offset) |= val << (bit_pos & 0xf);
    bit_pos += bit_cnt;
};

Answer 2

一般来说很难回答，因为它取决于许多因素，例如您正在读取的位大小的分布，客户端代码中的调用模式以及硬件和编译器。一般来说，从位流读(写)的两种可能的方法是:

1. 使用32位或64位缓冲区，并在需要更多位时有条件地从底层数组中读取(写入)。这就是你的write_bits方法所采用的方法。
2. 在每个比特流读(写)时无条件地从底层数组读(写)，然后移动和屏蔽结果值。

(1)的主要优点包括:

• 仅以对齐的方式从底层缓冲区读取所需的最小次数。
• 快速路径(不读取数组)有点快，因为它不需要做读取和相关的寻址数学。
• 方法可能内联更好，因为它没有读取-如果你有几个连续的read_bits调用，例如，编译器可以潜在地组合很多逻辑并产生一些真正快速的代码。

(2)的主要优点是它是完全可预测的——它不包含不可预测的分支。

仅仅因为(2)只有一个优势并不意味着它更糟糕:这个优势可以轻易地压倒其他一切。

特别是，您可以基于两个因素分析算法可能的分支行为:

• 比特蒸汽需要多久从底层缓冲区读取一次?
• 在需要读取之前调用的次数有多可预测?

例如，如果你在50%的时间读1位，50%的时间读2位，你将在需要底层读之前进行64 / 1.5 = ~42读(如果你可以使用64位缓冲区)。这有利于方法(1)，因为读取底层数据的次数很少，即使预测错误也是如此。另一方面，如果您通常读取20位以上的数据，则每隔几次调用就会从底层读取数据。这可能有利于方法(2)，除非底层读取的模式非常可预测。例如，如果您总是读取22到30位之间的数据，那么您可能总是调用正好三次来耗尽缓冲区并读取底层的¹数组。因此分支将被很好地预测，并且(1)将保持快速。

同样，这取决于你如何调用这些方法，以及编译器如何内联和简化代码。特别是如果您曾经使用编译时常量大小重复调用这些方法，那么可以进行大量简化。当码字在编译时已知时，几乎没有简化可用。

最后，您可以通过提供更复杂的API来提高性能。这主要适用于实现选项(1)。例如，您可以提供ensure_available(unsigned size)调用，以确保至少可以读取size位(通常限制缓冲区大小)。然后，您可以使用不检查缓冲区大小的unchecked调用读取该位数。这可以通过强制缓冲区填充到可预测的计划来帮助您减少错误预测，并允许您编写更简单的未检查方法。

---

¹这取决于你的"从底层读取"例程是如何写入的，因为这里有几个选项:有些总是填充到64位，有些填充到57位到64位之间(即读取整数字节)，有些可能填充到32位或33位到64位之间(就像你的例子一样读取32位块)。

Answer 3

你可能要等到2013年才能得到真正的硬件，但"Haswell"新指令将带来适当的向量化移位(即将每个矢量元素移动另一个矢量中指定的不同数量的能力)到x86/AVX。不确定细节(有足够的时间来弄清楚)，但这肯定会使比特流构造代码的性能得到巨大的提高。

Answer 4

我没有时间为您写(我不太确定您的示例是否足够完整)，但如果您必须这样做，我可以考虑

• 为各种输入/输出位移位偏移使用转换表;这种优化对于n位的固定单元(n足够大(8位?)以期望性能提升)是有意义的。实际上，您可以执行

  destloc &= (lookuptable[bits_left_in_buffer][input_offset][codeword]);
  

免责声明:这是一个非常草率的伪代码，我只是希望它传达了我的想法，一个查找表来防止位移运算

• 用汇编编写它(我知道i386有XLAT，但话又说回来，一个好的编译器可能已经使用了类似的东西);此外，xslt似乎仅限于8位和AL寄存器，所以它不是真正通用的

更新

警告:请务必使用分析器并测试您的优化的正确性和速度。根据引用的局部性，使用查找表可能会导致较差的性能。因此，您可能需要在单个核心上更改位流线程(设置线程关联)以获得好处，并且您可能必须调整查找表的大小以适应处理器的二级缓存。

另外，看看SIMD, SSE4或GPU (CUDA)指令集，如果你知道，你会有某些功能在你的处置。