[Performance] List functions that process front-to-back should use mutation internally

[Jason94]

When building up a new list front-to-back, the fastest way to do it is to mutate the tails as you go, not to push and reverse. Examples of this kind of operation are take and append.

For example, the List implementation of iter:collect! does this:

  (define-instance (iter:FromIterator (List :elt) :elt)
    (define (iter:collect! iter)
      ;; Dropping into lisp is necessary because building a list from
      ;; front to back requires mutability.
      (lisp (List :elt) (iter)
        (cl:loop
           :with top := cl:nil
           :with current := cl:nil
           :for res := (iter:next! iter)
           :while (some? res)
           :do (cl:if current
                      (cl:progn
                        (cl:setf (cl:cdr current) (cl:cons (from-some "" res) cl:nil))
                        (cl:setf current (cl:cdr current)))
                      (cl:progn
                        (cl:setf top (cl:cons (from-some "" res) cl:nil))
                        (cl:setf current top)))
           :finally (cl:return top)))))

However, many of the functions do this immutably, which requires at least performing an unnecessary reverse and might require more Consing depending. For example, take:

  (declare take (UFix -> List :a -> List :a))
  (define (take n xs)
    "Returns the first N elements of a list."
    (let ((rec
            (fn (n in out)
              (if (== n 0)
                  out
                  (match in
                    ((Cons x xs) (rec (- n 1) xs (Cons x out)))
                    ((Nil) out))))))
      (%reverse! (rec n xs Nil))))

The best solution is probably to rewrite List functions in Common Lisp as necessary to improve performance. I'm not familiar with optimizing over the Coalton/CL bridge, so I'm not sure how much care needs to be taken to make sure that SBCL is able to utilize all of Coalton's type information.

[stylewarning]

I would probably introduce private List mutation primitives for stdlib implementation only.