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

Question

看来对于 std::bitset<1 to 32>，大小设置为 4 字节。对于大小 33 到 64，它直接跳到 8 字节。不会有任何开销，因为 std::bitset<32>是偶数4个字节。

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

这是VS2010下的。

Answer 1

最可能的解释是 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%（随着位集站点的增加，开销会减少）。考虑到可能的性能优势，听起来​​很合理。

Answer 3

现代机器上的内存系统除了从内存中获取单词之外无法获取任何其他内容，除了一些提取所需位的遗留功能之外。因此，将位集与单词对齐可以使处理速度更快，因为在访问它时不需要屏蔽掉不需要的位。如果你不屏蔽，做类似的事情

bitset<4> foo = 0;
if (foo) {
    // ...
}

很可能会失败。除此之外，我记得不久前读到有一种方法可以将几个位集压缩在一起，但我记不太清楚了。我认为当您在一个结构中拥有多个位集时，它们可以占用“共享”内存，这不适用于位域的大多数用例。

Answer 4

我在 Aix 和 Linux 实现中具有相同的功能。在 Aix 中，内部位集存储是基于字符的：

typedef unsigned char _Ty;
....
_Ty _A[_Nw + 1];

在 Linux 中，内部存储是基于长的：

typedef unsigned long _WordT;
....
_WordT            _M_w[_Nw];

出于兼容性原因，我们使用基于字符的存储修改了 Linux 版本

检查您在 bitset.h 中使用的是哪种实现

Answer 5

因为 32 位 Intel 兼容处理器无法单独访问字节（或者更好，它可以通过隐式应用一些位掩码和移位来访问），但一次只能访问 32 位字。

如果您声明

bitset<4> a,b,c;

即使库将其实现为 char，a、b 和 c 也将是 32 位对齐，因此存在相同的浪费空间。但是，在让位集代码执行自己的掩码之前，处理器将被迫预先掩码字节。

因此，MS 使用 int[1+(N-1)/32] 作为位的容器。

Answer 6

也许是因为它默认使用 int ，如果溢出则切换到 long long ？ （只是猜测...）

Answer 7

如果你的 std::bitset< 8> 是结构体的成员，则可能会出现以下情况：

struct A
{
  std::bitset< 8 > mask;
  void * pointerToSomething;
}

如果 bitset<8> 存储在一个字节中（并且结构打包在 1 字节边界上），那么结构中跟随它的指针将是未对齐的，这将是一件坏事。拥有 bitset<8> 是安全且有用的唯一一次。如果它是在打包结构中，则存储在一个字节中，并且后面跟着一些其他可以将其打包在一起的单字节字段。我想这个用例太窄了，不值得提供库实现。

基本上，在八叉树中，单字节位集只有在打包结构中后面跟着另外一到三个单字节成员时才有用。否则，无论如何（在 32 位机器上）都必须将其填充到四个字节，以确保后面的变量是字对齐的。