O(N^2) behavior in LOOP

[Daniel Colascione <daniel@censorshipresearch.org>]

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

Erm, what's going on here?

  (loop for x in '(1 2 3)
        collect x into foo)

Expands into

  (cl-block-wrapper
   (catch '--cl-block-nil--
     (let*
         ((--cl-var--
           '(1 2 3))
          (x nil)
          (foo nil))
       (while
           (consp --cl-var--)
         (setq x
               (car --cl-var--))
         (setq foo
               (nconc foo
                      (list x)))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ WTF?
         (setq --cl-var--
               (cdr --cl-var--)))
       nil)))


What is going on with the indicated line? That's O(N^2) because nconc
has to traverse the entire 'foo' list each time a value is appended.
Without the 'into' clause, loop uses push and nreverse, which, while
still suboptimal, is at least linear.

Before I go fix the loop macro, is there a _reason_ for the nconc silliness?


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 195 bytes --]