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

Question

我们知道基于哈希表的容器实现，如 std::unordered_map 使用大量内存，但我不知道多少是多少？

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

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

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

原文由 rahman 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

如果你想得到一个粗略的大小，我认为 bucket_count() 和 max_load_factor() 就足够了，它给出了当前的桶数和负载因子。

合理的：

• 如果 load_factor <= 1，表示 bucket_count() >= map中的item，那么bucket_count()就是内存使用的大小。

• 如果 load_factor > 1，则 bucket_count() \* load_factor 表示地图中的最大项目。请注意，这是最大尺寸，而不是实际尺寸。

因此，粗略的内存使用情况可能如下所示：

   unsigned n = mymap.bucket_count();
  float m = mymap.max_load_factor();
  if (m > 1.0) {
    return n * m;
  }
  else {
    return n;
  }

如果您想获得准确的内存使用情况，您可能需要统计所有的桶以查看其中有多少个元素：

   size_t count = 0;
  for (unsigned i = 0; i < mymap.bucket_count(); ++i) {
    size_t bucket_size = mymap.bucket_size(i);
    if (bucket_size == 0) {
      count++;
    }
    else {
      count += bucket_size;
    }
  }

原文由 Mine 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

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

• 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 存储每个桶，因此可能只有恒定的 摊销 复杂性—我自己以这种方式实现它）

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

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

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

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

总而言之，一个大致合理的数字是：

 (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 如何报告不同的内存使用情况来进一步探索这一点。

原文由 Tony Delroy 发布，翻译遵循 CC BY-SA 4.0 许可协议