Re: [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP)

[Daniel Colascione]

On 5/29/10 8:45 PM, Ken Raeburn wrote:
> On May 29, 2010, at 19:58, Daniel Colascione wrote:
>> We do this only for the anonymous-variable case, but it's still an
>> improvement.
> 
> If it's only in the anonymous case, where (if I understand
> correctly)
> the value isn't accessible until the loop construct returns a value, why
> not keep it simple and build the list in reverse, doing an nreverse call
> at the end? It doesn't need to be "in order" in the intermediate states.
> Is it any faster to build the list in order? (Simply avoiding nreverse
> obviously makes things a little faster, but are you doing more work each
> time around the loop to maintain and use the tail pointer?)

It's only a little bit more work to use the tail pointer, and it saves
having to traverse the entire list on return, which could be a lot of
work for a large list. For small lists, it might be a tossup, but then
the difference doesn't matter much in that case anyway.

Also, other LOOP implementations use tail pointers.

signature.asc
Description: OpenPGP digital signature