Differences/similarities between llvm::DenseMap and std::map

Question

Recently I came across DenseMap data structure which is widely used in llvm. I think it is some sort of optimized version of std::map(?). Could anyone help me understand the difference or similarities between them?

Answer 1

llvm::DenseMap is a replacement for std::unordered_map, so it's not quite meant to replace std::map (at least not if you've carefully chosen based on the ordered vs. unordered properties).

Unlike std::unordered_map, std::map guarantees that the iteration order of the container matches the order defined by your comparator (by default, std::less). In many cases, you don't care about iteration order... but in the few cases where it matters, DenseMap isn't an option.

Now, to contrast DenseMap with std::unordered_map: unlike the std container, DenseMap keeps all its data in one memory allocation, and it does away with buckets in favor of keeping keys and values next to each other in memory. Both these features are a big win for data locality and thus speed in nearly all contexts.

In addition, DenseMap allocates a large number of key/value pairs by default (64, in fact), so at small sizes, insertions are nearly free. The downside of that, of course, is that it’s memory inefficient if you’re creating a lot of very small maps, or if your types themselves are large; if your container will never grow to 64 elements, you're wasting memory. That may or may not actually hurt you depending on your use case.

One final difference compared to std::unordered_map can catch some people off guard: a DenseMap's iterators are invalidated after every insertion (unlike std::map and std::unordered_map, where the iterators are only invalidated if a cache rehashing occurs). This strikes me as mostly a theoretical problem, since you could of course just store the keys rather than iterators. (And unlike with vectors, it's rather uncommon to find real code that retains map iterators.)

I've put together some benchmarks comparing DenseMap to the std containers, as well as a GitHub repo if you'd like to run the benchmarks on your own machine. Four selected graphs are below, showing insertion and random lookup speeds for maps at various sizes.

Insertion speeds in small maps

Insertion speeds in large maps

Random lookups in small maps

Random lookups in large maps