Performance issue w/ `cl-loop`s `collect...into`

Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

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

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.

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

Re: Performance issue w/ `cl-loop`s `collect...into`

[Clément Pit-Claudel]

On 2018-04-07 20:51, Tianxiang Xiong wrote:
> The following runs nearly instantaneously:
> 
> (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)

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

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)

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

Re: Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

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

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


On Sat, Apr 7, 2018 at 8:26 PM, Clément Pit-Claudel <cpitclaudel@gmail.com>
wrote:

> On 2018-04-07 20:51, Tianxiang Xiong wrote:
> > The following runs nearly instantaneously:
> >
> > (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)
>
> > 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)
>
> 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)
>
> > 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.
>
>
>

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

Re: Performance issue w/ `cl-loop`s `collect...into`

[Clément Pit-Claudel]

On 2018-04-08 01:56, Tianxiang Xiong wrote:
> 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.

Re: Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

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

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?


On Sat, Apr 7, 2018 at 11:12 PM, Clément Pit-Claudel <cpitclaudel@gmail.com>
wrote:

> On 2018-04-08 01:56, Tianxiang Xiong wrote:
> > 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.
>

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

Re: Performance issue w/ `cl-loop`s `collect...into`

[Clément Pit-Claudel]

On 2018-04-08 04:50, Tianxiang Xiong wrote:
>   (let* ((--cl-var-- (number-sequence 0 130000))

Bonus point if you take that opportunity to get rid of the call to number-sequence, too :)

Re: Performance issue w/ `cl-loop`s `collect...into`

[Stefan Monnier]

> 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

Re: Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

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

Here's a first attempt at a patch, if someone'd take a look.

On Sun, Apr 8, 2018 at 9:07 AM, Stefan Monnier <monnier@iro.umontreal.ca>
wrote:

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

[-- Attachment #1.2: Type: text/html, Size: 780 bytes --]

[-- Attachment #2: 0001-Optimize-collect.into.patch --]
[-- Type: text/x-patch, Size: 7423 bytes --]

From c98679670ad541017aaaa98a5cfe4c36116f71c7 Mon Sep 17 00:00:00 2001
From: Tianxiang Xiong <tianxiang.xiong@gmail.com>
Date: Sun, 8 Apr 2018 12:36:41 -0700
Subject: [PATCH] Optimize `collect...into`

Avoid O(n^2) nconc-ing by keeping track of tail of collection.
---
 lisp/emacs-lisp/cl-macs.el | 127 ++++++++++++++++++++++++++-------------------
 1 file changed, 73 insertions(+), 54 deletions(-)

diff --git a/lisp/emacs-lisp/cl-macs.el b/lisp/emacs-lisp/cl-macs.el
index 9600230c07..523bfc5a9a 100644
--- a/lisp/emacs-lisp/cl-macs.el
+++ b/lisp/emacs-lisp/cl-macs.el
@@ -1537,59 +1537,63 @@ cl--parse-loop-clause
 	(push `(>= (setq ,temp (1- ,temp)) 0) cl--loop-body)))
 
      ((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--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)))))
 
      ((memq word '(nconc nconcing append appending))
-      (let ((what (pop cl--loop-args))
-	    (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)))
+      (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))))
 
      ((memq word '(concat concating))
-      (let ((what (pop cl--loop-args))
-	    (var (cl--loop-handle-accum "")))
-	(push `(progn (cl-callf concat ,var ,what) t) cl--loop-body)))
+      (let ((what (pop cl--loop-args)))
+	(cl-destructuring-bind (var) (cl--loop-handle-accum "" nil 'string)
+          (push `(progn (cl-callf concat ,var ,what) t) cl--loop-body))))
 
      ((memq word '(vconcat vconcating))
-      (let ((what (pop cl--loop-args))
-	    (var (cl--loop-handle-accum [])))
-	(push `(progn (cl-callf vconcat ,var ,what) t) cl--loop-body)))
+      (let ((what (pop cl--loop-args)))
+	(cl-destructuring-bind (var) (cl--loop-handle-accum [] nil 'vector)
+          (push `(progn (cl-callf vconcat ,var ,what) t) cl--loop-body))))
 
      ((memq word '(sum summing))
-      (let ((what (pop cl--loop-args))
-	    (var (cl--loop-handle-accum 0)))
-	(push `(progn (cl-incf ,var ,what) t) cl--loop-body)))
+      (let ((what (pop cl--loop-args)))
+	(cl-destructuring-bind (var) (cl--loop-handle-accum 0 nil 'number)
+          (push `(progn (cl-incf ,var ,what) t) cl--loop-body))))
 
      ((memq word '(count counting))
-      (let ((what (pop cl--loop-args))
-	    (var (cl--loop-handle-accum 0)))
-	(push `(progn (if ,what (cl-incf ,var)) t) cl--loop-body)))
+      (let ((what (pop cl--loop-args)))
+	(cl-destructuring-bind (var) (cl--loop-handle-accum 0 nil 'number)
+          (push `(progn (if ,what (cl-incf ,var)) t) cl--loop-body))))
 
      ((memq word '(minimize minimizing maximize maximizing))
       (push `(progn ,(macroexp-let2 macroexp-copyable-p temp
                                     (pop cl--loop-args)
-                       (let* ((var (cl--loop-handle-accum nil))
-                              (func (intern (substring (symbol-name word)
-                                                       0 3))))
-                         `(setq ,var (if ,var (,func ,var ,temp) ,temp))))
+                       (let ((func (intern (substring (symbol-name word)
+                                                      0 3))))
+                         (cl-destructuring-bind (var)
+                             (cl--loop-handle-accum nil)
+                           `(setq ,var (if ,var (,func ,var ,temp) ,temp)))))
                     t)
             cl--loop-body))
 
@@ -1726,22 +1730,37 @@ cl--loop-let
       `(,(if par 'let 'let*)
         ,(nconc (nreverse temps) (nreverse new)) ,@body))))
 
-(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))
+  (let ((intop (eq (car cl--loop-args) 'into)))
+    (cond
+     ((and intop (eq 'list type))
+      (let* ((var (cl--pop2 cl--loop-args))
+             (var-tail (gensym (concat (symbol-name var) "-tail-"))))
+        (if (memq var cl--loop-accum-vars)
+            (push `((,var-tail ,(last def))) cl--loop-bindings)
+          (push `((,var ,def)) cl--loop-bindings)
+          (push `((,var-tail ,(last def))) cl--loop-bindings)
+          (push var cl--loop-accum-vars))
+        (list var var-tail)))
+
+     ((and intop (not (eq 'list type)))
       (let ((var (cl--pop2 cl--loop-args)))
-	(or (memq var cl--loop-accum-vars)
-	    (progn (push (list (list var def)) cl--loop-bindings)
-		   (push var cl--loop-accum-vars)))
-	var)
-    (or cl--loop-accum-var
-	(progn
-	  (push (list (list
-                       (setq cl--loop-accum-var (make-symbol "--cl-var--"))
-                       def))
-                cl--loop-bindings)
-	  (setq cl--loop-result (if func (list func cl--loop-accum-var)
-                                  cl--loop-accum-var))
-	  cl--loop-accum-var))))
+        (or (memq var cl--loop-accum-vars)
+            (progn (push `((,var ,def)) cl--loop-bindings)
+                   (push var cl--loop-accum-vars)))
+        (list var)))
+
+     (t (if cl--loop-accum-var
+            (list cl--loop-accum-var)
+          (progn
+            (push (list (list
+                         (setq cl--loop-accum-var (make-symbol "--cl-var--"))
+                         def))
+                  cl--loop-bindings)
+            (setq cl--loop-result (if func (list func cl--loop-accum-var)
+                                    cl--loop-accum-var))
+            (list cl--loop-accum-var)))))))
 
 (defun cl--loop-build-ands (clauses)
   "Return various representations of (and . CLAUSES).
-- 
2.14.3

Re: Performance issue w/ `cl-loop`s `collect...into`

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

Re: Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

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

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.

On Sun, Apr 8, 2018 at 2:13 PM, Stefan Monnier <monnier@iro.umontreal.ca>
wrote:

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

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

Re: Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

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

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

On Sun, Apr 8, 2018 at 4:29 PM, Tianxiang Xiong <tianxiang.xiong@gmail.com>
wrote:

> 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.
>
> On Sun, Apr 8, 2018 at 2:13 PM, Stefan Monnier <monnier@iro.umontreal.ca>
> wrote:
>
>> > 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.
>>
>>
>>
>

[-- Attachment #1.2: Type: text/html, Size: 5414 bytes --]

[-- Attachment #2: 0002-Optimize-collect.into.patch --]
[-- Type: text/x-patch, Size: 5773 bytes --]

From 2d91f7ae9755976363460e58d647e7826db3e549 Mon Sep 17 00:00:00 2001
From: Tianxiang Xiong <tianxiang.xiong@gmail.com>
Date: Sun, 8 Apr 2018 12:36:41 -0700
Subject: [PATCH] Optimize `collect...into`

Avoid O(n^2) nconc-ing by keeping track of tail of collection.
---
 lisp/emacs-lisp/cl-macs.el | 115 ++++++++++++++++++++++++++++++---------------
 1 file changed, 77 insertions(+), 38 deletions(-)

diff --git a/lisp/emacs-lisp/cl-macs.el b/lisp/emacs-lisp/cl-macs.el
index 9600230c07..47a5413f49 100644
--- a/lisp/emacs-lisp/cl-macs.el
+++ b/lisp/emacs-lisp/cl-macs.el
@@ -1537,31 +1537,34 @@ cl--parse-loop-clause
 	(push `(>= (setq ,temp (1- ,temp)) 0) cl--loop-body)))
 
      ((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)))
+      (let ((what (pop cl--loop-args)))
+        (cl-destructuring-bind (var var-tail) (cl--loop-handle-list-accum nil)
+          (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))))
 
-     ((memq word '(nconc nconcing append appending))
-      (let ((what (pop cl--loop-args))
-	    (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)))
+     ((memq word '(append appending))
+      (let ((what (pop cl--loop-args)))
+        (cl-destructuring-bind (var var-tail) (cl--loop-handle-list-accum nil)
+          (push `(progn
+                   (if (null ,var-tail)
+                       (setq ,var (copy-sequence ,what) ,var-tail (last ,var))
+                     (setq ,var-tail (setcdr ,var-tail (copy-sequence ,what))))
+                   t)
+                cl--loop-body))))
+
+     ((memq word '(nconc nconcing))
+      (let ((what (pop cl--loop-args)))
+        (cl-destructuring-bind (var var-tail) (cl--loop-handle-list-accum nil)
+          (push `(progn
+                   (if (null ,var-tail)
+                       (setq ,var ,what ,var-tail (last ,var))
+                     (setq ,var-tail (setcdr ,var-tail ,what)))
+                   t)
+                cl--loop-body))))
 
      ((memq word '(concat concating))
       (let ((what (pop cl--loop-args))
@@ -1726,22 +1729,58 @@ cl--loop-let
       `(,(if par 'let 'let*)
         ,(nconc (nreverse temps) (nreverse new)) ,@body))))
 
-(defun cl--loop-handle-accum (def &optional func) ; uses loop-*
-  (if (eq (car cl--loop-args) 'into)
-      (let ((var (cl--pop2 cl--loop-args)))
-	(or (memq var cl--loop-accum-vars)
-	    (progn (push (list (list var def)) cl--loop-bindings)
-		   (push var cl--loop-accum-vars)))
-	var)
-    (or cl--loop-accum-var
-	(progn
-	  (push (list (list
-                       (setq cl--loop-accum-var (make-symbol "--cl-var--"))
-                       def))
-                cl--loop-bindings)
-	  (setq cl--loop-result (if func (list func cl--loop-accum-var)
-                                  cl--loop-accum-var))
-	  cl--loop-accum-var))))
+(defun cl--loop-handle-list-accum (def)
+  "Handle list value accumulation clause.
+
+DEF is the initial value of the accumulation variable.
+
+Returns (VAR VAR-TAIL), where VAR is the accumulation variable
+and VAR-TAIL is the tail of the accumulator."
+  (cl-flet ((tail-symbol (var)
+              (gensym (concat (symbol-name var) "-tail-"))))
+    (cond
+      ((eq (car cl--loop-args) 'into)
+       (let* ((var (cl--pop2 cl--loop-args))
+              (var-tail (tail-symbol var)))
+         (if (memq var cl--loop-accum-vars)
+             (push `((,var-tail ,(last def))) cl--loop-bindings)
+           (push `((,var ,def)) cl--loop-bindings)
+           (push `((,var-tail ,(last def))) cl--loop-bindings)
+           (push var cl--loop-accum-vars))
+         (list var var-tail)))
+
+      (cl--loop-accum-var
+       `(,cl--loop-accum-var ,(tail-symbol cl--loop-accum-var)))
+
+      (t (let* ((var (make-symbol "--cl-var--"))
+                (var-tail (tail-symbol var)))
+           (push `((,var ,def)) cl--loop-bindings)
+           (push `((,var-tail ,(last def))) cl--loop-bindings)
+           (setq cl--loop-accum-var var
+                 cl--loop-result var)
+           (list var var-tail))))))
+
+(defun cl--loop-handle-accum (def)
+  "Handle non-list value accumulation clause.
+
+DEF is the initial value of the accumulation variable.
+
+Returns the accumulation variable VAR."
+  (cond
+    ((eq (car cl--loop-args) 'into)
+     (let* ((var (cl--pop2 cl--loop-args)))
+       (unless (memq var cl--loop-accum-vars)
+         (push `((,var ,def)) cl--loop-bindings)
+         (push var cl--loop-accum-vars))
+       var))
+
+    (cl--loop-accum-var cl--loop-accum-var)
+
+    (t (let* ((var (make-symbol "--cl-var--")))
+         (push `((,var ,def)) cl--loop-bindings)
+         (setq cl--loop-accum-var var
+               cl--loop-result var)
+         var))))
 
 (defun cl--loop-build-ands (clauses)
   "Return various representations of (and . CLAUSES).
-- 
2.14.3

Re: Performance issue w/ `cl-loop`s `collect...into`

[Stefan Monnier]

> 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


> +(defun cl--loop-handle-accum (def)
[...]
> +  (cond
[...]
> +    (cl--loop-accum-var cl--loop-accum-var)

You can write this line as just

       (cl--loop-accum-var)


-- Stefan

Re: Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

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

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

On Sun, Apr 8, 2018 at 6:59 PM, Stefan Monnier <monnier@iro.umontreal.ca>
wrote:

> > 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
>
>
> > +(defun cl--loop-handle-accum (def)
> [...]
> > +  (cond
> [...]
> > +    (cl--loop-accum-var cl--loop-accum-var)
>
> You can write this line as just
>
>        (cl--loop-accum-var)
>
>
> -- Stefan
>
>
>

[-- Attachment #1.2: Type: text/html, Size: 2075 bytes --]

[-- Attachment #2: 0003-Optimize-collect.into.patch --]
[-- Type: text/x-patch, Size: 5754 bytes --]

From e56fd89c5838013011e729e5a21ff074588f2ad2 Mon Sep 17 00:00:00 2001
From: Tianxiang Xiong <tianxiang.xiong@gmail.com>
Date: Sun, 8 Apr 2018 12:36:41 -0700
Subject: [PATCH] Optimize `collect...into`

Avoid O(n^2) nconc-ing by keeping track of tail of collection.
---
 lisp/emacs-lisp/cl-macs.el | 115 ++++++++++++++++++++++++++++++---------------
 1 file changed, 77 insertions(+), 38 deletions(-)

diff --git a/lisp/emacs-lisp/cl-macs.el b/lisp/emacs-lisp/cl-macs.el
index 9600230c07..bd4ce1a64b 100644
--- a/lisp/emacs-lisp/cl-macs.el
+++ b/lisp/emacs-lisp/cl-macs.el
@@ -1537,31 +1537,34 @@ cl--parse-loop-clause
 	(push `(>= (setq ,temp (1- ,temp)) 0) cl--loop-body)))
 
      ((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)))
+      (let ((what (pop cl--loop-args)))
+        (cl-destructuring-bind (var var-tail) (cl--loop-handle-list-accum nil)
+          (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))))
 
-     ((memq word '(nconc nconcing append appending))
-      (let ((what (pop cl--loop-args))
-	    (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)))
+     ((memq word '(append appending))
+      (let ((what (pop cl--loop-args)))
+        (cl-destructuring-bind (var var-tail) (cl--loop-handle-list-accum nil)
+          (push `(progn
+                   (if (null ,var-tail)
+                       (setq ,var (copy-sequence ,what) ,var-tail (last ,var))
+                     (setq ,var-tail (setcdr ,var-tail (copy-sequence ,what))))
+                   t)
+                cl--loop-body))))
+
+     ((memq word '(nconc nconcing))
+      (let ((what (pop cl--loop-args)))
+        (cl-destructuring-bind (var var-tail) (cl--loop-handle-list-accum nil)
+          (push `(progn
+                   (if (null ,var-tail)
+                       (setq ,var ,what ,var-tail (last ,var))
+                     (setq ,var-tail (setcdr ,var-tail ,what)))
+                   t)
+                cl--loop-body))))
 
      ((memq word '(concat concating))
       (let ((what (pop cl--loop-args))
@@ -1726,22 +1729,58 @@ cl--loop-let
       `(,(if par 'let 'let*)
         ,(nconc (nreverse temps) (nreverse new)) ,@body))))
 
-(defun cl--loop-handle-accum (def &optional func) ; uses loop-*
-  (if (eq (car cl--loop-args) 'into)
-      (let ((var (cl--pop2 cl--loop-args)))
-	(or (memq var cl--loop-accum-vars)
-	    (progn (push (list (list var def)) cl--loop-bindings)
-		   (push var cl--loop-accum-vars)))
-	var)
-    (or cl--loop-accum-var
-	(progn
-	  (push (list (list
-                       (setq cl--loop-accum-var (make-symbol "--cl-var--"))
-                       def))
-                cl--loop-bindings)
-	  (setq cl--loop-result (if func (list func cl--loop-accum-var)
-                                  cl--loop-accum-var))
-	  cl--loop-accum-var))))
+(defun cl--loop-handle-list-accum (def)
+  "Handle list value accumulation clause.
+
+DEF is the initial value of the accumulation variable.
+
+Returns (VAR VAR-TAIL), where VAR is the accumulation variable
+and VAR-TAIL is the tail of the accumulator."
+  (cl-flet ((tail-symbol (var)
+              (gensym (concat (symbol-name var) "-tail-"))))
+    (cond
+      ((eq (car cl--loop-args) 'into)
+       (let* ((var (cl--pop2 cl--loop-args))
+              (var-tail (tail-symbol var)))
+         (if (memq var cl--loop-accum-vars)
+             (push `((,var-tail ,(last def))) cl--loop-bindings)
+           (push `((,var ,def)) cl--loop-bindings)
+           (push `((,var-tail ,(last def))) cl--loop-bindings)
+           (push var cl--loop-accum-vars))
+         (list var var-tail)))
+
+      (cl--loop-accum-var
+       `(,cl--loop-accum-var ,(tail-symbol cl--loop-accum-var)))
+
+      (t (let* ((var (make-symbol "--cl-var--"))
+                (var-tail (tail-symbol var)))
+           (push `((,var ,def)) cl--loop-bindings)
+           (push `((,var-tail ,(last def))) cl--loop-bindings)
+           (setq cl--loop-accum-var var
+                 cl--loop-result var)
+           (list var var-tail))))))
+
+(defun cl--loop-handle-accum (def)
+  "Handle non-list value accumulation clause.
+
+DEF is the initial value of the accumulation variable.
+
+Returns the accumulation variable VAR."
+  (cond
+    ((eq (car cl--loop-args) 'into)
+     (let* ((var (cl--pop2 cl--loop-args)))
+       (unless (memq var cl--loop-accum-vars)
+         (push `((,var ,def)) cl--loop-bindings)
+         (push var cl--loop-accum-vars))
+       var))
+
+    (cl--loop-accum-var)
+
+    (t (let* ((var (make-symbol "--cl-var--")))
+         (push `((,var ,def)) cl--loop-bindings)
+         (setq cl--loop-accum-var var
+               cl--loop-result var)
+         var))))
 
 (defun cl--loop-build-ands (clauses)
   "Return various representations of (and . CLAUSES).
-- 
2.14.3

Re: Performance issue w/ `cl-loop`s `collect...into`

[Stefan Monnier]

> 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


> Attached is a new patch that uses `(cl--loop-accum-var)`.
>
> On Sun, Apr 8, 2018 at 6:59 PM, Stefan Monnier <monnier@iro.umontreal.ca>
> wrote:
>
>> > 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
>>
>>
>> > +(defun cl--loop-handle-accum (def)
>> [...]
>> > +  (cond
>> [...]
>> > +    (cl--loop-accum-var cl--loop-accum-var)
>>
>> You can write this line as just
>>
>>        (cl--loop-accum-var)
>>
>>
>> -- Stefan
>>
>>
>>

Re: Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

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

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.

On Sun, Apr 8, 2018 at 7:20 PM, Stefan Monnier <monnier@iro.umontreal.ca>
wrote:

> > 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
>
>
> > Attached is a new patch that uses `(cl--loop-accum-var)`.
> >
> > On Sun, Apr 8, 2018 at 6:59 PM, Stefan Monnier <monnier@iro.umontreal.ca
> >
> > wrote:
> >
> >> > 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
> >>
> >>
> >> > +(defun cl--loop-handle-accum (def)
> >> [...]
> >> > +  (cond
> >> [...]
> >> > +    (cl--loop-accum-var cl--loop-accum-var)
> >>
> >> You can write this line as just
> >>
> >>        (cl--loop-accum-var)
> >>
> >>
> >> -- Stefan
> >>
> >>
> >>
>

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

Re: Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

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

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.



On Sun, Apr 8, 2018 at 8:34 PM, Tianxiang Xiong <tianxiang.xiong@gmail.com>
wrote:

> 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.
>
> On Sun, Apr 8, 2018 at 7:20 PM, Stefan Monnier <monnier@iro.umontreal.ca>
> wrote:
>
>> > 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
>>
>>
>> > Attached is a new patch that uses `(cl--loop-accum-var)`.
>> >
>> > On Sun, Apr 8, 2018 at 6:59 PM, Stefan Monnier <
>> monnier@iro.umontreal.ca>
>> > wrote:
>> >
>> >> > 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
>> >>
>> >>
>> >> > +(defun cl--loop-handle-accum (def)
>> >> [...]
>> >> > +  (cond
>> >> [...]
>> >> > +    (cl--loop-accum-var cl--loop-accum-var)
>> >>
>> >> You can write this line as just
>> >>
>> >>        (cl--loop-accum-var)
>> >>
>> >>
>> >> -- Stefan
>> >>
>> >>
>> >>
>>
>
>

[-- Attachment #1.2: Type: text/html, Size: 5603 bytes --]

[-- Attachment #2: loop-perf-old --]
[-- Type: application/octet-stream, Size: 27342 bytes --]

[profiler-profile "24.3" cpu #s(hash-table size 145 test equal rehash-size 1.5 rehash-threshold 0.8125 data ([nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil] 40 [sp--do-action-p sp--get-allowed-pair-list sp--get-allowed-regexp sp-skip-forward-to-symbol sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil] 1 [sp--get-allowed-stringlike-list sp--get-stringlike-regexp sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil] 1 [window-edges window-inside-pixel-edges window-screen-lines line-move-partial line-move next-line funcall-interactively call-interactively command-execute nil nil nil nil nil nil nil] 3 [line-move next-line funcall-interactively call-interactively command-execute nil nil nil nil nil nil nil nil nil nil nil] 1 [apply eldoc-minibuffer-message eldoc-message eldoc-print-current-symbol-info "#<compiled 0x27c40d>" apply timer-event-handler nil nil nil nil nil nil nil nil nil] 2 [sp-get-pair sp--do-action-p sp--get-allowed-stringlike-list sp--get-stringlike-regexp sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil nil nil] 1 [line-move-visual line-move next-line funcall-interactively call-interactively command-execute nil nil nil nil nil nil nil nil nil nil] 1 [apply eldoc-minibuffer-message eldoc-message eldoc-pre-command-refresh-echo-area nil nil nil nil nil nil nil nil nil nil nil nil] 3 [-mapcat -flatten sp--do-action-p sp--get-allowed-pair-list sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil nil nil] 2 [sp-get-pair sp--do-action-p sp--get-allowed-pair-list sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil nil nil nil] 1 [regexp-opt-charset regexp-opt-group regexp-opt-group regexp-opt-group regexp-opt sp--regexp-for-group apply "#<compiled 0x15cde71>" mapconcat sp--strict-regexp-opt sp--get-opening-regexp sp-skip-backward-to-symbol sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply] 1 [sp-get-sexp sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil nil nil nil] 1 [regexp-opt-charset regexp-opt-group regexp-opt sp--regexp-for-group apply "#<compiled 0x15cde71>" mapconcat sp--strict-regexp-opt sp--get-allowed-regexp sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply] 1 [sp-show--pair-create-overlays "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil nil nil nil nil] 1 [sp-show--pair-echo-match "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil nil nil nil nil] 1 [framep-on-display display-graphic-p if eval redisplay_internal\ \(C\ function\) nil nil nil nil nil nil nil nil nil nil nil] 1 [-flatten sp--do-action-p sp--get-allowed-pair-list sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil nil nil nil] 3 [sp--get-pair-definition sp-get-pair sp--do-action-p sp--get-allowed-pair-list sp-skip-backward-to-symbol sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil] 2 [sp--strict-regexp-opt sp--get-closing-regexp sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil nil nil] 1 [sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil nil] 1 [sp--search-backward-regexp sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil] 1 [let* progn eval elisp--eval-last-sexp eval-last-sexp eros-eval-last-sexp funcall-interactively call-interactively command-execute nil nil nil nil nil nil nil] 215 [while let* progn eval elisp--eval-last-sexp eval-last-sexp eros-eval-last-sexp funcall-interactively call-interactively command-execute nil nil nil nil nil nil] 163 [setq while let* progn eval elisp--eval-last-sexp eval-last-sexp eros-eval-last-sexp funcall-interactively call-interactively command-execute nil nil nil nil nil] 142 ["#<compiled 0x14e3579>" map-char-table regexp-opt-charset regexp-opt-group regexp-opt sp--regexp-for-group apply "#<compiled 0x15cde71>" mapconcat sp--strict-regexp-opt sp--get-closing-regexp sp-show--pair-function apply timer-event-handler nil nil] 2 [sp-point-in-string sp--do-action-p sp--get-allowed-pair-list sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil nil] 1 [sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil nil nil nil nil] 1 [sp--strict-regexp-opt sp--get-allowed-regexp sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil] 1 [sp--looking-back sp--search-backward-regexp sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15d7089>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil] 1 [helm-source--persistent-help-string "#<compiled 0x12bea21>" apply "#<compiled 0x13a00a5>" apply helm--setup-source helm-make-source helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil nil nil] 2 [slot-value helm--create-source helm-make-source helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil nil nil nil nil nil nil] 1 [helm-comp-read-get-candidates "#<compiled 0x1860af1>" "#<compiled 0x202cbf5>" apply helm-funcall-with-source helm-funcall-foreach helm-initial-setup helm-initialize helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code] 14 [mapconcat helm-init-candidates-in-buffer "#<compiled 0x202cbf5>" apply helm-funcall-with-source helm-funcall-foreach helm-initial-setup helm-initialize helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code] 1 [helm-create-helm-buffer helm-initial-setup helm-initialize helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil nil] 1 [window--maybe-raise-frame display-buffer-pop-up-window display-buffer--maybe-pop-up-frame-or-window display-buffer helm-default-display-buffer helm-display-buffer helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute] 3 [helm-M-x-transformer-1 helm-M-x-transformer-hist apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command] 2 [helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command] 2 [sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read] 1 ["#<compiled 0x136eba5>" helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-read-pattern-maybe helm-internal apply helm apply] 2 [helm-mm-split-pattern helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-read-pattern-maybe helm-internal apply helm apply] 1 [helm-insert-match helm-render-source helm-update helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil] 1 [helm-display-mode-line helm-move-selection-common helm--update-move-first-line helm-update helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil] 1 [helm-display-mode-line "#<compiled 0x18c5841>" helm-update helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil] 1 [helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil nil nil nil] 32 [timer--time-less-p timer--activate timer-activate run-at-time undo-auto--boundary-ensure-timer undo-auto--undoable-change read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code] 2 [read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil nil nil] 59 [helm-M-x-transformer-1 helm-M-x-transformer-hist apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal] 18 [helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply] 6 [assoc-default "#<compiled 0x1910039>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input] 1 ["#<compiled 0x1910039>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>"] 7 [helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply] 2 [replace-regexp-in-string helm-mm-split-pattern helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply] 4 [helm-mm-split-pattern helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler] 3 ["#<compiled 0x136eba5>" helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler] 11 [split-string helm-mm-split-pattern helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply] 2 ["#<compiled 0x17fdca9>" helm-fuzzy-default-highlight-match helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe] 2 [replace-buffer-in-windows kill-buffer "#<compiled 0x1809c2d>" helm-fuzzy-default-highlight-match helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler] 2 [helm-insert-match helm-render-source helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read] 5 [helm-display-mode-line helm-move-selection-common helm--update-move-first-line helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm] 25 [helm-display-mode-line "#<compiled 0x18af209>" helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read] 19 [timer-activate-when-idle timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil] 1 [helm-mm-3-search-base helm-mm-3-search helm-mm-search "#<compiled 0x15562f9>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update] 7 [helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal] 14 [generate-new-buffer helm-fuzzy-default-highlight-match helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe] 1 [helm-fuzzy-default-highlight-match helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal] 6 [helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code] 1 [helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm] 1 [kill-buffer "#<compiled 0x18b8d61>" helm-fuzzy-default-highlight-match helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer] 2 [apply replace-regexp-in-string helm-mm-split-pattern helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>"] 1 [sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe] 2 [helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer] 1 [helm-fast-remove-dups helm-cr-default-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal] 1 [apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm] 1 [cl--parse-loop-clause "#<compiled 0x4117ed>" cl-loop "#<lambda 0xd7736ded3c8b0>" apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer] 1 [helm-mm-exact-search "#<compiled 0x1f88315>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input] 3 [helm-render-source helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command] 1 [helm-pos-header-line-p helm-end-of-source-1 helm-end-of-source-p helm-empty-source-p helm-show-candidate-number save-current-buffer with-current-buffer with-helm-buffer eval redisplay_internal\ \(C\ function\) read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply] 1 ["#<compiled 0x4117ed>" cl-loop "#<lambda 0xd7736ded3c8b0>" apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe] 2 [helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler] 1 [eval redisplay_internal\ \(C\ function\) read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil] 1 ["#<compiled 0x4113f1>" cl-block cl-loop "#<lambda 0xd7736ded3c8b0>" apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer] 1 [helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply] 2 [helm-pos-multiline-p helm-mark-current-line helm-move-selection-common helm--update-move-first-line helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply] 1 [helm-mm-3-search helm-mm-search "#<compiled 0x1ab1d75>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input] 1 [helm-candidates-in-buffer-search-default-fn "#<compiled 0x1ab1d75>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input] 1 [helm-show-candidate-number save-current-buffer with-current-buffer with-helm-buffer eval redisplay_internal\ \(C\ function\) read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code] 2 [cl-loop "#<lambda 0xd7736ded3c8b0>" apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal] 2 ["#<compiled 0x20221ad>" helm-match-from-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply] 2 [split-string helm-mm-split-pattern helm-fuzzy-default-highlight-match helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer] 2 [replace-regexp-in-string helm-mm-split-pattern helm-mm-3-get-patterns-internal helm-mm-3-get-patterns helm-mm-3-match helm-mm-match helm-match-from-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer] 1 [undo-auto--ensure-boundary undo-auto--boundaries undo-auto--add-boundary read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil] 2 [helm-M-x-transformer-hist apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply] 1 [replace-regexp-in-string helm-update-source-p helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read] 1 [helm-mm-search "#<compiled 0x17ded61>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input] 1 ["#<compiled 0x17df055>" "#<compiled 0x17df131>" map-keymap cl--map-keymap-recursively "#<compiled 0x17df07d>" map-keymap cl--map-keymap-recursively helm-M-x-get-major-mode-command-alist helm-M-x-current-mode-map-alist helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches] 1 [cl--safe-expr-p "#<compiled 0x4113f1>" cl-block cl-loop "#<lambda 0xd7736ded3c8b0>" apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler] 1 [helm-mm-split-pattern helm-search-match-part "#<compiled 0x185dea5>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input] 1 [replace-regexp-in-string helm-get-mode-map-from-mode helm-M-x-current-mode-map-alist helm-M-x-transformer-1 helm-M-x-transformer-hist apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x12d1045>" apply timer-event-handler] 2 [helm-confirm-and-exit-minibuffer funcall-interactively call-interactively command-execute read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute] 5 [window-min-size "#<compiled 0x1efe745>" walk-window-tree-1 walk-window-tree-1 walk-window-tree window--sanitize-window-sizes read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code] 2 [select-frame-set-input-focus helm-frame-or-window-configuration helm-cleanup "#<compiled 0x12714c9>" helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil] 3 [profiler-cpu-profile profiler-report-cpu profiler-report funcall-interactively call-interactively command-execute helm-M-x funcall-interactively call-interactively command-execute nil nil nil nil nil nil] 5 [Automatic\ GC] 113)) (23242 57185 643672 36000) nil]

[-- Attachment #3: loop-perf-new --]
[-- Type: application/octet-stream, Size: 27322 bytes --]

[profiler-profile "24.3" cpu #s(hash-table size 145 test equal rehash-size 1.5 rehash-threshold 0.8125 data ([nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil] 27 [font-lock-default-fontify-region font-lock-fontify-region "#<compiled 0x245acf9>" run-hook-wrapped jit-lock--run-functions jit-lock-fontify-now jit-lock-function redisplay_internal\ \(C\ function\) nil nil nil nil nil nil nil nil] 1 [eval redisplay_internal\ \(C\ function\) nil nil nil nil nil nil nil nil nil nil nil nil nil nil] 1 [sp--do-action-p sp--get-allowed-pair-list sp--get-allowed-regexp sp-skip-forward-to-symbol sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil] 1 [sp--get-pair-definition sp-get-pair sp--do-action-p sp--get-allowed-stringlike-list sp--get-stringlike-regexp sp-skip-forward-to-symbol sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil] 1 [sp-get-sexp sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil nil nil nil nil] 1 [syntax-ppss sp--syntax-ppss sp-point-in-string sp-point-in-string-or-comment sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil nil nil nil] 1 [apply timer-event-handler nil nil nil nil nil nil nil nil nil nil nil nil nil nil] 2 [regexp-opt-group regexp-opt sp--regexp-for-group apply "#<compiled 0x15eb139>" mapconcat sp--strict-regexp-opt sp--get-allowed-regexp sp-skip-forward-to-symbol sp-get-thing sp-forward-sexp if *-forward-sexp funcall-interactively call-interactively command-execute] 1 [sp--get-pair-definition sp-get-pair sp--do-action-p sp--get-allowed-pair-list sp-get-thing sp-forward-sexp if *-forward-sexp funcall-interactively call-interactively command-execute nil nil nil nil nil] 1 [sp--get-pair-definition sp-get-pair sp--do-action-p sp--get-allowed-pair-list sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing sp-forward-sexp if *-forward-sexp funcall-interactively call-interactively command-execute nil nil] 1 [sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing sp-forward-sexp if *-forward-sexp funcall-interactively call-interactively command-execute nil nil nil nil nil nil] 1 [-mapcat -flatten sp--do-action-p sp--get-allowed-pair-list sp-skip-backward-to-symbol sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil] 1 [regexp-opt-charset regexp-opt-group regexp-opt-group regexp-opt-group regexp-opt sp--regexp-for-group apply "#<compiled 0x15eb139>" mapconcat sp--strict-regexp-opt sp--get-allowed-regexp sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function] 1 [sp--elisp-skip-match sp--skip-match-p sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil] 1 [regexp-opt sp--regexp-for-group apply "#<compiled 0x15eb139>" mapconcat sp--strict-regexp-opt sp--get-closing-regexp sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil] 2 [regexp-opt sp--regexp-for-group apply "#<compiled 0x15eb139>" mapconcat sp--strict-regexp-opt sp--get-closing-regexp sp-skip-backward-to-symbol sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil nil nil] 1 [regexp-opt-charset regexp-opt-group regexp-opt-group regexp-opt-group regexp-opt-group regexp-opt-group regexp-opt sp--regexp-for-group apply "#<compiled 0x15eb139>" mapconcat sp--strict-regexp-opt sp--get-allowed-regexp sp-get-expression sp-get-sexp sp-get-thing] 1 ["#<compiled 0x15eb125>" -group-by sp--strict-regexp-opt sp--get-allowed-regexp sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil nil nil nil] 1 [let* progn eval elisp--eval-last-sexp eval-last-sexp eros-eval-last-sexp funcall-interactively call-interactively command-execute nil nil nil nil nil nil nil] 192 [setq while let* progn eval elisp--eval-last-sexp eval-last-sexp eros-eval-last-sexp funcall-interactively call-interactively command-execute nil nil nil nil nil] 162 [while let* progn eval elisp--eval-last-sexp eval-last-sexp eros-eval-last-sexp funcall-interactively call-interactively command-execute nil nil nil nil nil nil] 170 [ispell-get-decoded-string ispell-get-otherchars flyspell-check-word-p flyspell-post-command-hook nil nil nil nil nil nil nil nil nil nil nil nil] 1 [regexp-opt-group regexp-opt-group regexp-opt-group regexp-opt sp--regexp-for-group apply "#<compiled 0x15eb139>" mapconcat sp--strict-regexp-opt sp--get-closing-regexp sp-show--pair-function apply timer-event-handler nil nil nil] 1 [regexp-opt-group regexp-opt-group regexp-opt-group regexp-opt-group regexp-opt sp--regexp-for-group apply "#<compiled 0x15eb139>" mapconcat sp--strict-regexp-opt sp--get-closing-regexp sp-skip-backward-to-symbol sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply] 1 [sp-point-in-comment sp-point-in-string-or-comment sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil nil] 1 [sp--get-pair-definition sp-get-pair sp--do-action-p sp--get-allowed-pair-list sp--get-allowed-regexp sp-skip-backward-to-symbol sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil nil nil nil nil] 1 ["#<compiled 0x1a40b71>" mapcar -mapcat -flatten sp--do-action-p sp--get-allowed-pair-list sp-skip-backward-to-symbol sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil nil nil nil] 1 [sp--get-pair-definition sp-get-pair sp--do-action-p sp--get-allowed-pair-list sp--get-allowed-regexp sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil nil nil nil] 1 [regexp-opt sp--regexp-for-group apply "#<compiled 0x15eb139>" mapconcat sp--strict-regexp-opt sp--get-allowed-regexp sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function apply timer-event-handler nil] 1 [regexp-opt-group regexp-opt-group regexp-opt-group regexp-opt sp--regexp-for-group apply "#<compiled 0x15eb139>" mapconcat sp--strict-regexp-opt sp--get-allowed-regexp sp-get-paired-expression sp-get-expression sp-get-sexp sp-get-thing "#<compiled 0x15f62c9>" sp-show--pair-function] 1 [syntax-ppss sp--syntax-ppss sp-point-in-string sp--save-pre-command-state nil nil nil nil nil nil nil nil nil nil nil nil] 2 [helm-source--persistent-help-string "#<compiled 0x1325449>" apply "#<compiled 0x13a8dcd>" apply helm--setup-source helm-make-source helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil nil nil] 2 [helm-make-source helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil nil nil nil nil nil nil nil nil] 1 [helm-comp-read-get-candidates "#<compiled 0x1c95429>" "#<compiled 0x1e21055>" apply helm-funcall-with-source helm-funcall-foreach helm-initial-setup helm-initialize helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code] 18 [helm-init-candidates-in-buffer "#<compiled 0x1e21055>" apply helm-funcall-with-source helm-funcall-foreach helm-initial-setup helm-initialize helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively] 2 [set-face-attribute page-break-lines--update-display-table mapc page-break-lines--update-display-tables set-window-buffer window--display-buffer display-buffer-pop-up-window display-buffer--maybe-pop-up-frame-or-window display-buffer helm-default-display-buffer helm-display-buffer helm-internal apply helm apply helm] 1 [window--maybe-raise-frame display-buffer-pop-up-window display-buffer--maybe-pop-up-frame-or-window display-buffer helm-default-display-buffer helm-display-buffer helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute] 4 [helm-M-x-transformer-1 helm-M-x-transformer-hist apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command] 2 [helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command] 3 [helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code] 1 [helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-read-pattern-maybe helm-internal apply helm apply helm] 2 [helm-mm-split-pattern helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-read-pattern-maybe helm-internal apply helm apply] 1 ["#<compiled 0x139324d>" helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-read-pattern-maybe helm-internal apply helm apply] 4 [helm-insert-match helm-render-source helm-update helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil] 1 [helm-display-mode-line helm-move-selection-common helm--update-move-first-line helm-update helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil] 1 [helm-display-mode-line "#<compiled 0x1887ccd>" helm-update helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil] 2 [helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil nil nil nil] 33 [minibuffer-inactive-mode read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil nil] 2 [read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil nil nil] 67 [apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil] 3 [helm-M-x-transformer-hist apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply] 4 [helm-M-x-transformer-1 helm-M-x-transformer-hist apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal] 15 [helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply] 3 [helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read] 2 [helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal] 10 [sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe] 3 ["#<compiled 0x139324d>" helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler] 7 [helm-mm-split-pattern helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler] 2 [helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply] 6 ["#<compiled 0x14fa865>" helm-fuzzy-default-highlight-match helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe] 3 [helm-insert-match helm-render-source helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read] 7 [helm-display-mode-line helm-move-selection-common helm--update-move-first-line helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm] 17 [helm-display-mode-line "#<compiled 0x1a84951>" helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read] 16 [helm-set-case-fold-search helm-match-from-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply] 7 ["#<compiled 0x1eb1151>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>"] 3 [split-string helm-mm-split-pattern helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply] 2 [helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer] 5 [helm-add-face-text-properties helm-fuzzy-default-highlight-match helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe] 3 [helm--reset-update-flag helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command] 1 [helm-mm-3-match helm-mm-match helm-match-from-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm] 2 [helm-mm-exact-search "#<compiled 0x18ec06d>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input] 3 [helm-mm-search "#<compiled 0x18ec06d>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input] 1 [replace-regexp-in-string helm-mm-split-pattern helm-generic-sort-fn sort helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply] 2 [kill-buffer "#<compiled 0x14f1329>" helm-fuzzy-default-highlight-match helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer] 1 [helm-mm-3-search-base helm-mm-3-search helm-mm-search "#<compiled 0x2470449>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update] 3 [helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply] 2 [magit-preserve-section-visibility-cache kill-buffer "#<compiled 0x184abb5>" helm-fuzzy-default-highlight-match helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler] 1 [helm-pos-header-line-p helm-follow-execute-persistent-action-maybe helm-move-selection-common helm--update-move-first-line helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply] 1 [helm-basename helm-set-case-fold-search "#<compiled 0x20b7331>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input] 1 [helm-candidates-in-buffer-search-default-fn "#<compiled 0x20b7331>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input] 4 [helm-update-source-p helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command] 1 [helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively] 2 [helm-show-candidate-number save-current-buffer with-current-buffer with-helm-buffer eval redisplay_internal\ \(C\ function\) read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code] 1 [helm-insert-header helm-insert-header-from-source helm-render-source helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm] 1 [eval redisplay_internal\ \(C\ function\) read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil] 1 [helm-match-from-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm] 2 [helm-set-case-fold-search "#<compiled 0x2180aad>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input] 2 [helm-fuzzy-default-highlight-match helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe helm-internal] 3 ["#<compiled 0x412b79>" cl-loop "#<lambda 0xfe793a987a99f>" apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer helm-read-pattern-maybe] 1 [replace-regexp-in-string helm-mm-split-pattern helm-search-match-part "#<compiled 0x1c8c691>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update] 1 ["#<compiled 0x1c8c8e5>" "#<compiled 0x246ce25>" map-keymap cl--map-keymap-recursively "#<compiled 0x246cd7d>" map-keymap cl--map-keymap-recursively helm-M-x-get-major-mode-command-alist helm-M-x-current-mode-map-alist helm-M-x-transformer-1 helm-M-x-transformer apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches] 1 [split-string helm-mm-split-pattern helm-fuzzy-default-highlight-match helm-fuzzy-highlight-matches apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer] 1 ["#<compiled 0x412b29>" cl-block cl-loop "#<lambda 0xfe793a987a99f>" apply helm-funcall-with-source helm-process-filtered-candidate-transformer helm-compute-matches helm--collect-matches helm-update helm-check-new-input helm-check-minibuffer-input "#<compiled 0x13353d5>" apply timer-event-handler read-from-minibuffer] 1 [helm-mm-3-search helm-mm-search "#<compiled 0x1ca9071>" helm--search-from-candidate-buffer-1 helm-search-from-candidate-buffer helm-candidates-in-buffer-1 helm-candidates-in-buffer apply helm-funcall-with-source helm-interpret-value helm-get-candidates helm-get-cached-candidates helm-compute-matches helm--collect-matches helm-update helm-check-new-input] 1 [helm-confirm-and-exit-minibuffer funcall-interactively call-interactively command-execute read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute] 9 [global-edit-server-edit-mode-cmhh kill-all-local-variables minibuffer-inactive-mode read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil] 1 [walk-window-tree-1 walk-window-tree window--sanitize-window-sizes read-from-minibuffer helm-read-pattern-maybe helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil] 1 [custom-load-symbol customize-set-variable progn if *-popwin-help-mode-on run-hooks helm-log-run-hook helm-cleanup "#<compiled 0x13217b5>" helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command] 1 [select-frame-set-input-focus helm-frame-or-window-configuration helm-cleanup "#<compiled 0x13217b5>" helm-internal apply helm apply helm helm-comp-read helm-M-x-read-extended-command byte-code call-interactively command-execute nil nil] 4 [helm-M-x funcall-interactively call-interactively command-execute nil nil nil nil nil nil nil nil nil nil nil nil] 1 [profiler-cpu-profile profiler-report-cpu profiler-report funcall-interactively call-interactively command-execute helm-M-x funcall-interactively call-interactively command-execute nil nil nil nil nil nil] 1 [Automatic\ GC] 95)) (23242 57220 396807 575000) nil]

Re: Performance issue w/ `cl-loop`s `collect...into`

[Stefan Monnier]

> 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

Re: Performance issue w/ `cl-loop`s `collect...into`

[Basil L. Contovounesios]

Tianxiang Xiong <tianxiang.xiong@gmail.com> writes:

> 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

Re: Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

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

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.

On Mon, Apr 9, 2018 at 5:22 AM, Basil L. Contovounesios <contovob@tcd.ie>
wrote:

> Tianxiang Xiong <tianxiang.xiong@gmail.com> writes:
>
> > 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
>

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

Re: Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

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

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 🙄!


On Mon, Apr 9, 2018 at 8:28 AM, Tianxiang Xiong <tianxiang.xiong@gmail.com>
wrote:

> 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.
>
> On Mon, Apr 9, 2018 at 5:22 AM, Basil L. Contovounesios <contovob@tcd.ie>
> wrote:
>
>> Tianxiang Xiong <tianxiang.xiong@gmail.com> writes:
>>
>> > 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
>>
>
>

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

Re: Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

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

Since it appears there's no performance degradation, can we merge this?

If others would like to do some testing, that'd be great.

On Mon, Apr 9, 2018 at 8:33 AM, Tianxiang Xiong <tianxiang.xiong@gmail.com>
wrote:

> 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 🙄!
>
>
> On Mon, Apr 9, 2018 at 8:28 AM, Tianxiang Xiong <tianxiang.xiong@gmail.com
> > wrote:
>
>> 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.
>>
>> On Mon, Apr 9, 2018 at 5:22 AM, Basil L. Contovounesios <contovob@tcd.ie>
>> wrote:
>>
>>> Tianxiang Xiong <tianxiang.xiong@gmail.com> writes:
>>>
>>> > 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
>>>
>>
>>
>

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