Go maps don't appear to be O(1)

https://medium.com/@ConnorPeet/go-maps-are-not-o-1-91c1e61110bf

by alpb • 11 years ago

16 14 11 years ago

medium.com

rudolf0• 11 years ago

Reddit discussion thread: https://www.reddit.com/r/golang/comments/3n0lf8/go_maps_dont...

No consensus regarding the true cause, yet.

mindslight4• 11 years ago

The basic complexity of any map lookup is Ω(log n) - as the number of elements grows, keysize must grow logarithmically (to be able to fit them), and so the comparison time grows as (log n) as well.

With reasonable sizes on common hardware, various operations can be considered constant time. But this can be misleading when, for example, the size of your working set overflows a level of cache hierarchy and your "constant" time changes.

36erhefg2• 11 years ago

That is not what we are measuring. We don't care about the cost of the comparison itself, as long as it stays the same for every element for a chosen key size, but the number of comparisons performed. A hash algorithm, that has a constant number of chains, will always perform a constant number of comparisons, regardless of the key size.

Article makes a different mistake, OP doesn't understand big-O notation and takes his conclusion on a real world example, instead of it being theoretical.

mindslight4• 11 years ago

Sure, the entire goal of a hash construction is to carve out a constant time in a limited context. But the general problem is lower-bounded by (log n), and nothing can change that. The hash appears O(1) because it incorporates large fixed constants, and the working set size never "outruns" that head start.

It's not surprising that the complexity of the general problem could leak through, since various best-case optimizations (eg caching) can erase the head start that was supposed to hide the growth.

SilasX5• 11 years ago

Yes! This has been a big source of frustration for me! That you can't logically look at the hashtable algorithm and derive O(1). Instead, it's some ridiculous gentlemen's agreement where we call it O(1) even though it can't be. See my previous "am I the crazy one here" posts:

https://news.ycombinator.com/item?id=9807739

mindslight4• 11 years ago

Any big-O analysis is necessarily done with a context of assumptions, most importantly the machine model.

You can derive that a hash table is O(1) if you add the assumption that the size of the keys is fixed. This assumption isn't generally wrong, but like all assumptions it has its limits.

I personally think the blind mantra that "hash tables are O(1)" is destructive because it fosters an intuition that they're akin to a pointer dereference and strictly better than trees, when really that constant factor is huge. After all, when memory is bounded (and it always is on any physical machine), every algorithm is O(1)!

Given that the hash table construction is designed specifically to be constant-time on the model of a modern microprocessor, I think it makes sense to look under the hood a bit and see how it really behaves if memory and nkeys are truly unbounded.

And in this case, that result is indeed informative when you start thinking about things like cache hierarchy. The assumption of a table "fitting in memory" goes out the window when for a given size, "memory" could be L2 cache with a higher access speed, or not.

In that previous thread you say:

the defining (good) thing about STEM is that there's actual logic to the discipline, where if I forget an answer, I can re-derive it

Each letter of S.T.E.M. is its own field with its own methods. It's easy to forget this, because when all you're doing is rote learning in school, they seem awfully similar - follow a pattern of technical steps through to its conclusion. Specifically, math works by having a foundation of assumptions for each problem, and outside of that context any solution is meaningless.

For this particular topic, "assume keys are fixed size" is an assumption you just have to memorize the idea of, just like for big-O notation in general you have to memorize the assumption that constant factors don't matter.

Go maps don't appear to be O(1)

Related Stories