On Monday 21 of February 2011 21:54:17 you wrote:
> Hi Dexen & Jos=E9,
> >> Now if you access the array in a semi-random order, so-called `cache
> >> trashing' will ensue. Pretty much like reading random data from the
> >> harddrive (for example from swap). The CPU, starved of data, will
> >> idle uselessly.
> this is quite a low level detail and the effect on lists is the same.
> The PicoLisp lists live on the heap which is an array of cells in the C
> terms after all. However, for lists this happens more often, depending
> on how the list came into existence because the data will be quite
> likely spread over many different memory pages.
I'm not much experienced in details, but I'd guess `yes and no' ;)
A `naive' implementation of compiler would emit code that *just* operates on
the data, and a`naive' CPU would *just* execute explicit instructions.
However, modern CPUs have instructions for data pre-fetch & prefetching hints
(for explicit indication of prefetch) and a competent compiler can be expected
to include such ones in proper places. Also, the CPU performs some analysis of
all opcodes & is free to pre-fetch any data & code it considers likely to be
used in future -- up to and including speculative execution of future
In the end, I'd guess walking a (linked) list can be more explicit indicator
for CPU to get the right data pre-fetched.
But then again, that's just speculative fiction :)
``One can't proceed from the informal to the formal by formal means.''