#:g1: util.stringの紹介

Posted 2014-03-23 15:00:00 GMT

(LISP Library 365参加エントリ)

 LISP Library 365 の83日目です。

util.stringとはなにか

 util.stringは、Allegro CLの文字列ユーティリティです。
現在のところは、string+のみの様子。

パッケージ情報

パッケージ名util.string
ドキュメントString utility functions in Allegro CL

インストール方法

 Allegro CLで

(require :util-string)

します。

試してみる

内容は、string+のみですが、string+は、Clojureでいうstr、Arcでいうstringのような感じです。
ドキュメントによれば、string+では効率が良く高速な文字列生成が可能とのこと。util.stringが文字列を生成する上で最適化されている形式は、

とのこと。
ちなみに、最適化されているということであって他のデータ型が使えないという訳ではありません。

(util.string:string+ "a" #\b '|c| 1 '(2 3))
;=> "abc1(2 3)"

 util.stringの高速さはどんなものかということで色々調べたり計測してみることにしました。

(defun test-string+ ()
  (declare (optimize (debug 0) (safety 0) (speed 3)))
  (util.string:string+ "foo" "bar"))

(compiler-macro-function #'util.string:string+) ;=> NIL

(disassemble 'test-string+) ;>> ;; disassembly of #<Function TEST-STRING+> ;>> ;; formals: ;>> ;; constant vector: ;>> 0: "foo" ;>> 1: "bar" ;>> 2: UTIL.STRING:STRING+ ;>> ;>> ;; code start: #x1001319408: ;>> 0: 49 8b 7e 36 movq rdi,[r14+54] ; "foo" ;>> 4: 49 8b 76 3e movq rsi,[r14+62] ; "bar" ;>> 8: 49 8b 6e 46 movq rbp,[r14+70] ; UTIL.STRING:STRING+ ;>> 12: ff 63 d0 jmp *[rbx-48] ; SYS::TRAMP-TWO ;>> 15: 90 nop ;>> ;=> <no values>

 コンパイラマクロは付いてないようで、引数に文字列定数が来たら文字列を返してしまう、というようなことはしないようです。

 次にCL:CONCATENATEと速度を比べてみます。
CL:CONCATENATEよりstring+の方が文字列に変換するオブジェクトの種類は多いですが、さてどうか。

(defun test-concatenate ()
  (declare (optimize (debug 0) (safety 0) (speed 3)))
  (concatenate 'string "foo" "bar"))
(time (dotimes (i 1000000) (test-string+)))
; cpu time (non-gc) 0.176013 sec user, 0.004000 sec system
; cpu time (gc)     0.040001 sec user, 0.000000 sec system
; cpu time (total)  0.216014 sec user, 0.004000 sec system
; real time  0.225760 sec
; space allocation:
;  0 cons cells, 48,000,000 other bytes, 0 static bytes

(time (dotimes (i 1000000) (test-concatenate))) ; cpu time (non-gc) 0.060004 sec user, 0.004000 sec system ; cpu time (gc) 0.060004 sec user, 0.000000 sec system ; cpu time (total) 0.120008 sec user, 0.004000 sec system ; real time 0.123422 sec ; space allocation: ; 0 cons cells, 48,000,000 other bytes, 0 static bytes

 CL:CONCATENATEの方が速いという結果になりました。
素のCL:CONCATENATEもそんなに速くはなかった気がしたので、速くなりそうなものを自作して、それと比較してみます。

(defun ss+ (&rest strings)
  (declare (optimize (safety 0) (speed 3))
           (dynamic-extent strings))
  (let ((len 0)
        (pos 0))
    (declare (fixnum len pos))
    (dolist (s strings)
      (declare (simple-string s))
      (incf len (length s)))
    (let ((result (make-string len)))
      (declare (simple-string result))
      (dolist (s strings)
        (declare (simple-string s))
        (loop :for c :across s
              :do (setf (schar result pos) c) (incf pos)))
      result)))

(defun test-ss+ () (declare (optimize (debug 0) (safety 0) (speed 3))) (ss+ "foo" "bar"))

(time (dotimes (i 1000000) (test-ss+))) ; cpu time (non-gc) 0.016001 sec user, 0.000000 sec system ; cpu time (gc) 0.128008 sec user, 0.000000 sec system ; cpu time (total) 0.144009 sec user, 0.000000 sec system ; real time 0.149153 sec ; space allocation: ; 0 cons cells, 48,000,000 other bytes, 0 static bytes

 simple-stringに限定してベタベタに書くと、CL:CONCATENATEと比較して約3倍、string+と比較して約10倍位速くはできるようです。

 以上の結果からすると、どうも比較するものが間違っている気がしてきたので、様々な型のオブジェクトを文字列として連結する方向で比較してみます。

(time 
 (dotimes (i 1000000) 
   (with-output-to-string (out)
     (dolist (obj '("a" #\b |c| 1 (2 3)))
       (princ obj out)))))
; cpu time (non-gc) 11.752734 sec user, 0.000000 sec system
; cpu time (gc)     0.276017 sec user, 0.000000 sec system
; cpu time (total)  12.028751 sec user, 0.000000 sec system
; real time  12.056454 sec
; space allocation:
;  19,000,245 cons cells, 64,015,600 other bytes, 0 static bytes

(time (dotimes (i 1000000) (format nil "~{~A~}" '("a" #\b |c| 1 (2 3))))) ; cpu time (non-gc) 8.152510 sec user, 0.004000 sec system ; cpu time (gc) 0.352022 sec user, 0.004001 sec system ; cpu time (total) 8.504532 sec user, 0.008001 sec system ; real time 8.533479 sec ; space allocation: ; 14,000,126 cons cells, 64,010,656 other bytes, 0 static bytes

 CL:WITH-OUTPUT-TO-STRINGの場合と比較して約70倍、CL:FORMATと比較して約45倍string+の方が高速なようです。
使い勝手もstring+の方が良さそうなので、比較の対象としては、CL:FORMATや、CL:WITH-OUTPUT-TO-STRINGになりそうです。

まとめ

 今回は、util.stringを紹介してみました。
util.stringのような関数は、最近のLLには備わっていたりするので、速度よりは簡便さを優先して設計されたものなのかもな、と思ったりです。

comments powered by Disqus