Discussion:
Performance issue w/ `cl-loop`s `collect...into`
(too old to reply)
Tianxiang Xiong
2018-04-08 00:51:19 UTC
Permalink
The following runs nearly instantaneously:

(progn
(cl-loop for i in (number-sequence 0 130000)
collect (cons (number-to-string i) i))
:done)


This seems to take a long time (didn't wait for it to finish):

(progn
(cl-loop for i in (number-sequence 0 130000)
collect (cons (number-to-string i) i) into pairs)
:done)


Is this a known issue? I couldn't find anything in the bug tracker about it.
Clément Pit-Claudel
2018-04-08 03:26:00 UTC
Permalink
Post by Tianxiang Xiong
(progn
(cl-loop for i in (number-sequence 0 130000)
collect (cons (number-to-string i) i))
:done)
This expands to the following:

(progn
(cl-block nil
(let* ((#:--cl-var-- (number-sequence 0 130000))
(i nil)
(#:--cl-var-- nil))
(while (consp #:--cl-var--)
(setq i (car #:--cl-var--))
(setq #:--cl-var-- (cons (cons (number-to-string i) i) #:--cl-var--))
(setq #:--cl-var-- (cdr #:--cl-var--)))
(nreverse #:--cl-var--)))
:done)
Post by Tianxiang Xiong
(progn
(cl-loop for i in (number-sequence 0 130000)
collect (cons (number-to-string i) i) into pairs)
:done)
Whereas that expands to this:

(progn
(cl-block nil
(let* ((#:--cl-var-- (number-sequence 0 130000))
(i nil)
(pairs nil))
(while (consp #:--cl-var--)
(setq i (car #:--cl-var--))
(setq pairs (nconc pairs (list (cons (number-to-string i) i))))
(setq #:--cl-var-- (cdr #:--cl-var--)))
nil))
:done)
Post by Tianxiang Xiong
Is this a known issue? I couldn't find anything in the bug tracker about it.
The second form is quadratic, maybe because user code is allowed to access the accumulation variable during iteration?

It should likely be documented, but it doesn't seem to be ATM.

Clément.
Tianxiang Xiong
2018-04-08 05:56:56 UTC
Permalink
Yikes--wasn't expecting that. Similar code in SBCL runs nearly
instantaneously.

(ql:quickload :alexandria)
(macroexpand-1
'(loop for i in (alexandria:iota 130000)
collect (cons (write-to-string i) i) into pairs
finally (return (length pairs))))

;; =>
(BLOCK NIL
(LET ((I NIL) (#:LOOP-LIST-585 (ALEXANDRIA.0.DEV:IOTA 130000)))
(DECLARE (TYPE LIST #:LOOP-LIST-585))
(SB-LOOP::WITH-LOOP-LIST-COLLECTION-HEAD (#:LOOP-LIST-HEAD-586
#:LOOP-LIST-TAIL-587 PAIRS)
(TAGBODY
SB-LOOP::NEXT-LOOP
(WHEN (ENDP #:LOOP-LIST-585) (GO SB-LOOP::END-LOOP))
(SB-LOOP::LOOP-REALLY-DESETQ I (CAR #:LOOP-LIST-585))
(SB-LOOP::LOOP-REALLY-DESETQ #:LOOP-LIST-585 (CDR #:LOOP-LIST-585))
(SB-LOOP::LOOP-COLLECT-RPLACD
(#:LOOP-LIST-HEAD-586 #:LOOP-LIST-TAIL-587 PAIRS)
(LIST (CONS (WRITE-TO-STRING I) I)))
(GO SB-LOOP::NEXT-LOOP)
SB-LOOP::END-LOOP
(RETURN (LENGTH PAIRS))))))
Post by Tianxiang Xiong
Post by Tianxiang Xiong
(progn
(cl-loop for i in (number-sequence 0 130000)
collect (cons (number-to-string i) i))
:done)
(progn
(cl-block nil
(let* ((#:--cl-var-- (number-sequence 0 130000))
(i nil)
(#:--cl-var-- nil))
(while (consp #:--cl-var--)
(setq i (car #:--cl-var--))
(setq #:--cl-var-- (cons (cons (number-to-string i) i)
#:--cl-var--))
(setq #:--cl-var-- (cdr #:--cl-var--)))
(nreverse #:--cl-var--)))
:done)
Post by Tianxiang Xiong
(progn
(cl-loop for i in (number-sequence 0 130000)
collect (cons (number-to-string i) i) into pairs)
:done)
(progn
(cl-block nil
(let* ((#:--cl-var-- (number-sequence 0 130000))
(i nil)
(pairs nil))
(while (consp #:--cl-var--)
(setq i (car #:--cl-var--))
(setq pairs (nconc pairs (list (cons (number-to-string i) i))))
(setq #:--cl-var-- (cdr #:--cl-var--)))
nil))
:done)
Post by Tianxiang Xiong
Is this a known issue? I couldn't find anything in the bug tracker about
it.
The second form is quadratic, maybe because user code is allowed to access
the accumulation variable during iteration?
It should likely be documented, but it doesn't seem to be ATM.
Clément.
Clément Pit-Claudel
2018-04-08 06:12:03 UTC
Permalink
Yikes--wasn't expecting that. Similar code in SBCL runs nearly instantaneously.
Indeed, fixing the implementation would be nice. It shouldn't be too hard to keep a reference to the last `cons' of `pairs' and to append to that using setcdr.

Clément.
Tianxiang Xiong
2018-04-08 08:50:16 UTC
Permalink
Indeed, I modified the macroexpanded form into:

(cl-block nil
(let* ((--cl-var-- (number-sequence 0 130000))
i
pairs
pairs-end)
(while (consp --cl-var--)
(setq i (car --cl-var--))
(let ((v (list (cons (number-to-string i) i))))
(if (null pairs-end)
(setq pairs v pairs-end (last pairs))
(setq pairs-end (setcdr pairs-end v))))
(setq --cl-var-- (cdr --cl-var--)))
(length pairs)))

and it runs near instantaneously.

I'd *guess* the fix would be applied in `cl--parse-loop-clause`? Perhaps
Stefan could give some pointers?
Post by Tianxiang Xiong
Post by Tianxiang Xiong
Yikes--wasn't expecting that. Similar code in SBCL runs nearly
instantaneously.
Indeed, fixing the implementation would be nice. It shouldn't be too hard
to keep a reference to the last `cons' of `pairs' and to append to that
using setcdr.
Clément.
Clément Pit-Claudel
2018-04-08 13:19:39 UTC
Permalink
  (let* ((--cl-var-- (number-sequence 0 130000))
Bonus point if you take that opportunity to get rid of the call to number-sequence, too :)
Stefan Monnier
2018-04-08 16:07:38 UTC
Permalink
Post by Tianxiang Xiong
I'd *guess* the fix would be applied in `cl--parse-loop-clause`?
Perhaps Stefan could give some pointers?
Maybe I'm one of the least unknowledgeable about this code, but it's
still pretty obscure for me, sorry,


Stefan
Tianxiang Xiong
2018-04-08 19:58:10 UTC
Permalink
Here's a first attempt at a patch, if someone'd take a look.
Post by Stefan Monnier
Post by Tianxiang Xiong
I'd *guess* the fix would be applied in `cl--parse-loop-clause`?
Perhaps Stefan could give some pointers?
Maybe I'm one of the least unknowledgeable about this code, but it's
still pretty obscure for me, sorry,
Stefan
Stefan Monnier
2018-04-08 21:13:18 UTC
Permalink
Avoid O(n^2) nconc-ing by keeping track of tail of collection.
I took a quick look at your patch, and it looks pretty good.
See comments below.


Stefan
((memq word '(collect collecting))
- (let ((what (pop cl--loop-args))
- (var (cl--loop-handle-accum nil 'nreverse)))
- (if (eq var cl--loop-accum-var)
- (push `(progn (push ,what ,var) t) cl--loop-body)
- (push `(progn
- (setq ,var (nconc ,var (list ,what)))
- t)
- cl--loop-body))))
+ (let ((what (pop cl--loop-args)))
+ (cl-multiple-value-bind (var var-tail)
`cl-multiple-value-bind` is the "destructor" corresponding to the
`cl-values` "constructor". Since your code doesn't use `cl-values` it
should not use `cl-multiple-value-bind` either (you probably meant to
use cl-destructuring-bind instead).
+ (cl--loop-handle-accum nil 'nreverse)
+ (if (eq var cl--loop-accum-var)
+ (push `(progn (push ,what ,var) t) cl--loop-body)
+ (push `(progn
+ (if (null ,var-tail)
+ (setq ,var (list ,what) ,var-tail (last ,var))
+ (setq ,var-tail (setcdr ,var-tail (list ,what))))
+ t)
+ cl--loop-body)))))
The cl-loop macro's code lacks comments. Could you take advantage of
"being there" to try and add comments? E.g. in the above code I see
that depending on (eq var cl--loop-accum-var) we end up accumulating in
the from or in the back. Could you add a comments explaining why and
mentioning where we correct this discrepancy?
+ (let ((what (pop cl--loop-args)))
+ (cl-destructuring-bind (var) (cl--loop-handle-accum nil 'nreverse)
+ (push `(progn
+ (setq ,var
+ ,(if (eq var cl--loop-accum-var)
+ `(nconc
+ (,(if (memq word '(nconc nconcing))
+ #'nreverse #'reverse)
+ ,what)
+ ,var)
+ `(,(if (memq word '(nconc nconcing))
+ #'nconc #'append)
+ ,var ,what)))
+ t)
+ cl--loop-body))))
In the `nconc` case (when (eq var cl--loop-accum-var) is nil) we could
also use the `var-tail` to speed up the `nconc`.

Also, to avoid the N² behavior for the `append` case, maybe we
could/should make it use `copy-sequence`, i.e.

`(nconc ,var-tail (copy-sequence ,what))
-(defun cl--loop-handle-accum (def &optional func) ; uses loop-*
- (if (eq (car cl--loop-args) 'into)
+(defun cl--loop-handle-accum (def &optional func type) ; uses loop-*
+ (setq type (or type 'list))
Please add a docstring explaining whatever you managed to understand of
this code, and describing also what this new arg `type` does.
Tianxiang Xiong
2018-04-08 23:29:56 UTC
Permalink
One thing I don't understand is the common

(push `(progn (setq ...) t) cl--loop-body)

pattern found in the code. I'm not sure why the `(progn ... t)` is
necessary. If anyone could explain that I'd add it as a comment.
Post by Stefan Monnier
Avoid O(n^2) nconc-ing by keeping track of tail of collection.
I took a quick look at your patch, and it looks pretty good.
See comments below.
Stefan
((memq word '(collect collecting))
- (let ((what (pop cl--loop-args))
- (var (cl--loop-handle-accum nil 'nreverse)))
- (if (eq var cl--loop-accum-var)
- (push `(progn (push ,what ,var) t) cl--loop-body)
- (push `(progn
- (setq ,var (nconc ,var (list ,what)))
- t)
- cl--loop-body))))
+ (let ((what (pop cl--loop-args)))
+ (cl-multiple-value-bind (var var-tail)
`cl-multiple-value-bind` is the "destructor" corresponding to the
`cl-values` "constructor". Since your code doesn't use `cl-values` it
should not use `cl-multiple-value-bind` either (you probably meant to
use cl-destructuring-bind instead).
+ (cl--loop-handle-accum nil 'nreverse)
+ (if (eq var cl--loop-accum-var)
+ (push `(progn (push ,what ,var) t) cl--loop-body)
+ (push `(progn
+ (if (null ,var-tail)
+ (setq ,var (list ,what) ,var-tail (last ,var))
+ (setq ,var-tail (setcdr ,var-tail (list ,what))))
+ t)
+ cl--loop-body)))))
The cl-loop macro's code lacks comments. Could you take advantage of
"being there" to try and add comments? E.g. in the above code I see
that depending on (eq var cl--loop-accum-var) we end up accumulating in
the from or in the back. Could you add a comments explaining why and
mentioning where we correct this discrepancy?
+ (let ((what (pop cl--loop-args)))
+ (cl-destructuring-bind (var) (cl--loop-handle-accum nil 'nreverse)
+ (push `(progn
+ (setq ,var
+ ,(if (eq var cl--loop-accum-var)
+ `(nconc
+ (,(if (memq word '(nconc nconcing))
+ #'nreverse #'reverse)
+ ,what)
+ ,var)
+ `(,(if (memq word '(nconc nconcing))
+ #'nconc #'append)
+ ,var ,what)))
+ t)
+ cl--loop-body))))
In the `nconc` case (when (eq var cl--loop-accum-var) is nil) we could
also use the `var-tail` to speed up the `nconc`.
Also, to avoid the N² behavior for the `append` case, maybe we
could/should make it use `copy-sequence`, i.e.
`(nconc ,var-tail (copy-sequence ,what))
-(defun cl--loop-handle-accum (def &optional func) ; uses loop-*
- (if (eq (car cl--loop-args) 'into)
+(defun cl--loop-handle-accum (def &optional func type) ; uses loop-*
+ (setq type (or type 'list))
Please add a docstring explaining whatever you managed to understand of
this code, and describing also what this new arg `type` does.
Tianxiang Xiong
2018-04-09 01:10:28 UTC
Permalink
Here's a second, cleaner attempt that separates the `cl--loop-handle-accum`
function into two functions, one to deal with lists and one to deal w/
non-lists.

The tail-tracking optimizing is also applied to `append(ing)` and
`nconc(ing)`.
Post by Tianxiang Xiong
One thing I don't understand is the common
(push `(progn (setq ...) t) cl--loop-body)
pattern found in the code. I'm not sure why the `(progn ... t)` is
necessary. If anyone could explain that I'd add it as a comment.
Post by Stefan Monnier
Avoid O(n^2) nconc-ing by keeping track of tail of collection.
I took a quick look at your patch, and it looks pretty good.
See comments below.
Stefan
((memq word '(collect collecting))
- (let ((what (pop cl--loop-args))
- (var (cl--loop-handle-accum nil 'nreverse)))
- (if (eq var cl--loop-accum-var)
- (push `(progn (push ,what ,var) t) cl--loop-body)
- (push `(progn
- (setq ,var (nconc ,var (list ,what)))
- t)
- cl--loop-body))))
+ (let ((what (pop cl--loop-args)))
+ (cl-multiple-value-bind (var var-tail)
`cl-multiple-value-bind` is the "destructor" corresponding to the
`cl-values` "constructor". Since your code doesn't use `cl-values` it
should not use `cl-multiple-value-bind` either (you probably meant to
use cl-destructuring-bind instead).
+ (cl--loop-handle-accum nil 'nreverse)
+ (if (eq var cl--loop-accum-var)
+ (push `(progn (push ,what ,var) t) cl--loop-body)
+ (push `(progn
+ (if (null ,var-tail)
+ (setq ,var (list ,what) ,var-tail (last ,var))
+ (setq ,var-tail (setcdr ,var-tail (list
,what))))
+ t)
+ cl--loop-body)))))
The cl-loop macro's code lacks comments. Could you take advantage of
"being there" to try and add comments? E.g. in the above code I see
that depending on (eq var cl--loop-accum-var) we end up accumulating in
the from or in the back. Could you add a comments explaining why and
mentioning where we correct this discrepancy?
+ (let ((what (pop cl--loop-args)))
+ (cl-destructuring-bind (var) (cl--loop-handle-accum nil 'nreverse)
+ (push `(progn
+ (setq ,var
+ ,(if (eq var cl--loop-accum-var)
+ `(nconc
+ (,(if (memq word '(nconc nconcing))
+ #'nreverse #'reverse)
+ ,what)
+ ,var)
+ `(,(if (memq word '(nconc nconcing))
+ #'nconc #'append)
+ ,var ,what)))
+ t)
+ cl--loop-body))))
In the `nconc` case (when (eq var cl--loop-accum-var) is nil) we could
also use the `var-tail` to speed up the `nconc`.
Also, to avoid the N² behavior for the `append` case, maybe we
could/should make it use `copy-sequence`, i.e.
`(nconc ,var-tail (copy-sequence ,what))
-(defun cl--loop-handle-accum (def &optional func) ; uses loop-*
- (if (eq (car cl--loop-args) 'into)
+(defun cl--loop-handle-accum (def &optional func type) ; uses loop-*
+ (setq type (or type 'list))
Please add a docstring explaining whatever you managed to understand of
this code, and describing also what this new arg `type` does.
Stefan Monnier
2018-04-09 01:59:25 UTC
Permalink
Post by Tianxiang Xiong
Here's a second, cleaner attempt that separates the `cl--loop-handle-accum`
function into two functions, one to deal with lists and one to deal w/
non-lists.
The tail-tracking optimizing is also applied to `append(ing)` and
`nconc(ing)`.
Thanks. Looks good.
I see you've dropped the (eq var cl--loop-accum-var) optimization.
Have you tried to measure the effect?


Stefan
Post by Tianxiang Xiong
+(defun cl--loop-handle-accum (def)
[...]
Post by Tianxiang Xiong
+ (cond
[...]
Post by Tianxiang Xiong
+ (cl--loop-accum-var cl--loop-accum-var)
You can write this line as just

(cl--loop-accum-var)


-- Stefan
Tianxiang Xiong
2018-04-09 02:16:08 UTC
Permalink
IIUC the `(eq var cl--loop-accum-var)` is used to test whether the
accumulation is `into` or not. If not, clauses like `collect(ing)` use a
`cons-nreverse` rather than `nconc` algorithm, which is O(n) instead of
O(n^2). Since we're doing `setcdr` in all cases where the accumulation is
into a list, we're always O(n), so the optimization is unnecessary.

Attached is a new patch that uses `(cl--loop-accum-var)`.
Post by Tianxiang Xiong
Post by Tianxiang Xiong
Here's a second, cleaner attempt that separates the
`cl--loop-handle-accum`
Post by Tianxiang Xiong
function into two functions, one to deal with lists and one to deal w/
non-lists.
The tail-tracking optimizing is also applied to `append(ing)` and
`nconc(ing)`.
Thanks. Looks good.
I see you've dropped the (eq var cl--loop-accum-var) optimization.
Have you tried to measure the effect?
Stefan
Post by Tianxiang Xiong
+(defun cl--loop-handle-accum (def)
[...]
Post by Tianxiang Xiong
+ (cond
[...]
Post by Tianxiang Xiong
+ (cl--loop-accum-var cl--loop-accum-var)
You can write this line as just
(cl--loop-accum-var)
-- Stefan
Stefan Monnier
2018-04-09 02:20:21 UTC
Permalink
Post by Tianxiang Xiong
IIUC the `(eq var cl--loop-accum-var)` is used to test whether the
accumulation is `into` or not. If not, clauses like `collect(ing)` use a
`cons-nreverse` rather than `nconc` algorithm, which is O(n) instead of
O(n^2). Since we're doing `setcdr` in all cases where the accumulation is
into a list, we're always O(n), so the optimization is unnecessary.
I agree that the algorithmic complexity of "cons+nreverse" is no better
than that of the setcdr, but that doesn't mean that it's the same speed.
Since (eq var cl--loop-accum-var) is expected to be the most common
case, it'd be good to make sure that your patch doesn't make the
code slower, hence the need to test the performance.


Stefan
Post by Tianxiang Xiong
Attached is a new patch that uses `(cl--loop-accum-var)`.
Post by Tianxiang Xiong
Post by Tianxiang Xiong
Here's a second, cleaner attempt that separates the
`cl--loop-handle-accum`
Post by Tianxiang Xiong
function into two functions, one to deal with lists and one to deal w/
non-lists.
The tail-tracking optimizing is also applied to `append(ing)` and
`nconc(ing)`.
Thanks. Looks good.
I see you've dropped the (eq var cl--loop-accum-var) optimization.
Have you tried to measure the effect?
Stefan
Post by Tianxiang Xiong
+(defun cl--loop-handle-accum (def)
[...]
Post by Tianxiang Xiong
+ (cond
[...]
Post by Tianxiang Xiong
+ (cl--loop-accum-var cl--loop-accum-var)
You can write this line as just
(cl--loop-accum-var)
-- Stefan
Tianxiang Xiong
2018-04-09 03:34:24 UTC
Permalink
Is there a function to easily time operations in Emacs Lisp? Something like
Clojure's `core/time`?

`profile-*` a chore to use for short stuff.
Post by Stefan Monnier
Post by Tianxiang Xiong
IIUC the `(eq var cl--loop-accum-var)` is used to test whether the
accumulation is `into` or not. If not, clauses like `collect(ing)` use a
`cons-nreverse` rather than `nconc` algorithm, which is O(n) instead of
O(n^2). Since we're doing `setcdr` in all cases where the accumulation is
into a list, we're always O(n), so the optimization is unnecessary.
I agree that the algorithmic complexity of "cons+nreverse" is no better
than that of the setcdr, but that doesn't mean that it's the same speed.
Since (eq var cl--loop-accum-var) is expected to be the most common
case, it'd be good to make sure that your patch doesn't make the
code slower, hence the need to test the performance.
Stefan
Post by Tianxiang Xiong
Attached is a new patch that uses `(cl--loop-accum-var)`.
Post by Tianxiang Xiong
Post by Tianxiang Xiong
Here's a second, cleaner attempt that separates the
`cl--loop-handle-accum`
Post by Tianxiang Xiong
function into two functions, one to deal with lists and one to deal w/
non-lists.
The tail-tracking optimizing is also applied to `append(ing)` and
`nconc(ing)`.
Thanks. Looks good.
I see you've dropped the (eq var cl--loop-accum-var) optimization.
Have you tried to measure the effect?
Stefan
Post by Tianxiang Xiong
+(defun cl--loop-handle-accum (def)
[...]
Post by Tianxiang Xiong
+ (cond
[...]
Post by Tianxiang Xiong
+ (cl--loop-accum-var cl--loop-accum-var)
You can write this line as just
(cl--loop-accum-var)
-- Stefan
Tianxiang Xiong
2018-04-09 03:38:59 UTC
Permalink
I profiled

(progn
(cl-loop for i in (number-sequence 1 1E6)
collect i)
:done)

w/ both the old and new code.

Old:

+ command-execute 847 85%
+ ... 113 11%
+ timer-event-handler 27 2%
+ eldoc-pre-command-refresh-echo-area 3 0%
+ redisplay_internal (C function) 1 0%

New:

+ command-execute 852 87%
+ ... 95 9%
+ timer-event-handler 22 2%
+ redisplay_internal (C function) 2 0%
+ sp--save-pre-command-state 2 0%
+ flyspell-post-command-hook 1 0%

As you can see there's virtually no difference. I've attached the profile
output for both.
Post by Tianxiang Xiong
Is there a function to easily time operations in Emacs Lisp? Something
like Clojure's `core/time`?
`profile-*` a chore to use for short stuff.
Post by Stefan Monnier
Post by Tianxiang Xiong
IIUC the `(eq var cl--loop-accum-var)` is used to test whether the
accumulation is `into` or not. If not, clauses like `collect(ing)` use a
`cons-nreverse` rather than `nconc` algorithm, which is O(n) instead of
O(n^2). Since we're doing `setcdr` in all cases where the accumulation
is
Post by Tianxiang Xiong
into a list, we're always O(n), so the optimization is unnecessary.
I agree that the algorithmic complexity of "cons+nreverse" is no better
than that of the setcdr, but that doesn't mean that it's the same speed.
Since (eq var cl--loop-accum-var) is expected to be the most common
case, it'd be good to make sure that your patch doesn't make the
code slower, hence the need to test the performance.
Stefan
Post by Tianxiang Xiong
Attached is a new patch that uses `(cl--loop-accum-var)`.
On Sun, Apr 8, 2018 at 6:59 PM, Stefan Monnier <
Post by Tianxiang Xiong
Post by Tianxiang Xiong
Here's a second, cleaner attempt that separates the
`cl--loop-handle-accum`
Post by Tianxiang Xiong
function into two functions, one to deal with lists and one to deal
w/
Post by Tianxiang Xiong
Post by Tianxiang Xiong
Post by Tianxiang Xiong
non-lists.
The tail-tracking optimizing is also applied to `append(ing)` and
`nconc(ing)`.
Thanks. Looks good.
I see you've dropped the (eq var cl--loop-accum-var) optimization.
Have you tried to measure the effect?
Stefan
Post by Tianxiang Xiong
+(defun cl--loop-handle-accum (def)
[...]
Post by Tianxiang Xiong
+ (cond
[...]
Post by Tianxiang Xiong
+ (cl--loop-accum-var cl--loop-accum-var)
You can write this line as just
(cl--loop-accum-var)
-- Stefan
Stefan Monnier
2018-04-09 12:07:42 UTC
Permalink
Post by Tianxiang Xiong
Is there a function to easily time operations in Emacs Lisp? Something like
Clojure's `core/time`?
There's `benchmark`, `benchmark-run`, and `benchmark-run-compiled`.


Stefan
Basil L. Contovounesios
2018-04-09 12:22:45 UTC
Permalink
Post by Tianxiang Xiong
Is there a function to easily time operations in Emacs Lisp? Something
like Clojure's `core/time`?
There are the macros benchmark-run and benchmark-run-compiled, as
mentioned under (info "(elisp) Profiling").
--
Basil
Tianxiang Xiong
2018-04-09 15:28:48 UTC
Permalink
Here's the result of `benchmark-run` on the new code:

(benchmark-run 10 (cl-loop for i in (number-sequence 1 1E6)
collect i))

;; => (10.488984668 6 3.555157208999999)

and old code:

(benchmark-run 10 (cl-loop for i in (number-sequence 1 1E6)
collect i))

;; => (14.876455789000001 25 2.328459104999999)

So there actually seems to be an improvement due to less GC.
Post by Basil L. Contovounesios
Post by Tianxiang Xiong
Is there a function to easily time operations in Emacs Lisp? Something
like Clojure's `core/time`?
There are the macros benchmark-run and benchmark-run-compiled, as
mentioned under (info "(elisp) Profiling").
--
Basil
Tianxiang Xiong
2018-04-09 15:33:17 UTC
Permalink
I also figured out what the `(progn ... t)` pattern does. Here's a
macroexpansion w/ it:

(macroexpand-1 '(cl-loop for i in '(1 2 3) collect i))

(cl-block nil
(let*
((--cl-var--
'(1 2 3))
(i nil)
(--cl-var-- nil))
(while
(consp --cl-var--)
(setq i
(car --cl-var--))
(push i --cl-var--)
(setq --cl-var--
(cdr --cl-var--)))
(nreverse --cl-var--)))

And one w/out it:

(macroexpand-1 '(cl-loop for i in '(1 2 3) collect i))

(cl-block nil
(let*
((--cl-var--
'(1 2 3))
(i nil)
(--cl-var-- nil))
(while
(and
(consp --cl-var--)
(progn
(setq i
(car --cl-var--))
(push i --cl-var--)))
(setq --cl-var--
(cdr --cl-var--)))
(nreverse --cl-var--)))

Apparently `cl--loop-build-ands` uses this pattern
<http://git.savannah.gnu.org/cgit/emacs.git/tree/lisp/emacs-lisp/cl-macs.el?h=emacs-26#n1723>
to determine whether clauses go into an `and` or not 🀷. Of course 🙄!
Post by Tianxiang Xiong
(benchmark-run 10 (cl-loop for i in (number-sequence 1 1E6)
collect i))
;; => (10.488984668 6 3.555157208999999)
(benchmark-run 10 (cl-loop for i in (number-sequence 1 1E6)
collect i))
;; => (14.876455789000001 25 2.328459104999999)
So there actually seems to be an improvement due to less GC.
Post by Basil L. Contovounesios
Post by Tianxiang Xiong
Is there a function to easily time operations in Emacs Lisp? Something
like Clojure's `core/time`?
There are the macros benchmark-run and benchmark-run-compiled, as
mentioned under (info "(elisp) Profiling").
--
Basil
Tianxiang Xiong
2018-04-14 07:01:32 UTC
Permalink
Since it appears there's no performance degradation, can we merge this?

If others would like to do some testing, that'd be great.
Post by Tianxiang Xiong
I also figured out what the `(progn ... t)` pattern does. Here's a
(macroexpand-1 '(cl-loop for i in '(1 2 3) collect i))
(cl-block nil
(let*
((--cl-var--
'(1 2 3))
(i nil)
(--cl-var-- nil))
(while
(consp --cl-var--)
(setq i
(car --cl-var--))
(push i --cl-var--)
(setq --cl-var--
(cdr --cl-var--)))
(nreverse --cl-var--)))
(macroexpand-1 '(cl-loop for i in '(1 2 3) collect i))
(cl-block nil
(let*
((--cl-var--
'(1 2 3))
(i nil)
(--cl-var-- nil))
(while
(and
(consp --cl-var--)
(progn
(setq i
(car --cl-var--))
(push i --cl-var--)))
(setq --cl-var--
(cdr --cl-var--)))
(nreverse --cl-var--)))
Apparently `cl--loop-build-ands` uses this pattern
<http://git.savannah.gnu.org/cgit/emacs.git/tree/lisp/emacs-lisp/cl-macs.el?h=emacs-26#n1723>
to determine whether clauses go into an `and` or not 🀷. Of course 🙄!
Post by Tianxiang Xiong
(benchmark-run 10 (cl-loop for i in (number-sequence 1 1E6)
collect i))
;; => (10.488984668 6 3.555157208999999)
(benchmark-run 10 (cl-loop for i in (number-sequence 1 1E6)
collect i))
;; => (14.876455789000001 25 2.328459104999999)
So there actually seems to be an improvement due to less GC.
Post by Basil L. Contovounesios
Post by Tianxiang Xiong
Is there a function to easily time operations in Emacs Lisp? Something
like Clojure's `core/time`?
There are the macros benchmark-run and benchmark-run-compiled, as
mentioned under (info "(elisp) Profiling").
--
Basil
Loading...