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

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

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