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

[Tianxiang Xiong]

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 <address@hidden> 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.