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