在x86 / x86-64上写入比特流的最快方法是什么？ （代码字<= 32位）
通过写一个比特流，我指的是将可变比特长度符号连接成一个连续的内存缓冲区的过程。
目前我有一个带有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;
}
}
有没有人知道任何好的优化，快速指令或其他可能有用的信息？
干杯，
我写了一个相当快的实现，但它有一些限制：当你写和读取比特流时它适用于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;
};
一般来说很难回答，因为它取决于许多因素，例如您正在读取的位大小的分布，客户端代码中的调用模式以及硬件和编译器。通常，从比特流中读取（写入）的两种可能方法是：
- 当您需要更多位时，使用32位或64位缓冲区并从底层数组有条件地读取（写入）。这就是你的方法
write_bits 方法需要。
- 无条件地从每个比特流上的基础数组读取（写入）读取（写入），然后移位和屏蔽结果值。
（1）的主要优点包括：
- 仅以对齐的方式从底层缓冲区读取最低要求的次数。
- 快速路径（没有数组读取）有点快，因为它不必进行读取和相关的寻址数学运算。
- 该方法可能更好地内联，因为它没有读取 - 如果你连续几次
read_bits 例如，调用程序可以组合很多逻辑并生成一些非常快的代码。
（2）的主要优点是它是完全可预测的 - 它不包含不可预测的分支。
仅仅因为（2）只有一个优势并不意味着它更糟糕：这种优势很容易压倒其他一切。
特别是，您可以基于以下两个因素分析算法的可能分支行为：
- bitsteam需要多久从底层缓冲区读取一次？
- 在需要读取之前调用的数量有多可预测？
例如，如果您在50％的时间内读取1位，在50％的时间内读取2位，那么您将会这样做 64 / 1.5 = ~42 在需要基础读取之前读取（如果可以使用64位缓冲区）。这有利于方法（1），因为即使错误预测，对底层的读取也是罕见的。另一方面，如果您通常读取20多位，您将从每次调用的基础读取。这可能有利于方法（2），除非基础读取的模式是非常可预测的。例如，如果你总是在22到30位之间读取，你可能总是会读 究竟 三次调用耗尽缓冲区并读取底层1 阵列。因此，该分支将得到很好的预测，并且（1）将保持快速。
同样，它取决于您如何调用这些方法，以及编译器如何内联和简化代码。特别是如果您使用编译时常量大小重复调用这些方法，则可以进行大量简化。很少甚至没有简化 码字 在编译时已知。
最后，您可以通过提供更复杂的API来提高性能。这主要适用于实施选项（1）。例如，您可以提供 ensure_available(unsigned size) 呼叫，至少确保 size 可以读取位（通常限制缓冲区大小）。然后你可以使用读取最多这个位数 未选中 不检查缓冲区大小的调用。这可以通过强制缓冲区填充到可预测的计划来帮助您减少错误预测，并允许您编写更简单的未经检查的方法。
1 这取决于你如何写“从底层读取”例程，因为这里有一些选项：一些总是填充到64位，一些填充到57到64位之间（即，读取整数个字节） ，有些可能填充32或33和64位（就像你读取32位块的例子）。
您可能要等到2013年才能获得真正的硬件，但是 “Haswell”新指令 将带来适当的矢量化移位（即将每个矢量元素按另一个矢量中指定的不同量移位的能力）到x86 / AVX。不确定细节（有足够的时间来解决它们），但这肯定会在比特流构造代码中实现大规模的性能提升。
我没有时间为你写（不太确定你的样品实际上是否足够完成）但如果你必须，我可以想到
免责声明：这是非常草率的伪代码，我只希望它传达我的查找表的想法o阻止bitshift算术
- 在汇编中写它（我知道i386有
XLAT，但又一次，一个好的编译器可能已经使用了类似的东西）
;此外，XLAT似乎限于8位和AL寄存器，因此它并不是真正的多功能
更新
警告：确保使用分析器并测试优化的正确性和速度。使用查找表 能够 根据参考地点导致较差的表现。因此，您可能需要更改单个核心上的位流线程（设置线程关联）以获得好处，并且您可能必须使查找表大小适应处理器的L2缓存。
Als，看看 SIMD， SSE4 要么 GPU（CUDA） 指令集如果你 知道 您可以随意使用某些功能。