O(N^2) behavior in LOOP

O(N^2) behavior in LOOP

[Daniel Colascione]

[-- Attachment #1: Type: text/plain, Size: 892 bytes --]

Erm, what's going on here?

  (loop for x in '(1 2 3)
        collect x into foo)

Expands into

  (cl-block-wrapper
   (catch '--cl-block-nil--
     (let*
         ((--cl-var--
           '(1 2 3))
          (x nil)
          (foo nil))
       (while
           (consp --cl-var--)
         (setq x
               (car --cl-var--))
         (setq foo
               (nconc foo
                      (list x)))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ WTF?
         (setq --cl-var--
               (cdr --cl-var--)))
       nil)))


What is going on with the indicated line? That's O(N^2) because nconc
has to traverse the entire 'foo' list each time a value is appended.
Without the 'into' clause, loop uses push and nreverse, which, while
still suboptimal, is at least linear.

Before I go fix the loop macro, is there a _reason_ for the nconc silliness?


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: O(N^2) behavior in LOOP

[Daniel Colascione]

[-- Attachment #1: Type: text/plain, Size: 759 bytes --]

On 5/29/10 5:56 PM, Daniel Colascione wrote:
> Before I go fix the loop macro, is there a _reason_ for the nconc silliness?

Err, never mind. LOOP has to work that way. An 'into' variable is
visible; code that LOOP knows nothing about can modify it in arbitrary
ways, which would invalidate any cached tail pointer, ruling out that
approach. Also, code that inspects the variable should see a
representation "as it should be", which rules out a temporarily-reversed
representation, ruling out the push and nconc used in the
anonymous-variable case.

I don't see any way to do better than what LOOP does now without some
kind of code-walker. I still want to fix the anonymous-variable case to
use a tail pointer though.

Sorry for the noise.


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: O(N^2) behavior in LOOP

[Lennart Borgman]

On Sun, May 30, 2010 at 12:06 AM, Daniel Colascione
<daniel@censorshipresearch.org> wrote:
> On 5/29/10 5:56 PM, Daniel Colascione wrote:
>> Before I go fix the loop macro, is there a _reason_ for the nconc silliness?
>
> Err, never mind. LOOP has to work that way. An 'into' variable is
> visible; code that LOOP knows nothing about can modify it in arbitrary
> ways, which would invalidate any cached tail pointer, ruling out that
> approach. Also, code that inspects the variable should see a
> representation "as it should be", which rules out a temporarily-reversed
> representation, ruling out the push and nconc used in the
> anonymous-variable case.
>
> I don't see any way to do better than what LOOP does now without some

Perhaps advice against using it and give alternatives?

Re: O(N^2) behavior in LOOP

[Geoff Gole]

For what it's worth, the elisp and SBCL implementations of LOOP behave
differently when the last cdr of the loop is assigned to.

; elisp
(loop for i from 1 to 3
      collecting i into x
      collecting (progn (setf (cdr (last x)) (list 'foo)) 1) into x
      finally (return x))
(1 foo 1 2 foo 1 3 foo 1)

; SBCL
(loop for i from 1 to 3
      collecting i into x
      collecting (progn (setf (cdr (last x)) (list 'foo)) 1) into x
      finally (return x))
(1 1 2 1 3 1)

The SBCL macro emits much more efficient code, but I think it's wrong.
Not that LOOP is a particuarly well defined thing to judge correctness
against.

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

[Daniel Colascione]

[-- Attachment #1: Type: text/plain, Size: 5755 bytes --]

We do this only for the anonymous-variable case, but it's still an
improvement.

---
/Applications/Emacs.app/Contents/Resources/lisp/emacs-lisp/cl-macs.el
2008-01-06 20:07:45.000000000 -0500
+++ cl-macs2.el	2010-05-29 19:52:09.000000000 -0400
@@ -625,6 +625,7 @@
 (defvar loop-initially) (defvar loop-map-form) (defvar loop-name)
 (defvar loop-result) (defvar loop-result-explicit)
 (defvar loop-result-var) (defvar loop-steps) (defvar loop-symbol-macs)
+(defvar loop-accum-tailptr)

 (defmacro loop (&rest args)
   "The Common Lisp `loop' macro.
@@ -650,7 +651,8 @@
 	  (loop-accum-var nil)	(loop-accum-vars nil)
 	  (loop-initially nil)	(loop-finally nil)
 	  (loop-map-form nil)   (loop-first-flag nil)
-	  (loop-destr-temps nil) (loop-symbol-macs nil))
+	  (loop-destr-temps nil) (loop-symbol-macs nil)
+          (loop-accum-tailptr nil))
       (setq args (append args '(cl-end-loop)))
       (while (not (eq (car args) 'cl-end-loop)) (cl-parse-loop-clause))
       (if loop-finish-flag
@@ -984,28 +986,49 @@

      ((memq word '(collect collecting))
       (let ((what (pop args))
-	    (var (cl-loop-handle-accum nil 'nreverse)))
+	    (var (cl-loop-handle-accum nil :use-tailptr)))
 	(if (eq var loop-accum-var)
-	    (push (list 'progn (list 'push what var) t) loop-body)
-	  (push (list 'progn
-		      (list 'setq var (list 'nconc var (list 'list what)))
-		      t) loop-body))))
+            ;; Anonymous case; we can use a tail pointer here
+            (push `(progn
+                     (if ,var
+                         (setq ,loop-accum-tailptr
+                               (setcdr ,loop-accum-tailptr (list ,what)))
+                       (setq ,var (list ,what))
+                       (setq ,loop-accum-tailptr ,var))
+                     t)
+                  loop-body)
+
+          ;; 'into' case. We have to use nconc here instead of
+          ;; tail-ptr setup or push-then-nreverse because user code
+          ;; can inspect and modify the given variable at any time.
+          (push `(progn
+                   (setq ,var (nconc ,var (list ,what)))
+                   t)
+                loop-body))))

-     ((memq word '(nconc nconcing append appending))
+     ((memq word '(nconc noncing append appending))
       (let ((what (pop args))
-	    (var (cl-loop-handle-accum nil 'nreverse)))
-	(push (list 'progn
-		    (list 'setq var
-			  (if (eq var loop-accum-var)
-			      (list 'nconc
-				    (list (if (memq word '(nconc nconcing))
-					      'nreverse 'reverse)
-					  what)
-				    var)
-			    (list (if (memq word '(nconc nconcing))
-				      'nconc 'append)
-				  var what))) t) loop-body)))
+	    (var (cl-loop-handle-accum nil :use-tailptr)))

+        (push (if (eq var loop-accum-var)
+                  (let ((func (if (memq word '(nconc noncing))
+                                  'identity 'copy-sequence)))
+
+                    ;; use tail pointer
+                    `(if ,var
+                         (setq ,loop-accum-tailptr
+                               (last (setcdr ,loop-accum-tailptr
+                                             (,func ,what))))
+                       (setq ,var (,func ,what))
+                       (setq ,loop-accum-tailptr (last ,var))))
+
+                ;; visible variable; no tail pointer
+                (let ((func
+                       (if (memq word '(nconc nconcing)) 'nconc append)))
+                  `(setq ,var (,func ,var ,what))))
+              loop-body)
+        (push t loop-body)))
+
      ((memq word '(concat concating))
       (let ((what (pop args))
 	    (var (cl-loop-handle-accum "")))
@@ -1144,20 +1167,36 @@
       (list* (if par 'let 'let*)
 	     (nconc (nreverse temps) (nreverse new)) body))))

-(defun cl-loop-handle-accum (def &optional func)   ; uses args, loop-*
-  (if (eq (car args) 'into)
-      (let ((var (cl-pop2 args)))
-	(or (memq var loop-accum-vars)
-	    (progn (push (list (list var def)) loop-bindings)
-		   (push var loop-accum-vars)))
-	var)
-    (or loop-accum-var
-	(progn
-	  (push (list (list (setq loop-accum-var (make-symbol "--cl-var--")) def))
-		   loop-bindings)
-	  (setq loop-result (if func (list func loop-accum-var)
-			      loop-accum-var))
-	  loop-accum-var))))
+(defun cl-loop-handle-accum (def &optional listp)   ; uses args, loop-*
+  (cond ((eq (car args) 'into) ; accumulate into visible variable
+         (let ((var (cl-pop2 args)))
+           (or (memq var loop-accum-vars)
+               (progn (push (list (list var def)) loop-bindings)
+                      (push var loop-accum-vars)))
+           var))
+
+        ;; Otherwise, if we've already configured our anonymous
+        ;; accumulation variable so just return it.
+        (loop-accum-var)
+
+        ;; We're accumulating a list, so in addition to setting up
+        ;; loop-accum-var, set up loop-accum-tailptr.
+        (listp
+         (push (list (list (setq loop-accum-var (make-symbol
"--cl-accum--")) def))
+               loop-bindings)
+         (push (list (list (setq loop-accum-tailptr
+                                 (make-symbol "--cl-tailptr--")) def))
+               loop-bindings)
+         (setq loop-result loop-accum-var)
+         loop-accum-var)
+
+        ;; We're accumulating something else.
+        (t
+         (push (list (list (setq loop-accum-var (make-symbol
"--cl-var--")) def))
+               loop-bindings)
+         (setq loop-result (if func (list func loop-accum-var)
+                             loop-accum-var))
+         loop-accum-var)))

 (defun cl-loop-build-ands (clauses)
   (let ((ands nil)



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

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

[Ken Raeburn]

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?)

Ken

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

[Daniel Colascione]

[-- Attachment #1: Type: text/plain, Size: 1035 bytes --]

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.


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: [PATCH] use tail pointer for LOOP

[Štěpán Němec]

Daniel Colascione <daniel@censorshipresearch.org> writes:

> We do this only for the anonymous-variable case, but it's still an
> improvement.
>
> ---
> /Applications/Emacs.app/Contents/Resources/lisp/emacs-lisp/cl-macs.el
> 2008-01-06 20:07:45.000000000 -0500
> +++ cl-macs2.el	2010-05-29 19:52:09.000000000 -0400
> -     ((memq word '(nconc nconcing append appending))
> +     ((memq word '(nconc noncing append appending))

[...]

> +                  (let ((func (if (memq word '(nconc noncing))

[...]

??? If that's a typo (and I can hardly think about any other reason),
then it's an interesting one, indeed.

Štěpán

Re: [PATCH] use tail pointer for LOOP

[Daniel Colascione]

[-- Attachment #1: Type: text/plain, Size: 953 bytes --]

Good catch. That is indeed a typo. Clearly, that should be "nconcing". I'm blaming dabbrev right now. :-)



-- Sent from my Palm Pre
On May 30, 2010 1:06 PM, Štěpán Němec <stepnem@gmail.com> wrote: 

Daniel Colascione <daniel@censorshipresearch.org> writes:



> We do this only for the anonymous-variable case, but it's still an

> improvement.

>

> ---

> /Applications/Emacs.app/Contents/Resources/lisp/emacs-lisp/cl-macs.el

> 2008-01-06 20:07:45.000000000 -0500

> +++ cl-macs2.el	2010-05-29 19:52:09.000000000 -0400

> -     ((memq word '(nconc nconcing append appending))

> +     ((memq word '(nconc noncing append appending))



[...]



> +                  (let ((func (if (memq word '(nconc noncing))



[...]



??? If that's a typo (and I can hardly think about any other reason),

then it's an interesting one, indeed.



Štěpán





[-- Attachment #2: Type: text/html, Size: 1296 bytes --]

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

[tomas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

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.

For the very curious (and to add some scientific varnish to this ;-),
here's my Emacs:

  GNU Emacs 23.1.91.1 (i486-pc-linux-gnu, GTK+ Version 2.12.12)
  of 2010-01-11 on elegiac, modified by Debian

Enjoy -- and may this keep you too from doing more important things ;-)

Regards
- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFMGQ10Bcgs9XrR2kYRAoRdAJoCbSaPZ2eUX6QiKKDW1NjQGV3G8gCfca9C
tyyHzMbrUJopGOPzwTEJUjs=
=ZBiq
-----END PGP SIGNATURE-----

Re: [PATCH] use tail pointer for LOOP

[David Kastrup]

tomas@tuxteam.de 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

Re: [PATCH] use tail pointer for LOOP

[tomas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wed, Jun 16, 2010 at 08:10:48PM +0200, David Kastrup wrote:
> tomas@tuxteam.de writes:

[...]

> > This has intrigued me for quite a while.

> > (Maybe the tail pointer version could be done more elegantly: I'd be
> > delighted to be taught more :)

[...]

> Did you byte-compile?

Thanks, David. Good point. That's the outcome:

Without byte compilation:

       Reverse: (2.165832 5 0.7267649999999994)
  Tail pointer: (2.795332 4 0.8909630000000011)

Byte compiling copy1, copy2 (and runtwo, for good measure, but I
wouldn't expect that to matter):

        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.

Regards
- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFMGa49Bcgs9XrR2kYRAu/DAJwK+aD1fiV3nISL212UR8JqFTaokwCdEt/G
D64HURkJwg2EduxzFNvfY9g=
=wSpa
-----END PGP SIGNATURE-----

Re: [PATCH] use tail pointer for LOOP

[Thien-Thi Nguyen]

() tomas@tuxteam.de
() Thu, 17 Jun 2010 07:10:21 +0200

   Still, reversing seems to be worth it (by some 30 percent).
   Unless we find some way to streamline the tail pointer better.

How does this variant fare?

(defun copy3 (lst)
  "Return a copy of LST."
  (let* ((box (list nil))
         (tp box))
    (while lst
      (setq tp (cdr (nconc tp (list (pop lst))))))
    (cdr box)))

thi

Re: [PATCH] use tail pointer for LOOP

[tomas]

[-- Attachment #1.1: Type: text/plain, Size: 943 bytes --]

On Thu, Jun 17, 2010 at 09:18:28AM +0200, Thien-Thi Nguyen wrote:
> () tomas@tuxteam.de
> () Thu, 17 Jun 2010 07:10:21 +0200
> 
>    Still, reversing seems to be worth it (by some 30 percent).
>    Unless we find some way to streamline the tail pointer better.
> 
> How does this variant fare?
> 
> (defun copy3 (lst)
>   "Return a copy of LST."
>   (let* ((box (list nil))
>          (tp box))
>     (while lst
>       (setq tp (cdr (nconc tp (list (pop lst))))))
>     (cdr box)))

Cute. You all are successfully keeping me from work. Enjoing it ;-)

Here are the results. Attached the modified source.

  copy1: (1.058881 5 0.7366780000000048)
  copy2: (1.27958 6 0.8913360000000026)
  copy3: (1.337353 6 0.9249420000000015)

Still the reverse version is the winner. Yours seems to be a tad slower
(although I wouldn't know whether it's in the noise).

But  it looks so sharp ;-)

Thanks, regards
-- tomás


[-- Attachment #1.2: bm.el --]
[-- Type: text/plain, Size: 1403 bytes --]

;; This buffer is for notes you don't want to save, and for Lisp evaluation.
;; If you want to create a file, visit that file with C-x C-f,
;; then enter the text in that file's own buffer.

(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 copy3 (lst)
  "Return a copy of LST."
  (let* ((box (list nil))
         (tp box))
    (while lst
      (setq tp (cdr (nconc tp (list (pop lst))))))
    (cdr box)))

(defun do-benchmark (n)
  (let ((lst))
    (while (> n 0)
      (setq lst (cons n lst)
            n (1- n)))
    (garbage-collect)
    (message (concat "copy1: %S\n"
                     "copy2: %S\n"
                     "copy3: %S\n")
            (benchmark-run (copy1 lst))
            (benchmark-run (copy2 lst))
            (benchmark-run (copy3 lst)))))

(byte-compile 'copy1)
(byte-compile 'copy2)
(byte-compile 'copy3)
(byte-compile 'do-benchmark)

(do-benchmark 1000000)

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] use tail pointer for LOOP

[Thien-Thi Nguyen]

() tomas@tuxteam.de
() Thu, 17 Jun 2010 11:22:32 +0200

   Cute. You all are successfully keeping me from work. Enjoing it ;-)

   Here are the results. Attached the modified source.

     copy1: (1.058881 5 0.7366780000000048)
     copy2: (1.27958 6 0.8913360000000026)
     copy3: (1.337353 6 0.9249420000000015)

   Still the reverse version is the winner. Yours seems to be a tad slower
   (although I wouldn't know whether it's in the noise).

   But  it looks so sharp ;-)

How about this one?

(defun copy4 (lst)
  "Return a copy of LST."
  (let* ((box (list nil))
         (tp box))
    (while lst
      (setq tp (setcdr tp (list (pop lst)))))
    (cdr box)))

thi

Re: [PATCH] use tail pointer for LOOP

[Thien-Thi Nguyen]

() tomas@tuxteam.de
() Thu, 17 Jun 2010 11:22:32 +0200

Oops, i didn't look at this carefully before:

   (defun do-benchmark (n)
     (let ((lst))
       (while (> n 0)
         (setq lst (cons n lst)
               n (1- n)))
       (garbage-collect)
       (message (concat "copy1: %S\n"
                        "copy2: %S\n"
                        "copy3: %S\n")
               (benchmark-run (copy1 lst))
               (benchmark-run (copy2 lst))
               (benchmark-run (copy3 lst)))))

Probably for more meaningful results, you should ‘garbage-collect’
prior to each ‘benchmark-run’.  Otherwise, each run is disadvantaged
(less memory "easily" available) with respect to its predecessor.
A standard benchmarking principle (useful in other disciplines, too)
is to eliminate these differences.

thi

Re: [PATCH] use tail pointer for LOOP

[tomas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thu, Jun 17, 2010 at 12:03:16PM +0200, Thien-Thi Nguyen wrote:
> () tomas@tuxteam.de
> () Thu, 17 Jun 2010 11:22:32 +0200
> 
>    Cute. You all are successfully keeping me from work. Enjoing it ;-)
> 
>    Here are the results. Attached the modified source.
> 
>      copy1: (1.058881 5 0.7366780000000048)
>      copy2: (1.27958 6 0.8913360000000026)
>      copy3: (1.337353 6 0.9249420000000015)
> 
>    Still the reverse version is the winner. Yours seems to be a tad slower
>    (although I wouldn't know whether it's in the noise).
> 
>    But  it looks so sharp ;-)
> 
> How about this one?
> 
> (defun copy4 (lst)
>   "Return a copy of LST."
>   (let* ((box (list nil))
>          (tp box))
>     (while lst
>       (setq tp (setcdr tp (list (pop lst)))))
>     (cdr box)))

Here you go:

  copy1: (1.115929 5 0.7795429999999997)
  copy2: (1.210733 5 0.8172469999999996)
  copy3: (1.2816079999999999 5 0.8502519999999998)
  copy4: (1.295846 5 0.9325959999999993)

(I did implement the garbage-collect-before-each-run as you suggested in
your other mail: this can be nicely seen in the constant number "5"
above).

I won't spam this list with the modified source (unless someone clamours
for it, that is).

So without the GC the gap narrows significantly. But still: reverse's
the king of the hill.

OTOH, the differences in GC times start to be a considerable fraction of
the whole difference, so I might be measuring noise anyway.

Seems we can't beat an old Lisp idiom (my guess is that Lisp is alien
technology, but hey).

Regards
- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFMGiuNBcgs9XrR2kYRApnTAJ9Lo7J8EHjOr8JMthPQa/E9zwrEIQCePKI4
b7laoSJWtxDrlrzPeDNkhzE=
=S9WC
-----END PGP SIGNATURE-----

Re: [PATCH] use tail pointer for LOOP

[Thien-Thi Nguyen]

() tomas@tuxteam.de
() Thu, 17 Jun 2010 16:05:01 +0200

   Here you go:

     copy1: (1.115929 5 0.7795429999999997)
     copy2: (1.210733 5 0.8172469999999996)
     copy3: (1.2816079999999999 5 0.8502519999999998)
     copy4: (1.295846 5 0.9325959999999993)

   (I did implement the garbage-collect-before-each-run as you suggested in
   your other mail: this can be nicely seen in the constant number "5"
   above).

   I won't spam this list with the modified source (unless someone clamours
   for it, that is).

   So without the GC the gap narrows significantly. But still: reverse's
   the king of the hill.

   OTOH, the differences in GC times start to be a considerable fraction of
   the whole difference, so I might be measuring noise anyway.

You can test this hypothesis (or rather the sensitivity of the system to this
effect) by permuting the order.  E.g., what if you do ‘copy1’ last?

   Seems we can't beat an old Lisp idiom (my guess is that Lisp is alien
   technology, but hey).

Don't give up, yet.

Another idea is to 10x the input length.

thi

Re: [PATCH] use tail pointer for LOOP

[Stefan Monnier]

>         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.


        Stefan

Re: [PATCH] use tail pointer for LOOP

[David Kastrup]

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

Re: [PATCH] use tail pointer for LOOP

[Stefan Monnier]

> 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