Re: [PATCH] use tail pointer for LOOP

[David Kastrup <dak@gnu.org>]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

>>         Reverse: (1.006534 3 0.682734)
>>    Tail pointer: (1.305476 4 0.9159619999999986)
>
>> Still, reversing seems to be worth it (by some 30 percent). Unless we
>> find some way to streamline the tail pointer better.
>
> That's really not surprising: count the number of function calls and
> you'll see that the nreverse way is likely to win every time, simply
> because it suffers about half as much from the interpretation overhead.

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.

-- 
David Kastrup