What's the size of a node in std::map containing an enum

I am working on reducing memory requirement of my application , for that I am thinking of moving from array of 30 entries ( of which many are empty / NULL ) to an std::map with key as enum and value as the pointer . This way , I will only have the entries I need .

// I create around 50 million objects of my_class type 
class my_class 
{
// I want to change this 
   my_ptr* arr[30];
// to
   std::map<enum_type,my_ptr*> my_map;
};

I create 50 million objects of above class , so I will have 50 million such maps . I want to undertsand whats the size of a single node of std::map .. I read they are implemented as Red-Black trees and each node would hold pointers to children , so I'm guessing at least 16 bytes for children and maybe 8 bytes more for storing the color . Is it better to use std::unordered_map here or should I try a different data structure ?

CodePudding user response：

read they are implemented as Red-Black trees and each node would hold pointers to children

A parent pointer is probably needed as well.

should I try a different data structure ?

If the only thing that you care about is the memory use, then you should use a vector of objects that contain the index and the pointer.

CodePudding user response：

There are different kinds of memory use you can care about. The array has a constant size and no allocations outside of the my_class data structure. Using a map may cause other allocations to happen. Same with a vector.

You might be satisfied if the single object is smaller -- as @eerorika points out, a vector might be index pointer for handwaves 16 bytes, for an empty my_class. The array implementation stays 240 bytes regardless. What about when the object is used? Insert a couple of elements, maybe there's a reallocation happening, and you suddenly get memory fragmentation, overhead from the underlying allocation libraries, etc.

Here is a highly unportable example using jemalloc's malloc_stats_print() to show what might be going on:

#include <malloc_np.h>
#include <stdio.h>
#include <stdlib.h>

#include <map>

struct my_ptr;
struct my_class_arr {
  my_ptr *arr[30];
};
struct my_class_map {
  std::map<int, my_ptr *> my_map;
};

int main(int argc, char **argv) {
  constexpr const int million = 1000000;

  printf("Memory usage before:\n");
  malloc_stats_print(nullptr, nullptr, nullptr);
  if (argc > 1) {
    auto *arr = new my_class_arr[million];
    arr[17].arr[3] = nullptr;
  } else {
    auto *map = new my_class_map[million];
    map[17].my_map[3] = nullptr;
  }

  printf("Memory usage after:\n");
  malloc_stats_print(nullptr, nullptr, nullptr);

  return 0;
}

Stats are printed on program startup, and after allocating a million objects. I believe the Allocated line in the (very verbose!) output is the most relevant. Just run it with no args for the array approach, or with an argument to use the map structures.

Using clang, no optimization (beware the uselessness of no optimization!):

./a.out 2>&1 | grep ^Allocated
Allocated: 69640, active: 77824, metadata: 4509640 (n_thp 0), resident: 4562944, mapped: 6369280, retained: 2019328
Allocated: 25240896, active: 25276416, metadata: 4551504 (n_thp 0), resident: 29810688, mapped: 33669120, retained: 6176768

Doing a little table of the second line of output for various combinations:

unoptimized, array: 25240896
unoptimized, map: 268505728 (over 10x as much)
optimized -O3, array: 25240896 (unchanged)
optimized -O3, map: 69640 (the compiler clearly knows something I don't)

Or, to put it more generically: measure (for your specific uses), don't guess.