Understand std::map::insert & emplace with hint

Question

Question> I try to understand the usage of insert & emplace with hint introduced to std::map. During the following test, it seems to me that the old fashion insert is fastest. Did I do something wrong here?

Thank you

static void MapEmplaceWithHint(benchmark::State& state) {
    std::vector v{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    std::map mapInt;
    auto where(std::end(mapInt));
        
  for (auto _ : state) {
   for (const auto &n : v) { // Items in non-incremental order
        where = mapInt.emplace_hint(where, n, n+1);
    }
  }
}
BENCHMARK(MapEmplaceWithHint);

static void MapInsertWithHint(benchmark::State& state) {
    std::vector v{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    std::map mapInt;
    auto where(std::end(mapInt));
        
  for (auto _ : state) {
   for (const auto &n : v) { // Items in non-incremental order
        where = mapInt.insert(where, {n, n+1});
    }
  }
}
BENCHMARK(MapInsertWithHint);

static void MapInsertNoHint(benchmark::State& state) {
    std::vector v{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    std::map mapInt;
        
  for (auto _ : state) {
   for (const auto &n : v) { // Items in non-incremental order
        mapInt.insert({n, n+1});
    }
  }
}
BENCHMARK(MapInsertNoHint);

static void MapReverseInsertNoHint(benchmark::State& state) {
    std::vector v{0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12};
    std::map mapInt;
        
  for (auto _ : state) {
   for (const auto &n : v) { // Items in incremental order
        mapInt.insert({n, n+1});
    }
  }
}
BENCHMARK(MapReverseInsertNoHint);

static void MapEmplaceNoHint(benchmark::State& state) {
    std::vector v{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    std::map mapInt;
        
  for (auto _ : state) {
   for (const auto &n : v) { // Items in non-incremental order
        mapInt.emplace(n, n+1);
    }
  }
}
BENCHMARK(MapEmplaceNoHint);

user_7976805 · Answer

First, let's create a dataset more meaningful than 12 integers:

  std::vector v(10000);
  std::iota(v.rbegin(), v.rend(), 0);

Results from all functions are now more comparable: https://quick-bench.com/q/HW3eYL1RaFMCJvDdGLBJwEbDLdg

However, there's a worse thing. Notice that looping over state makes it perform the same operations several times to measure the average time. But, since you are reusing the same map, each insert or emplace after the first loop iteration is failing, so you mostly measure time of failed inserts, where hint doesn't help.

Test cases should look more like this:

  std::vector v(1000);
  std::iota(v.rbegin(), v.rend(), 0);

  for (auto _ : state) {
    std::map mapInt;
    auto where(std::end(mapInt));
        
   for (const auto &n : v) { // Items in non-incremental order
        where = mapInt.emplace_hint(where, n, n+1);
    }
  }

And with this, hints start to shine (had to limit data to 1000, otherwise I'd get timeouts): https://quick-bench.com/q/2cR4zU_FZ5HQ6owPj9Ka_y9FtZE

I'm not sure if the benchmarks are correct, but quick glance in the assembly suggests that inserts were not optimized altogether, so there's a chance it's good enough.

As noticed by Ted Lyngmo, try_emplace() with hint tends to perform (slightly) better:
https://quick-bench.com/q/evwcw4ovP20qJzfsyl6M-_37HzI

Understand std::map::insert & emplace with hint

1 Answers