The Myth of RAM (2014)

The article was specifically talking about putting algorithms onto real machines and the speed consequences. This creates a new version of the algorithm with certain limits. And because of these limits, there is a maximum runtime for any halting code, and it is a constant number.

The colloquial use of big O as a general growth factor doesn't hold up to its definition, if you want to be sure it's valid for small inputs too.

I'm in agreement that saying algorithms on computers are all O(1) doesn't make much sense. In a finite memory model, it's impossible to solve big problems, so the running time function becomes undefined for big enough inputs, so big O becomes completely inappropriate in this situation.

So yes, your algorithm is bound by O(N^2), and that's the number that matters on practical computers... but it's also bound by O(1) with a stupidly large constant. So it's O(1).

> I guess you're the kind of guy that chooses to uses not 8-bit bytes in an interview?

Dude, I'm here specifically to argue against insisting on the exact literal meaning, and to choose the practical option.

Mechanical sympathy has little (if anything) to do with big-O, btw. LMAX, the poster child of mechanical sympathy, is really about minimizing the use of memory coherence machinery and not taking the substantial latency hits.

Now, the actual layout of your address space in RAM is not necessarily contiguous of course. That has nothing to do with ASLR, it is all related to virtual memory, a much older concept. However, this is also irrelevant for performance, at least until you get to NUMA architectures which anyway need their own specific models.

The reason virtual memory to physical memory mapping doesn't really matter for performance is that RAM is, actually, random access at this level. Reading two contiguous cache lines worth of data from physical RAM into the processor cache is just as fast as reading two non-contiguous ones.

The reason random memory accesses are much slower than linear ones is not the physical layout in RAM. It is because when doing linear reads, you'll get most of the data from the processor cache with a single slow read from RAM, whereas with random access you'll need to go all the way to RAM (or gods forbid, to disk) for each and every read. The difference is exacerbated even more by predictive pre-fetchers, which can paralleize reading the next cache line from RAM while your code is running on the current cache line - but those only work if your code will indeed use the predicted next cache line, otherwise you'll stall.

So, random access code is slow because it is actually running at the RAM's speed. Linear access code is fast because it is actually running at the L1 cache's speed. Physical layout of your pages in memory is almost entirely irrelevant (it's only a problem if your reads are not page-size aligned, which is not normally possible).

And finally, the cache-oblivious computing model for complexity analysis is pretty well established, and it is known to be significantly better at predicting real-world performance differences than the more traditional system. It is more complex to work with, though, so some people don't bother. And it is not of that much theoretical interest in the field of computational complexity analysis, since it doesn't fundamentally change the complexity class of any algorithms (e.g. both this and the simpler O(1) memory access model will agree on whether an algorithm is polynomial or exponential).

People very very often work with data that doesn't fit into the fastest available memory, so modeling that fact that memory accesses taking O(foo(N)) time makes a lot of sense if you want to compare the performance of algorithms with different amounts of memory accesses. The performance differences predicted by a model that adds this complexity compared to a model that doesn't will be better.

For example, traditional complexity analysis predicts that linear search in a linked list should be about as fast as in an array up to some constant factor. If you instead model memory access as taking longer the larger the data structure you seek to access, you'll predict that linked list search is in fact worse and worse compared to array search as the size of each increases. This second prediction will more closely match the actual performance on real hardware.

In contrast, people very rarely work on problems where fixed, small size integers (i32, i64) are not good enough. Those that do also typically model addition as an O(foo(N)) operation.

There is of course some interesting overlap where you'd perhaps want to model the actual address calculation using large integers, but since in practice that will almost always be much faster than the actual memory access itself, it's rarely useful to account for it inatead of the memory access cost.