> You'll know that iterating through a linked list is O(N), binary search is O(log(N)) and a hash table lookup is O(1). What if I told you that all of the above is wrong?
It's not wrong, it doesn't have enough contextual information to be right or wrong.
Ehh, his assumption is that O notation should say something at lower bounds, which is simply wrong. He should be testing 10-15+ GByte data structures not < MB data structures.
Consider, O(X * Log (X)) is generally thought of as good. But, let's assume the algorithm takes 24 hours + x * log(x) nanoseconds. Well for low values of X that 24 hours is going to be a pain and it's going to look like constant time, but for really really big data sets x * Log(x) will actually dominate.
I'm not sure the cost of accessing the storage medium belongs in the complexity of the algorithm, since that cost will change based on the storage medium, not the algorithm itself. It strikes me as more of a constant, (even though it isn't constant).
In part two, the author demonstrates that if you packed information as densely as possible, i.e. your computer is a black hole, the best you could do is O(n^1/2).
If, and only if, you're accessing that memory randomly. If you're accessing it in a linear scan, that line is going to drop away from sqrt(N) very quickly.
Yeah, but that is not an argument not to include that in the analysis of how a function behaves when you throw lots of data into it. Also, the author comments this in one of the parts.
I agree that in practice most of the time it won't affect your choice of algorithms. But it may be helpful in understanding how your run time will actually scale as your data size increases.
Also, I could conceive it being useful in odd cases if there are choices between two algorithms:
Algorithm 1: O(N) memory access operations, O(N log^2 N) cpu operations
Algorithm 2: O(N log N) memory access operations, O(N log N) cpu operations
If we assume memory accesses are O(1) time, then Algorithm 1 is faster, but if we assume memory access are O(sqrt(N)) then Algorithm 2 is faster.
Here's the problem, the sqrt(N) assumption is based on completely random access, where most accesses bust all the caches. What will matter more, when it comes to the cost of memory in real applications, is the actual size of your dataset in relation to the cache sizes, and whether your access is sequential across a region of memory (an array) or random (a scrambled linked list).
In practical terms, the plateaus of the stair step graphs matter more than the general trend of the line.
Unless you're concerned about worst case scenario, where the last part is definitely not a plateau ever. You can reduce it to a Turing machine fetching you data sequentially.
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.
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
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.
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.
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.
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.
You missed what I was illustrating by referencing bounded memory - every realized program has a finite (therefore constant-bounded) number of states. The point is that such analysis is not useful, because it "cheats" with an misleading implicit constant for the bound.
Similarly, if one is analyzing the performance of a general algorithm and assumes memory access is constant time, then that constant needs to be understood as the full access time of main memory (assuming that's what problems will always fit in).
One cannot casually make this assumption to get an O(n) complexity result, profile the program with a problem size that actually fits in cache, and then combine the two to extrapolate larger running time. They each have different baked-in assumptions.
If you make that assumption, sure. If instead you assume that you live in a universe where information can't propogate faster than the speed of light (true), storage takes up space (true), and memory is arranged on an plane (generally true in practice), then you get back to sqrt(n) access times. If some day we move to totally 3D computers we can get that down to cube root of n.
Anthropic O(1) argument: An algorithm will either finish before all humanity dies, or it won't. If it does, it's bounded from above by a constant. If it doesn't, it's completely irrelevant to everyone. So for all practical purposes every algorithm is O(1).
We live in a world where we buy hardware to run our programs, not write programs to run our hardware. [This is a Dijkstra paraphrase—can somebody find me the original?]
Think of the O(1) as paying the worst cost of a given memory tier, uniformly. The more data your program uses the more hardware you need to run it the worse your worst case will be.
Makes the analysis completely worthless. The idea of the analysis is to evaluate asymptotic behaviour for large data sets. Of the idea ever a nonlinear cost of accessing the data, you should take it into account.
Suppose the memory is tree structured like typical TLB, you do get at least one extra log n factor. And actually there are even more costs on the way.
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.
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.
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.
>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.
You have to do this anyway to make sure that the constant factors aren't big enough to change the optimal approach at the size of your dataset. Big-O only really buys you an initial rule to not do things that are obviously wrong.
And in fact, some data structures that scale poorly will perform better on small sets of data.
For example, a simple list of pairs with linear lookup time can be faster than a hash table for small amounts of data, because it doesn't have to compute the hash.
I would say it differently: you absolutely should trust big O numbers for data structures and use that as a major guiding principle in terms of how to structure a program ... and you should require extraordinary evidence, like a surprising result in a performance test, before navigating away from trusting the big O analysis.
What this all says to me is that for an extreme claim (e.g. using an array and doing a linear search will be faster than a hashmap lookup) it should require equally extreme evidence to substantiate it (e.g. the results of performance tests that stand up to heavy scrutiny).
I feel there is a trap in which someone might look at this sort of thing and say, a-ha I don't actually need to care about big O reasoning or standard understanding of data structures at all! That would be a tragic misreading of this sort of example.
> before navigating away from trusting the big O analysis.
I don't think that's the spirit of the article. The spirit is to not assume O(1) is O(1) if you work with a physical computer and care about anything beyond how many times your program counter increments. Make sure to use big O notation that includes the complexities of carrying out those single instructions.
If you work with more than 32k of data, you either need to modify your big O to take latency into account, or you're assuming some worst case cache level, which is fine, and what you're doing with an idealistic big O...but that's a terrible assumption if you're actually trying to achieve speed or realistic metrics.
I agree. That's why the article is wrong-headed in its presentation.
Generally when you begin working on problems where this sort of thing is relevant, you have to make choices to get something going. You want to avoid premature optimization and you need something on the ground. In short, you have to assume O(1) is O(1) ... and it basically always is, except when there's evidence that it's not.
The value of the article is to point out cases when these abstractions break down, and the value of performance testing. But carrying it to an extreme such as, "Never make any assumptions about how any data structures work until you've performance tested every single thing in your application" is of course wildly unproductive.
Totally with you on 'benchmark everything, who knows when the branch predictor will mispredict or a full cache flush will happen. (Interestingly enough, I rarely try to beat the compiler since ICC is super smart but strategically placed, manually inserted CLFLUSHes have sped up some my work. Go figure.)
Eh L1 is bigger than you think. What cache-trashes is context switching. A common technique is shielding processes[1], delegating all interrupts to certain processors. Here's an easy example - since HT has it's own set of caches for both "CPUs" inside the physical CPU [i.e., the ALU (and all the aux AVR registers too) is shared between both], if you're doing anything computationally intensive with an unpredictable set of interrupts, but your crunch pattern is predictable enough do the following-- set the affinity for the 'cruncher' to one CPU with a full shield, and then all other components like interrupts, IO, things that you don't mind re: cache misses, etc.
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.
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.
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.
The problem is, that's not really true. There isn't a hard/fast rule that'll get you what you want given the way modern hardware is designed. Run something on a core designed for mobile workloads and that changes vs. one designed for server workloads vs. one designed for HPC. They're definitely not all the same, and the differences will kick you in the rear when trying to simplify.
I do agree teaching people that there are differences, and give them the tools to learn when algorithmic changes are necessary to optimize for the hardware.
The article rationalizes with physics, arguing that a physically large data store, when it is efficiently implemented, is limited by the inverse-square of distance inherent in a 3D world.
Certainly there are exceptions when you make a system more efficient (for example, filling empty memory slots or moving systems closer together or paying for a better interconnect).
There is a middle ground between tuning an algorithm to the exact memory hierarchy of the system it is running on and ignoring the problem altogether: https://en.wikipedia.org/wiki/Cache-oblivious
But that’s one of the main points of the article: You don’t have to. Asymptotically, you won’t be better than O(sqrt(N)) because physics does not allow it. You can put all the different caches in you want, you can buy the most expensive RAM there is, you can buy the best interconnect systems for the fanciest NUMA cluster you can find: You won’t beat O(sqrt(N)) if you wish to go to arbitrary N.
Of course, if you bound your problem size, you may well get O(1) access times and for some applications, it may well be sensible to consider the coefficient associated to the square-root scaling small enough to neglect it, but if you truly want to talk about algorithmic complexity (and not just the scaling of one particular implementation for one particular range of valid N), you should take that additional square root into account.
I don’t know of a mechanism in quantum mechanics that would allow to pack information more densely (or even infinitely dense as would be required by O(1) random access times), what did you have in mind?
Check out "cache-oblivious algorithms" for code that is designed to work well with memory hierarchies but which does not need to be tuned for the specifics of any particular architecture.
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.
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.
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.
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...
> 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.
Can you link to an example? That seems plainly wrong and I haven't seen an analysis which makes that assumption.
https://en.wikipedia.org/wiki/Binary_search_algorithm#Perfor... is a simple example. It goes to great pains to talk about numbers of comparisons per iteration, but never once considers the number of memory accesses per iteration (which happens to be 1 or 2 depending on how you count things).
In fact, most of the performance analysis of algorithms on Wikipedia that I've seen look like this. Similar for introductory algorithms textbooks, if I recall correctly (which I may not; it's been a while since I looked at one of those).
Now in practice the number of memory accesses in an algorithm like this is typically O(1) in the number of comparisons so an implicit assumption that all your memory accesses are O(1) means just adding a constant factor to your overall complexity, so it's OK to just not worry about the whole thing. And counting "memory accesses" is complicated because whether something is a "memory access" or not is a bit tricky. For example, in the binary search case, do you need to "memory access" the value you're searching for before every compare, or can you assume it's stored in O(1) storage like a register? But all of this falls down if your memory accesses are not in fact O(1).
There is a complimentary notation for additional memory use.
Any engineer worth their salt actually specifies basic operations separately. This includes comparisons, fused or normal multiplies and additions, divisions of applicable, memory loads and writes.
> purely to compare one algorithm to another, not actually measure literal, real world performance.
Estimating real world performance is the whole point of Big-O notation. Trying to solve the traveling salesman problem on all the stars in the Milky Way is something your PC isn't going to do in your lifetime, for instance.
> 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.
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.
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.
Only after reading the last article of the series I checked the link to share it. Only then noticed that I misread the heading on the blog. I read "I like big tits" and though is this page hacked or something? The url corrected my dirty mind :).
Great series. Even if you don't agree with the notation it has still valuable information. Thanks author!
This is a circular linked list walk where the elements of the list are in order in memory. So in C the list walk looks like this:
while (1) p = *p;
Then the time per access was measured as the total length of the array was increased and the stride across that array was increased. The linked-list walk prevents out of order processors from getting ahead. (BTW another huge reason why vectors are better than lists)
(This is from an old processor that didn't have a memory prefetcher with stride detection in the memory controller. A modern x86 will magically go fast.)
From that chart you can read, L1 size, L2 size, cache line size, cache associativly, page size, TLB size. (It also exposed an internal port scheduling bug on the L2. A 16-byte stride should have been faster than a 32-byte stride.)
I am pretty sure it's wrong. I just made a comment about this on the author's article. He claims information N~rm, but for any normal material you have mass proportional to r^3. So N~r^4, not r^2 as the author claims.
Black holes and information is a thorny issue, see e.g. [1]. So I suspect something went awry in the argument when (s)he brought quantum gravity into it.
You have a volume V1, and let d1 be the maximum density of information you can store in V1. If you try to store any more, your storage will collapse into a black hole, so d1 is the maximum density.
Now you get 8 times more data. But cannot story this data in a volume 8*V1, because if you try to use 8 volumes V1 with density d1, and place these next to each other, they will collapse into a black hole.
Thus, the more data you have, the smaller density you can use for storing it.
RAM should be filled with 1) Things that are likely to be reused or 2) Things you want faster access to, or at least a constant fast access time when needed.
RAM should not be filled with 1) Things you will never use again (for example log files, or things that are very quickly invalidated by synchronous writes but rarely read) and 2) bloated data structures. For example if you have data format a and data format b that achieve the same thing, but b takes 30% more space at the same speed, b is very bad and should not be used.
I am sorry... but no, the article is interesting and well written, but it has nothing to do with big O notation.
Random access in memory is still in O(1), it doesn't depend on the size of the data structure (I am assuming that is the "n" the author talk about by pretending that a memory access is O(sqrt(n)).
Even if you have a very complex memory architecture with 15 caching levels, spread all over the world, if you have a maximum of 5 day delay for accessing your memory through the mail, it will still be O(1), because 5 day is constant, it does not depend on the size of the data structure.
The "n" the author is really talking about may be the depth of the cache hierarchy.
I see the point and it is interesting, it's just not big O ^^
If I replace in my head all O(thing) by MyCustomComplexityMeasureYetToBeDefinedProperly(thing) then it makes perfect sens.
Big O is basically that. Big O notation predates computers (late 19th/early 20th century) -- it's simply a notation to signify how a problem scales in complexity in relation to the size of the data set. I would argue that multi-level memory access is itself a problem that scales complexity in the same way.
...but if you have a significantly smaller dataset, you don't need such a complex caching architecture, which brings faster access times at the margins. So even in your example, worst-case access time scales with dataset size.
There are models like the Transdichotomous model [1], where the properties of the machine vary based on the problem. That seems to be what is happening here.
You can say everything is O(1) because nothing would ever take more than `2^128` seconds. In practice, O-notation means "with a reasonably small constant".
If this has nothing to do with Big-O then Big-O is a useless concept and should be abandoned. You may be interested in measuring the number of CPU instructions it takes to traverse a linked list in which case O(N) is accurate.
Personally I care about how much wall-clock time it takes in which case a linked list is very much not O(N) and the larger the list the further away from O(N) it becomes. There is a rather large delta between a 10K and a 100MB linked list. You can go test this for yourself right now.
> Random access in memory is still in O(1)
No it isn't. Random access only looks like O(1) at certain plateaus, like size of L1, size of L2, size of L3, size of RAM on the local NUMA node, size of RAM on neighboring NUMA nodes, size of RAM on distant NUMA nodes, size of SSD, size of HDD, size of NAS locally connected, size of NAS distantly connected, size of cloud storage.
Constants can matter in Big-O, especially if they are very large. Compared to the number of instructions 3Ghz CPU must execute to do a hash lookup, accessing RAM has a relatively large constant factor and execution time can be massively impacted by sub-optimal RAM access patterns.
Except Big-O was never intended to describe wall clock time. As soon as you try to use Big-O to describe a number of concrete units you'll fail. Big-O is purely a comparative measure, this algorithm vs. that algorithm. As it stands, it is fairly meaningless outside of purely academic exercises.
EDIT: I mean, consider that the entire basis for Big-O notation assumes that every "operation" are always equal. Adding is always constant. Big-O is very hand wavey and claiming the constants matter is to invent an entirely new notation.
Big-O isn't handwavey, it was absolutely intended to describe (among other things!) wall-clock time, and the article isn't just talking about constants. Also, many operations (like adding) are constant-time on modern computers, outside of memory hierarchy effects, ALU stalls, etc., since they're bound to finish within exactly one clock-cycle.
Big-O is mathematically rigorously defined, but has nothing to do with wall-clock time. It's about the asymptotic behaviour of functions. How you interpret the values of these functions is up to you - of course you can model wall-clock time, but then you'd probably be interested in all the constant factors and lower-order terms that asymptotics hide from you, so Big-O analysis is the wrong tool.
If wall-clock time is being affected by non-constant factors (as the article convincingly asserts), why on earth wouldn't you want to model those factors with big-O notation? Moreover, why do you think that people uninterested in wall-clock time wouldn't care about constant factors, but people interested in wall-clock time unilaterally would?
If your program does two steps, one of which takes time O(n) and the other O(√n), then your program takes time O(n) because that dominates. That's an example of lower order terms. If you measure wall-clock time, then you'd be interested to know about that second step. But if you're looking at asymptotic analysis, then it's completely irrelevant because the linear term dominates it.
Your other questions are all best answered by: Big-O notation is not the right tool if you want to make predictions about wall-clock time. I don't think I need to justify why someone interested in wall-clock time would be very interested in the constant factors involved - the difference between n and 20n is a factor of twenty, and whether a program takes half a second or ten does make quite the difference.
But asymptotically, they're the same. Someone who is interested in the asymptotic behaviour wants to know how fast the function grows - is it linear? linearithmic? quadratic? cubic? exponential? (with which base - 1.1^n, 2^n, 10^n?). For them, a constant factor isn't interesting.
Of course, neither extreme is particularly helpful when trying to compare algorithms in practice. Modelling the hardware extensively and including all the little constant factors is exceedingly tedious, even if you can actually get all the information required to do so. Pure asymptotics also don't help much if they hide huge constant factors. That's why Algorithm Engineering is a thing (and a very good thing!). Basically, it tries to bridge the gap between algorithms that theorists like, and those that practitioners use. To that end, design, analysis, implementation, and experimentation must form a circle and influence each other. Wikipedia probably does a better job of explaining it, though.
The article points out that accessing n words of RAM takes O(nsqrt(n)), which is not dominated by O(n), which is my entire point here. And in the cache-oblivious model (for example), big-O notation is still alive and well; there are just additional variables introduced to account for the various constants.
I guess the author is trying to simplify, but its way more complex than that. Simply assuming a few layers of cache completely misses all the other layers that have effects starting with.
Cache lines, RAM Read vs write turnaround, dram pages, number of open dram pages, other CPU's interfering with the same RAM channel, remote NUMA nodes, and probably some I'm forgetting. All this is very similar to secondary storage access rules (even for SSDs)...
Sure, but I think the point is that big-O notation fails miserably at analyzing certain algorithms because it doesn't have a way to represent the locality of the algorithm.
Put another way, all the little "constants" thrown away in the analysis may not actually be constants, and their non-constantness may be enforced with actual physics. In other words, like the article says, the idea that storage access times are constant is nonsense. Due to physical limitations, this is insurmountable rather than being a side effect of architecture. So, its quite possible that for certain algorithms the "constant" factors may be overriding terms in the analysis.
"I can vaguely fit a line to this graph that's clearly nonlinear, so that line describes the asymptotic complexity of the system."
Huh? Am I taking crazy pills, or is this a horrible analysis? It looks like the behavior is O(whatever it's supposed to be) times a constant multiplier at a few different regions. The OP conveniently cuts off the graph so you can't see it level off.
It levels out until you fill up your SSD, then it levels out until you fill up your HD, then it levels out until you fill up your NAS, then it levels out until you run into scaling problems on AWS, then ...
You'll always eventually expand past the limits of whatever storage you're using. It's clearly impossible to build totally unlimited storage with constant access time, and you'll always eventually need larger storage (to disk, to other machines, to other data centres, etc), at the cost of speed.
Take a look at [part two](http://www.ilikebigbits.com/blog/2014/4/28/the-myth-of-ram-p...), where he runs through this in more concrete depth to back his claims up. The theoretical physical limit for accessing N bits of data is O(sqrt(n)), no matter how you do it, just from the speed of light.
It's counter-intuitive, but this really is true in the general case, not only in the regions shown on that graph.
I don't think it's all that counter intuitive. You just need to consider that information transfer is limited by speed of light - it naturally follows that access times must grow with size of data unless you are able to pack the information infinitely dense.
It's a great series for reminding us of that, though, and illustrating it well and actually putting numbers on it.
If this were the only factor, access time would actually grow with the cubic root of N, because you could arrange memory in a sphere, which grows with r^3.
The ultimate theoretical limit is the berkenstein bound, which implies that the information content of a region is bounded by its area, not its volume. This is where r^2 comes from.
I get that there's additional constraints - my point was simply that intuitively even without thinking through or knowing about additional ways the communication is constrained, you'll arrive at the necessity of an increase in latency just with the knowledge of the limitation of speed of light alone
Using Schwarzchild radius of a black hole as the limiting case of a sphere of radius r and then using that information to determine something about arbitrary spheres of radius r? Unorthodox.
While this is true, the analysis in part one is really bad and that sort of incorrect hand-wavy line fitting should be discouraged.
Part two is much better and is based on sound principles. The only complaint there is that it's a bit misleading; if you arrange your memory in a sphere, you get access times as the cube root of N for a very long time before you start running into information-theoretical limits based on the area of the memory region.
Just that, present day memory is arranged in 2d surface, not in 3d volume. And there are issues like cooling, so we don't know if r^3 scaling memories will happen in the future.
Since it is a topic I'm interested in I took the time to read all 4 parts, the author manages to summarize it in a paragraph which would have been helpful at the beginning:
When somebody says “Iterating through a linked list is a O(N) operation” what they mean to say is “The number of instructions needed to be executed grows linearly with the size of the list.”. That is a correct statement. The argument I’m trying to make is that it would be a mistake to also assume that the amount of time needed would grow linearly with the size of the list as well. This is an important distinction. If you only care about the number of instructions executed that’s fine, you can use Big-O for that! If you care about the time taken, that’s fine too, and you can use Big-O for that too!
Sadly, he doesn't take this knowledge to its conclusion. Let's introduce the notation Oi() for the Big-O notation in instructions, and Ot() for the Big-O notation for time.
Lemma: For all f(N), if Oi(f(N)) > Oi(g(N)), Ot(f(N) will be > Ot(g(N)).
Or put another way, it's important not to confuse complexity scaling with time scaling, but the more complex the computation, the longer it will take.
Don't think your conclusion holds - and that's actually something the author brings up.
It might be quicker in time (not in the amount of instructions executed) to calculate something multiple times, or to do a more complex calculation or what have you, in order to touch less memory.
log_b(n) * log(b) = log(n). log(b) is a constant in our algorithmic analysis, and can therefore be removed. There will never be a log_b(x^2) that grows at slower than log(x), no matter how big b is.
Which is why you have to evaluate in a model with an explicit cache width. In such a model, b is not a constant. The cache-oblivious model [1] is a fairly well-known example, but that won't work in this case, since we need to know b to set the tree width. Any of the other external memory models will do.
The quantity the author describes is commonly called the working set. His explicit thesis is that the time to process the working set is related to the size of the working set regardless of computational complexity. He spends the entire first part of his discussion belaboring this point with a linked list example. He goes on to do a systems analysis of the results and concludes that time of execution is system dependent not complexity dependent. Again using the same algorithm engaging with a larger and larger memory system.
Generally engineers would experience this important principal in a more binary way, once their program started swapping to disk, its performance would fall through the floor.
If you hold the size of the datum constant (and that is important), then processing fewer of them will take less time than processing more of them.
The argument you make, as I understand it is as follows;
Consider two algorithms that process N and P datums respectively to achieve the same computational result, and where N > P. There exists an algorithm such that P datums takes less per unit time to process than N. Resulting in a violation of my Lemma because Oi(P) > Oi(N) but Ot(P) < Ot(N). And you cite cache obliviousness as the principle that enables that violation.
Would you agree that I have accurately summed up your argument?
It's roughly right, but it's not cache obliviousness that enables the violation. For the argument to work out, you have to evaluate it within a model that has an explicit cache and hence, treats big O results as being parametrized over the cache width.
O(log_b(n)) is the same as O(log n). With O(sqrt i) memory accesses you still have a constant factor separation between the absolute time performance of the two.
It has nothing to do with the model and is just a question of whether b is a variable in the big O notation.
And in this case of O(sqrt i) memory access times, a binary tree and b-tree stay within a constant factor even as you vary b. (The reason is, the binary tree accesses that a single b-sized access replaces get exponentially more "local.")
I don't know what that means. I'm assuming a random element of the tree is picked, that parent nodes are in a smaller or equal cache level than children, that all but one cache levels are used completely, that each cache level has O(sqrt n) access time, and that there is an upper bound on the ratio between successive cache sizes.
Or less generally: it takes sqrt(j) nanoseconds to dereference the pointer with value j, and parent nodes are at smaller addresses than their children.
1) The article shows that the time to process N datums of data is related to the size of the total data processed. And that as the size of the data set grows, the time to process it grows with the root of N.
2) Computational complexity's order of magnitude is relative number of datums need to be processed in order to complete the computation.
3) Less complex computations process fewer datums, fewer datums mean a smaller total memory footprint.
Therefore, processing fewer datums will lower your total memory processing cost which will lower your total time.
Q.E.D.
Does that really follow? The sqrt(N) factor is the overhead of memory access only, so if you're comparing an algorithm where every operation is a memory access to another where that is not the case it would seem you could have the inverse relation in Oi and Ot.
A complexity measure is a measure of complexity over a model. Mostly we talk about input size models, but we can (and do) talk about other models. It isn't a question of complexity scaling vs. time scaling, but of complexity scaling over an input size model vs. a machine architecture model.
There are tons of well-researched machine architectural models for complexity analysis. In the case of the article, any one of the many external memory (EM) or hierarchical memory models would be appropriate. These can capture latencies and bandwidth of hierarchical memories and storage, and in some cases even eviction, contention, partition, etc.
This isn't some esoteric point. In high performance computing, distributed algorithms, or even systems & architecture it's pretty much expected that if you talk about complexity, you should do so under some sort of EM model.
I just assume that every big-O equation has some sort of units (possibly implicit) and that neither the inputs nor the results are dimensionless quantities.
We just tend to assume that "N" is clear from context and that the result is some number of similarly-loose "instructions".
I think that at some point this O(n * sqrt(n)) is actualy not precise. Maybe it works for the first few GB, but then other mechanisms come into play.
For example processing 100GB of data actually don't have to be O(nsqrt(n)) because if you process it on cluster, then other machines are also using L1, L2, L3 caches and RAM. Then the whole process can be streamlined which means that some operations can be faster than the pessimistic nsqrt(n).
There comes a point where the latency is high enough that you're very unwilling to pay for random access. And very often that point is "broadcast over a network," where think time really is often dominated by things like the speed of light. So yes, it's still n * sqrt(n) in some abstract sense (where n is the amount of theoretically available memory within a given distance over the network); in practice it's much worse than that because you never come close to saturating all the available space between computers with storage nodes.
Closely related but unfamiliar to most software geeks, Bélády's work in the 1960s and later on the theoretical limits of operation throughput when using cache hierarchies is very relevant to high-performance software design. The theory generalizes nicely to any topology where you can control how access latencies are distributed, and carefully designed software can get relatively close to the throughput limits (though it is somewhat incompatible with the way most software engineers design systems these days e.g. multithreaded concurrency is a non-starter).
Do you think something like lightweight modular staging (https://scala-lms.github.io/) would allow fairly high level code to get to the theoretical limit?
Math is pure and not constrained by the real world. Big O analysis begins with the assumption that you have unlimited uniform memory. The author points out that memory is not uniform in the real world. It's equally untrue that we have infinite memory at our disposal. The limits of the real world are good to remember but that does not invalidate Big O analysis.
For the analysis in the article, it is enough to assume an unlimited amount of space into which you can put your memory as well as an unlimited amount of time. For your own analysis, you can of course make any assumptions you wish, but the author argues (and I agree with him there) that the spatial scaling O(sqrt(N)) for random access is both relevant in practice (as seen by the caching graph) and cannot be improved on when considering the laws of physics.
> The limits of the real world are good to remember but that does not invalidate Big O analysis.
No, it just means that you failed to take one specific bit into account and that your analysis may hence be less relevant to the real world. Much the same way we can say that integer addition is O(1), because usually we deal with fixed-size integers, we can say that memory access is O(1), because usually we deal with a fixed maximal memory size. Of course, integer addition is O(log(N)) and, according to the arguments made in the article, memory access is O(sqrt(N)).
The author assumes throughout the article uniformly random memory access. This is the worst case for a cache. If you're going to get down to the nuts and bolts of your implementation and come out of the high world of mathematics and Big O then you cannot just consider one element, namely, in this case caching. You should also consider your access pattern which very likely is not uniformly random and therefore probably does not fit the authors analysis. In fact, the only reason caching works is because the authors premise is generally wrong.
The author does address this point in part three of the series where he compares access times to a small area of a larger memory region. Even with absolutely sequential access to an array of size K, you first have to find this particular array in your larger memory region of size N, giving you total cost to iterate over the full array as O(sqrt(N) + K).
I am not sure how costly it is to iterate through your entire memory (assuming a no-op), but I would argue that eventually you reach some bottleneck and end up at O(sqrt(N)+N), too.
If I understood it correctly, the author links cache miss from memory subsystem hierarchy to asymptotic complexity (big O), so if an operation for fixing a cache miss takes higher time complexity, he takes that instead of O(1).
Similar happens when you write an O(1) algorithm while relying on malloc(), which is usually O(n log n), thus your algorithm is not really O(1), but O(n log n).
What's your n? The amount of memory allocated? In that case, I'd be interested to see such an algorithm that takes time O(1) but touches O(n) memory cells in the process...
Obviously you need to include the time your calls take in the analysis, but your example seems ood.
Interesting read. Researchers in the HPC community have developed a number of performance models to predict real-world performance in more detail than possibe through simple Big-Oh of number of operations, e.g. while OP concentrates on latency, the Roofline model ( https://en.wikipedia.org/wiki/Roofline_model ) mainly considers limited memory bandwidth.
To me, all this article has show is that depending on the size of a data structure, you will need slower and slower memory. We already know that. The article shows that within the bounds of a particular type of memory the access time is mostly constant, which is exactly what O(1) means.
I think there is a key point in the FAQ (article four, all linked through the series):
> You are conflating Big-O with memory hierarchies
> No, I’m applying Big-O to memory hierarchies. Big-O is a tool, and I am applying it to analyze the latency of memory accesses based on the amount of memory you are using.
As some others have pointed out, the line is crossing hierarchies of cache, and that he is not looking at the big O of instructions. Both of these are accurate, and the author is aware of this.
He is using the tool of big O analysis to measure a performance characteristic. That characteristic is not the traditional number of instructions or amount of memory utilized in the computation of an algorithm. It is the latency for access to a random piece of data stored on a system.
There are two cases considered, the practical, and the theoretical.
At the practical level, we do not have a unified physical implementation of the address space in a modern computer. This means that accessing a random address in memory is an action that will most likely cross levels of the cache hierarchy. It is well known that there are order of magnitude jumps crossing these levels. Perhaps it is uninteresting to you, and the importance of cache locality in an algorithm is something that you already have a very strong handle on. That makes his observation of time-to-access a random address trivial, but not wrong.
Big O tells us that a binary search is the most efficient search algorithm for an array (constraint - the array must be sorted), but in practice a linear search with a sentinel value across an unsorted array will be faster if the array fits in cache. Keeping in mind the big O latency of random memory access across cache hierarchy levels would be the theoretical analysis to tell us this. The traditional big O looks at number of instructions. These are both valid tools in choosing an optimal algorithm.
The second point the author makes is the theoretical limit. Assume the ideal storage medium with minimum access latency and maximum information density. This storage medium is matter. The limit of packing is the point at which you would create a black hole.
With this ideal storage medium, you cannot pack an infinite amount of data within a distance that can be traversed at the speed of light within one clock cycle. For this colossal storage array, there are some addresses which cannot be physically reached by a signal moving at the speed of light within the amount of time that a single clock cycle (or single instruction) takes. Accessing a random address is not a constant time operation, though the instruction can be dispatched in a constant time. There is a variable time for the result of that instruction to return to the processor.
At this theoretical limit, we would still end up with a cache hierarchy, though it would be 100% logical. With a single storage medium and unified address space, the cache hierarchy would be determined by physical distance from CPU to physical memory location. Those storage cells (whatever form they take) that can be round-tripped by a speed of light signal in one clock cycle are the first level of cache, and so on. You could have very granular, number-of-clock-cycles cache levels stepping by one at each concentric layer of the sphere, or you could bucket the number of clock cycles. Either would effectively act as a cache.
This theoretical exercise is an extreme limit, but bears out the practical implications that our current physical implementations of cache hierarchy exhibits in practice.
Again, perhaps these observations are trivial, but I believe they do stand up to scrutiny. The key insight is that the performance characteristic being described by big O is time, not the more traditional space or number of instructions.
I think time is a valuable metric in terms of algorithm selection. If we think about end users - they don't care that one instruction or 1,000,000,000 are being executed. They care about how quickly work is done for them by the computer. Instructi...
> Big O tells us that a binary search is the most efficient search algorithm for an array (constraint - the array must be sorted), but in practice a linear search with a sentinel value across an unsorted array will be faster if the array fits in cache.
From a cache perspective, a binary search is actually the most pessimal case. If you want efficiency, look at b-trees optimized for memory hierarchies.
I find this really odd, it's not wrong, but it doesn't invalidate O(1). It's mashing two-things together that are unneccessary and can cause misunderstanding.
Big-O provides a decent tool for generic analysis and an understanding of access times of memory hierarchies. Since memory hierarchies can vary, they shouldn't be considered while doing generic analysis, much anyways.
Both are important to understand. The key thing is setting your Big-O access expectations to the slowest level of your heirarchy. In that way, your expectation remains generic and still proximally accurate across the average cases.
When you consider them together, think of the heirarchy as a series of piecewise functions that modify the value of the constant time based on the speed of the bounds that fit your data.
This square of N notation falls apart in other cases. 128GB's of RAM would have roughly the same access speed as the 8GB's he had available, if he had that much in his system. But having 128GB of RAM would completely destroy the squaring by flattening an entire magnitude from his hypothesis.
But it is a nice display of memory heirarchies, IMO.
If you go on to read the later parts, the author explains how physics limits random access to N bits to O(sqrt(N)) even without a memory hierarchy. This has practical implications when comparing sequential access in an array to random access in a hashmap.
> This square of N notation falls apart in other cases.
Not particularly; since O(n^1/2) is typically used as a catchall for all O(n^x) where 0 < x < 1. The whole idea of Big O notation is that it provides an idea of systemic complexity that is normalized to a theoretical "constant" system represented by a coefficient (that is usually dropped when writing out the Big O).
IMO it still holds: distributed systems behave differently than local ones. Now that we're writing algorithms on the cloud, we've added an abstraction layer that adds complexity, and that brings some non-constant amount of overhead. It didn't make sense to think about memory like this 50 years ago; but it does now.
The article is conflating theoretical algorithm analysis and low level implementation details.
Big O analysis is a theoretical measurement of algorithm performance. By definition it ignores details like memory access speed, the exact instructions used, and other details of specific hardware architectures.
Real life algorithm implementations obviously need to deal with those low level implementation details, but that doesn't change the theoretical analysis. It's easy enough to find (or design) machines without cache where this difference in memory speed doesn't exist.
"RAM+arithmetic"-style complexity analysis in terabyte-scale-and-above problems is unable to distinguish between very practical and absolutely impractical algorithms. "square-root ideal cache hierarchy + arithmetic" has much better distinguishing power (for parallel programs, you also need to remember to bound throughput, e.g. Bernstein's area*time, for similar reasons).
287 comments
[ 4.8 ms ] story [ 269 ms ] threadIt's not wrong, it doesn't have enough contextual information to be right or wrong.
Consider, O(X * Log (X)) is generally thought of as good. But, let's assume the algorithm takes 24 hours + x * log(x) nanoseconds. Well for low values of X that 24 hours is going to be a pain and it's going to look like constant time, but for really really big data sets x * Log(x) will actually dominate.
Still, interesting read, nontheless.
Also, I could conceive it being useful in odd cases if there are choices between two algorithms: Algorithm 1: O(N) memory access operations, O(N log^2 N) cpu operations Algorithm 2: O(N log N) memory access operations, O(N log N) cpu operations
If we assume memory accesses are O(1) time, then Algorithm 1 is faster, but if we assume memory access are O(sqrt(N)) then Algorithm 2 is faster.
In practical terms, the plateaus of the stair step graphs matter more than the general trend of the line.
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.
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.
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.
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.
Similarly, if one is analyzing the performance of a general algorithm and assumes memory access is constant time, then that constant needs to be understood as the full access time of main memory (assuming that's what problems will always fit in).
One cannot casually make this assumption to get an O(n) complexity result, profile the program with a problem size that actually fits in cache, and then combine the two to extrapolate larger running time. They each have different baked-in assumptions.
Think of the O(1) as paying the worst cost of a given memory tier, uniformly. The more data your program uses the more hardware you need to run it the worse your worst case will be.
Suppose the memory is tree structured like typical TLB, you do get at least one extra log n factor. And actually there are even more costs on the way.
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.
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.
99% might mean every 100th customer does not get a service.
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.
You have to do this anyway to make sure that the constant factors aren't big enough to change the optimal approach at the size of your dataset. Big-O only really buys you an initial rule to not do things that are obviously wrong.
Big-O is great for telling you which algorithms/datastructures won't scale, it can't tell you which are actually fast enough.
For example, a simple list of pairs with linear lookup time can be faster than a hash table for small amounts of data, because it doesn't have to compute the hash.
What this all says to me is that for an extreme claim (e.g. using an array and doing a linear search will be faster than a hashmap lookup) it should require equally extreme evidence to substantiate it (e.g. the results of performance tests that stand up to heavy scrutiny).
I feel there is a trap in which someone might look at this sort of thing and say, a-ha I don't actually need to care about big O reasoning or standard understanding of data structures at all! That would be a tragic misreading of this sort of example.
I don't think that's the spirit of the article. The spirit is to not assume O(1) is O(1) if you work with a physical computer and care about anything beyond how many times your program counter increments. Make sure to use big O notation that includes the complexities of carrying out those single instructions.
If you work with more than 32k of data, you either need to modify your big O to take latency into account, or you're assuming some worst case cache level, which is fine, and what you're doing with an idealistic big O...but that's a terrible assumption if you're actually trying to achieve speed or realistic metrics.
Generally when you begin working on problems where this sort of thing is relevant, you have to make choices to get something going. You want to avoid premature optimization and you need something on the ground. In short, you have to assume O(1) is O(1) ... and it basically always is, except when there's evidence that it's not.
The value of the article is to point out cases when these abstractions break down, and the value of performance testing. But carrying it to an extreme such as, "Never make any assumptions about how any data structures work until you've performance tested every single thing in your application" is of course wildly unproductive.
For small enough sets of data, this will likely be true, simply because you don't have to compute a hash.
Of course, it likely won't scale very well.
Eh L1 is bigger than you think. What cache-trashes is context switching. A common technique is shielding processes[1], delegating all interrupts to certain processors. Here's an easy example - since HT has it's own set of caches for both "CPUs" inside the physical CPU [i.e., the ALU (and all the aux AVR registers too) is shared between both], if you're doing anything computationally intensive with an unpredictable set of interrupts, but your crunch pattern is predictable enough do the following-- set the affinity for the 'cruncher' to one CPU with a full shield, and then all other components like interrupts, IO, things that you don't mind re: cache misses, etc.
[1] https://rt.wiki.kernel.org/index.php/Cpuset_Management_Utili... This is just one way to do it, but it explains the concept.
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.
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.
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.
I do agree teaching people that there are differences, and give them the tools to learn when algorithmic changes are necessary to optimize for the hardware.
Certainly there are exceptions when you make a system more efficient (for example, filling empty memory slots or moving systems closer together or paying for a better interconnect).
But that’s one of the main points of the article: You don’t have to. Asymptotically, you won’t be better than O(sqrt(N)) because physics does not allow it. You can put all the different caches in you want, you can buy the most expensive RAM there is, you can buy the best interconnect systems for the fanciest NUMA cluster you can find: You won’t beat O(sqrt(N)) if you wish to go to arbitrary N.
Of course, if you bound your problem size, you may well get O(1) access times and for some applications, it may well be sensible to consider the coefficient associated to the square-root scaling small enough to neglect it, but if you truly want to talk about algorithmic complexity (and not just the scaling of one particular implementation for one particular range of valid N), you should take that additional square root into account.
It gives a name to a good default way of writing code.
This post might spur new thought about containers and how there usage should really be governed by their expected capacity.
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.
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...
Can you link to an example? That seems plainly wrong and I haven't seen an analysis which makes that assumption.
In fact, most of the performance analysis of algorithms on Wikipedia that I've seen look like this. Similar for introductory algorithms textbooks, if I recall correctly (which I may not; it's been a while since I looked at one of those).
Now in practice the number of memory accesses in an algorithm like this is typically O(1) in the number of comparisons so an implicit assumption that all your memory accesses are O(1) means just adding a constant factor to your overall complexity, so it's OK to just not worry about the whole thing. And counting "memory accesses" is complicated because whether something is a "memory access" or not is a bit tricky. For example, in the binary search case, do you need to "memory access" the value you're searching for before every compare, or can you assume it's stored in O(1) storage like a register? But all of this falls down if your memory accesses are not in fact O(1).
Any engineer worth their salt actually specifies basic operations separately. This includes comparisons, fused or normal multiplies and additions, divisions of applicable, memory loads and writes.
Even then you can get fooled due to locality.
Estimating real world performance is the whole point of Big-O notation. Trying to solve the traveling salesman problem on all the stars in the Milky Way is something your PC isn't going to do in your lifetime, for instance.
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.
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.
The one thing array is better at its sometimes locality, especially if you iterate over neighbouring elements.
Great series. Even if you don't agree with the notation it has still valuable information. Thanks author!
Here is another chart I like you show people: https://dl.dropboxusercontent.com/u/4893/mem_lat3.jpg
This is a circular linked list walk where the elements of the list are in order in memory. So in C the list walk looks like this: while (1) p = *p;
Then the time per access was measured as the total length of the array was increased and the stride across that array was increased. The linked-list walk prevents out of order processors from getting ahead. (BTW another huge reason why vectors are better than lists)
(This is from an old processor that didn't have a memory prefetcher with stride detection in the memory controller. A modern x86 will magically go fast.)
From that chart you can read, L1 size, L2 size, cache line size, cache associativly, page size, TLB size. (It also exposed an internal port scheduling bug on the L2. A 16-byte stride should have been faster than a 32-byte stride.)
Black holes and information is a thorny issue, see e.g. [1]. So I suspect something went awry in the argument when (s)he brought quantum gravity into it.
[1]: https://en.wikipedia.org/wiki/Black_hole_information_paradox
Now you get 8 times more data. But cannot story this data in a volume 8*V1, because if you try to use 8 volumes V1 with density d1, and place these next to each other, they will collapse into a black hole.
Thus, the more data you have, the smaller density you can use for storing it.
RAM should be filled with 1) Things that are likely to be reused or 2) Things you want faster access to, or at least a constant fast access time when needed.
RAM should not be filled with 1) Things you will never use again (for example log files, or things that are very quickly invalidated by synchronous writes but rarely read) and 2) bloated data structures. For example if you have data format a and data format b that achieve the same thing, but b takes 30% more space at the same speed, b is very bad and should not be used.
The "n" the author is really talking about may be the depth of the cache hierarchy.
[1] http://www.ilikebigbits.com/blog/2015/2/9/the-myth-of-ram-pa...
[1] https://en.wikipedia.org/wiki/Transdichotomous_model
If this has nothing to do with Big-O then Big-O is a useless concept and should be abandoned. You may be interested in measuring the number of CPU instructions it takes to traverse a linked list in which case O(N) is accurate.
Personally I care about how much wall-clock time it takes in which case a linked list is very much not O(N) and the larger the list the further away from O(N) it becomes. There is a rather large delta between a 10K and a 100MB linked list. You can go test this for yourself right now.
> Random access in memory is still in O(1)
No it isn't. Random access only looks like O(1) at certain plateaus, like size of L1, size of L2, size of L3, size of RAM on the local NUMA node, size of RAM on neighboring NUMA nodes, size of RAM on distant NUMA nodes, size of SSD, size of HDD, size of NAS locally connected, size of NAS distantly connected, size of cloud storage.
Constants can matter in Big-O, especially if they are very large. Compared to the number of instructions 3Ghz CPU must execute to do a hash lookup, accessing RAM has a relatively large constant factor and execution time can be massively impacted by sub-optimal RAM access patterns.
EDIT: I mean, consider that the entire basis for Big-O notation assumes that every "operation" are always equal. Adding is always constant. Big-O is very hand wavey and claiming the constants matter is to invent an entirely new notation.
Your other questions are all best answered by: Big-O notation is not the right tool if you want to make predictions about wall-clock time. I don't think I need to justify why someone interested in wall-clock time would be very interested in the constant factors involved - the difference between n and 20n is a factor of twenty, and whether a program takes half a second or ten does make quite the difference.
But asymptotically, they're the same. Someone who is interested in the asymptotic behaviour wants to know how fast the function grows - is it linear? linearithmic? quadratic? cubic? exponential? (with which base - 1.1^n, 2^n, 10^n?). For them, a constant factor isn't interesting.
Of course, neither extreme is particularly helpful when trying to compare algorithms in practice. Modelling the hardware extensively and including all the little constant factors is exceedingly tedious, even if you can actually get all the information required to do so. Pure asymptotics also don't help much if they hide huge constant factors. That's why Algorithm Engineering is a thing (and a very good thing!). Basically, it tries to bridge the gap between algorithms that theorists like, and those that practitioners use. To that end, design, analysis, implementation, and experimentation must form a circle and influence each other. Wikipedia probably does a better job of explaining it, though.
Cache lines, RAM Read vs write turnaround, dram pages, number of open dram pages, other CPU's interfering with the same RAM channel, remote NUMA nodes, and probably some I'm forgetting. All this is very similar to secondary storage access rules (even for SSDs)...
Put another way, all the little "constants" thrown away in the analysis may not actually be constants, and their non-constantness may be enforced with actual physics. In other words, like the article says, the idea that storage access times are constant is nonsense. Due to physical limitations, this is insurmountable rather than being a side effect of architecture. So, its quite possible that for certain algorithms the "constant" factors may be overriding terms in the analysis.
Huh? Am I taking crazy pills, or is this a horrible analysis? It looks like the behavior is O(whatever it's supposed to be) times a constant multiplier at a few different regions. The OP conveniently cuts off the graph so you can't see it level off.
You'll always eventually expand past the limits of whatever storage you're using. It's clearly impossible to build totally unlimited storage with constant access time, and you'll always eventually need larger storage (to disk, to other machines, to other data centres, etc), at the cost of speed.
Take a look at [part two](http://www.ilikebigbits.com/blog/2014/4/28/the-myth-of-ram-p...), where he runs through this in more concrete depth to back his claims up. The theoretical physical limit for accessing N bits of data is O(sqrt(n)), no matter how you do it, just from the speed of light.
It's counter-intuitive, but this really is true in the general case, not only in the regions shown on that graph.
It's a great series for reminding us of that, though, and illustrating it well and actually putting numbers on it.
The ultimate theoretical limit is the berkenstein bound, which implies that the information content of a region is bounded by its area, not its volume. This is where r^2 comes from.
https://en.wikipedia.org/wiki/Holographic_principle
Part two is much better and is based on sound principles. The only complaint there is that it's a bit misleading; if you arrange your memory in a sphere, you get access times as the cube root of N for a very long time before you start running into information-theoretical limits based on the area of the memory region.
http://www.intel.com/content/www/us/en/solid-state-drives/3d...
When somebody says “Iterating through a linked list is a O(N) operation” what they mean to say is “The number of instructions needed to be executed grows linearly with the size of the list.”. That is a correct statement. The argument I’m trying to make is that it would be a mistake to also assume that the amount of time needed would grow linearly with the size of the list as well. This is an important distinction. If you only care about the number of instructions executed that’s fine, you can use Big-O for that! If you care about the time taken, that’s fine too, and you can use Big-O for that too!
Sadly, he doesn't take this knowledge to its conclusion. Let's introduce the notation Oi() for the Big-O notation in instructions, and Ot() for the Big-O notation for time.
Lemma: For all f(N), if Oi(f(N)) > Oi(g(N)), Ot(f(N) will be > Ot(g(N)).
Or put another way, it's important not to confuse complexity scaling with time scaling, but the more complex the computation, the longer it will take.
It might be quicker in time (not in the amount of instructions executed) to calculate something multiple times, or to do a more complex calculation or what have you, in order to touch less memory.
That doesn't hold. Some instructions take longer than others.
[1] https://en.wikipedia.org/wiki/Cache-oblivious_algorithm
The quantity the author describes is commonly called the working set. His explicit thesis is that the time to process the working set is related to the size of the working set regardless of computational complexity. He spends the entire first part of his discussion belaboring this point with a linked list example. He goes on to do a systems analysis of the results and concludes that time of execution is system dependent not complexity dependent. Again using the same algorithm engaging with a larger and larger memory system.
Generally engineers would experience this important principal in a more binary way, once their program started swapping to disk, its performance would fall through the floor.
If you hold the size of the datum constant (and that is important), then processing fewer of them will take less time than processing more of them.
The argument you make, as I understand it is as follows; Consider two algorithms that process N and P datums respectively to achieve the same computational result, and where N > P. There exists an algorithm such that P datums takes less per unit time to process than N. Resulting in a violation of my Lemma because Oi(P) > Oi(N) but Ot(P) < Ot(N). And you cite cache obliviousness as the principle that enables that violation.
Would you agree that I have accurately summed up your argument?
Not in every abstract model. See other reply.
And in this case of O(sqrt i) memory access times, a binary tree and b-tree stay within a constant factor even as you vary b. (The reason is, the binary tree accesses that a single b-sized access replaces get exponentially more "local.")
There are models, like the cache oblivious model, where b is assumed to be a variable, so the model matters.
> a binary tree and b-tree stay within a constant factor even as you vary b.
it's not a constant factor if b is a variable. It's a factor of log b.
It's between 1/(sqrt(2)-1) and sqrt(2)/(sqrt(2)-1), depending on how full the b-tree nodes are.
sqrt(n)+sqrt(n/b)+sqrt(n/b^2)+... versus sqrt(n)+sqrt(n/2)+sqrt(n/4)+...
And since b-tree nodes can be half empty, there's a sqrt(2) uncertainty. (And of course there is no other memory overhead at all, none whatsoever.)
Or less generally: it takes sqrt(j) nanoseconds to dereference the pointer with value j, and parent nodes are at smaller addresses than their children.
1) The article shows that the time to process N datums of data is related to the size of the total data processed. And that as the size of the data set grows, the time to process it grows with the root of N.
2) Computational complexity's order of magnitude is relative number of datums need to be processed in order to complete the computation.
3) Less complex computations process fewer datums, fewer datums mean a smaller total memory footprint.
Therefore, processing fewer datums will lower your total memory processing cost which will lower your total time. Q.E.D.
Edit: A counterexample then:
Oi(f(N)) = N^(2/3) (memory accessing operations) Oi(g(N)) = N (non memory accessing operations)
Ot(f(N)) = N^(7/6) Ot(g(N)) = N
So Oi(f(N)) < Oi(g(N)) but Ot(f(N)) > Ot(g(N))
There are tons of well-researched machine architectural models for complexity analysis. In the case of the article, any one of the many external memory (EM) or hierarchical memory models would be appropriate. These can capture latencies and bandwidth of hierarchical memories and storage, and in some cases even eviction, contention, partition, etc.
This isn't some esoteric point. In high performance computing, distributed algorithms, or even systems & architecture it's pretty much expected that if you talk about complexity, you should do so under some sort of EM model.
We just tend to assume that "N" is clear from context and that the result is some number of similarly-loose "instructions".
For example processing 100GB of data actually don't have to be O(nsqrt(n)) because if you process it on cluster, then other machines are also using L1, L2, L3 caches and RAM. Then the whole process can be streamlined which means that some operations can be faster than the pessimistic nsqrt(n).
I think the problem is that at each stage there is different component (sqrt(n)) that comes into play.
> The limits of the real world are good to remember but that does not invalidate Big O analysis.
No, it just means that you failed to take one specific bit into account and that your analysis may hence be less relevant to the real world. Much the same way we can say that integer addition is O(1), because usually we deal with fixed-size integers, we can say that memory access is O(1), because usually we deal with a fixed maximal memory size. Of course, integer addition is O(log(N)) and, according to the arguments made in the article, memory access is O(sqrt(N)).
I am not sure how costly it is to iterate through your entire memory (assuming a no-op), but I would argue that eventually you reach some bottleneck and end up at O(sqrt(N)+N), too.
Similar happens when you write an O(1) algorithm while relying on malloc(), which is usually O(n log n), thus your algorithm is not really O(1), but O(n log n).
Obviously you need to include the time your calls take in the analysis, but your example seems ood.
https://channel9.msdn.com/Events/Build/2014/2-661 @ 23:30
> You are conflating Big-O with memory hierarchies
> No, I’m applying Big-O to memory hierarchies. Big-O is a tool, and I am applying it to analyze the latency of memory accesses based on the amount of memory you are using.
As some others have pointed out, the line is crossing hierarchies of cache, and that he is not looking at the big O of instructions. Both of these are accurate, and the author is aware of this.
He is using the tool of big O analysis to measure a performance characteristic. That characteristic is not the traditional number of instructions or amount of memory utilized in the computation of an algorithm. It is the latency for access to a random piece of data stored on a system.
There are two cases considered, the practical, and the theoretical.
At the practical level, we do not have a unified physical implementation of the address space in a modern computer. This means that accessing a random address in memory is an action that will most likely cross levels of the cache hierarchy. It is well known that there are order of magnitude jumps crossing these levels. Perhaps it is uninteresting to you, and the importance of cache locality in an algorithm is something that you already have a very strong handle on. That makes his observation of time-to-access a random address trivial, but not wrong.
Big O tells us that a binary search is the most efficient search algorithm for an array (constraint - the array must be sorted), but in practice a linear search with a sentinel value across an unsorted array will be faster if the array fits in cache. Keeping in mind the big O latency of random memory access across cache hierarchy levels would be the theoretical analysis to tell us this. The traditional big O looks at number of instructions. These are both valid tools in choosing an optimal algorithm.
The second point the author makes is the theoretical limit. Assume the ideal storage medium with minimum access latency and maximum information density. This storage medium is matter. The limit of packing is the point at which you would create a black hole.
With this ideal storage medium, you cannot pack an infinite amount of data within a distance that can be traversed at the speed of light within one clock cycle. For this colossal storage array, there are some addresses which cannot be physically reached by a signal moving at the speed of light within the amount of time that a single clock cycle (or single instruction) takes. Accessing a random address is not a constant time operation, though the instruction can be dispatched in a constant time. There is a variable time for the result of that instruction to return to the processor.
At this theoretical limit, we would still end up with a cache hierarchy, though it would be 100% logical. With a single storage medium and unified address space, the cache hierarchy would be determined by physical distance from CPU to physical memory location. Those storage cells (whatever form they take) that can be round-tripped by a speed of light signal in one clock cycle are the first level of cache, and so on. You could have very granular, number-of-clock-cycles cache levels stepping by one at each concentric layer of the sphere, or you could bucket the number of clock cycles. Either would effectively act as a cache.
This theoretical exercise is an extreme limit, but bears out the practical implications that our current physical implementations of cache hierarchy exhibits in practice.
Again, perhaps these observations are trivial, but I believe they do stand up to scrutiny. The key insight is that the performance characteristic being described by big O is time, not the more traditional space or number of instructions.
I think time is a valuable metric in terms of algorithm selection. If we think about end users - they don't care that one instruction or 1,000,000,000 are being executed. They care about how quickly work is done for them by the computer. Instructi...
From a cache perspective, a binary search is actually the most pessimal case. If you want efficiency, look at b-trees optimized for memory hierarchies.
Big-O provides a decent tool for generic analysis and an understanding of access times of memory hierarchies. Since memory hierarchies can vary, they shouldn't be considered while doing generic analysis, much anyways.
Both are important to understand. The key thing is setting your Big-O access expectations to the slowest level of your heirarchy. In that way, your expectation remains generic and still proximally accurate across the average cases.
When you consider them together, think of the heirarchy as a series of piecewise functions that modify the value of the constant time based on the speed of the bounds that fit your data.
This square of N notation falls apart in other cases. 128GB's of RAM would have roughly the same access speed as the 8GB's he had available, if he had that much in his system. But having 128GB of RAM would completely destroy the squaring by flattening an entire magnitude from his hypothesis.
But it is a nice display of memory heirarchies, IMO.
Not particularly; since O(n^1/2) is typically used as a catchall for all O(n^x) where 0 < x < 1. The whole idea of Big O notation is that it provides an idea of systemic complexity that is normalized to a theoretical "constant" system represented by a coefficient (that is usually dropped when writing out the Big O).
IMO it still holds: distributed systems behave differently than local ones. Now that we're writing algorithms on the cloud, we've added an abstraction layer that adds complexity, and that brings some non-constant amount of overhead. It didn't make sense to think about memory like this 50 years ago; but it does now.
Big O analysis is a theoretical measurement of algorithm performance. By definition it ignores details like memory access speed, the exact instructions used, and other details of specific hardware architectures.
Real life algorithm implementations obviously need to deal with those low level implementation details, but that doesn't change the theoretical analysis. It's easy enough to find (or design) machines without cache where this difference in memory speed doesn't exist.
I should note that this paper is more than 25 years old. :-)