リリカル☆Lisp開発日記

それなりに速い文字列探索は書けましたが、
これを使って文字列の置換を行うプログラムを書いたら、
GCが頻繁に動きあまり速くありませんでした ＼（＾o＾）／
make-arrayで作った配列に、with-output-to-stringを使って
princで書き込むといった感じのプログラムを書いたんですが、
配列の大きさが足りなくなるのを恐れて:adjustableをtにしたのが速度を低下させてるかも。
けど、nilにしたところで、自分で境界のチェックとかした方が遅いかもしれません。
文字列の一部をコピーする際にsubseqしたものをprincで書き込んでるけど、
これは文字列のコピーが一旦作られるからGC発生の原因の一つになってそうです。
Cのmemcpyみたいな関数があればい\いんですけどね。
subseqの代わりにdisplaced-arrayでも\使えばいいのか？
CLで高速な文字列操作を行うのは色々とコツがいりそうです。
*恐怖! 処理系組み込みのsearchは遅かった!?*
(追記)SBCLは一工夫でかなり速くなりました。最後まで読んでね。
なんだか悲しい事実を知ってしまいました。

(defmacro! dfa-search (str1 str2 &key start2 end2)
`(dfa-multi-search (,str2 ,g!pos :start ,start2 :end ,end2)
,str1 ,g!pos))

dfa-searchは見ての通り、dfa-multi-searchのラッパーです。
dfa-multi-searchは複数の候補をDFAを使って探索しますが、
候補が一つしかない場合は、単に文字列を先頭から1文字ずつ見るだけなので、
決して特別速いコードは生成されません。

(defvar *text*
"Function SEARCH
...(全体で1490文字)...
matching subsequence is returned.")
(defun bench% ()
(declare (optimize (speed 3) (safety 0) (space 0)))
(time (progn (dotimes (i 1000) (search "Syntax" *text*))
(dotimes (i 1000) (search "Arguments" *text*))
(dotimes (i 1000) (search "Description" *text*))
(dotimes (i 1000) (search "\\(^o^)/" *text*))))
(time (progn (dotimes (i 1000) (dfa-search "Syntax" *text*))
(dotimes (i 1000) (dfa-search "Arguments" *text*))
(dotimes (i 1000) (dfa-search "Description" *text*))
(dotimes (i 1000) (dfa-search "\\(^o^)/" *text*)))))

HyperSpecのsearchの説明(の一部)から4種類の文字列を
searchとdfa-searchで検索してみました。
結果は次の通りです。

;;; CLISP
;; search
Real time: 1.104947 sec.
Run time: 1.085989 sec.
Space: 0 Bytes
;; dfa-search
Real time: 0.768655 sec.
Run time: 0.746108 sec.
Space: 0 Bytes

;;; SBCL
;; search
Evaluation took:
0.139 seconds of real time
0.138718 seconds of total run time (0.138718 user, 0.000000 system)
100.00% CPU
208,102,940 processor cycles
0 bytes consed
;; dfa-search
Evaluation took:
0.048 seconds of real time
0.048145 seconds of total run time (0.048145 user, 0.000000 system)
100.00% CPU
72,104,234 processor cycles
0 bytes consed

;;; CMUCL
;; search
; Evaluation took:
;   0.33 seconds of real time
;   0.31113 seconds of user run time
;   0.0 seconds of system run time
;   488,008,050 CPU cycles
;   0 page faults and
;   0 bytes consed.
;; dfa-search
; Evaluation took:
;   0.09 seconds of real time
;   0.071036 seconds of user run time
;   0.0 seconds of system run time
;   125,955,056 CPU cycles
;   0 page faults and
;   0 bytes consed.

search遅い!!!
自分の書いたプログラムの方が速かったのに、全然嬉しくない…
基本的な関数なんだからしっかりと最適化してほしいです。
(それとも、ひょっとすると本物のLisperはあまりsearchを使わないのか?)

This entry was posted on 火曜日, 3月 17th, 2009 at 2:16 PM and is filed under プログラミング. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.