|
![](/i/fill.gif) |
>> 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.
>
> You cannot just take a mathematical paper and expect it to
> work as described on a computer, you never have been able to.
Back in the days of the 8-bit home computer, memory access really was a
constant-time operation that always took 1 clock cycle. Unfortunately it
seems that the larger a memory bank is, the slower it is to access. What
this means is that a 2.2 GHz CPU only runs at 2.2 GHz if you use a tiny
amount of data. If you try to random-access a large chunk of data,
suddenly the program slows down to the speed of the RAM bus.
I guess the only consolation is that my CPU's L3 cache is probably
bigger than the entire address space of the 6502...
> Sure, but it's always been like that and always will, there's nothing
> you can do about it.
It wasn't always like that - but, as you say, there's nothing you can do
about it.
>> Possibly the worst part is that, unless you program in some horribly
>> low-level language, you have no control over any of this.
>
> If your language/compiler is clever enough to switch around the order
> and storage of your code, then it should be clever enough to optimise
> for the memory structure of the machine.
Sure. But if it isn't, you can't do anything about it. You can't rewrite
the compiler, after all...
Post a reply to this message
|
![](/i/fill.gif) |