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

[Tianxiang Xiong <tianxiang.xiong@gmail.com>]

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