为什么std :: bitset <8> 4个字节大？

Question

似乎对于std :: bitset <1到32>,大小设置为4个字节.对于33到64的大小,它会直接跳到8个字节.不能有任何开销,因为std :: bitset <32>是偶数4个字节.

在处理位时我可以看到对齐字节长度,但是为什么bitset需要与字长对齐,特别是对于最有可能在内存预算紧张的情况下使用的容器？

这是在VS2010下.

Answer 1

最可能的解释是bitset使用大量机器字来存储数组.

这可能是出于存储器带宽的原因而做的:读取/写入在字边界处对齐的字通常相对便宜.另一方面,在某些体系结构上,读取(尤其是写入!)任意对齐的字节可能很昂贵.

由于我们讨论的是每个字节固定大小的惩罚bitset,这听起来像是一个通用库的合理权衡.

Answer 2

我假设对位集的索引是通过获取 32 位值然后隔离相关位来完成的，因为这在处理器指令方面是最快的（在 x86 上处理较小尺寸的值速度较慢）。为此所需的两个索引也可以很快计算出来：

int wordIndex = (index & 0xfffffff8) >> 3;
int bitIndex = index & 0x7;

然后你就可以这样做，这也非常快：

int word = m_pStorage[wordIndex];
bool bit = ((word & (1 << bitIndex)) >> bitIndex) == 1;

另外，恕我直言，每个位集最多浪费 3 个字节并不是内存问题。考虑到位集已经是存储此类信息的最有效的数据结构，因此您必须以总结构大小的百分比来评估浪费。

对于 1025 位，此方法使用 132 个字节而不是 129 个字节，开销为 2.3%（随着位集站点的增加，开销会减少）。考虑到可能的性能优势，听起来​​很合理。