The number of repetitions in an unordered map

Question

What is the correct way to evaluate unordered_map performance? [C ++ 14]

In my code, I use std :: unordered_map very widely in the order of billions of keys. For performance purposes, I wanted to know the behavior of unordered_map, how many times he had to replay, and all other parameters (how many buckets? How many buckets, where is empty before rebooting?). I know that stl provides the number of buckets. But what else is needed for the profile or what you use for analysis?

Answer 1

As with many std containers, unordered_map has the mandate to grow exponentially. The exact speed is determined by the implementation; You can study the specifications of your implementation or its source code.

As it changes, it is determined. If you wrapped it in a gasket, you can detect these changes by examining the bucket_count before and after each operation that is allowed to grow the container.

You can sort through buckets:

template<class UnorderedMeow>
std::size_t empty_buckets( UnorderedMeow&& meow ) {
  std::size_t r = 0;
  auto buckets = meow.buckets_count();
  for (decltype(buckets) i = 0; i < buckets; ++i)
    if (meow.bucket_size(i)==0)
      ++r;
  return r;
}

to find out how many of them are empty.

If you use the inheritance structure and redefine only those that, as you know, can add / remove material ...

template<class Base>
struct instrumented_unordered_map:Base {
  using Self = instrumented_unordered_map;
  using Base::Base;
  using key_type = Base::key_type; // etc
  struct instrument {
    Self* self;
    instrument( Self* s ):self(s) {
      self->start_instrument();
    }
    ~instrument() {
      self->end_instrument();
    }
  };
  struct instrument_state {
    // blah
  };
  instrument_state state;
  void start_instrument() {
    // populate state
  }
  void end_instrument() {
    // extract from state, generate report
  }
  decltype(auto) operator[]( key_type const& key ) {
    instrument _(this);
    return Base::operator[](key);
  }
  // etc  
};