The Myth of RAM (2014)
ilikebigbits.com
ilikebigbits.com
The reason has to do with hashing, but a different type: TLB.
I posted more details as https://news.ycombinator.com/item?id=12385458
> Moreover, an adversary can try to increase a number of necessary rehashes.
It seems to me that the section is a bit too dismissive, though, as there are hash tables and hash functions that mitigate these concerns. In particular, collisions can be replaced with trees, like in Java, limiting the worst case to O(log n) again.
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.
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.
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".
The statement "f is O(g)" means there exists some input, call it t, such that for every x >= t, it only takes some constant multiplier M (i.e., constant in x) to always have g absolutely no smaller than f. In notation:
|f(x)| <= M * |g(x)|, where x is at least t.
This bit about "x is at least t" is very important and notifies us that this is "asymptotic behavior".
It does not make a difference how wacky or weird f is compared to g below t. It can contain all these crazy memory hierarchy artifacts, it could contain a short burst of exponential slowdown, it could contain anything.
Furthermore, according to the above definition, big-O has nothing to do with any tangible quantity whatsoever. It's a method for comparing functions. The functions may represent whatever is of tangible or intangible interest: memory, time, money, instructions, ...
Big-O analysis usually posits that the details below t aren't the details that matter. (Of course, there are situations where they do, but in such you would not use big-O.) If you want to have some analysis that is global, you don't need asymptotic analysis (though it might help as a start). You can just talk about functions that are strictly greater than or less than your function of interest everywhere. But these analyses are difficult because a much higher level of understanding of your function of interest is required.
Here are the definitions:
https://cathyatseneca.gitbooks.io/data-structures-and-algori...
Basically, big-O is a claim that your process is at least -this- fast. Small-o is a claim that your process can't be faster than -this-. He means the latter.
> Still not convinced? Think I'm misunderstanding Big-O?
Yea, I do.
Big-O is valid notation for _many aspects_ of an algorithm. The author applied it to a very practical one and explained what exactly he describes very well.
You might also be objecting to the fact that he makes a distinction between time and instruction count, and is using big-O notation for both. I don't think there's anything nonstandard about making this distinction when it needs to be made. Take, for example, Karmarkar's algorithm:
The definition of big-O has a completely standardized and unambiguous definition, and the author of the article somehow has a four-part blog post on big-O without knowing it.
That's why everyone writes that comparison sorts are O(n lg N), even though it's also technically O(exp N) as well.
The speed of light limitation on distance to DRAM memory is real, but so far seems to affect mostly supercomputers. Are there any large server boards where speed of light lag is the limit on memory capacity?
I wonder if this is what one interviewer was trying to get at when he asked me over and over again if a binary search was worst case O(log N). I just kept saying that if you took more than log N steps to perform a binary search then you by definition did not perform a binary search. He was off his rocker so I kind of doubt he was looking for the difference between little-o, theta, and big-O. It's good stuff to remember and might impress a more sane interviewer some day though.
That page says o(f) == O(f) and not Theta(f). When you say "small-o is a claim that your process can't be faster than -this-", that seems to match the definition of Omega(f). Did you mean that the author should have used big-Omega?
As a side-note, I've always thought that {big-O,Theta,Omega,small-o} notation was very confusing. We should just have a notation for "the asymptotic equivalence class of a function", let's say A(f). Then to say f \in O(g), we say A(f) <= A(g). To say f \in Theta(g), we say A(f) = A(g). f \in o(g) becomes A(f) < A(g). And so forth. Instead of lots of new notation, we add a single function A and re-use notation for orderings which everyone already knows. (Of course, I'm omitting the definition of the ordering on these equivalence classes, so maybe there is some difficulty in defining that...)
Your A is pretty much equivalent to \Theta. Saying f \in \Theta(g) is equivalent to saying \Theta(f) = \Theta(g).
Edit: as an aside O(f) = O(g) is also equivalent to f \in \Theta(g), and O(f) \subset O(g) is equivalent to f \in O(g).
A(f) <= A(g) iff f is O(g)
It might be possible to define an ordering on Theta-classes that does what I want, though.
Edit: I just saw your comment about O. I think O might just work! So instead of remembering big-O, Theta, and Omega, I can just use
O(f) <= O(g) for f is O(g)
O(f) = O(g) for f is Theta(g)
O(f) >= O(g) for f is Omega(g)
(I think small-o might be slightly more complicated, unfortunately. It has a more unusual definition: https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notati...)
> O(f) <= O(g) for f is O(g) > O(f) = O(g) for f is Theta(g) > O(f) >= O(g) for f is Omega(g)
>Is that true?
Yeah, I'm pretty sure that will work (haven't checked it very rigorously though). The definition of O(f) <= O(g) would simply be O(f) \subset O(g), which immediately satisfies almost all criteria (only tricky bit is proving that either O(f) is a subset of O(g) or the other way around).
For little o I think you should be able to use O(f) < O(g), using the ordering defined above.
Yes, and that's the reason why
- g \in O(f) is an upper bound on g
- g \in Omega(f) is a lower bound on g
- g \in Theta(f) is a "tight" bound on g, or both an upper and a lower bound at the same time
For comparison, suppose that someone claims that for all x, sin(x) ≤ 1/2. That would just be wrong. If someone claims that sin(x) ≤ 2, then that is true, but not as informative as saying that sin(x) ≤ 1. There's something special about 1 here. If you want to highlight that, you can say that 1 is the least upper bound for sin(x). This is a bit of a mouthful, but we cannot achieve the same meaning by just replacing "≤" by "≥" or "=" or "<". Any of these replacements would just make the statement incorrect.
Big-O is something like the asymptotic version of ≤. For example, how many comparisons does heapsort need to sort an array of length n? If someone says O(n), that's just wrong. If someone says O(n^2), then that's correct, but not as informative as saying O(n log n). O(n log n) is special here, since it is the smallest complexity class that contains the number of comparisons. Again, it is a bit of a mouthful, but we cannot say the same thing by just replacing big-O by Omega, Theta, or little-o (the asymptotic versions of ≥, =, and <, respectively). For example, Theta(n log n) and Omega(n log n) are incorrect, since heapsort only requires a linear number of comparisons if the array already happens to be sorted.
The author argues that random memory access time is O(sqrt(n)), meaning that for large n, it might take up to constant * sqrt(n) time, but might also be faster if the memory to be accessed happens to be very close. Using Omega(sqrt(n)) instead would mean that random memory access can take an arbitrarily long time, but at least constant * sqrt(n). This is not what the author is trying to say.
Yes, but if you continue reading the next post, the author is essentially arguing that the cache hierarchy extends indefinitely due to 1) the speed of light and 2) the amount of information that can fit within a light cone of a certain radius.
In that case, cache hierarchy effects aren't 'weird things that happen below t', they represent the asymptotic behavior we can expect due to the laws of physics, no matter how far out to the right we go.
http://arstechnica.com/science/2014/08/are-processors-pushin...
"Even if signals in the chip were moving at the speed of light, a chip running above 5GHz wouldn't be able to transmit information from one side of the chip to the other". Note that a light-nanosecond is about a foot, so I'm assuming this is talking about the propagation delay of electrons in silicon that need to go through gates, which I'm sure is much slower than light in a vacuum.
To put this another way, you can view the scaling law as a hard upper bound on the speed of access to data; engineers can only approach that bound from below as technology improves.
But given a certain level of technology, it's easier to make a faster L1 cache than an L2 cache, and that will hold even as we approach theoretical limits.
Speed of signal in copper is about ⅔c, I suspect silicon will be in a similar ballbark – and the metal layers linking the silicon layers are made of copper anyway. So it's about 8"/ns… and the (three dimensional, 10+ layer) signal routes are anything but a straight line.
If you look at mainboards (or some smaller PCBs), the connecting lanes between e.g. RAM and CPU closer to the centre are often zigzagged, to match the lengths – and delays – of the necessarily longer outer lanes. The speed of light is actually really damn slow.
I don't think one really appreciates that until they found out that after X hours of place&route they missed timing by some fraction of a nanosecond
It's say it's the opposite, really. The longer the wires, the more effort it takes to synchronize their delays within a certain number of picoseconds.
You've got plenty of stuff at the test stage too. E.g., the gear on high-end Lecroy's metrology test gear is at 100ghz. Agilent (Keysight, whatever, it's still HP to me) has a full test rig for USB3.1[0] at 10gbps for their consumer level gear (again, fairly slow). Step it up to FPGA speeds and here's[1] an app-note by Altera with way higher speeds.
Here's a really brief overview of 'rules of thumb' that work up to PCI-e[2] by TI. 50 minutes and worth a watch. Clean power that won't couple in, matching lines lengths on diff pairs, proper isolated ground planes (give AGND and DGND their own layers) and proper termination will easily get you 95% of the way there.
(Shameless promotion-- available for high-speed design, pre-EMC compliance testing, fault diagnostics, etc).
[0] http://www.keysight.com/en/pd-2472798-pn-U7243B/usb-31-compl... [1] https://www.altera.com/en_US/pdfs/literature/an/an528.pdf [2] https://www.youtube.com/watch?v=A3qw_Ecx9Co
I don't even know what the actual materials are with current technologies, but whatever it is, the speed will be much lower than the vacuum speed of light.
It's possible weird dopings or quantum effect change this dramatically, I suppose. But if I had to guess, they don't.
That's almost completely misleading. Except for the clock itself, nothing that happens inside a processor takes a single clock cycle. And clock distribution delays need compensation anyway.
That's also true of memory. No one has ever seen 1-0-0-0 CAS RAM. (And no one ever will.)
It's true that pushing up against distribution times makes topology more complicated and lowers the maximum possible speed.
But that's actually the difference between electronics and photonics, which promise to run many orders of magnitude faster than EM-based silicon design. (I've seen "millions" quoted, but that may turn out to be hyperbole. Even so - optical fibre can run at tens of Tbps.)
Of course there's a difference between transmission speed, which is a function of the speed of light, and maximum data rate, which is a function of bandwidth.
But unlike electrons-in-silicon connections, photonics may not need to be 100% serial. It's entirely possible to get multiple data channels down a single line with frequency multiplexing, and perhaps also by phase rotation.
That has huge potential to change the packing density and the speed of processor designs; potentially you could have processor elements that were massively parallel but connected with single lines.
There's also some hope that because power dissipation shouldn't be such a problem, it will be easier to make 3D designs - although that's probably more speculative.
Bottom line is silicon is nearly done, but photonics is just getting started. Like fusion power it's probably a couple of decades away, but when it arrives it will be huge.
Now, if we had (partially) clockless processors...
Also, your details are a lot more misleading than those in the article. lots of things in a modern processor take 1 clock cycle. Agner has lovely tables:www.agner.org/optimize/ and note that most basic integer and floating point operations on a skylake processor take 1 cycle - things like bit shuffling, moving, adding (not floats), and quite a few incidental other operations. Now, I'm sure you can quibble that a latency of 1 cycle in that table isn't really 1 cycle under some unusual interpretation of what's going on, but at that point you're quibbling about what "doing something" means, which isn't helpful. What programmers/compiler writers call 1 clock cycle can execute what most people call 1 instruction for many common instructions, even today.
Photonics has a serious density problem: visible light is too large in terms of wavelength. This is already an issue with etching silicon. It's also at best at the 1950s stage where people have developed single photonic transistors in the lab but not yet photonic VLSI.
Anyway, the main factor of delay in chips is capacitance, both between wires and on the gates of FETs. This must be charged through the on resistance of the driving FET and all the intermediate wiring.
Why aren't they any more? Because the speed of light doesn't allow it.
Multi-cycle cache/memory latency and the cache hierarchy it implies is a result of being bound by the speed of light.
They produce downforce to counteract the lift effect of air moving under the car.
It is only necessary at very high speeds, and prevents loss of grip in (especially) the rear tires.
But, yeah, horse and buggy. I'm with you there.
The downforce is there so the car can go around corners quicker; the downforce increases the friction (Ff<=mu x Fn), i.e. the force of friction is less than or equal to the coefficient of friction (mu / μ) multiplied by the normal force. In the case of a tire the normal force is the downward force (provided by the wings or spoilers). Therefore the more downward force the higher the friction hence the more the tire can exert lateral force (cornering force). For example a F1 car at high speed can exert approximately 4Gs of lateral force when cornering, or 5Gs of force when breaking (at slower speeds a F1 car can't brake as hard).
That's not really valid; it's not how algorithmic analysis works. The author's conclusion for what is happening and why is correct, but I believe he is confused about how to get there.
Simply, when doing complexity analysis on an algorithm, one must always count an operation. It's not okay to point to the time taken for an implementation and say "That's our function." It is a function, but it's a function of time, not a count of how many operations are performed at given sizes of N.
However, he is correct that naive analysis of arrays and linked lists will result in this odd behavior: arrays will tend to outperform lists on real systems. The problem with the naive analysis is in what it counts. For example, on an insert, a naive analysis will count the number of elements accessed in the structure. That's naive because it assume all accesses are the same - which is what he's getting at with the "myth of RAM". Because of the memory hierarchy, they are not all equal.
But the correct response is not to give up counting operations and look at time, the correct response is to find the right thing to count. And the right thing to count is basically going to be last level cache misses - the operations that force one to go to memory. If you do that, then you will find that the operations you are counting will correlate much better to the actual time spent.
In some places, the author gets this mostly correct: "You can also use Big-O to analyze the time it takes to access a piece of memory as a function of the amount of memory you are regularly accessing." That's fine, as you're counting memory accesses.
In other places, it's not correct: "That I use Big O to analyze time and not operations is important." You can't count time, only operations. You want to count the operations that correlate with your actual running time, but the entire point of good analysis is to find those operations. You can't just shortcut it, only measure time, and then call it algorithmic analysis.
The author gets a lot right, but despite the lengthy discussion, I think he still has some confusions about algorithm complexity analysis.
For the record, these lessons should be familiar to anyone who has done serious performance analysis of computer systems, either on their own, or in the context of a course that focused on systems or architecture.
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.)
> 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.
That is theoretically correct. But, the difference between theory and practice is that in practice there exists a large percentage of programmers writing code for the real world without understanding and using BigO properly. Their mental model of performance begins and ends with BigO. As far as they are aware, its model is reality.
Source: I've been giving a large number of programmer job interviews lately. It's a rare day when I encounter an engineer (even a senior one) who is aware of any of the issues brought up in this series. And, I work in games!
This is the motivation behind e.g. the "x32 ABI" in Linux: All the power of x86-64 instructions, with none of the additional cache pressure/overhead of 64-bit pointers - log(32) being cheaper than log(64).
...ahh, being this explicit in your Big-O notation is probably not that useful, usually, although I've seen it occasionally in papers (where they're quite explicit about also counting the number of bits involved). Maybe they're dealing with BigNum s, which would make it a practical concern? The key takeaway is this:
> That I use Big O to analyze time and not operations is important.
Time depends on compiler settings, allocation strategy, and a whole host of other factors that are outside the purview of your algorithm. Operations is a lot easier to contrast and compare between different algorithms, the meat of what you're trying to do most of the time. Both are valid choices, just know which one you're dealing with.
The time factors are good to be aware of, to be sure - the performance pitfalls of (potentially) highly fragmented, hard-to-prefetch linked lists over unfragmented flat arrays should be well known to anyone charged with optimizing code - but it's probably easier to think of them as some nebulous large time constant (as even array iteration is going to hit the same worse-than-O(N) behavior, although with proper prefetching the bottleneck may become memory bandwidth rather than memory latency) and deal with those differences with profiling and other measurements, instead of Big-O notation.
Feel free to introduce a packed pointer type that would be asymptotically faster, but then it is a different data structure.
Returning back to the modern era - one also does not need a packed pointer type, merely support for multiple pointer sizes within the same process, and the ability to dynamically dispatch to the correct one for the job. And multiple pointer sizes within the same process are a matter of routine:
In the 16-bit C era, vanilla "near" and "far" pointers very clearly weren't the same size. A very similar situation occurs under the hood when dealing with 32-bit processes on 64-bit windows via WoW64, which can lead to some interesting complications if you use a 64-bit application to create a crashdump for a "32-bit" process, where you can actually inspect the 64-bit side of things too (fire up WinDbg and dig in: https://msdn.microsoft.com/en-us/library/windows/desktop/aa3... )
This is to say nothing of 20+ byte member function pointers on 32-bit architectures because C++ is only out-crazied by C++ compilers. Or dealing with the complications of multiple pointer sizes via shared memory. Or dealing with file "pointers" (read: offsets) of varying sizes.
It'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.
I should note that this paper is more than 25 years old. :-)
His argument has nothing to do with caching or prefetching, etc.
First, it's about random access. You can't prefetch a random fetch!
Second, he's measuring time, a perfectly valid thing to do. And the reality is when you lay your memory cells out in 2 dimensions it takes order of sqrt(n) time to fetch a random memory cell value, where n is the number of memory cells you're using.
Third, it turns out order of sqrt(n) time is the best you can do even if you had the best technology in the universe.
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.
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.
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.
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.
It's interesting to see linked-list as his example, because it is the most likely to have cache-misses as you move through it as the allocations are very fragmented. I'd be very curious to see the same chart on a warmed-up hash-table.
Also, if we're considering the hardware, can we take into account pre-fetching and branch prediction? What are your numbers then? Yeah RAM is farther out then the local caches, but the CPU is also not completely ignorant of what it has to do next.
They don't in the random access machine model, but there are other models where cache misses do factor in.
His argument is that in this universe, the specific laws of physics we have here enforce the property that memory access takes o(sqrt(N)) time [1] where N is the size of your data set.
[1] - What's actually going on is that it takes o(N * sqrt(N)) time to touch N bits of information. Since for any particular bit, it might be very close to the processor and thus fast, but hitting N bits necessitates that most of the bits you access are far away.
Yes as we increase in memory size latency goes up, but he never proves that this is sqrt(N) (he correlates that it is). Each jump in up can be explained by cache misses in each successive local cache, but RAM can scale more than a few orders of magnitude beyond the L3 cache. He needed to keep his chart going past 1GB to see that there is actually a plateau to be hit. If he had scaled to 10GB and then to 100GB he would have seen access times be about the same that they were for 1GB.
If you scale the radius of a sphere by one unit then you indeed get an order of magnitude increase in volume (bits of info), but that's not the correct model! We don't increase by on unit! RAM isn't a one unit increase in radius! It's an order of magnitude increase! If you increase the radius by an order of magnitude you get a 3 fold order of magnitude increase in memory. So you jump up in latency by one order of magnitude and you get 3 orders of magnitude of memory in return.
His analysis and math are wrong.
If the density of your RAM is d, then the volume that a mass of M RAM takes up is M/d. If it's arranged in a sphere, the radius is ((3M)/(4dpi))^(1/3). Notice how this radius is a constant times the cube root of M.
Whereas the Schwarzschild radius scales proportionally to mass.
https://en.wikipedia.org/wiki/Schwarzschild_radius
Thus, if you put enough mass of constant postive density together (no matter how small that density is) eventually you get a black hole.
N.B. - The author's argument is a little more subtle because he's talking about information density via the Berkenstein Bound, and he gets a square root instead of a cube root. But the argument is the same flavor.
And why is there so much misunderstanding on HN of big-O notation wrt cache misses lately?
All you kids, get off my lawn.
No, your model is wrong. Others have already pointed out some issues with the author's understanding of Big-O notation. However, this is a fundamental misunderstanding. Big-O is a tool to analyse some function's asymptotic behaviour, i.e., how it behaves when the input parameter grows versus infinity. You have to put your model of cost into that function. If your measure is time, and memory access doesn't take constant time in your model, then you have to account for that in your cost function. You can just as well use Big-O notation to describe the asymptotic space complexity of an algorithm (how much memory does it need?). O(1) has no special meaning - it's just the set of all unary functions whose value stays below a constant, no matter how large their input parameter gets.
The author is literally blaming his tools for his own misunderstandings.
The notation is worthless for big data use due to unrealistic machine model it implies.
The easy reactive response is that with respect to algorithm design the size of RAM, N, is a constant.
On the other hand for very high scaling factors, as input size rises the size of RAM must also rise. In this way N can be thought of as a variable and that seems to be what the author is thinking. Different algorithms will behave differently as they are scaled to infinity and beyond.
I think the author's argument is interesting but maybe it's better to make new models for time complexity analysis. I think Bob Harper's students have done good work on this.
In addition to distance there is also the cost of selection, namely the muxes and decoders, which would multiply the cost of access by log N.
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...
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.
Assuming the author's O(sqrt(n)) is correct, it seems only relevant on much, much larger scales.
In light of that, it really doesn't make sense to pollute the typical use of Big O notation. It should always be understood to be just one metric to understand an algorithm.
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.
Viewed in this way, O(N) is still O(N), and a processor with caches is a magic device that somehow computes faster than O(N)... or for O(1) computes in sub-constant time (if that can be even well-defined).
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.
> 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. Instruction-based analysis can be a huge help in this consideration, but so can time-based analysis.
Neither should be ignored, and neither invalidates the other.
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.
Great series. Even if you don't agree with the notation it has still valuable information. Thanks author!
And that's IMHO exactly where the original author erred. But i find his musings so incredibly funny and enlightening, that i will use them as a future reference of how NOT to do an analysis.
He didn't just do an apple vs oranges comparison, but he essentially threw eggs, potatoes and ham in the mix and tried to deduce an universal law from his concoction by sprinkling some quantum mechanics fairy dust into the mix! Hilarious!
Just by simply looking at his sloppy graph (Typical origin-shenanigans are often a dead give away for the quality of an examination.) one should be able to recognize the form of an underlying step function, as expected from a multi-layered memory system (L1,L2,L3,RAM, ...) .
But NO, he envisions a Square-Root function, just by arbitrarly placing a line in a logarithmic coordinate system. WTF?! Where is the fitting? And how does he defend his conclusion? drum-roll QUANTUM MECHANICS .... Muhahahaha! Great show!
So essentially it's not cost that prohibits our brave engineers of increasing L1 cache size ad infinitum, but because of quantum mechanics! Muhahahaha! Stop it, my stomach hurts.....
Just by looking at his graphs you could argue, if it's about RAM he should just look at the the part from 10MB to 8G, which shows an almost ideal approximation to O(n log n). The L1 part is even better then O(1), which is curious in itself.
So please excuse me if i'm a bit sarcastic about the "groundbreaking" insights. "Myth of RAM" seems like an attention grabbing caption, and i couldn't help to comment in an according way. No insult or harm ever meant. If perceived as such i do apologize.
This assumption is a shaky one to make, and is easily violated. Imagine if you have a hashmap that is small enough to fit entirely in L3 cache. However, most of it has been evicted from the L1/L2 caches, by other data that the core has been reading/writing to as well. Eventually, the thread returns to the hashmap and performs a single lookup on it. In this scenario, the time required will indeed be O(1).
So what you really have is a best-case-complexity of O(sqrt(N)), if your data has been preloaded in the closest possible caches, and a worst-case-complexity of O(1) if your data is stuck in an outer level cache/DRAM. Given that we usually care more about the worst-case-scenarios, not the best-case-scenario, using the O(1) time complexity seems like a reasonable choice.
Going back to the author's premise that the time-complexity of a single memory access is O(sqrt(N)), not O(1), this is true only where N represents all/most of the dataset being processed. If N represents only a small fraction of the dataset being processed, and your caches are going to be mostly filled with other unrelated data, then the time complexity is closer to O(1).
Clearly the O(sqrt(N)) is more accurate than O(1) under some circumstances, but even so, it's not clear what benefit this accuracy confers. All models are inaccurate simplifications of reality, but simple-inaccurate models can still be useful if they can help in decision-making. Big-O analysis isn't used to estimate the practical running-time of an application. For that, you'd be better off just running the thing. Big-O analysis is more used to compare and decide between different competing algorithms/data-structures. And in that sense, whether you choose to model linked-lists/binary-search/hash-maps as O(Nsqrt(N))/O(log(N)sqrt(N))/O(sqrt(N)), or O(N)/O(logN)/O(1), the recommendation you end up with is the same.
"In general, the amount of books N that fits in a library is proportional to the square of the radius r of the library, and we write N∝ r²."
No, the number of books N is proportional to the area of the front face of the shelving, not the area enclosed within the circle. Assuming all libraries are the same height, that means N is proportional to the circumference of the circle, which is proportional to r, not r². Meanwhile, assuming that all books are reachable in the same amount of time by the librarian no matter their height on the shelf, that means T ∝ r (as before). Since T ∝ r and N ∝ r, that means T ∝ N or T=O(N).
Hint for more efficient placement: You can put shelves away from the outer wall in arbitrary positions within the circle. At that point, the assumption that the librarian can reach any point in the circle at constant time is blatantly false (as the books closer to the centre will generally be faster to reach).
This is rubbish. Re-iterating it is the same as iterating it the first time: if you array doesn't fit into cache, you're going to pay for pulling it from further out into the memory hierarchy.
To anyone who doubts me: try it. Try iterating an array that fits entirely in L1 many times, then do the same with an array that has to be pushed out to swap. The slowdown will be considerably worse than linear.
But in practice, you usually know the order of magnitude of your data, so access is rather O(1), for some constant that depends on the size of the data. Jeff Dean's "Numbers Everyone Should Know" quantifies this constant.
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.
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.
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...
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.
Apples and Oranges? You'll select the relevant data structure depending on your application needs.
mindblown.jpg
It all depends on what kind of machine you are talking about...
http://www.ilikebigbits.com/blog/2014/4/28/the-myth-of-ram-p...
A Turing machine can only go left or right one cell in each step, so e.g. comparing two strings for equality takes O(n²) time as you have to go character by character, moving the head over a suffix of the first word and a prefix of the second word for every character.