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<int> v{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; std::map<int, int> 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<int> v{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; std::map<int, int> 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<int> v{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; std::map<int, int> 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<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12}; std::map<int, int> 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<int> v{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; std::map<int, int> mapInt; for (auto _ : state) { for (const auto &n : v) { // Items in non-incremental order mapInt.emplace(n, n+1); } } } BENCHMARK(MapEmplaceNoHint);

why the hint is incorrect here? I refer to vishalchovatiya.com/using-std-map-wisely-with-modern-cpp May you please tell me the correct hint? — q0987
– q0987, Commented Apr 12, 2022 at 20:43
Inserts a new element to the container as close as possible to the position just before hint. The element is constructed in-place, i.e. no copy or move operations are performed. The number is in non-incremental order so I assume the hint is correct. — q0987
– q0987, Commented Apr 12, 2022 at 20:47
You did however leave it up to the compiler to optimize away the result. I therefore added benchmark::DoNotOptimize(mapInt); after the inserting/emplacing loop in all the tests. It didn't change the outcome though :-) — Ted Lyngmo
– Ted Lyngmo, Commented Apr 12, 2022 at 20:48
@q0987 Yes, and you do not wish to perform many costly non-essential operation within the loop (because doing so will shadow the results), so it can be tricky. Clearing the target map in the loop, like this, is pretty quick though. Using larger data sets is also useful. You should also use benchmark::DoNotOptimize on a variable that is the target of the whole operation so that the compiler doesn't notice that the result isn't used and throws it all away :-) — Ted Lyngmo
– Ted Lyngmo, Commented Apr 12, 2022 at 21:23

Yksisarvinen · Accepted Answer · 2022-04-12 21:38:59Z

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

 std::vector<int> 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<int> v(1000); std::iota(v.rbegin(), v.rend(), 0); for (auto _ : state) { std::map<int, int> 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

Good! An even more brootal diff can be shown if we clear the target map between each loop or use try_emplace. I'm using try_emplace and clearing the target in the link (overkill since every try_emplace will succeed). Edited: Now even more clear that hinting works
@TedLyngmo Interesting, with clear() emplace_hint performs worse than insert_hint, but good call about try_emplace, it's a definite winner: quick-bench.com/q/nUWwVMJjpxHGLWUvGcmQlY9mrdk.
That was unexpected since both emplace_hint and try_emplace should succeed every time :-) I had the wrong sizes in the first example that you copied though. Here's your example where both makef and maker creates vectors of equal size. I can't say why the diff between emplace_hint and try_emplace isn't shown here though. They used the same sized vectors in your example too.
@TedLyngmo Yeah, I just noticed that and re-run the benchmark, results are now identical: quick-bench.com/q/_YFHh9bcshgsj6J2G5552NINtkA, and the same with 1024*1024:quick-bench.com/q/Qa-mfZ7ZtND8iHr11dz-gaVo7Rk No idea what happened there, maybe a hiccup of the server.
Cool. I ran a test where I cleared the map every other iteration and then the diff between the hinting versions and the non-hinting versions wasn't quite as big - but still well over 2x as fast. quick-bench.com/q/RDtwNm1Lokj0eY1C4s4YeBk-9XU

Collectives™ on Stack Overflow

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

1 Answer 1

7 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Related