c++ - 为什么 std::set 容器使用的内存比其数据大小多得多？

Question

例如，我们有 10^7 个 32 位整数。将这些整数存储在数组中的内存使用量为 32*10^7/8=40MB。但是，将 10^7 个 32 位整数插入一个集合中需要超过 300MB 的内存。代码:

#include <iostream>
#include <set>

int main(int argc, const char * argv[]) {
    std::set<int> aa;
    for (int i = 0; i < 10000000; i++)
        aa.insert(i);
    return 0;
}

map、unordered_set 等其他容器在类似测试中占用更多内存。我知道set是用红黑树实现的，但是数据结构本身并不能解释内存占用高的问题。

我想知道这 5 到 8 倍原始数据内存使用量背后的原因，以及一些更高效内存集的解决方法/替代方案。

Answer 1

让我们检查一下 GCC 中的 std::set 实现(这在其他编译器中没有太大区别)。 std::set 在 GCC 上实现为红黑树。每个节点都有一个指向父节点、左节点和右节点的指针以及一个颜色枚举器(_S_red 和 _S_black)。这意味着除了 int(可能是 4 个字节)之外，还有 3 个指针(对于 64 位系统，8 * 3 = 24 个字节)和一个枚举器(因为它位于 _Rb_tree_node_base 中的指针之前，所以它被填充为 8 个字节边界，所以实际上它需要额外的 8 个字节)。

到目前为止，我已经为集合中的每个整数计算了 24 + 8 + 4 = 36 个字节。但是由于节点必须对齐到 8 个字节，因此必须对其进行填充以使其可以被 8 整除。这意味着每个节点占用 40 个字节(比 int 大 10 倍)。

但这还不是全部。每个这样的节点都由 std::allocator 分配。这个分配器使用 new 来分配每个节点。由于 delete 不知道要释放多少内存，每个节点也有一些与堆相关的元数据。元数据至少应该包含分配 block 的大小，通常需要 8 个字节(理论上，可以使用某种霍夫曼编码，在大多数情况下只存储 1 个字节，但我从未见过有人这样做).

综合考虑，每个 int 节点的总大小为 48 字节。这是 int 的 12 倍。集合中的每个 int 比它在数组或 vector 中花费的时间多 12 倍。

您的数字表明您使用的是 32 位系统，因为您的数据仅占用 300 MB。对于 32 位系统，指针占用 4 个字节。这使得 3 * 4 + 4 = 16 字节用于节点中的红黑树相关数据 + 4 用于 int + 4 用于元数据。每个 int 总共有 24 个字节，而不是 4 个。这使得它比大集合的 vector 大 6 倍。这些数字表明堆元数据需要 8 个字节，而不仅仅是 4 个字节(可能是由于对齐约束)。

因此在您的系统上，预计需要 280MB，而不是 40MB(如果是 std::vector)。

如果你想节省一些花生，你可以为你的集合使用一个非标准的分配器。您可以通过使用 boost 的隔离存储节点分配器来避免元数据开销。但就内存而言，这并不是一个很大的胜利。不过，它可以提高性能，因为分配器比 new 和 delete 中的代码更简单。