Warp wrote:

>   The absolute worst case scenario would be that the list is so large that
> it does not fit entirely in the cache, the elements are scattered randomly
> in memory, far apart from each other (they don't even have to be a lot
> apart from each other; I don't remember how large a typical cache block
> is, but it was something like 32 bytes or so), and the list is traversed
> several times. This causes each single list element access to cause a
> cache miss, which makes it really slow.

I'm told there are special processor intructions for accessing memory 
locations where you "know" that the data will only be read once, so 
there's no point attempting to cache it. This way you can save the cache 
for stuff that *will* be accessed multiple times.

Of course, unless you're programming in assembly, this isn't much help.

>   Sometimes you could make your program faster by simply doing things a
> bit differently. For example, if you are running an algorithm on a list
> several times, and the algorithm doesn't actually require you to traverse
> the list completely in order to get partial results, you could run the
> algorithm on only a part of the list the necessary number of times, after
> which you run it on the next part of the list, etc. If the size of the
> partial list is small enough, all of its elements will fit in the cache
> and the subsequent passes will become a lot faster. This should be so
> even if all the list elements are scattered randomly in memory (it causes
> the first traversal of the partial list to be slow, but subsequent
> traversals should be fast because all the elements will be in the cache).

This is the kind of thing that Haskell does to you automatically. Of 
course, Haskell "lists" are linked lists, scattered over all of the heap 
(and periodically moving around). I don't know much about how CPU caches 
work, but I imagine having the data scattered over several memory pages 
isn't very cache-friendly.

Post a reply to this message