2010-12-29

文字列操作の性能（1）

公開日時
ラベル
,

Common Lispで文字列を操作する場合に、何種類かある方法のうち、どれが一番効率的か知りたかったので、調べることにした。今回は参照編。

次のコードを使って、シーケンシャルアクセスの時間を測った。処理系はClozure CL 1.6。get-internal-real-timeの単位はミリ秒。

(defmacro with-random-string ((var &optional (length 1000)) &body body)
  `(let ((,var (make-string ,length)))
     (iter (for i index-of-string ,var)
           (setf (aref ,var i) (code-char (+ 32 (random 95)))))
     ,@body))

(defmacro with-null-stream ((var) &body body)
  `(let ((,var (make-two-way-stream (make-concatenated-stream) 
                                    (make-broadcast-stream))))
     (with-open-stream (,var ,var)
       ,@body)))

(defmacro with-benchmark (&body body)
  (with-gensyms (time)
    `(let ((,time (get-internal-real-time)))
       ,@body
       (- (get-internal-real-time) ,time))))

(defparameter *times* 1000)
(defparameter *length* 1024)

(iter (repeat *times*)
      (sum (with-random-string (str *length*)
             (with-null-stream (*standard-output*)
               (with-benchmark
                 (iter (for i index-of-string str)
                       (princ (char str i))))))))

(iter (repeat *times*)
      (sum (with-random-string (str *length*)
             (with-null-stream (*standard-output*)
               (with-benchmark
                 (iter (for i index-of-string str)
                       (princ (aref str i))))))))

(iter (repeat *times*)
      (sum (with-random-string (str *length*)
             (with-null-stream (*standard-output*)
               (with-benchmark
                 (iter (for i index-of-string str)
                       (princ (elt str i))))))))

(iter (repeat *times*)
      (sum (with-random-string (str *length*)
             (with-null-stream (*standard-output*)
               (with-input-from-string (s str)
                 (with-benchmark
                   (iter (for c = (read-char s nil))
                         (while c)
                         (princ c))))))))

結果は、

関数 所要時間（ミリ秒）
char 1093
aref 998
elt 1063
read-char 1189

arefが一番速い。eltは、型に合わせて下位のアクセサを呼ぶと思っていたので、一番速くないのは予想通り。何となくcharはプリミティブなアクセサだと思い込んでいたけど、実際はarefとeltよりも遅い。文字列ストリームが一番遅いのは予想外。予想以上に上位の関数で組み立てられている模様。

実際のコードを読んでみた。まずはchar。

(defun char (string index)
  "Given a string and a non-negative integer index less than the length of
  the string, returns the character object representing the character at
  that position in the string."
  (if (typep string 'simple-string)
    (schar (the simple-string string) index)
    (if (stringp string)
      (multiple-value-bind (data offset) (array-data-and-offset string)
        (schar (the simple-string data) (+ index offset)))
      (report-bad-arg string 'string))))

scharを呼んでいる。scharの定義は、

(defun schar (s i)
  "SCHAR returns the character object at an indexed position in a string
   just as CHAR does, except the string must be a simple-string."
  (let* ((typecode (typecode s)))
    (declare (fixnum typecode))
    (if (= typecode target::subtag-simple-base-string)
      (aref (the simple-string s) i)
      (report-bad-arg s 'simple-string))))

で、結局呼ぶのはaref。Common Lispでは文字列は文字のベクタなので、ベクタに対する処理のarefの方が下位ということなんだろう。

(defun aref (a &lexpr subs)
  "Return the element of the ARRAY specified by the SUBSCRIPTS."
  (let* ((n (%lexpr-count subs)))
    (declare (fixnum n))
    (if (= n 1)
      (%aref1 a (%lexpr-ref subs n 0))
      (if (= n 2)
        (%aref2 a (%lexpr-ref subs n 0) (%lexpr-ref subs n 1))
        (if (= n 3)
          (%aref3 a (%lexpr-ref subs n 0) (%lexpr-ref subs n 1) (%lexpr-ref subs n 2))
          (let* ((typecode (typecode a)))
            (declare (fixnum typecode))
            (if (>= typecode target::min-vector-subtag)
              (%err-disp $XNDIMS a n)
              (if (< typecode target::min-array-subtag)
                (report-bad-arg a 'array)
                ;;  This typecode is Just Right ...
                (progn
                  (unless (= (the fixnum (%svref a target::arrayH.rank-cell)) n)
                    (%err-disp $XNDIMS a n))
                  (let* ((rmi (%array-index a subs n)))
                    (declare (fixnum rmi))
                    (multiple-value-bind (data offset) (%array-header-data-and-offset a)
                      (declare (fixnum offset))
                      (uvref data (the fixnum (+ offset rmi))))))))))))))

arefはあからさまにプリミティブな内容。

(defun elt (sequence idx)
  "Return the element of SEQUENCE specified by INDEX."
  (seq-dispatch
   sequence
   (let* ((cell (nthcdr idx sequence)))
     (if (consp cell)
       (car (the cons cell))
       (if cell
         (report-bad-arg sequence '(satisfies proper-list-p))
         (%err-disp $XACCESSNTH idx sequence))))
       
   (progn
     (unless (and (typep idx 'fixnum) (>= (the fixnum idx) 0))
       (report-bad-arg idx 'unsigned-byte))
     (locally 
       (if (>= idx (length sequence))
         (%err-disp $XACCESSNTH idx sequence)
         (aref sequence idx))))))

eltは、総称関数ではなく、普通の関数。規格上でもそう決まっている。これもarefを呼んでいる。

文字列ストリームは、level-1/l1-streams.lispに定義がある。read-charしたとき、最終的に呼ばれるのは、おそらくこれ。

(defun string-input-stream-ioblock-read-char (ioblock)
  (let* ((string (string-stream-ioblock-string ioblock))
         (idx (string-input-stream-ioblock-index ioblock))
         (end (string-input-stream-ioblock-end ioblock)))
    (declare (fixnum idx end)
             (simple-string string))
    (if (< idx end)
      (progn (setf (string-input-stream-ioblock-index ioblock)
                   (the fixnum (1+ idx)))
             (schar string idx))
      :eof)))

scharを呼んでいるので、最終的に呼ばれるのはaref。

というわけで、実際の定義も計測結果を裏付ける内容だった。定義を見る限り、ランダムアクセスでも順位は変わらない。文字列ストリームだけ、file-positionで位置を指定する分、他と差が開くかもしれない。

結論としては、Clozure CL 1.6においては、文字列の要素を参照する場合、arefが一番速い。

情報を頂いたので追記。SBCLでは、最適化を掛けると、charやeltがarefに展開されるようで、ディスアセンブルした結果も一致するとのこと。良いなあ。

0 件のコメント:

コメントを投稿