[Sbcl-devel] fill pointer slowness

[Stanislaw H. <sth...@te...>]

Hi,

I noticed that the performance of fill pointers is anomalously low. I
attach a simple test case:

  (defvar *garbage* (loop repeat 1000 collect (make-array 1000 :element-type 'base-char)))

  (defun vector-append (old new)
    (declare (optimize (speed 3) (safety 0) (debug 1))
             (type vector old new))
    (prog1 old
      (let* ((fill (fill-pointer old))
             (new-len (+ fill (length new))))
        (when (> new-len (array-dimension old 0))
          (adjust-array old new-len))
        (setf (fill-pointer old) new-len)
        (replace old new :start1 fill))))

  (defun vector-concatenate (arrays &key (element-type t))
    (declare (optimize (speed 3) (safety 0) (space 0)))
      (do* ((length (reduce #'+ arrays :key #'length))
            (retval (make-array length :element-type element-type))
            (offset 0 (+ offset (length i)))
            (rest arrays (cdr rest))
            (i (car rest) (car rest)))
           ((endp rest) retval)
        (declare (type vector i)
                 (type fixnum length))
        (replace retval i :start1 offset)))

  ;; concatenate all arrays at once, without using a fill pointer

  (time (vector-concatenate *garbage* :element-type 'base-char))

  ;; concatenate all arrays one by one, using an adjustable array with a
  ;; fill pointer

  (let ((retval (make-array 0 :element-type 'base-char :adjustable t :fill-pointer 0)))
    (time (reduce #'vector-append *garbage* :initial-value retval)))

  ;; wastefully concatenate all arrays by consing a new one for each
  ;; *garbage* elt

  (time (reduce (lambda (x y)
                  (vector-concatenate (list x y) :element-type
                  'base-char))
                *garbage*))

  ;; concatenate all arrays one by one, using an array with a fill pointer
  ;; and preallocated space

  (let ((retval (make-array 1000000 :element-type 'base-char :adjustable t :fill-pointer 0)))
    (time (reduce #'vector-append *garbage* :initial-value retval)))

Results on my system (Linux IA-32, SBCL 1.0.11.0) are as follows:

;; concatenate all arrays at once, without using a fill pointer

Evaluation took:
  0.048 seconds of real time
  0.048003 seconds of user run time
  0.0 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  1,016,392 bytes consed.

;; concatenate all arrays one by one, using an adjustable array with a
;; fill pointer

Evaluation took:
  22.666 seconds of real time
  19.401213 seconds of user run time
  0.404025 seconds of system run time
  [Run times include 0.14 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  500,519,048 bytes consed.

;; wastefully concatenate all arrays by consing a new one for each
;; *garbage* elt

Evaluation took:
  21.331 seconds of real time
  19.765236 seconds of user run time
  0.63604 seconds of system run time
  [Run times include 0.14 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  500,617,248 bytes consed.

;; concatenate all arrays one by one, using an array with a fill pointer
;; and preallocated space

Evaluation took:
  0.05 seconds of real time
  0.048003 seconds of user run time
  0.0 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  0 bytes consed.

Case 2 uses as much CPU time and conses about as much space as
purposefully inefficient case 3.

I bring this to your attention hoping that a willing developer would
implement a fast path for arrays with fill pointers.

-- 
   /\   
    /   Jabber ID       :: st...@ja...
  \ \/  Unix stuff      :: http://tehran.lain.pl
 \/\    Yet Another RBL :: http://rbl.lain.pl