Why use find() in unordered_map is much faster than directly read?

Question

Its hard to describe so I will just show the code:

#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 
    clock_t start, end; 
    unordered_map<int, int> m;
    long test=0;
    int size = 9999999;
    for (int i=0; i<size/3; i++) {
        m[i] = 1;
    }
    start = clock(); 
    for (int i=0; i<size; i++) {
        //if (m.find(i) != m.end())
            test += m[i];
    }
    end = clock(); 
    double time_taken = double(end - start) / double(CLOCKS_PER_SEC); 
    cout << "Time taken by program is : " << fixed  
         << time_taken << setprecision(5); 
    cout << " sec " << endl; 
    return 0; 
}

The result(3 times): Without if (m.find(i) != m.end()):

Time taken by program is : 3.508257 sec 
Time taken by program is : 3.554726 sec 
Time taken by program is : 3.520102 sec

With if (m.find(i) != m.end())：

Time taken by program is : 1.734134 sec 
Time taken by program is : 1.663341 sec 
Time taken by program is : 1.736100 sec

Can anyone explain why? What really happened inside add m[i] when the key not appeared?

Just to be sure: Have you tried reversing the order of your tests and verifying that the measurements are consistent? With this type of testing, the current state of the cache along with the caching heuristics of the HW itself may well yield an impact (P.S.: I haven't gone through your actual code, under the assumption that it does what you've promised in the description). — goodvibration, Jun 13 '19 at 07:57
This measurement of time doesn't make any sense, because you get two different maps as result, first has 9999999, the other one has only 3333333 items (with `find`). — rafix07, Jun 13 '19 at 07:59
@George: OP use (unordered) map which insert default element with `[]` (contrary to `std::vector`), so no out of bound accesses. — Jarod42, Jun 13 '19 at 08:02
@rafix07 I am on purpose to make some key not appeared in map. To see how it may affect the performance. — Michael, Jun 13 '19 at 08:03
@George I thought it should be zero if key out of first loop... but by experience only. — Michael, Jun 13 '19 at 08:05
*If* you use find already, would be even more efficient to reuse the result: `auto it = find(); if(it != end()) { /* use */ it->second }` — Aconcagua, Jun 13 '19 at 08:09
`operator[]` of `unordered_map` will insert default initialized value if key does not exist. Recommended viewing: https://www.youtube.com/watch?v=lkgszkPnV8g — odyss-jii, Jun 13 '19 at 08:10
You should try to call find, ignore the result and always do `test += m[i];`. See what timings you get. This will show if find is what makes things faster or if it's just its impact on m's content — jpo38, Jun 13 '19 at 08:11
Unrelated, but a must read: [Why should I not #include ?](https://stackoverflow.com/q/31816095/673852) — Ruslan, Jun 13 '19 at 08:12
the most important question hasnt been asked yet: Did you turn on compiler optimizations? What flags did you use to compile? This information should always be included when measuring time. Measuring time with optimizations turned off is meaningless — 463035818_is_not_an_ai, Jun 13 '19 at 08:14
@formerlyknownas_463035818 Yes, I turn off the optimization. Thanks for your comments. Reading. — Michael, Jun 13 '19 at 08:16
1) "_is much faster than directly read_" Technically, it's **not** direct read. The `operator[]` still performs `find` under the hood. 2) "_Yes, I turn off the optimization._" Why did you turn them off, when measuring? Measuring execution time, with optimizations turned off is meaningless. — Algirdas Preidžius, Jun 13 '19 at 08:17
measuring time with optimisation set differently to what you'd use for production release is meaningless. (And yes I have worked at a company where that was how code was released) — Tom Tanner, Jun 13 '19 at 08:22
what do you mean with "I turn off the optimizations" ? Please include the compiler flags you used to compile in the question. Typically you have to turn **on** optimizations because they are off by default — 463035818_is_not_an_ai, Jun 13 '19 at 08:23
@formerlyknownas_463035818 Oh I used online compiler, which has the option to choose optimazation:none. — Michael, Jun 13 '19 at 08:56

463035818_is_not_an_ai · Accepted Answer · 2019-06-13T08:50:22.793

In this line

test += m[i];

the operator[] does two things: First it tries to find the entry for the given key, then if the entry does not exist it creates a new entry.

On the other hand here:

if (m.find(i) != m.end())
        test += m[i];

the operator[] does only one thing: It finds the element with the given key (and because you checked before that it exists, no new entry has to be constructed).

As the map contains only keys up to size/3 your results suggest that creating the element outweights the overhead for first checking if the element does exist.

In the first case there are size elements in the map while in the second there are only size/3 elements in the map. Note that calling operator[] can get more expensive the more elements are in the map. It is Average case: constant, worst case: linear in size. and the same holds for find. However, calling the methods many times, the worst case should amortize and you are left with average constant.

Thanks to Aconcagua, for pointing out that you did not reserve space in the map. In the first case you add many elements that require to allocate space, while in the second, the size of the map stays constant during the part you measure. Try to call reserve before the loop. Naively I would expect that the loops would be very similar in that case.

Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackoverflow.com/rooms/194918/discussion-on-answer-by-formerlyknownas-463035818-why-use-find-in-unordered-ma). — Samuel Liew, Jun 14 '19 at 02:18
Why guess at the performance when it's so easy to actually just measure: https://godbolt.org/z/Ub-Voq -- the performance is not anywhere near similar. — xaxxon, Jun 14 '19 at 06:21
@xaxxon oh interesting, seems like I will have to fix the answer, will do that later — 463035818_is_not_an_ai, Jun 14 '19 at 09:16

Tom Tanner · Answer 2 · 2019-06-13T10:18:16.413

3

The difference with and without the if is down to you having only populated the first third of the map.

If you do a find, then the program will go and find the element, and if it exists then it will do the operator[], which finds it again (not terribly efficient), find it exists, and return the value

Without the if, when you do the operator[]. it will try and find the element, fail, and create the element (with the default value for an int, which is 0), and return it

So without the if, you are populating the whole map, which will increase the runtime.

If you wanted to be more efficient, you could use the result of the find to fetch the value

auto iter = m.find(i);
if (iter != m.end()) 
{
    test += iter->second;
}

edited Jun 13 '19 at 10:18

answered Jun 13 '19 at 08:11

Tom Tanner

9,244
3
33
61

1

It's a map, not a set – so you'd need `test += iter->second` as `*iter` is a pair of key and value... – Aconcagua Jun 13 '19 at 08:39
true. lack of caffeine when answering – Tom Tanner Jun 13 '19 at 10:17

Why use find() in unordered_map is much faster than directly read?

2 Answers2