Hi,

A few days ago I was pointed to THIS series (4) of articles. When you posess a proper grasp on math (I, as a bookkeeper of sorts, merely get the gist), you may indulge in it. Have a nice read!

OldFart

_________________
More then three levels of indigestion and you're scroomed!

@OldFart

Where's the myth part? We all know that ram accesses tend to transfer entire cache lines, even when asking for a single byte where data cache exists and is enabled and that randomly accessing data over a wide distance (like traversing a linked list with node addresses scattered all over the show) is suboptimal. The best memory performance is achieved generally for streaming sequential operations under such circumstances.

After that you've got additional complications from memory management, paging strategies and so forth.

_________________
Doing stupid things for fun...

@Karlos

Quote:

Where's the myth part?

The myth, as the author clearly states, is, that memoryaccess of the kind he depicts are/were considered to be O(1), whatever that means (remember I'm a bookkeeper!), however he debunks, or tries to debunk that.

From the preface:
Quote:

This article is the first of four in a series, in which I argue that thinking of a memory access as O(1) is generally a bad idea, and we should instead think of them as taking O(√N) time.

Please, don't shoot the messenger!

OldFart

_________________
More then three levels of indigestion and you're scroomed!

@OldFart

Not shooting, don't worry. I guess I wasn't sure why even when the article was written any engineers would still think memory accesses were simple things you just counted in basic cycles. That all went out of the window with caches.

_________________
Doing stupid things for fun...

Quote:

Karlos wrote: Where's the myth part? We all know that ram accesses tend to transfer entire cache lines, ...

Some really don't know or they don't accept the consequences, reading data from continuous addresses is much faster than reading data from a lot of different addresses. The Amiga DMA engine would have needed caches to do the same for higher DMA transfers with the same memory chips.