読者です 読者をやめる 読者になる 読者になる

DoubleArray(1.5) - 文字エンコーディングの違いによる速度・サイズ差

lisp

DoubleArray(1)で実装したDoubleArrayのテストも兼ねて、文字のエンコーディング方法の違いによって、どれくらい処理速度やサイズに差が出るのかを簡単に調べてみる。

それぞれを厳密に比較しているわけではないので、特に正確な情報が得られるわけではないが、大まかな感じは掴めると思う。


比較対象となるのは、utf-8euc-jp、shift-jisの三つ。


比較方法は、5万個の単語を順にDoubleArrayに挿入して、掛かった処理時間と最終的な配列のサイズを比べるというもの。
テストコードは以下の通り。

;; stringをoctetsに変換している関数
;; これを上書きして、エンコーディング方法(external-format)を指定する
(defun make-octets (#1=string-or-octets)
  (if (stringp #1#) (string-to-octets #1# :external-format :utf-8) #1#))

(defmacro a.while (expr &body body) 
  `(let (it)
     (loop while (setf it ,expr)
       ,@body)))  

;; 実行
(let ((da (make-da)))
  (time
   (with-open-file (in "/path/to/words")
      (a.while (read-line in nil nil)
        (handler-bind ((SB-IMPL::OCTETS-ENCODING-ERROR 
                         (lambda (c) (use-value #\? c))))
          (insert it da)))))
  da)

実行結果は以下の通り。

;;; utf8 ;;;
Evaluation took:
  984.957 seconds of real time
  984.789546 seconds of total run time (981.905365 user, 2.884181 system)
  [ Run times consist of 42.770 seconds GC time, and 942.020 seconds non-GC time. ]
  99.98% CPU
  3,124,717,944,534 processor cycles
  276,843,319,608 bytes consed
;; base,check,tailの横の数字は、それぞれの配列の長さ
#<DOUBLE-ARRAY base:309534 check:309534 tail:564589>


;;; shift-jis ;;;
  592.490 seconds of real time
  592.457026 seconds of total run time (590.712917 user, 1.744109 system)
  [ Run times consist of 25.337 seconds GC time, and 567.121 seconds non-GC time. ]
  99.99% CPU
  1,879,638,481,755 processor cycles
  167,058,115,608 bytes consed
#<DOUBLE-ARRAY base:175216 check:144288 tail:411995>


;;; euc-jp ;;;
  591.160 seconds of real time
  591.112942 seconds of total run time (589.188822 user, 1.924120 system)
  [ Run times consist of 25.639 seconds GC time, and 565.474 seconds non-GC time. ]
  99.99% CPU
  1,875,417,963,058 processor cycles
  165,358,802,528 bytes consed
#<DOUBLE-ARRAY base:196470 check:196458 tail:411597>

これを見た限りでは、utf-8が速度・サイズともに一番悪く、shift-jisとeuc-jpは速度で同程度、サイズならshift-jisが若干良い、といった感じだ。ただ、このバージョンは処理速度を気にせずに実装しているだけあって、どれも遅い。


最初に書いたように全然厳密な比較ではないが、それでもエンコーディングの方法によって割合大きな違い出ていることが見てとれて面白い。

もう少し実装を進めたら(特にオンメモリではなく、ファイル上で二重配列を操作するようにした後で)もう一度、もっとちゃんとした比較を行ってみる、かもしれない。


あと、挿入する文字列の集合があらかじめ決まっている場合には、それらに対して最適なエンコーディングを施すようにすれば、上で試したような汎用(?)の文字エンコーディングを使う場合よりも、少なくともサイズは小さくなると思うので、それも試してみたい(文字列圧縮アルゴリズムの勉強も兼ねて)。