c++ - 计算无序映射占用的内存空间

Question

我有两个无序映射:(代码在 linux 中执行)

第一个无序 map :

它至少包含 65536 个条目。每个条目包括

int
unsigned char
unsigned char

第二张无序图:

它由少于 65536 个条目组成。每个条目包括

int
int
int
vector <char>

现在我想根据以上两个无序映射占用的内存(以字节为单位)对两者进行比较。之后我要计算实现的内存压缩。请指导我如何找到两个无序映射占用的内存？

第二张无序图的更多细节:

typedef std::tuple<int, int> key_t;

struct KeyHasher
{
  std::size_t operator()(const key_t& k) const
  {
      using boost::hash_value;
      using boost::hash_combine;

      // Start with a hash value of 0    .
      std::size_t seed = 0;

      // Modify 'seed' by XORing and bit-shifting in
      // one member of 'Key' after the other:
      hash_combine(seed,hash_value(std::get<0>(k)));
      hash_combine(seed,hash_value(std::get<1>(k)));

      // Return the result.
      return seed;
  }
};

struct Ndata
{
int value;
vector<char> accept ;
};

typedef boost::unordered_map<const key_t,Ndata,KeyHasher> SecondMap;
}

Answer 1

如果不查看您的 STL 使用的精确 unordered_map 实现，我认为不可能准确地回答您的问题。

但是，基于unordered_map interface ，你可以做出体面的有根据的猜测:

一个unordered_map需要存储:

• 一个bucket容器(可能是一个类似 vector 的结构)

• max_bucket_count 个桶(可能是单链表结构)

• 每个项目一个完整的条目(不仅是值，还有键，以处理键哈希冲突)

快速浏览完Libc++实现，还需要空间来存放:

• 哈希函数对象

• 相等性测试函数对象

• 分配函数对象

考虑到这一点，我的猜测是这样的:

typedef unordered_map<K, V, ...> tMyMap;

size_t getMemoryUsage(const tMyMap& map) {
  auto entrySize = sizeof(K) + sizeof(V) + sizeof(void*);
  auto bucketSize = sizeof(void*);
  auto adminSize = 3 * sizeof(void*) + sizeof(size_t);

  auto totalSize = adminSize + map.size() * entrySize + map.max_bucket_count() * bucketSize();
  return totalSize;
}

这只适用于第一种情况，因为在第二种情况下，根据每个 vector 的大小，每个条目可以有完全不同的内存使用。因此，对于第二种情况，您必须添加如下内容:

size_t getMemoryUsage(const tMyMap& map) {
  auto entrySize = sizeof(K) + sizeof(V) + sizeof(void*);
  auto bucketSize = sizeof(void*);
  auto adminSize = 3 * sizeof(void*) + sizeof(size_t);
  auto totalSize = adminSize + map.size() * entrySize + map.max_bucket_count() * bucketSize();

  auto contentSize = 0;
  for (const auto& kv : map) {
    // since accept is a vector<char>, 
    // it uses capacity() bytes of additional memory
    contentSize += kv.second.accept.capacity();
  }
  totalSize += contentSize;

  return totalSize;
}

但是，考虑到现实世界的分配逻辑，您的 map 实际使用的内存可能与此有很大差异，例如，外部碎片。如果您想 100% 确定 unordered_map 使用了多少内存，您还需要考虑分配器行为。