* O(N^2) behavior in LOOP @ 2010-05-29 21:56 Daniel Colascione 2010-05-29 22:06 ` Daniel Colascione 0 siblings, 1 reply; 21+ messages in thread From: Daniel Colascione @ 2010-05-29 21:56 UTC (permalink / raw To: Emacs development discussions [-- 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 --] ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: O(N^2) behavior in LOOP 2010-05-29 21:56 O(N^2) behavior in LOOP Daniel Colascione @ 2010-05-29 22:06 ` Daniel Colascione 2010-05-29 22:14 ` Lennart Borgman 2010-05-29 22:35 ` Geoff Gole 0 siblings, 2 replies; 21+ messages in thread From: Daniel Colascione @ 2010-05-29 22:06 UTC (permalink / raw To: Emacs development discussions [-- 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 --] ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: O(N^2) behavior in LOOP 2010-05-29 22:06 ` Daniel Colascione @ 2010-05-29 22:14 ` Lennart Borgman 2010-05-29 22:35 ` Geoff Gole 1 sibling, 0 replies; 21+ messages in thread From: Lennart Borgman @ 2010-05-29 22:14 UTC (permalink / raw To: Daniel Colascione; +Cc: Emacs development discussions 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? ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: O(N^2) behavior in LOOP 2010-05-29 22:06 ` Daniel Colascione 2010-05-29 22:14 ` Lennart Borgman @ 2010-05-29 22:35 ` Geoff Gole 2010-05-29 23:58 ` [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP) Daniel Colascione 1 sibling, 1 reply; 21+ messages in thread From: Geoff Gole @ 2010-05-29 22:35 UTC (permalink / raw To: Daniel Colascione; +Cc: Emacs development discussions 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. ^ permalink raw reply [flat|nested] 21+ messages in thread
* [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP) 2010-05-29 22:35 ` Geoff Gole @ 2010-05-29 23:58 ` Daniel Colascione 2010-05-30 0:45 ` Ken Raeburn 2010-05-30 17:05 ` Štěpán Němec 0 siblings, 2 replies; 21+ messages in thread From: Daniel Colascione @ 2010-05-29 23:58 UTC (permalink / raw To: Geoff Gole; +Cc: Emacs development discussions [-- 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 --] ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP) 2010-05-29 23:58 ` [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP) Daniel Colascione @ 2010-05-30 0:45 ` Ken Raeburn 2010-05-30 0:49 ` Daniel Colascione 2010-05-30 17:05 ` Štěpán Němec 1 sibling, 1 reply; 21+ messages in thread From: Ken Raeburn @ 2010-05-30 0:45 UTC (permalink / raw To: Daniel Colascione; +Cc: Emacs development discussions 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP) 2010-05-30 0:45 ` Ken Raeburn @ 2010-05-30 0:49 ` Daniel Colascione 2010-06-16 17:44 ` tomas 0 siblings, 1 reply; 21+ messages in thread From: Daniel Colascione @ 2010-05-30 0:49 UTC (permalink / raw To: Ken Raeburn; +Cc: Emacs development discussions [-- 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 --] ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP) 2010-05-30 0:49 ` Daniel Colascione @ 2010-06-16 17:44 ` tomas 2010-06-16 18:10 ` [PATCH] use tail pointer for LOOP David Kastrup 0 siblings, 1 reply; 21+ messages in thread From: tomas @ 2010-06-16 17:44 UTC (permalink / raw To: Daniel Colascione; +Cc: Ken Raeburn, Emacs development discussions -----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----- ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-06-16 17:44 ` tomas @ 2010-06-16 18:10 ` David Kastrup 2010-06-17 5:10 ` tomas 0 siblings, 1 reply; 21+ messages in thread From: David Kastrup @ 2010-06-16 18:10 UTC (permalink / raw To: emacs-devel 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-06-16 18:10 ` [PATCH] use tail pointer for LOOP David Kastrup @ 2010-06-17 5:10 ` tomas 2010-06-17 7:18 ` Thien-Thi Nguyen 2010-06-17 20:48 ` Stefan Monnier 0 siblings, 2 replies; 21+ messages in thread From: tomas @ 2010-06-17 5:10 UTC (permalink / raw To: David Kastrup; +Cc: emacs-devel -----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----- ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-06-17 5:10 ` tomas @ 2010-06-17 7:18 ` Thien-Thi Nguyen 2010-06-17 9:22 ` tomas 2010-06-17 20:48 ` Stefan Monnier 1 sibling, 1 reply; 21+ messages in thread From: Thien-Thi Nguyen @ 2010-06-17 7:18 UTC (permalink / raw To: tomas; +Cc: emacs-devel () 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-06-17 7:18 ` Thien-Thi Nguyen @ 2010-06-17 9:22 ` tomas 2010-06-17 10:03 ` Thien-Thi Nguyen 2010-06-17 10:12 ` Thien-Thi Nguyen 0 siblings, 2 replies; 21+ messages in thread From: tomas @ 2010-06-17 9:22 UTC (permalink / raw To: Thien-Thi Nguyen; +Cc: tomas, emacs-devel [-- 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 --] ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-06-17 9:22 ` tomas @ 2010-06-17 10:03 ` Thien-Thi Nguyen 2010-06-17 14:05 ` tomas 2010-06-17 10:12 ` Thien-Thi Nguyen 1 sibling, 1 reply; 21+ messages in thread From: Thien-Thi Nguyen @ 2010-06-17 10:03 UTC (permalink / raw To: tomas; +Cc: emacs-devel () 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-06-17 10:03 ` Thien-Thi Nguyen @ 2010-06-17 14:05 ` tomas 2010-06-17 15:16 ` Thien-Thi Nguyen 0 siblings, 1 reply; 21+ messages in thread From: tomas @ 2010-06-17 14:05 UTC (permalink / raw To: Thien-Thi Nguyen; +Cc: emacs-devel -----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----- ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-06-17 14:05 ` tomas @ 2010-06-17 15:16 ` Thien-Thi Nguyen 0 siblings, 0 replies; 21+ messages in thread From: Thien-Thi Nguyen @ 2010-06-17 15:16 UTC (permalink / raw To: tomas; +Cc: emacs-devel () 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-06-17 9:22 ` tomas 2010-06-17 10:03 ` Thien-Thi Nguyen @ 2010-06-17 10:12 ` Thien-Thi Nguyen 1 sibling, 0 replies; 21+ messages in thread From: Thien-Thi Nguyen @ 2010-06-17 10:12 UTC (permalink / raw To: tomas; +Cc: emacs-devel () 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-06-17 5:10 ` tomas 2010-06-17 7:18 ` Thien-Thi Nguyen @ 2010-06-17 20:48 ` Stefan Monnier 2010-06-18 7:07 ` David Kastrup 1 sibling, 1 reply; 21+ messages in thread From: Stefan Monnier @ 2010-06-17 20:48 UTC (permalink / raw To: tomas; +Cc: David Kastrup, emacs-devel > 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-06-17 20:48 ` Stefan Monnier @ 2010-06-18 7:07 ` David Kastrup 2010-06-18 13:40 ` Stefan Monnier 0 siblings, 1 reply; 21+ messages in thread From: David Kastrup @ 2010-06-18 7:07 UTC (permalink / raw To: emacs-devel 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-06-18 7:07 ` David Kastrup @ 2010-06-18 13:40 ` Stefan Monnier 0 siblings, 0 replies; 21+ messages in thread From: Stefan Monnier @ 2010-06-18 13:40 UTC (permalink / raw To: David Kastrup; +Cc: emacs-devel > 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-05-29 23:58 ` [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP) Daniel Colascione 2010-05-30 0:45 ` Ken Raeburn @ 2010-05-30 17:05 ` Štěpán Němec 2010-05-30 17:09 ` Daniel Colascione 1 sibling, 1 reply; 21+ messages in thread From: Štěpán Němec @ 2010-05-30 17:05 UTC (permalink / raw To: Daniel Colascione; +Cc: Geoff Gole, Emacs development discussions 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH] use tail pointer for LOOP 2010-05-30 17:05 ` Štěpán Němec @ 2010-05-30 17:09 ` Daniel Colascione 0 siblings, 0 replies; 21+ messages in thread From: Daniel Colascione @ 2010-05-30 17:09 UTC (permalink / raw To: Štěpán Němec Cc: Geoff Gole, Emacs development discussions [-- 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 --] ^ permalink raw reply [flat|nested] 21+ messages in thread
end of thread, other threads:[~2010-06-18 13:40 UTC | newest] Thread overview: 21+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2010-05-29 21:56 O(N^2) behavior in LOOP Daniel Colascione 2010-05-29 22:06 ` Daniel Colascione 2010-05-29 22:14 ` Lennart Borgman 2010-05-29 22:35 ` Geoff Gole 2010-05-29 23:58 ` [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP) Daniel Colascione 2010-05-30 0:45 ` Ken Raeburn 2010-05-30 0:49 ` Daniel Colascione 2010-06-16 17:44 ` tomas 2010-06-16 18:10 ` [PATCH] use tail pointer for LOOP David Kastrup 2010-06-17 5:10 ` tomas 2010-06-17 7:18 ` Thien-Thi Nguyen 2010-06-17 9:22 ` tomas 2010-06-17 10:03 ` Thien-Thi Nguyen 2010-06-17 14:05 ` tomas 2010-06-17 15:16 ` Thien-Thi Nguyen 2010-06-17 10:12 ` Thien-Thi Nguyen 2010-06-17 20:48 ` Stefan Monnier 2010-06-18 7:07 ` David Kastrup 2010-06-18 13:40 ` Stefan Monnier 2010-05-30 17:05 ` Štěpán Němec 2010-05-30 17:09 ` Daniel Colascione
Code repositories for project(s) associated with this public inbox https://git.savannah.gnu.org/cgit/emacs.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).