Re: [PATCH] use tail pointer for LOOP

[David Kastrup]

address@hidden writes:

> On Sat, May 29, 2010 at 08:49:13PM -0400, Daniel Colascione wrote:
>> On 5/29/10 8:45 PM, Ken Raeburn wrote:
>
> [...]
>
>> > 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 [...]
>
> This has intrigued me for quite a while.
>
> Since I really should be doing tax declarations, I couldn't hold back for
> longer -- here is my (very unscientific) approach, to help you all
> procrastinate a bit too:
>
>  | (defun copy1 (lst)
>  |   "Build up a copy of lst by consing up in reverse order, then
>  | reversing"
>  |   (let ((res))
>  |     (while lst
>  |       (setq res (cons (car lst) res)
>  |             lst (cdr lst)))
>  |     (nreverse res)))
>  | 
>  | (defun copy2 (lst)
>  |   "Build up a copy of lst by consing up in order, keeping a tail
>  | pointer"
>  |   (when lst
>  |     (let ((res) (tail))
>  |       (setq res (cons (car lst) nil)
>  |             tail res
>  |             lst (cdr lst))
>  |       (while lst
>  |         (setcdr tail (cons (car lst) nil))
>  |         (setq tail (cdr tail)
>  |               lst (cdr lst)))
>  |       res)))
>  | 
>  | (defun runtwo (n)
>  |   (let ((lst))
>  |     (while (> n 0)
>  |       (setq lst (cons n lst)
>  |             n (1- n)))
>  |     (garbage-collect)
>  |     (cons (benchmark-run (copy1 lst)) 
>  |           (benchmark-run (copy2 lst)))))
>  | 
>  | (runtwo 1000000)
>
> (Maybe the tail pointer version could be done more elegantly: I'd be
> delighted to be taught more :)
>
> Turns out that the nreverse version is a tad faster (on my hardware, one
> of those Atom based netbooks, in case it matters) -- about 2.1 versus
> 2.7 seconds for a list of size 10^6. Garbage collections are comparable.

Did you byte-compile?

-- 
David Kastrup