|
![](/i/fill.gif) |
Darren New wrote:
> Kind of like what Warp talks about w.r.t. cache lines, except with VM
> pages.
It's all just different levels of the memory hierachy.
It used to be that you had a block of RAM, all accessible in O(1) time.
Now you have virtual memory (which pretends to be RAM, but is orders of
magnitude slower), maybe three levels of cache (which pretends to be
RAM, but is orders of magnitude faster - except if it's another core's
cache, in which case it's *slower* than RAM again due to coherance
issues), and you could regard the CPU registers themselves as the
ultimate level-0 "cache".
The sad fact is, processors are now 1000x faster than they used to be,
but RAM is still roughly the same speed. And that means that if you
don't want your expensive new CPU to just spend 1000x more cycles doing
nothing, you need to have this memory hierachy. And *that* means that
the time complexity of your algorithm is now *irrelevant*. The *only*
thing that matters now is cache behaviour.
As the paper says, a stupid O(n^2) algorithm could be *faster* than a
sophisticated algorithm with O(log n) or even O(1) time-complexity, all
due to cache effects that shouldn't be there in the first place. Decades
of research and development ruined. Now we have no way to predict
performance, because it depends on cache behaviour, which intimately
depends on the specifics of a particular implementation, not on the
abstract properties of the algorithm used.
Possibly the worst part is that, unless you program in some horribly
low-level language, you have no control over any of this.
Post a reply to this message
|
![](/i/fill.gif) |