Re: [PATCH] use tail pointer for LOOP

[Stefan Monnier <monnier@iro.umontreal.ca>]

> nreverse is also cons-neutral.  The only situation where I'd expect it
> to be able to lose is under virtual memory pressure, where the nreverse
> approach has to cons the list forwards when building, and again
> backwards when reversing the conses.  A tail pointer approach will
> traverse the list just once.  So if it does not fit in real memory, tail
> pointers may cause half the page faults than nreverse does.

Doesn't have to be as drastic as "virtual memory".  If the list is long
enough to overflow some level of the memory hierarchy, then the
tail-pointer approach has a fighting change.  Hopefully such lists are
really rare (lists that overflow the L1 cache are probably fairly common
(about 1000 elements), but the speed difference between L1 and L2 cache
is probably not sufficient to defeat nreverse).


        Stefan