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

没有可移植的方法来确定使用了多少字节。您可以发现:

• size() 指示已将多少数据元素插入到容器中
• bucket_count() 指示基础哈希表有多少个桶,每个桶都可能将迭代器保存在元素的链接列表中(GCC至少为整个容器中的所有元素维护一个链接列表,因此它总是可以在O(1)时间内递增迭代器,即使bucket_count()较高,size()较低)

现在:

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

• 用于哈希表桶的字节取决于内部列表的存储方式- std::unordered_map::bucket_size 具有恒定的复杂性,因此我们可以得出结论 大小() 和每个bucket的链表迭代器,因此 m.bucket_count() * (sizeof(size_t) + sizeof(void*)) 尽管可能只有常数 已摊销的 由于 load_factor() 有界且无 size 存储在每个桶中(我更希望自己用这种方式实现)

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

• 一些实现,如GCC,将哈希值与每个元素一起存储,从而允许快速而彻底地检查在同一存储桶中发生冲突的元素之间的不平等性(使用一个像样的哈希函数,这很可能是因为哈希值在修改到存储桶计数后发生冲突,而不是因为哈希值相同),并且避免在调整桶阵列的大小时重新计算; 如果 实现有这个,很可能 m.size() * sizeof(size_t) ; 因为它是可选的,所以我不会将其包含在下面的总体公式中,但如果您的实现做到了这一点,请将其添加进来

• 每个内存分配 也许 四舍五入到便于内存分配库管理的大小,例如二次幂,这意味着您可以分配最多两倍当前使用的内存,但平均而言,您分配的内存可能是1.5倍左右(即比您使用的内存多50%)。因此,让我们增加50%,仅针对列表节点,因为桶可能是给定的2的幂 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报告不同的内存使用情况。

如果你想得到一个粗略的尺寸,我想 bucket_count() 和 max_load_factor() 这就足够了,它给出了桶的当前计数和负载系数。

理性:

• 如果 load_factor <=1,表示 bucket_count() >=映射中的项,则Bucketcount()是内存使用的大小。

• 如果 负载因子 >1,那么 bucket_count() * 负载因子 指示地图中的最大项目。请注意,这是最大尺寸,而不是实际尺寸。

因此,粗略的内存使用情况如下:

  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;
    }
  }

如果您想观察堆内存被分配和释放(对于 unordered_map 或其他任何事情),您可以始终重载全局 new 和 delete 操作员可以随时跟踪记录和/或打印当前记录。(注意:下面显示的示例代码不是线程安全的,在简单的玩具程序之外可能无法可靠地工作,但它足够好用)

# include <stdint.h>
# include <new>
# include <typeinfo>
# include <unordered_map>

static inline uint32_t    CONVERT_USER_TO_INTERNAL_SIZE(uint32_t uNumBytes) {return (uNumBytes+sizeof(size_t));}
static inline uint32_t    CONVERT_INTERNAL_TO_USER_SIZE(uint32_t iNumBytes) {return (iNumBytes-sizeof(size_t));}
static inline size_t *  CONVERT_USER_TO_INTERNAL_POINTER(void * uptr)   {return (((size_t*)uptr)-1);}
static inline void   *  CONVERT_INTERNAL_TO_USER_POINTER(size_t * iptr) {return ((void *)(iptr+1));}

static size_t _currentlyAllocatedBytes = 0;  // Running tally of how many bytes our process has allocated

void * instrumentedAlloc(size_t userSize)
{
   const size_t internalSize = CONVERT_USER_TO_INTERNAL_SIZE(userSize);

   void * userPtr = NULL;

   size_t * internalPtr = (size_t *) malloc(internalSize);
   if (internalPtr)
   {
      *internalPtr = internalSize;  // our little header tag so that instrumentedFree() will know how big the allocation was
      _currentlyAllocatedBytes += internalSize;
printf("instrumentedAlloc(%zu):  total allocation count is now %zu\n", internalSize, _currentlyAllocatedBytes);
      userPtr = CONVERT_INTERNAL_TO_USER_POINTER(internalPtr);
   }
   return userPtr;
}

void instrumentedFree(void * userPtr)
{
   if (userPtr)
   {
      size_t * internalPtr = CONVERT_USER_TO_INTERNAL_POINTER(userPtr);
      const size_t allocationSize = *internalPtr;
      _currentlyAllocatedBytes -= allocationSize;
printf("instrumentedFree(%p,%zu):  total allocation count is now %zu\n", userPtr, allocationSize, _currentlyAllocatedBytes);
      free(internalPtr);
   }
}

void * operator new(size_t s) throw ( std::bad_alloc )
{
   void * ret = instrumentedAlloc(s);
   if (ret == NULL) {throw std::bad_alloc ( );}
   return ret;
}

void * operator new[](size_t s) throw ( std::bad_alloc )
{
   void * ret = instrumentedAlloc(s);
   if (ret == NULL) {throw std::bad_alloc ( );}
   return ret;
}

void operator delete(  void * p) throw() {instrumentedFree(p);}
void operator delete[](void * p) throw() {instrumentedFree(p);}

int main(int, char **)
{
   printf("ABOUT TO DECLARE test_map\n");
   std::unordered_map<int, int> test_map;

   printf("ABOUT TO POPULATE test_map\n");
   for (int i=0; i<10; i++) test_map[i] = i;

   printf("ABOUT TO CLEAR test_map\n");
   test_map.clear();

   return 0;
}

…运行时,上述程序将在我的计算机上打印此输出:

Jeremys-Mac-mini-2:~ jaf$ ./a.out
ABOUT TO DECLARE test_map
ABOUT TO POPULATE test_map
instrumentedAlloc(32):  total allocation count is now 32
instrumentedAlloc(24):  total allocation count is now 56
instrumentedAlloc(32):  total allocation count is now 88
instrumentedAlloc(32):  total allocation count is now 120
instrumentedAlloc(48):  total allocation count is now 168
instrumentedFree(0x600003be1128,24):  total allocation count is now 144
instrumentedAlloc(32):  total allocation count is now 176
instrumentedAlloc(32):  total allocation count is now 208
instrumentedAlloc(32):  total allocation count is now 240
instrumentedAlloc(96):  total allocation count is now 336
instrumentedFree(0x6000035e0248,48):  total allocation count is now 288
instrumentedAlloc(32):  total allocation count is now 320
instrumentedAlloc(32):  total allocation count is now 352
instrumentedAlloc(32):  total allocation count is now 384
instrumentedAlloc(32):  total allocation count is now 416
ABOUT TO CLEAR test_map
instrumentedFree(0x600003be1228,32):  total allocation count is now 384
instrumentedFree(0x600003be1208,32):  total allocation count is now 352
instrumentedFree(0x600003be11e8,32):  total allocation count is now 320
instrumentedFree(0x600003be11c8,32):  total allocation count is now 288
instrumentedFree(0x600003be11a8,32):  total allocation count is now 256
instrumentedFree(0x600003be1188,32):  total allocation count is now 224
instrumentedFree(0x600003be1128,32):  total allocation count is now 192
instrumentedFree(0x600003be1168,32):  total allocation count is now 160
instrumentedFree(0x600003be1148,32):  total allocation count is now 128
instrumentedFree(0x600003be1108,32):  total allocation count is now 96
instrumentedFree(0x600001fe00c8,96):  total allocation count is now 0