Re: [Ocaml-lib-devel] Idea with ExtList.fold_right

[John M. S. <sk...@oz...>]

Brian Hurt wrote:

> On Tue, 17 Jun 2003, John Max Skaller wrote:
>
> Loop overhead is negligable.  Especially with today's imbalance between 
> processor and memory speeds, I'd be way more concerned about thrashing L1 
> code cache.  Especially for short lists which are probably in cache 
> anyways.  On a P4, a *single* cache miss can cost over 300 clock cycles.  
> I can do an awful lot of loops in 300 clock cycles.


That's true.


> With fold_right, it's impossible - 

On the contrary. A fold right has to recurse all down the list,
which is nasty, but after that it could be cache efficient in
the extreme: we have a linear array of the data on the stack now,
which the cache should handle with very high efficiency both
because it only requires sequential memory access and also because
if the system has any smarts, it knows the stack is a good candidate
for sequential-predictive caching. So it's possible the right fold, after
linearising the list, is actually FASTER than a left fold since
the whole of the operation can sometimes be done without a single
cache-miss if the predictive memory loading is optimised appropriately.
[Linear memory fetches can take 0 real time if they're spaced out
enough -- the memory itself can sometime cache linear chunks]

Basically: the tail chasing is efficient because while it
looks all over memory for the list nodes, the code
to do that is a tight loop in the cache. Then the user
fold operation can be loaded into the cache, and operate
directly on in-cache data in the case of integers,
or with one access for pointers.

The left fold, on the other hand, mixes the code
for the list access and folding, which may spill the
instruction cache, and there is no opportunity
for sequential-prediction (only invariant prediction
for the fold result). The additional code for the
left fold atom may also force a register spill
which doesn't happen in the right_fold (the fold accumulator)
and of course registers (L0 cache :-) are even faster
than the L1 cache.

Well, I'm totally unsure of any of this, but don't
be TOO fast to assume fold_right is always a dog :-)

-- 
John Max Skaller, mailto:sk...@oz...
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850