7 ms·

The problem with this analysis is that in the graph in the very first part he shows that memory access IS O(1) for pretty substantial scaling factors, and then

The problem with this analysis is that in the graph in the very first part he shows that memory access IS O(1) for pretty substantial scaling factors, and then when you hit some limit(e.g. size of cache, size of RAM) access times increase very rapidly. Sure, if you draw a line across 6 orders of magnitude, it ends up looking like O(n^1/2), but how often do you scale something through 6 orders of magnitude? The "memory access is O(1)" approximation is pretty good, certainly good enough for almost all every day use. The median size of a hash table I allocate definitely fits in L1 cache, so why shouldn't I think of it as O(1)? If you are reading off of disk, the O(1) approximation holds as long as your dataset stays between 1 MB and 1 GB. That's quite a bit of room to play around in. Yes, you need to be aware of access times and the changes in them if you are really scaling something way up. But I'm not convinced that I shouldn't just keep thinking of "hash access is O(1)" as a convenient, generally accurate shortcut.

stdbrouw 10y ago
You're failing to account for the fact that it's a log-log graph, though, so even a modest slope can be pretty significant. If you want a rule of thumb, might as well just stick to "hash tables are fast" instead of the false precision of O-notation.
- jimminy 10y ago
  Big O-notation isn't precise, it is an approximation by nature. It only cares about the largest factors for determining the estimate.
  - epistasis 10y ago
    The log-log graph is the way to determine those large factors. Taking the log removes the multiplicative constants. The differences between n^.5 and n^1 and n^1.5 are quite significant for big-o
- aaronbwebber 10y ago
  The graph really is totally flat below the L1 cache size line, and even on a log-log graph the slope between 10 MB and 1 GB is not significant.
  - AstralStorm 10y ago
    That being kB range for L1, single digit MB for L2. Relatively simple Java apps tend to eat multiple GB, while accessing most of it.
malisper 10y ago
The definition of big-O is what happens as n approaches infinity. You are free to model your computer as having O(1) memory access as it's a much simpler model and close enough in practice.
- adrianratnapala 10y ago
  As N climbs orders of magnitude, we start using ever more distant kinds of memory, so access time does not scale as O(1) in theory. As for practice, it's not O(1) either or else cache misses would just be a theoretical nicety that didn't matter in the real world.
  - malisper 10y ago
    If you make the assumption that there is an upper bound on the maximum time a read can take (e.g. reading from disk), reading from memory becomes an O(1) operation regardless of cache misses.
    - mindslight 10y ago
      By similar assumption, every terminating algorithm running on a real computer (having bounded memory) is O(1). This is technically true, but not useful. Most people assume the average memory access will be reasonably fast (why we have a cache hierarchy in the first place). Sometimes the growth of it matters, sometimes it does not. Algorithm complexity is not something to be memorized, but analyzed.
      - malisper 10y ago
        The assumption that the computer you are modeling has an infinite amount of memory finite number of caches is a useful assumption as it dramatically simplifies the analysis and still allows you to use big-O to somewhat accurately analyze the performance of a real computer.
        mindslight 10y ago
xenadu02 10y ago
It is trivial to exceed the L1 cache size and not that uncommon to exceed L2. That brings us to a 100x delta which is worth thinking about, no? Even exceeding L3 isn't horribly rare for average desktop CPUs (let alone mobile devices). There are other dimensions to this too like prefetching, streaming, pipelining, vectorization, etc. In some cases using an array and doing a linear search is faster than any hashmap on a modern CPU. I think the takeaway from this article is not to blindly trust the theoretical big-O numbers for data structures and actually test them with realistic datasets on your target hardware.
- aaronbwebber 10y ago
  This is a very good point. You should run actual performance tests. The results may surprise you! In my actual work, optimizing in memory searches is not worthwhile because saving half a dozen microseconds on a search is not real valuable when you are about to spend half a dozen milliseconds making a database call (which is technically O(log N), since there's a B-tree index back there). But I do spend quite a bit of time figuring out which of those queries should be moved to an in-memory O(1) cache (redis or memcache, depending). And I actually never think about the perf tradeoff between the DB and the cache being O(log N) vs O(1) - I think of it in terms of the median and 99th %tile times that I know from monitoring our actual production servers. So as xenadu points out, I guess there is some truth in the article, but it's just sort of lost in this somewhat academic discussion of scaling things to infinity and beyond.
  - deleted 10y ago
    [deleted]
  - AstralStorm 10y ago
    Random percentile abuse. 99% is less useful than a median. The real data is a true histogram as well as maximum time. 99% might mean every 100th customer does not get a service.
  - pjc50 10y ago
    In my actual work, optimizing in memory searches is not worthwhile Funnily enough, I had to do this last week. We started from the question "why does it take 160ms to scan 60,000 objects in memory?" and reached the disappointing conclusion that, on this particular platform (iMX6/800MHz/DDR3) a cache miss costs you an astonishing 233ns. I got as far as double-checking all the RAM initialisation parameters before giving up. There is now an index on the in-memory search.
nbadg 10y ago
I think that the "best" message here is that the performance of memory access, hash lookup, etc, is a more complicated question than always just O(1). Knowing the context -- basically, the second-to-last graph that highlights performance vs size vs cache limits -- is the bigger picture for the system. And it's perfectly usable everyday, you just have to remember a few more words: "memory access is O(1) as long as I stay within L1". The problem I have with the article is that the author has replaced one broad generalization with another equally reductive but diametrically opposed one. It's no more accurate, and no more decontextualized, than the original statement, and in my head that means it's also not really all that useful.
- AstralStorm 10y ago
  Simpler version: locality of data matters a lot.
jcbeard 10y ago
I agree with aaronbwebber that for general use, and for teaching, that it's far easier to assume O(1) memory access. It's a decent approximation, and works until you start having applications where loads/stores dominate. It also falls apart when things like multi-threaded apps start spinning on locks, but lets not go there in a HN post, could make an entire blog out of mem issues. Here's why we should continue to use O(1) access in general. Unless you enjoy rat-holes (I wouldn't have a job without them...so, why not). If we really wanted to, for every algorithm we could consider things like: 1) pre-fetch algorithm (assuming you know which one will be chosen) 2) associativity 3) cache size at each level (including buffering) 4) queueing depth at all levels 5) DDR controller capacity & while we're at it, do we have latency of mem controller on-chip..wait, which one? 6) bank conflicts in DDR 7) NUMAness (how about NUMA cache behavior?) 8) even worse...should we consider cost of differing mem tech. 9) TLB behavior...there's a lot there, can't list Here's why we don't: YOU CAN'T. Do you realize the incredible amount of work required to get the info for the analysis? The list of things that influence memory behavior is huge. Even if you can get all of it, you work it out for one algorithm...you've now wasted a year, and figured out a cost for one architecture/OS/run-time combo. Congratulations. I'm all for including the cost of memory...just realize what you're asking before you write a post asking about it. There's no end to how detailed you want to go. And in the end you end up destroying the asymptotic bound you're trying to create b/c you'll realize that it's now a probability distribution that really doesn't lend itself to generalizable asymptotic behavior, which is what you want when considering algorithms. When choosing an algorithm for a specific hardware, then you can choose an algorithm for that arch.....but most people don't do this, it's not necessary unless you're in HPC, Datacenter scale analytics, or in the embedded space/cyper-physical space.
- xenadu02 10y ago
  Permit me to disagree; I think it is useful to internalize the general rule that for every 100x increase in data size the theoretical performance will drop by 10x. This isn't a perfect rule but it is just as valid a shortcut as saying hash lookups are O(1). For all intents and purposes all modern CPU hardware works the same way (a cache hierarchy, superscalar, pipelined, with relatively slow DRAM hanging off some bus). In practice measure different approaches to performance-critical code with realistic datasets and don't make assumptions. Don't assume that you know dictionaries are O(1) and therefore searching an array must be slower.
sabarn01 10y ago
It happens all the time. In real world code people throw hash tables and maps at all types of problems of all sizes. If you hit arbitrary boundaries where your fundamental assertion of access time becomes non constant its an issue. This post might spur new thought about containers and how there usage should really be governed by their expected capacity.
krinchan 10y ago
I always thought the Big-O notation was purely to compare one algorithm to another, not actually measure literal, real world performance. Trying to describe a hardware operation in Big-O notation then assert everyone should something other than O(1) for a memory access operation seems like a gross misunderstanding of its purpose.
- fapjacks 10y ago
  This right here is the most relevant response to the article.
- TillE 10y ago
  Specifically, Big-O describes the relative performance of an algorithm as the input grows. That's why constants are discarded, and that's why O(n^2) is probably fine if you only ever have very small data sets.
- bzbarsky 10y ago
  Big-O notation is there purely to compare one algorithm to another, yes. But in terms of what? Say you have two search algorithms. For a dataset of size N, Algorithm 1 does N memory reads and N data compares. Algorithm 2 does N * (log N) memory reads and log N data compares. These are not real algorithms, just illustrations. It's not uncommon in the analysis of such algorithms (both searching and sorting) to only consider the number of data compares and assume memory reads are completely free. So that would give you O(N) for algorithm 1 and O(log N) for algorithm 2. Analyses with more sophistication will note that a memory read is not in fact free, and will look at the number of "operations", whether those be memory reads or compares. In terms of the number of "operations", algorithm 1 is O(N) and algorithm 2 is O(N log N). These are both true statements about these algorithms: Algorithm 2 is O(log N) if you look at number of compares and O(N log N) if you look at number of "operations". Which of these characterizations is more relevant to you? Depends on whether memory reads are actually free in your setup. Anyway, the original article is arguing that for the comparison most people care about, wall clock time, even the more sophisticated version is wrong, because it assumes that the time needed per operation does not depend on N, so you can just count all the operations and not worry about their relative speed, because that's just a constant factor. If the time taken for a memory read _does_ depend on N, then you can't do that. For example, if you want to look at the algorithmic complexity of these algorithms in terms of clock cycles, and a compare is one clock cycle (might not be, depending on what your data is!) and a memory read if sqrt(N) clock cycles (due to caching effects), then the complexity of algorithm 2 will be O(N * sqrt N * log N), whereas algorithm 1 is O(N * sqrt N). Of course once you're caring about actual time very often constant factors start to matter too, and the whole idea of doing asymptotic analysis might break down. But it might not. It really depends on your exact problem and on the assumptions underlying the asymptotic analysis...
smallnamespace 10y ago
> but how often do you scale something through 6 orders of magnitude? Well, that's the whole point of using big-O notation. Otherwise, there's no point in distinguishing between O(1) and O(lg N) either--lg(10^6) is only ~20, after all.
klodolph 10y ago
> but how often do you scale something through 6 orders of magnitude? I can't speak for others but the team I'm on has a mind-boggling amount of data. 6 orders of magnitude is not even close (no, I'm not doing something clever like starting with "byte" or "bit" as smallest unit). The truth is most people don't have "big data" but plenty of people do—petabyte scale is becoming pedestrian these days and a few larger organizations are into the exabyte range. Latency grows as you go from registers to RAM to hard drives in distant data centers. Consider that data centers don't really stack on top of each other, they have to be built flat or you can't get rid of the waste heat fast enough. Same with microprocessors and RAM. Everything is flat, in practice, with a limit to how much it gets stacked. Maybe you think that this is a special case, but with everyone building their applications on top of the same cloud providers, your provider's scalability starts to affect you personally. So even if you build a small application in the cloud, your ability to access data is impacted by the fact that your cloud provider is providing access to exabytes of data.
rocqua 10y ago
One can move across all these scaling factors by changing from linear access to random access. A common example is linked lists vs arraylists. Many articles show it takes about 5 inserts per read for a linked list to beat arraylists.
- AstralStorm 10y ago
  Not with large data sizes it doesn't. Which is the whole point. Array would be even slower than the list on insert because you actually have to move much more data around. The one thing array is better at its sometimes locality, especially if you iterate over neighbouring elements.

stdbrouw 10y ago

You're failing to account for the fact that it's a log-log graph, though, so even a modest slope can be pretty significant. If you want a rule of thumb, might as well just stick to "hash tables are fast" instead of the false precision of O-notation.

jimminy 10y ago
Big O-notation isn't precise, it is an approximation by nature. It only cares about the largest factors for determining the estimate.
- epistasis 10y ago
  The log-log graph is the way to determine those large factors. Taking the log removes the multiplicative constants. The differences between n^.5 and n^1 and n^1.5 are quite significant for big-o
aaronbwebber 10y ago
The graph really is totally flat below the L1 cache size line, and even on a log-log graph the slope between 10 MB and 1 GB is not significant.
- AstralStorm 10y ago
  That being kB range for L1, single digit MB for L2. Relatively simple Java apps tend to eat multiple GB, while accessing most of it.

malisper 10y ago

The definition of big-O is what happens as n approaches infinity. You are free to model your computer as having O(1) memory access as it's a much simpler model and close enough in practice.

adrianratnapala 10y ago
As N climbs orders of magnitude, we start using ever more distant kinds of memory, so access time does not scale as O(1) in theory. As for practice, it's not O(1) either or else cache misses would just be a theoretical nicety that didn't matter in the real world.
- malisper 10y ago
  If you make the assumption that there is an upper bound on the maximum time a read can take (e.g. reading from disk), reading from memory becomes an O(1) operation regardless of cache misses.
  - mindslight 10y ago
    By similar assumption, every terminating algorithm running on a real computer (having bounded memory) is O(1). This is technically true, but not useful. Most people assume the average memory access will be reasonably fast (why we have a cache hierarchy in the first place). Sometimes the growth of it matters, sometimes it does not. Algorithm complexity is not something to be memorized, but analyzed.
    - malisper 10y ago
      The assumption that the computer you are modeling has an infinite amount of memory finite number of caches is a useful assumption as it dramatically simplifies the analysis and still allows you to use big-O to somewhat accurately analyze the performance of a real computer.
      - mindslight 10y ago

xenadu02 10y ago

It is trivial to exceed the L1 cache size and not that uncommon to exceed L2. That brings us to a 100x delta which is worth thinking about, no? Even exceeding L3 isn't horribly rare for average desktop CPUs (let alone mobile devices). There are other dimensions to this too like prefetching, streaming, pipelining, vectorization, etc. In some cases using an array and doing a linear search is faster than any hashmap on a modern CPU. I think the takeaway from this article is not to blindly trust the theoretical big-O numbers for data structures and actually test them with realistic datasets on your target hardware.

aaronbwebber 10y ago
This is a very good point. You should run actual performance tests. The results may surprise you! In my actual work, optimizing in memory searches is not worthwhile because saving half a dozen microseconds on a search is not real valuable when you are about to spend half a dozen milliseconds making a database call (which is technically O(log N), since there's a B-tree index back there). But I do spend quite a bit of time figuring out which of those queries should be moved to an in-memory O(1) cache (redis or memcache, depending). And I actually never think about the perf tradeoff between the DB and the cache being O(log N) vs O(1) - I think of it in terms of the median and 99th %tile times that I know from monitoring our actual production servers. So as xenadu points out, I guess there is some truth in the article, but it's just sort of lost in this somewhat academic discussion of scaling things to infinity and beyond.
- deleted 10y ago
  [deleted]
- AstralStorm 10y ago
  Random percentile abuse. 99% is less useful than a median. The real data is a true histogram as well as maximum time. 99% might mean every 100th customer does not get a service.
- pjc50 10y ago
  In my actual work, optimizing in memory searches is not worthwhile Funnily enough, I had to do this last week. We started from the question "why does it take 160ms to scan 60,000 objects in memory?" and reached the disappointing conclusion that, on this particular platform (iMX6/800MHz/DDR3) a cache miss costs you an astonishing 233ns. I got as far as double-checking all the RAM initialisation parameters before giving up. There is now an index on the in-memory search.

nbadg 10y ago

I think that the "best" message here is that the performance of memory access, hash lookup, etc, is a more complicated question than always just O(1). Knowing the context -- basically, the second-to-last graph that highlights performance vs size vs cache limits -- is the bigger picture for the system. And it's perfectly usable everyday, you just have to remember a few more words: "memory access is O(1) as long as I stay within L1". The problem I have with the article is that the author has replaced one broad generalization with another equally reductive but diametrically opposed one. It's no more accurate, and no more decontextualized, than the original statement, and in my head that means it's also not really all that useful.

AstralStorm 10y ago
Simpler version: locality of data matters a lot.

jcbeard 10y ago

I agree with aaronbwebber that for general use, and for teaching, that it's far easier to assume O(1) memory access. It's a decent approximation, and works until you start having applications where loads/stores dominate. It also falls apart when things like multi-threaded apps start spinning on locks, but lets not go there in a HN post, could make an entire blog out of mem issues. Here's why we should continue to use O(1) access in general. Unless you enjoy rat-holes (I wouldn't have a job without them...so, why not). If we really wanted to, for every algorithm we could consider things like: 1) pre-fetch algorithm (assuming you know which one will be chosen) 2) associativity 3) cache size at each level (including buffering) 4) queueing depth at all levels 5) DDR controller capacity & while we're at it, do we have latency of mem controller on-chip..wait, which one? 6) bank conflicts in DDR 7) NUMAness (how about NUMA cache behavior?) 8) even worse...should we consider cost of differing mem tech. 9) TLB behavior...there's a lot there, can't list Here's why we don't: YOU CAN'T. Do you realize the incredible amount of work required to get the info for the analysis? The list of things that influence memory behavior is huge. Even if you can get all of it, you work it out for one algorithm...you've now wasted a year, and figured out a cost for one architecture/OS/run-time combo. Congratulations. I'm all for including the cost of memory...just realize what you're asking before you write a post asking about it. There's no end to how detailed you want to go. And in the end you end up destroying the asymptotic bound you're trying to create b/c you'll realize that it's now a probability distribution that really doesn't lend itself to generalizable asymptotic behavior, which is what you want when considering algorithms. When choosing an algorithm for a specific hardware, then you can choose an algorithm for that arch.....but most people don't do this, it's not necessary unless you're in HPC, Datacenter scale analytics, or in the embedded space/cyper-physical space.

xenadu02 10y ago
Permit me to disagree; I think it is useful to internalize the general rule that for every 100x increase in data size the theoretical performance will drop by 10x. This isn't a perfect rule but it is just as valid a shortcut as saying hash lookups are O(1). For all intents and purposes all modern CPU hardware works the same way (a cache hierarchy, superscalar, pipelined, with relatively slow DRAM hanging off some bus). In practice measure different approaches to performance-critical code with realistic datasets and don't make assumptions. Don't assume that you know dictionaries are O(1) and therefore searching an array must be slower.

sabarn01 10y ago

It happens all the time. In real world code people throw hash tables and maps at all types of problems of all sizes. If you hit arbitrary boundaries where your fundamental assertion of access time becomes non constant its an issue. This post might spur new thought about containers and how there usage should really be governed by their expected capacity.

krinchan 10y ago

I always thought the Big-O notation was purely to compare one algorithm to another, not actually measure literal, real world performance. Trying to describe a hardware operation in Big-O notation then assert everyone should something other than O(1) for a memory access operation seems like a gross misunderstanding of its purpose.

fapjacks 10y ago
This right here is the most relevant response to the article.
TillE 10y ago
Specifically, Big-O describes the relative performance of an algorithm as the input grows. That's why constants are discarded, and that's why O(n^2) is probably fine if you only ever have very small data sets.
bzbarsky 10y ago
Big-O notation is there purely to compare one algorithm to another, yes. But in terms of what? Say you have two search algorithms. For a dataset of size N, Algorithm 1 does N memory reads and N data compares. Algorithm 2 does N * (log N) memory reads and log N data compares. These are not real algorithms, just illustrations. It's not uncommon in the analysis of such algorithms (both searching and sorting) to only consider the number of data compares and assume memory reads are completely free. So that would give you O(N) for algorithm 1 and O(log N) for algorithm 2. Analyses with more sophistication will note that a memory read is not in fact free, and will look at the number of "operations", whether those be memory reads or compares. In terms of the number of "operations", algorithm 1 is O(N) and algorithm 2 is O(N log N). These are both true statements about these algorithms: Algorithm 2 is O(log N) if you look at number of compares and O(N log N) if you look at number of "operations". Which of these characterizations is more relevant to you? Depends on whether memory reads are actually free in your setup. Anyway, the original article is arguing that for the comparison most people care about, wall clock time, even the more sophisticated version is wrong, because it assumes that the time needed per operation does not depend on N, so you can just count all the operations and not worry about their relative speed, because that's just a constant factor. If the time taken for a memory read _does_ depend on N, then you can't do that. For example, if you want to look at the algorithmic complexity of these algorithms in terms of clock cycles, and a compare is one clock cycle (might not be, depending on what your data is!) and a memory read if sqrt(N) clock cycles (due to caching effects), then the complexity of algorithm 2 will be O(N * sqrt N * log N), whereas algorithm 1 is O(N * sqrt N). Of course once you're caring about actual time very often constant factors start to matter too, and the whole idea of doing asymptotic analysis might break down. But it might not. It really depends on your exact problem and on the assumptions underlying the asymptotic analysis...

smallnamespace 10y ago

> but how often do you scale something through 6 orders of magnitude? Well, that's the whole point of using big-O notation. Otherwise, there's no point in distinguishing between O(1) and O(lg N) either--lg(10^6) is only ~20, after all.

klodolph 10y ago

> but how often do you scale something through 6 orders of magnitude? I can't speak for others but the team I'm on has a mind-boggling amount of data. 6 orders of magnitude is not even close (no, I'm not doing something clever like starting with "byte" or "bit" as smallest unit). The truth is most people don't have "big data" but plenty of people do—petabyte scale is becoming pedestrian these days and a few larger organizations are into the exabyte range. Latency grows as you go from registers to RAM to hard drives in distant data centers. Consider that data centers don't really stack on top of each other, they have to be built flat or you can't get rid of the waste heat fast enough. Same with microprocessors and RAM. Everything is flat, in practice, with a limit to how much it gets stacked. Maybe you think that this is a special case, but with everyone building their applications on top of the same cloud providers, your provider's scalability starts to affect you personally. So even if you build a small application in the cloud, your ability to access data is impacted by the fact that your cloud provider is providing access to exabytes of data.

rocqua 10y ago

One can move across all these scaling factors by changing from linear access to random access. A common example is linked lists vs arraylists. Many articles show it takes about 5 inserts per read for a linked list to beat arraylists.

AstralStorm 10y ago
Not with large data sizes it doesn't. Which is the whole point. Array would be even slower than the list on insert because you actually have to move much more data around. The one thing array is better at its sometimes locality, especially if you iterate over neighbouring elements.