abseil-cpp: [Benchmark] flat_hash_map considerably slower than std::unordered_map

This is not a bug report, more of an interesting data point. In the past week I’ve been trying out absl::flat_hash_map and google::dense_hash_map (and sets) and comparing performance to STL counterparts.

The following gist contains benchmarks for STL (Master), abseil and dense_hash_map: https://gist.github.com/bstaletic/7d3e31db7fc8d40a12787fab09ff092f

The project whose benchmark results you’re looking at is https://github.com/Valloric/ycmd The benchmarks test two separate algorithms, FilterAndSortCandidates and IdentifierCompleter.

FilterAndSortCandidates benchmark

This is benchmarking the function of the same name. This one actually has the best timings with abseil.

IdentifierCompleter benchmark

This is benchmarking this piece of code. Surprisingly, abseil is the slowest of the three.

If there’s interest to investigate my benchmark results further, I will gladly provide any information needed.

About this issue

Original URL
State: closed
Created 6 years ago
Comments: 20 (14 by maintainers)

Links to this issue

hashmap benchmarks - what should I add?

Most upvoted comments

Obviously we’d like more information on what’s going in including compilers, build commands, etc, so we can reproduce this ourselves.

However, regardless of which container you are using, one thing I’d like to point out in the IdentifierDatabase::ResultsForQueryAndType() code you linked to:

if (ContainsKey(seen_candidates, candidate) {
  continue;
}
seen_candidates.insert(candidate);

The code above does redundant lookups (it does the same lookup twice - once on find, and once on insert).

This is likely faster:

if (!seen_candidates.insert(candidate).second) {
  continue;
}

derekmauro on Nov 20, 2018