c++ - 如何测量 std::unordered_map 的内存使用情况

Question

我们知道基于哈希表的容器实现如 std::unordered_map use a lot memory但我不知道多少是多少？

除了空间复杂度符号，不考虑容器元素是否是指向更大对象的指针:

有什么方法可以计算出这样的容器在运行时使用了多少字节？

有没有办法在运行时告诉任何容器使用了多少内存？

Answer 1

没有可移植的方法来判断正在使用的字节数。你能发现的是:

• size()表示容器中插入了多少数据元素
• bucket_count() 表示底层哈希表有多少个桶，每个桶都可以潜在地保存一个迭代器进入元素的链表(GCC 至少为所有元素维护一个链表整个容器中的元素，因此它始终可以在 O(1) 时间内递增迭代器，即使 bucket_count() 高且 size() 低)

现在:

• 实际用于元素存储的字节数为 m.size() * sizeof(M::value_type)

• 用于哈希表存储桶的字节数取决于内部列表的存储方式 - std::unordered_map::bucket_size 具有恒定的复杂性，因此我们可能会得出这样的结论: size() 和每个桶的链表迭代器，所以 m.bucket_count() * (sizeof(size_t) + sizeof(void*))，尽管可能是这样由于 load_factor() 是有界的，并且每个桶没有存储 size ，因此只有恒定的 amortised 复杂性(我更喜欢自己以这种方式实现它)

• 如果每个插入的元素都是列表的一部分，它们需要一个 next 指针，所以我们可以添加另一个 m.size() * sizeof(void *)

• 一些实现，例如 GCC，将哈希值与每个元素一起存储，允许快速而肮脏地检查在同一个桶中碰撞的元素之间的不等式(这 - 使用一个像样的哈希函数 - 更可能是因为在修改桶数后哈希值会发生冲突，而不是因为哈希值相同)，并且在调整桶数组大小时避免重新计算； 如果实现有这个，很可能m.size() * sizeof(size_t);由于它是可选的，因此我不会将其包含在下面的整体公式中，但如果您的实现这样做，则将其添加

• 每个内存分配可以向上取整到便于内存分配库管理的大小 - 例如下一个 2 的幂，这意味着您最多可以分配 2 倍当前正在使用的内存，但平均而言，您可能会分配大约 1.5 倍的内存(即比您正在使用的内存多 50%)。因此，让我们为列表节点添加 50%，因为桶可能是两个给定 size_t 和一个指针的幂:0.5 * size() * (sizeof(void*) + sizeof ((M::value_type))

• 尤其是在 Debug模式下，可能会有任意数量的特定于实现的内务管理和错误检测数据

总之，一个大致合理的数字是:

(m.size() * (sizeof(M::value_type) + sizeof(void*)) + // data list
 m.bucket_count() * (sizeof(void*) + sizeof(size_t))) // bucket index
* 1.5 // estimated allocation overheads

您可以通过创建许多大表并查看 top 或 Process Manager 如何报告不同的内存使用情况来进一步探索这一点。