sbclで文字列を効率的に扱う場合の型

あまり話題に関連性がないが、一応前々回の続き。

sbcl(1.0.37)での文字列関連の型の階層は以下のようになっている*1。

僕は最近までsimple-string型*2が文字列関連型の最下層だと思い込んでいたので、文字列を扱う部分のプログラムを高速化したい場合、(declare (simple-string ...))などを宣言していた。
しかし、上の図を見るとsimple-string型は、simple-base-string型とsimple-character-string型*3の基底型となっている。
実際、変数の型が事前に明らかな場合は、simple-string型の二つの副型を指定した方がsimple-string型を指定するより高速である。

;;;;;;;;;;
;;;; 準備
;;; 型準備
; simple-character-stringは、クラス名として存在しても型名ではないので、等価なものを定義しておく
(deftype simple-character-string () '(simple-array character *))  

;;; データ準備
;; 一万要素のランダムな文字列を作成する
;; ※base-string用のサンプルデータと合わせるために、個々の文字の値の上限が#xFFに収まるようにする
(defvar *sample-string* 
  (coerce (loop REPEAT 10000 COLLECT (code-char (random #x80))) 'string))
;; *sample-string*をbase-stringに変換する
(defvar *sample-base-string*
  (coerce *sample-string* 'simple-base-string))

(type-of *sample-string*)
--> (SIMPLE-ARRAY CHARACTER (10000))
(type-of *sample-base-string*)
--> (SIMPLE-BASE-STRING 10000)
(subtypep * **)
--> NIL  ; *sample-string*の型と*sample-base-string*の型は独立している
    T

;;; 関数準備
;; 文字列の各文字の値の合計値を求める関数を定義するマクロ
;; string-type引数で、処理対象の文字列の型を指定できる
(defmacro def-charcode-sum (fn-name string-type)
  `(defun ,fn-name (string &aux (sum 0))
     (declare (optimize (speed 3) (safety 0))
              (,string-type string)
              (fixnum sum))
     (loop FOR char ACROSS string 
           FOR code = (char-code char)
           DO (incf sum code))
     sum))

;; 関数定義
(def-charcode-sum charcode-sum1 string)
(def-charcode-sum charcode-sum2 simple-string)
(def-charcode-sum charcode-sum3 simple-character-string)
(def-charcode-sum charcode-sum4 simple-base-string)


;;;;;;;;;
;;;; 実行
(charcode-sum1 *sample-string*)
--> 637886

(charcode-sum1 *sample-base-string*)
--> 637886

(charcode-sum3 *sample-base-string*)
--> -5604664  ; simple-character-string型用の関数をsimple-base-string型の引数に適用すると結果が不正になる

(= (charcode-sum1 *sample-string*) (charcode-sum1 *sample-base-string*)
   (charcode-sum2 *sample-string*) (charcode-sum2 *sample-base-string*)
   (charcode-sum3 *sample-string*) (charcode-sum4 *sample-base-string*))
--> T

;;; 型宣言ごとの処理時間
(time  ; string型と宣言されている関数をsimple-character-stringに適用した場合
  (dotimes (i 10000 'done) 
    (charcode-sum1 *sample-string*)))
Evaluation took:
  0.594 seconds of real time  ; 0.594秒
  0.592037 seconds of total run time (0.592037 user, 0.000000 system)
  99.66% CPU
  1,883,232,728 processor cycles
  0 bytes consed
--> DONE

(time  ; simple-string型と宣言されている関数をsimple-character-stringに適用した場合
  (dotimes (i 10000 'done) 
    (charcode-sum2 *sample-string*)))
Evaluation took:
  0.284 seconds of real time  ; 0.284秒
  0.284018 seconds of total run time (0.284018 user, 0.000000 system)
  100.00% CPU
  901,336,060 processor cycles
  0 bytes consed
--> DONE

(time  ; simple-character-string型と宣言されている関数をsimple-character-stringに適用した場合
  (dotimes (i 10000 'done) 
    (charcode-sum3 *sample-string*)))
Evaluation took:
  0.096 seconds of real time  ; 0.096秒
  0.096006 seconds of total run time (0.096006 user, 0.000000 system)
  100.00% CPU
  305,298,289 processor cycles
  0 bytes consed
--> DONE

(time  ; string型と宣言されている関数をsimple-base-stringに適用した場合
  (dotimes (i 10000 'done) 
    (charcode-sum1 *sample-base-string*)))
Evaluation took:
  0.597 seconds of real time  ; 0.597秒
  0.596038 seconds of total run time (0.596038 user, 0.000000 system)
  99.83% CPU
  1,894,275,594 processor cycles
  0 bytes consed
--> DONE

(time  ; simple-string型と宣言されている関数をsimple-base-stringに適用した場合
  (dotimes (i 10000 'done) 
    (charcode-sum2 *sample-base-string*)))
Evaluation took:
  0.208 seconds of real time  ; 0.208秒
  0.204013 seconds of total run time (0.204013 user, 0.000000 system)
  98.08% CPU
  657,645,081 processor cycles
  0 bytes consed
--> DONE

(time  ; simple-base-string型と宣言されている関数をsimple-base-stringに適用した場合
  (dotimes (i 10000 'done) 
    (charcode-sum4 *sample-base-string*)))
Evaluation took:
  0.125 seconds of real time  ; 0.125秒
  0.124008 seconds of total run time (0.124008 user, 0.000000 system)
  99.20% CPU
  393,795,273 processor cycles
  0 bytes consed
--> DONE

;;; おまけ
;;; simpleではない文字列に対する処理時間
;; displaced
(let ((str (make-array (length *sample-string*) 
                       :element-type 'character 
                       :displaced-to *sample-string*
                       :displaced-index-offset 0)))
  (time  
   (dotimes (i 10000 'done) 
     (charcode-sum1 str))))  ; simpleではないので、適用可能なのはcharcode-sum1のみ
(AND (VECTOR CHARACTER 10000) (NOT SIMPLE-ARRAY))  ; 型
Evaluation took:
  1.644 seconds of real time  ; 1.644秒
  1.644102 seconds of total run time (1.640102 user, 0.004000 system)
  100.00% CPU
  5,215,281,747 processor cycles
  0 bytes consed
--> DONE

;; fill-pointer
(let ((str (make-array (length *sample-string*) 
                       :element-type 'character
                       :fill-pointer (length *sample-string*)
                       :initial-contents *sample-string*)))
  (print (type-of str))
  (time  
   (dotimes (i 10000 'done) 
     (charcode-sum1 str))))
(AND (VECTOR CHARACTER 10000) (NOT SIMPLE-ARRAY)) ; 型
Evaluation took:
  0.871 seconds of real time  ; 0.871秒
  0.872054 seconds of total run time (0.872054 user, 0.000000 system)
  100.11% CPU
  2,762,532,161 processor cycles
  0 bytes consed
--> DONE

このため、最近は処理速度を重視する場合には、(simple-array character *)と宣言するようにしている。
ただその場合は、型が異なると処理結果が不正となってしまう*4ので、対象となる値の型が確実に(simple-array character *)となるように気をつけなければならない*5。
igoやcreoleではそのために「文字列引数の型をチェックして(simple-array character *)ならそのまま、それ以外なら(simple-array character *)型になるように変換処理を施す」というようなことを行っている。

処理速度を考慮して文字列を扱う場合は、こういった型周りのことも考える必要がある。
しかし前々回も書いたように、こういったことを文字列処理を行う関数・ライブラリを各たびに意識しなければならないのは結構面倒。
なので、前々回に言及したJavaのStringライクなcommon lispの型(実際には構造体とその操作関数をまとめたパッケージ)で、文字列型に関する処理もまとめて行ってしまおう、というところで次に続く。
前置きが随分長くなってしまったが、次回が実装編。

*1:クラス間の階層関係はsb-mop:class-direct-subclasses及びsb-mop:class-direct-superclassesを用いて取得

*2:上の図に当てはめるなら本当はクラスと呼ぶのが正しいと思うが、今回の場合あまり厳密に区別する意味もないので"型"で統一することにする

*3: (simple-array character *)

*4:最悪のケースでは、プログラムが異常終了する

*5:全て均一に(simple-array character *)と宣言するのではなく「typecaseなどで分岐して各型ごとに処理を分ける」という方法もある。ただし、それはそれでいろいろと面倒なので、今のところ採用したことはない。もしかしたらそっちの方が良かったりして...