为什么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需要用类似的测试甚至更多的内存.我知道该集是用红黑树实现的,但数据结构本身并不能解释高内存使用率.

我想知道这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无法知道要释放多少内存,每个节点也都有一些与堆相关的元数据.元数据应该至少包含分配块的大小,通常需要8个字节(理论上,在大多数情况下,可以使用某种霍夫曼编码并且只存储1个字节,但我从未见过任何人这样做过).

考虑到所有内容,每个int节点的总数为48个字节.这是12倍多int.int集合中的每一个都比在数组或向量中所花费的多12倍.

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

所以在你的系统上,而不是40MB(如果它std::vector),它预计需要280MB.

如果你想保存一些花生,你可以使用非标准分配器.您可以使用boost的Segregated存储节点分配器来避免元数据开销.但就记忆而言,这并不是一个巨大的胜利.它可以提高你的表现,不过,由于分配器是比代码更简单new和delete.