Performance difference for iteration over all elements std::unordered_map vs std::map?

Question

I wanted to map data with pointer as the key. What container should I have chosen, map or unordered_map? There are multiple questions on stackoverflow for this topic but none of them covers the performance aspect when we need to iterate over all the key-value pairs.

std::map<classKey* , classData*> myMap;
std::unordered_map<classKey* , classData*> myUnorderedMap;

for (auto & iter : myMap) { //loop1
    display(iter.second);
}

for (auto & iter : myUnorderedMap) { //loop2
    display(iter.second);
}

loop1 vs loop2 which one gives better performance. Bench Mark Provided by @RetiredNinja

For size = 10,000,000 We get following benchmark results:

Interesting. Off had I have no idea. I'd put my money on `std::map` though. Are you able to set up some test cases for profiling? — Bathsheba, Jun 30 '19 at 14:28
Structurally, I would expect `std::map` to be slightly faster, but that the difference would be small enough to be swamped by other concerns (like whether the elements of either one were in your cache) — Marshall Clow, Jun 30 '19 at 14:31
Possible duplicate of [C++ std::unordered\_map complexity](https://stackoverflow.com/questions/19610457/c-stdunordered-map-complexity) — Michael Chourdakis, Jun 30 '19 at 14:34
@MichaelChourdakis again, OP asks about performance, not efficiency regarding time complexities. — Fureeish, Jun 30 '19 at 14:35
@Fureeish OP throws some codes in and claims that one performs better than the other, without giving any reproducible proof. — πάντα ῥεῖ, Jun 30 '19 at 14:45
It's likely people only talk about algorithmic complexity because different implementations of the standard library would of course have different efficiencies. That aside, *(though I haven't tested anything)* my money's on `unordered_map` because I see it used more often than `map` and therefore it would be a good target for optimization efforts. — Cruz Jean, Jun 30 '19 at 14:45
@πάνταῥεῖ I am not denying that. I think the question needs quite a lot of work. But we can agree that the main point is performance, not efficiency, correct? — Fureeish, Jun 30 '19 at 14:46
@Fureeish _Efficiency_ needs to have additional definitions by which means exactly anyways. — πάντα ῥεῖ, Jun 30 '19 at 14:48
@πάνταῥεῖ, I forgot which lecture (actually regarding the C++ data structures) was it, but the lecturer presented there a pretty simple and, as I thought, quite universal answer to that - efficiency is *how many operations* need to be done. An algorithm can be *efficient*. Performance, however, is how fast that algorithm runs. There can be more efficient algorithms with worse performance and vice versa. Recall quicksort vs bubblesort on a specific data. I can't, however, find that lecture (it's *somewhere* on YouTube) or quickly find any papers backing up this statement. — Fureeish, Jun 30 '19 at 14:54
@Fureeish _Efficiency_ can be meant _by memory consumption_, _by CPU resource consumption_. etc. It needs more specific definition, and can't stand alone. — πάντα ῥεῖ, Jun 30 '19 at 14:56
@πάνταῥεῖ agreed, however I do believe that when people can differentiate efficiency and performance in general case, one can pretty safely assume how it applies here. Although you are correct (and I already agreed) that the question and discussion itself needs clarification regarding quite a number of things. — Fureeish, Jun 30 '19 at 14:58
@Fureeish Well, at least I've been asking the OP to give a proof for their observations. As is that question is pretty useless and should be closed. — πάντα ῥεῖ, Jun 30 '19 at 15:01
@RetiredNinja Thanks for generating this. I didn't know about quick-bench. It looks like a handy tool. I was in the process of generating data om my machine. — nav_jan, Jun 30 '19 at 15:32
Quick Bench is outstanding; [have used it to great effect](https://stackoverflow.com/q/54237547/560648) (if I do say so myself) — Lightness Races in Orbit, Jun 30 '19 at 16:17
@nav_jan If I follow the quick-bench link, I see no major difference between the two. If the online benchmark data are valid, can you please revise your figure above? Otherwise it is quite misleading. (Obligatory SO caveat: I understand the limitations of simple benchmarks, so please do not go off-topic in any reply to this comment. Thanks.) — THK, Apr 02 '20 at 17:27
@RetiredNinja Your benchmark seems incorrect. The first function to get benchmarked seems to always be faster than the second, no matter which is order they're in. Please revise your link. — Chris, Apr 27 '23 at 01:56
Here's a corrected version https://quick-bench.com/q/4v7ZUDmGu7OzopNOWck70-SqqHw — Chris, Apr 27 '23 at 02:14

JimPri · Answer 1 · 2019-06-30T15:47:46.687

7

As you might expect, this depends heavily on the actual implementation of the standard library data structures. Therefore, this answer will be a bit more theoretical and less tied to any one implementation.

A std::map uses a balanced binary tree under the covers. This is why it has O(log(n)) insertion, deletion, and lookup. Iterating over it should be linear because you just have to do a depth-first traversal (which will require O(log(n)) memory in the form of stack space). The benefit of using a std::map for iteration is that you will iterate over the keys in sorted order and you will get that benefit "for free".

A std::unordered_map uses a hash table under the covers. This allows you to have an amortized constant time insertion, deletion, and lookup. If the implementation is not optimized for iterating, a naive approach would be to iterate over every bucket in the hash table. Since a good hash table (in theory) has exactly one element in 50% of the buckets and zero in the rest, this operation will also be linear. However, it will take more "wall clock time" than the same linear operation for a std::map. To get around this, some hash table implementations keep a side list of all of the elements for fast iterations. If this is the case, iterating on a std::unordered_map will be faster because you can't get much better than iterating over contiguous memory (still linear time though, obviously).

In the extremely unlikely case that you actually need to optimize to this level (instead of just being curious about the performance in theory), you likely have much bigger performance bottlenecks elsewhere in your code.

All of this ignores the oddity of keying off of a pointer value, but that's neither here nor there.

Sources for further reading:

GCC std::map implementation

GCC std::unordered_map implementation

How GCC std::unordered_map achieves fast iteration

edited Jun 30 '19 at 15:47

answered Jun 30 '19 at 15:05

JimPri

1,278
8
17

_"A std::map uses a balanced binary tree under the covers"_, _"A std::unordered_map uses a hash table under the covers."_ Any reliable source for these claims? – πάντα ῥεῖ Jun 30 '19 at 15:09
Admittedly, it is a broad statement since there is nothing explicitly in the standard to require those design choices. However, both the GCC and MS VS compilers implement them this way (as do most well known compilers). – JimPri Jun 30 '19 at 15:12
1

@πάνταῥεῖ humanity's inability to (so far) come up with better implementations satisfying standard's requirements combined with no contraindications to implement the structures in such a way is, for me, enough to assume this (or close to this) implementation. Yes, the standard says nothing about the concrete implementations, but what else do we got? – Fureeish Jun 30 '19 at 15:23
Your last source says that the hash map keeps a **linked** list of iterators(= **pointers** ) to buckets. That is not contiguous at all(2 indirections). Only buckets will be. And there's no reason why the map cannot do the same with nodes. I would really like to see some measurements as an answer. – Quimby Jun 30 '19 at 16:02
_"A std::map uses a balanced binary tree under the covers. This is why it has O(log(n)) insertion, deletion, and lookup."_ That's backwards. A tree is usually used under the covers so that it can abide by the standard's complexity requirements. _(Okay, those complexity requirements originally came from the properties of trees. But the standard doesn't know that!)_ – Lightness Races in Orbit Jun 30 '19 at 16:15
1

"Iterating over it should be linear because you just have to do a depth-first traversal (which will require O(log(n)) memory in the form of stack space)." - That's not how `std::map` iterators work. They are external iterators and cannot allocate any stack space. Incrementing a tree iterator is only *amortized* constant time. (Iterating over the entire tree is still linear.) See here: https://github.com/gcc-mirror/gcc/blob/41d6b10e96a1de98e90a7c0378437c3255814b16/libstdc%2B%2B-v3/src/c%2B%2B98/tree.cc – Sebastian Redl Jun 30 '19 at 16:37
As for the fancy iteration trick GCC's `unordered_map` does, I'm pretty sure, but can't find the legalese to back it up, that this is essentially required behavior. Iteration of any container must be O(N) in the number of elements; if the hashtable wasn't able to skip empty buckets (by threading a linked list through all nodes), iteration would be O(B+E), where E is the number of elements and B the number of buckets. – Sebastian Redl Jul 03 '19 at 16:33
Found it: [iterator.requirements.general]p13 (as of N4820) specifies that all iterator operations must be amortized constant time. That includes incrementing hash table iterators. – Sebastian Redl Jul 03 '19 at 16:51
I'm dying over "All of this ignores the oddity of keying off of a pointer value, but that's neither here nor there" – pcdangio Jan 21 '23 at 01:51

Performance difference for iteration over all elements std::unordered_map vs std::map?

1 Answers1