Is this slower because of two lookups instead of one?

Question

When I want to make sure that the entry I want to use exists, I usually do this.

#include <unordered_map>

struct type { int member; };
std::unordered_map<type> map;

if (map.find(key) != map.end())
    map[key].member = 42;

However, I think it performs two lookups for key in the hash map. This caches the lookup.

#include <unordered_map>

struct type { int member; };
std::unordered_map<type> map;

auto find = map.find(key);
if (find != map.end())
    find->second.member = 42;

The first option feels way more expressive. Is it really slower?

Answer 1

It may be slower, it may not (you're now doing an extra write in your "speed up") but one really shouldn't worry about such minor optimisations when writing code. Write clear expressive code. Then if your program really is too slow, run profiling tools on it and find your bottleneck(s). If this code is in fact a real problem, then and only then try your "speed up" and see if it matters.

Answer 2

Yes, because you search the key twice: map[key] search for the key exactly like map.find, of which you threw away the result.

It's like open a drawer to see if there is a given object, say "ah yes!" and close the drawer, then open it up again and research the object to change it.

The second code opens the drawer, search for an object and change it.

There can be compiler optimizations that allow to avoid the double search, or that may reduce the search in constant time, and there can be compiler optimization that allow to avoid the auto find variable to be stored on memory (it can be a CPU register, since it usage is very local).

The entire problem, will in effect reduce in comparing the time for twice hash computation twice (and walk the eventual map slot, in case of hash collision) and the time to access the extra variable:

2*H < H+M

That means H < M. If M is a register and H is not trivial, it's hard for H to be less than M.

Answer 3

Yes, it may be slower but probably not measurably slower. There is some extra work involved:

1. The hash will likely to be computed twice, unless you have sufficiently smart compiler , use vendor extentions such as pure or const or use similar method. Note that if hash is trivial and compiler knows it's code most of compilers probably are sufficiently smart nowadays.
2. The position of bucket needs to be found second time (unless compiler will notice that this is the same hash so it doesn't need to recompute)
3. The traversal of collision lists (or similar method depending on the collision resolution) needs to be performed. Again - sufficiently smart compiler might notice we are doing it twice, we don't actually modify anything etc. we might have such compilers nowadays but I'm not 100% sure if we are there. Even if they aren't they are cached reads and they probably will not impose any significant cost (compared to for example taking a hash or missed read). Not going into details of processor architecture L1$ read hit takes ~4 cycles latency on i7 (data from memory, might be wrong) and processor may do other work while waiting on it.

So to sum up if:

• Your hash function is expensive (for example it needs to take a hash of a string).
• The compiler is insufficiently smart to deduce that hash function does not modify the object and indeed return the same value.
• It's code in inner loop.

then you might see a difference.

---

As a final word - it probably won't matter and it's not big architectural difference but 5s optimization. So write whatever you find easier to maintain and revisit the question when the profiler will show that this functions causes a slowdown.