Go maps don't appear to be O(1)(medium.com)
medium.com
Go maps don't appear to be O(1)
https://medium.com/@ConnorPeet/go-maps-are-not-o-1-91c1e61110bf
15 comments
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
https://news.ycombinator.com/item?id=9807739
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.
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.
Having to "memorize" the idea of assuming bounded key size is fine.
What's not fine is selectively making that assumption without being aware of it, resulting in a situation where the kewl kids recite back "hashtables are O(1)" with no understanding of why, or what different assumptions you have to make to get there, resulting in an exception-laden body of knowledge. That's not what rigor looks like.
One time I was asked for the run time of a random-line-getter function for a file that seeks to a random byte and fans out to the line breaks. I said, "well, that would depend, not on the file size, but the line length, and it would be linear in that."
He "got me": "Wrong, it's constant." Indeed, if you implicitly assume that relevant parameter is file size, and don't understand the implications of "does not depend on ...", then you can compare answers against an answer key and regard someone as wrong for not saying exactly that.
"Hashtables are O(1)" results from exactly that lack of rigor, where it's all a game of which password to spit back, rather than "can you identify the constraints on solving this problem?"
What's not fine is selectively making that assumption without being aware of it, resulting in a situation where the kewl kids recite back "hashtables are O(1)" with no understanding of why, or what different assumptions you have to make to get there, resulting in an exception-laden body of knowledge. That's not what rigor looks like.
One time I was asked for the run time of a random-line-getter function for a file that seeks to a random byte and fans out to the line breaks. I said, "well, that would depend, not on the file size, but the line length, and it would be linear in that."
He "got me": "Wrong, it's constant." Indeed, if you implicitly assume that relevant parameter is file size, and don't understand the implications of "does not depend on ...", then you can compare answers against an answer key and regard someone as wrong for not saying exactly that.
"Hashtables are O(1)" results from exactly that lack of rigor, where it's all a game of which password to spit back, rather than "can you identify the constraints on solving this problem?"
I totally agree but for one point - seek() in a file is probably O(log <filesize>). So he wasn't even right in his own context...
Right, but the point is, even under the assumption of constant seek times, he didn't seem to get that "doesn't not depend on x" is the same as "constant [implicitly taking the only relevant parameter to be x]".
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.
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.
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.
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.
Actually in the theoretical world, the cost is always O(1) because the hash function computation always takes constant time. You are restricting yourself to a machine model with bits, which is not assumed by big-O notation.
But it doesn't even work in that theoretical world: as n gets arbitrarily large, you've used up all the keys and they have to start sharing buckets, forcing you to iterate over O(n) of them -- although the constant on that is only logarithmic in the size of the hash function output space (aka linear in the size of hash output)!
Edit: clarify and fix error.
Edit: clarify and fix error.
Generally you move to a larger hash table long before you get that much key collision. Which is a big cost once, but the amortized cost doesn't change much.
But in general with these discussions, you assume that certain operations are constant on your "machine". For instance, addition is usually considered constant even though it isn't if your numbers are larger than your machine's word size.
In the case of the hash tables, you assume your hash is constant, even if, as you note, it isn't really. But the fact is, the coefficient for the O(log N) term is so small, that it doesn't really offer any useful insight towards the performance of the algorithm.
But in general with these discussions, you assume that certain operations are constant on your "machine". For instance, addition is usually considered constant even though it isn't if your numbers are larger than your machine's word size.
In the case of the hash tables, you assume your hash is constant, even if, as you note, it isn't really. But the fact is, the coefficient for the O(log N) term is so small, that it doesn't really offer any useful insight towards the performance of the algorithm.
>Generally you move to a larger hash table long before you get that much key collision. Which is a big cost once, but the amortized cost doesn't change much.
No, it's a big cost every time you pass a threshold, which happens an infinite number of times, because big-O assumes numbers can be arbitrarily large.
>But in general with these discussions, you assume that certain operations are constant on your "machine". For instance, addition is usually considered constant even though it isn't if your numbers are larger than your machine's word size.
As long as the max number size is orthogonal to the number of elements n, you can assume a bound on the time for an addition operation, and then it becomes a constant in your run-time expression with respect to n. No sleight-of-hand there.
>In the case of the hash tables, you assume your hash is constant, even if, as you note, it isn't really. But the fact is, the coefficient for the O(log N) term is so small, that it doesn't really offer any useful insight towards the performance of the algorithm.
All true, but the spec for big-O doesn't say "assume away stuff that doesn't matter in practice". It says, "as n gets arbitrarily large". When you make inconsistent, varying assumptions between problems, you're not doing STEM anymore; you're doing memorization, the kind of thing STEM isn't supposed to be like.
If "the" definition of big-O consistently included a definition that "we never have to deal with more than 2^64 elements", that would be fine. Instead, we have to memorize "the right answers" for when you can and can't assume that, and only then does O(1) for hash lookup pop out.
And if you really just care about in-practice, then you can no safely assume that a typical balanced binary tree lookup takes fewer ops than e.g. SHA256.
No, it's a big cost every time you pass a threshold, which happens an infinite number of times, because big-O assumes numbers can be arbitrarily large.
>But in general with these discussions, you assume that certain operations are constant on your "machine". For instance, addition is usually considered constant even though it isn't if your numbers are larger than your machine's word size.
As long as the max number size is orthogonal to the number of elements n, you can assume a bound on the time for an addition operation, and then it becomes a constant in your run-time expression with respect to n. No sleight-of-hand there.
>In the case of the hash tables, you assume your hash is constant, even if, as you note, it isn't really. But the fact is, the coefficient for the O(log N) term is so small, that it doesn't really offer any useful insight towards the performance of the algorithm.
All true, but the spec for big-O doesn't say "assume away stuff that doesn't matter in practice". It says, "as n gets arbitrarily large". When you make inconsistent, varying assumptions between problems, you're not doing STEM anymore; you're doing memorization, the kind of thing STEM isn't supposed to be like.
If "the" definition of big-O consistently included a definition that "we never have to deal with more than 2^64 elements", that would be fine. Instead, we have to memorize "the right answers" for when you can and can't assume that, and only then does O(1) for hash lookup pop out.
And if you really just care about in-practice, then you can no safely assume that a typical balanced binary tree lookup takes fewer ops than e.g. SHA256.
> No, it's a big cost every time you pass a threshold, which happens an infinite number of times, because big-O assumes numbers can be arbitrarily large.
Yes, it happens repeatedly. But it's not a big cost on every operation. Instead, it's a bigger and bigger cost, that happens more and more rarely. Averaged over the run, it's insignificant.
> As long as the max number size is orthogonal to the number of elements n, you can assume a bound on the time for an addition operation, and then it becomes a constant in your run-time expression with respect to n.
But it isn't necessarily orthogonal. As you deal with more and more elements, it's probably true that those elements will get correspondingly large. But maybe they won't be! The point is, we've decided that that is not a significant issue, since it's not part of most algorithms involving addition.
> All true, but the spec for big-O doesn't say "assume away stuff that doesn't matter in practice"
Of course it does. Everything is built on axioms and assumptions; things that are relevant to the problem, and things that are not.
> When you make inconsistent, varying assumptions between problems, you're not doing STEM anymore; you're doing memorization, the kind of thing STEM isn't supposed to be like.
I have no idea where this came from, but it's neither relevant nor accurate. Every STEM field requires a significant amount of memorization, and any application of a STEM field requires understanding what is relevant to the discussion at hand, and what is not.
The point of any system—Big O included—is to understand a problem. The cost of the hashing operation isn't relevant for understanding the performance characteristics of hash tables. Maybe your hashing function is O(log N), and so lookups are O(log N). Maybe your hashing algorithm is O(N^2), and so your lookups are O(N^2). Neither tells you anything about how your hash will perform.
Yes, it happens repeatedly. But it's not a big cost on every operation. Instead, it's a bigger and bigger cost, that happens more and more rarely. Averaged over the run, it's insignificant.
> As long as the max number size is orthogonal to the number of elements n, you can assume a bound on the time for an addition operation, and then it becomes a constant in your run-time expression with respect to n.
But it isn't necessarily orthogonal. As you deal with more and more elements, it's probably true that those elements will get correspondingly large. But maybe they won't be! The point is, we've decided that that is not a significant issue, since it's not part of most algorithms involving addition.
> All true, but the spec for big-O doesn't say "assume away stuff that doesn't matter in practice"
Of course it does. Everything is built on axioms and assumptions; things that are relevant to the problem, and things that are not.
> When you make inconsistent, varying assumptions between problems, you're not doing STEM anymore; you're doing memorization, the kind of thing STEM isn't supposed to be like.
I have no idea where this came from, but it's neither relevant nor accurate. Every STEM field requires a significant amount of memorization, and any application of a STEM field requires understanding what is relevant to the discussion at hand, and what is not.
The point of any system—Big O included—is to understand a problem. The cost of the hashing operation isn't relevant for understanding the performance characteristics of hash tables. Maybe your hashing function is O(log N), and so lookups are O(log N). Maybe your hashing algorithm is O(N^2), and so your lookups are O(N^2). Neither tells you anything about how your hash will perform.
[deleted]
Reddit discussion thread: https://www.reddit.com/r/golang/comments/3n0lf8/go_maps_dont...
No consensus regarding the true cause, yet.
No consensus regarding the true cause, yet.
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.