3
$\begingroup$

It looks like most of today's algorithm analysis is done in models with constant-time random access, such as the word RAM model. I don't know much about physics but from popular sources I've heard that there's supposed to be a limit on information storage per volume and on information travel speed, so RAMs don't seem to be physically realizable. Modern computers have all these cache levels which I'd say makes them not very RAM-like. So why should theoretical algorithms be set in RAM?

$\endgroup$
3
$\begingroup$

Let me give a different take on it than vonbrand. Everything you said is true: the RAM model is not realistic for a number of reasons, and whereas it is possible to defend different aspects of it, such a defense doesn't really get to the heart of the matter.

The heart of the matter -- and the answer to your question -- is that the RAM model is the best thing we have. Compared to other models that are accepted, it more accurately models real-life computation. In particular, the reason we adopted the RAM model was primarily a response to Turing machines, as we found that the use of Turing machines leads to problems being artificially difficult to solve in terms of time complexity. The RAM model clearly solves this glaring issue, and thus it has been accepted, even though it remains far from perfect.

A classical example that illustrates the glaring issue with Turing machines is the problem of string equality: given input

$$ w_1 \# w_2$$

where $w_1, w_2$ are binary sequences and $\#$ is a separator, determining whether $w_1 = w_2$. It can be shown that any Turing machine for the equality problem takes $O(n^2)$ time. This is uncomfortable, because Turing machines are what everyone thinks of as the universal model of computation -- yet no software engineer or algorithms researcher believes that string equality really takes $O(n^2)$ time. So what gives? String equality should be linear, so we invent a new model where it is, and the best solution available right now is word RAM machines.

Perhaps some day in the future we will come up with a better model -- one that is simple, conceptually clear, and improves on RAM in its ability to model real-life computational complexity. For now, we can only make do with the best that we have.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You claim RAM to be the "best that we have", but you haven't mentioned in what sense. $\endgroup$ – plop Aug 18 at 13:58
  • $\begingroup$ @plop Thanks -- I meant in the sense of modeling real computation. $\endgroup$ – 6005 Aug 18 at 14:01
  • $\begingroup$ I did say that in the following sentence though, so not sure how to edit to clarify. $\endgroup$ – 6005 Aug 18 at 14:01
  • $\begingroup$ I suspected that. The thing is that if that is the only criterion, then it is just not true that it is the best in existence. There is another criterion that influences how wide spread a model is used and it is how easy it is to analyze problems and algorithms in it. $\endgroup$ – plop Aug 18 at 14:06
  • 2
    $\begingroup$ I think I weakly agree that "RAM model is the best thing we have", but only as a "default" when we're completely oblivious to our actual problem. In practice, what needs to be measured are the bottlenecks. The RAM model seems to hit the bottleneck quite often if nothing special is going on, but there are many cases in which it is obviously the wrong model, such as when exploiting parallelism with GPU's or dealing with massive data on external storage (this is where IO-complexity is more relevant). So while it may be the sharpest tool in the shed, it is far from the only one. $\endgroup$ – Discrete lizard Aug 18 at 14:39
1
$\begingroup$

As a first, rough, approximation you can take the time to access a word in memory as constant, independent of preceding accesses. I.e., the RAM model.

You are right, today's machines are quite un-RAM-like, it does pay off (even handsomely) to organize data access to be as sequential as possible or squeze the last bit of information out of a (short!) memory segment before manhandling the next. But you rarely have the leeway to do so, your memory accesses are essentially random and the model isn't that far from the truth. Plus today's machines have many more than one CPU, the model has just one. And then there is vector processing (doing the same operation on a vector of data, not one by one) as the "multimedia instructions" (and even more using graphics cards for processing) do.

A bit of discussion is given for example by Khoung's Binary search is a pathological case for caches. As you see, analyzing even simple, well-understood algorithms under more realistic memory access time models is daunting.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ So the motivation is that it's an approximation of modern computers? That doesn't seem very strong to me, especially since afaik how modern computers work is largely an accident of history. $\endgroup$ – acupoftea Aug 18 at 6:13
  • $\begingroup$ @acupoftea, not really. They model computers of decades past. Still a reasonably good model for rough estimates, though. $\endgroup$ – vonbrand Aug 18 at 13:04
  • $\begingroup$ @acupoftea: The main argument is that the RAM model, flawed as it is, is still a much better model than the other models we have, most famously Universal Turing Machine and λ-calculus. $\endgroup$ – Jörg W Mittag Aug 18 at 20:02
1
$\begingroup$

RAM model is motivated by asymptotic analysis of algorithms that are designed as single-threaded in-memory computations.

Optimising performance for specific instruction set, caches and whatnot is one thing. The other thing is to be prepared for growth of the problem size. To estimate how well your in-memory algorithm scales you probably want to ignore small factors and focus on big $\mathcal{O}$ notation. Big $\mathcal{O}$ isn't going to optimise everything for you, but at least it may tell you that your solution scales well (or that you should try something different).

RAM assumes small fixed instruction set, where each operation works in $\mathcal{O}(1)$. Note that this is a good model if we only care about asymptotic growth:

  1. Instruction set of a modern CPU is not small, but we can pretend that it actually is. Those additional op-codes do not make difference in the big $\mathcal{O}$ notation.

  2. CPUs may have instructions whose runtime depends on input. Again, we can ignore them, because we can model them using simpler instructions without affecting big $\mathcal{O}$ complexity. The same holds for cache levels: their performance is still bounded by some small constant, thus work in $\mathcal{O}(1)$ by definition.

  3. Yes, you can't access memory in constant time if it keeps growing. Luckily, this is never required thanks to common sense. Nobody is indexing the entire Internet into non-persistent memory of a lonely single-threaded machine.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.