String append

Esta rolando uma discução no comp.lang.lisp sobre a maneira mais rápida de concatenar string. Foram sugeridas as três alternativas abaixo:

(defun string-append0 (&rest strings)
  (declare (optimize (speed 3) (safety 0)))
  (apply #'concatenate 'string strings))

(defun string-append1 (&rest strings)
  (declare
   (optimize (speed 3) (safety 0)))
  (with-output-to-string (out)
    (loop for str in strings
         while str
       do (write-string str out))))

(defun string-append2 (&rest strings)
  (declare
   (optimize (speed 3) (safety 0)))
  (let ((output (make-array 0 :adjustable t :fill-pointer 0 :element-type 'base-char)))
    (loop for str in strings do
         (loop for char across str do
              (vector-push-extend char output)))
    output))


(defun string-append (&rest strings)
  (declare
   (optimize (speed 3) (safety 0)))
  (loop
     with len fixnum = (loop for str string in strings sum (length str))
     with output = (make-array len :element-type 'base-char )
     with  pos fixnum = -1

     for str string in strings
     while (< pos (1- len))
     do
       (loop for char across str
          do (setf (char output (incf pos)) char ))
     finally (return output)))

Executei o seguinte teste para avaliar o desempenho das implementações:

(eval-when (:execute)
  (declare (optimize ((speedy 3) (safety 0))))

  ; Cria uma list com 100 strings de 30 caracteres 
  (let ((lst (loop for i from 1 to 100
     collect
     (make-array 30 :element-type 'base-char :initial-element #\X))))

    ; Testa todas as funlções
    (dolist (f (list #'string-append0
       #'string-append1
       #'string-append2
       #'string-append))
      (format t "Running ~a~%" f)
      (time (loop repeat 1000 do (apply f lst))))))

Rodando no SBCL 1.0.0 em um Athlon 64 obtive os seguintes resultados:

Running #
Evaluation took:
  0.393 seconds of real time
  0.358946 seconds of user run time
  0.004999 seconds of system run time
  [Run times include 0.026 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  33,662,880 bytes consed.
Running #
Evaluation took:
  0.742 seconds of real time
  0.649901 seconds of user run time
  0.008999 seconds of system run time
  [Run times include 0.04 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  74,006,848 bytes consed.
Running #
Evaluation took:
  0.977 seconds of real time
  0.666898 seconds of user run time
  0.015997 seconds of system run time
  [Run times include 0.041 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  10,559,808 bytes consed.
Running #
Evaluation took:
  0.918 seconds of real time
  0.112983 seconds of user run time
  0.007999 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  4,640,224 bytes consed.

E o vencedor é STRING-APPEND, a função que utiliza o concatenate ficou em segundo lugar.