以前のエントリ CSV ファイルを読むコード で、ちょろっと
いかにも Scheme なコードなのでループと状態マシンに書き直すとかの高速化の余地がありますね。
今迄ちっこいファイルしか読んでなかったので、ちょっとメモリ使用量が多いなー。 まぁ、Gauche と違って immutable な文字列じゃないんで共有とかできないから効率わるいんじゃろ。 などと目を背けていたのですが、ある程度の規模の CSV を読んだら途端に性能問題が。うがぁ。
簡単に体感できる量だと 20MB 程度のデータを読み書きしてみればわかります。
(use text.csv)
(length
(call-with-input-file "KEN_ALL.utf8.CSV"
(cut port->list (make-csv-reader #\,) <>)))
Gauche 0.8.12 だとこんな感じ。
% time gosh test_csv.scm 121941 gosh csv.scm 25.85s user 1.92s system 82% cpu 33.606 total
Ruby 1.9.0 だとこんな感じ。
% time ruby -rcsv -e 'n=0;CSV.open("KEN_ALL.utf8.CSV","rb"){|row|n+=1;};puts n;'
121941
ruby -rcsv -e 'n=0;CSV.open("KEN_ALL.utf8.CSV","rb"){|row|n+=1;};puts n;' 57.90s user 0.24s system 99% cpu 58.361 total
Perl 5.8.8
% time perl -MText::CSV -MIO::File -e '$c=Text::CSV->new({binary=>1});my $io=IO::File->new("<KEN_ALL.utf8.CSV");while(my $row=$c->getline($io)){push @lst, $row;};print scalar @lst,"\n"';
121941
perl -MText::CSV -MIO::File -e 0.11s user 2.01s system 99% cpu 2.124 total
% time perl -MText::CSV_XS -MIO::File -e '$c=Text::CSV_XS->new({binary=>1});my $io=IO::File->new("<KEN_ALL.utf8.CSV");while(my $row=$c->getline($io)){push @lst, $row;};print scalar @lst,"\n"';
121941
perl -MText::CSV_XS -MIO::File -e 0.07s user 2.02s system 100% cpu 2.082 total
Python 2.4.4
% time python test_csv.py 121941 python bench_csv.py 0.39s user 0.83s system 99% cpu 1.223 total
こんな感じ。Perl の Text::CSV_XS モジュールと Python の csv モジュールは C で書かれた処理を抱えています。 読んでないけど、状態マシンを使った実装なんでしょう。 じゃあ Perl 使えよと言われそうなんですが、 Perl の CSV_XS モジュールは改行を含むエントリに対応していませんので、今回は対象外でした。
Python 速いな〜。実は Python で書き直すというのも手軽な選択肢だったか。 実は性能測定したのがこの記事書いてる今なもんで。まぁ SLIME から抜けるのが面倒だったし…。
CLISP
CL-USER> (time (length (text.csv:parse-csv-file "KEN_ALL.utf8.CSV" :external-format charset:utf-8)))
うがぁぁぁぁ遅いぃぃぃぃ。1 分ほど待ったところで挫折。 Common Lisp で状態マシンを使った実装に変更したところ、以下のようになりました。
[CLISP] CL-USER> (time (length (setf lst (text.csv:parse-csv-file "KEN_ALL.utf8.CSV" :external-format charset:utf-8)))) Real time: 7.389423f0 sec. Run time: 7.048441f0 sec. Space: 61589352 Bytes GC: 2, GC time: 0.272016f0 sec. 121941 CL-USER> (time (length (text.csv:parse-csv-file "KEN_ALL.utf8.CSV" :external-format :utf-8))) Evaluation took: 1.976 seconds of real time 1.380086 seconds of user run time 0.592037 seconds of system run time [Run times include 0.612 seconds GC run time.] 0 calls to %EVAL 0 page faults and 80,658,424 bytes consed. 121941
まぁ、許容範囲内かなー。SBCL はなかなか頑張ってますね。 Perl や Python に比べてイケてませんが、Pure Lisp のみでこのくらいまでいけます。C には勝てないですが、C を使うのは辛いので。
Lisp の read-line はストリームから一行読み出す標準的な API ですが、実は大容量のデータに対してはパフォーマンス問題をおこしやすい関数です。 呼ぶたびに一行分の文字列を返すのですが、「read-line は毎回新しく文字列を作る」という挙動になります。これは大量の行を読むと大量のごみを 作ってしまうという事になります。
20MB 程度のデータを読んで行数をカウントするとこのようになります。
CL-USER> (time
(with-open-file (f "KEN_ALL.utf8.CSV" :direction :input :external-format :utf-8)
(loop for line = (read-line f nil f)
until (eq line f)
count line)))
Evaluation took:
0.539 seconds of real time
0.496031 seconds of user run time
0.036002 seconds of system run time
[Run times include 0.036 seconds GC run time.]
0 calls to %EVAL
0 page faults and
54,060,336 bytes consed.
121941
ワオ!! 盛大にメモリ消費してますね。C ならどう書くでしょうか？固定長のバッファを容易して fgets で読み取ってカウントする、とかが定番ですから、 消費するメモリ量はバッファサイズ（一行分）のみ、というのが普通です。
Common Lisp では read-sequence という関数が良くつかわれます。これはあらかじめ用意したバッファにデータを読み込んで処理するための関数です。 これを使うと効率が大幅にアップします。ただし「行」という単位では処理してくれないので、自分で改行を数える必要がありますが…。
CL-USER> (time
(with-open-file (f "KEN_ALL.utf8.CSV" :direction :input :external-format :utf-8)
(loop with buffer = (make-string 4096 :element-type 'character :initial-element #\NULL)
for bytes = (read-sequence buffer f)
until (= bytes 0)
sum (count #\Newline buffer :end bytes))))
Evaluation took:
0.941 seconds of real time
0.924057 seconds of user run time
0.012 seconds of system run time
0 calls to %EVAL
0 page faults and
286,736 bytes consed.
121941
メモリ使用量が read-line 版に比べて 54,060,336 => 286,736 と激減しています。当然ですが、入力行数が増えると read-line 版は GC が増えてゆきますが、 この read-sequence 版をつかうと消費メモリは入力データの行数に関係なく固定量で済みます。
さらに、AllegroCL や xyzzy といった一部の処理系はもっと便利な関数を備えています。read-line-into という API で、固定長のバッファを利用しつつ、 「行」単位で処理できる、丁度 C の fgets に対応する関数です。
;; 普通の READ-LINE
CL-USER> (time
(with-open-file (f "KEN_ALL.utf8.CSV" :direction :input :external-format :utf-8)
(loop for line = (read-line f nil f)
until (eq line f)
count line)))
; cpu time (non-gc) 1,607 msec user, 31 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 1,607 msec user, 31 msec system
; real time 1,864 msec
; space allocation:
; 2,561,207 cons cells, 36,107,440 other bytes, 0 static bytes
121941
;; READ-LINE-INTO を使った場合
CL-USER> (time
(with-open-file (f "KEN_ALL.utf8.CSV" :direction :input :external-format :utf-8)
(loop with buffer = (make-string 4096 :element-type 'character :initial-element #\NULL)
for bytes = (read-line-into buffer f nil f)
until (eq bytes f)
count buffer)))
; cpu time (non-gc) 1,966 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 1,966 msec user, 0 msec system
; real time 1,881 msec
; space allocation:
; 2,683,188 cons cells, 12,698,056 other bytes, 0 static bytes
121941
ここでは cons セルは使っていないので、使用メモリの other bytes を見てください。大幅に減っている事がわかります。 これは read-line-into が副作用で固定長のバッファに文字を書き込んでゆくからです。 (ちなみに、cons cell を大量に消費しているのはインタプリタで実行しているためです。関数化してから測ればよかったですね)
read-line-into は読み取ったバイト数と、読み取りが完了した理由を返します。
典型的な read-line-into のコードは以下のようなものになります。
CL-USER> (time
(with-open-file (f "KEN_ALL.utf8.CSV" :direction :input :external-format :utf-8)
(let ((buffer (make-string 4096 :element-type 'character :initial-element #\NULL))
(n 0))
(loop
(multiple-value-bind (store stop)
(read-line-into buffer f nil)
(when (eq stop :eof)
(return-from nil n))
(incf n))))))
; cpu time (non-gc) 2,153 msec user, 31 msec system
; cpu time (gc) 15 msec user, 0 msec system
; cpu time (total) 2,168 msec user, 31 msec system
; real time 2,046 msec
; space allocation:
; 4,268,138 cons cells, 4,893,984 other bytes, 0 static bytes
121941
もちろん、じゃあ read-line 要らないじゃん？と考えるのは早計です。これは同じバッファをどんどん書きかえながら 使ってゆく C のようなスタイルなので、一行分の要素を集めていってリストにしたい、といった用途には以前 read-line がベストです。
さらに、read-line-into を使う場合に考慮しなければならないのが :SHORT が返る場合、つまりバッファサイズが 一行のサイズより小さい場合です。以下のように、一行のサイズを 1024 => 100 に変更してみます。 データ中には 100 文字を超える行が含まれているものとします。
CL-USER> (time
(with-open-file (f "KEN_ALL.utf8.CSV" :direction :input :external-format :utf-8)
(let ((buffer (make-string 100 :element-type 'character :initial-element #\NULL))
(n 0))
(loop
(multiple-value-bind (store stop)
(read-line-into buffer f nil)
(when (eq stop :eof)
(return-from nil n))
(incf n))))))
; cpu time (non-gc) 2,184 msec user, 31 msec system
; cpu time (gc) 15 msec user, 0 msec system
; cpu time (total) 2,199 msec user, 31 msec system
; real time 2,164 msec
; space allocation:
; 4,501,693 cons cells, 5,152,816 other bytes, 0 static bytes
128614 <= 結果がちがう!!
見事に不正な結果が得られました。:-p
では、:short を扱かうコードを追加しましょう。この礼は単なる行数カウントですので、単に :short を無視するだけです。
CL-USER> (time
(with-open-file (f "KEN_ALL.utf8.CSV" :direction :input :external-format :utf-8)
(let ((buffer (make-string 100 :element-type 'character :initial-element #\NULL))
(n 0))
(loop
(multiple-value-bind (store stop)
(read-line-into buffer f nil)
(when (eq stop :eof)
(return-from nil n))
(unless (eq stop :short)
(incf n)))))))
; cpu time (non-gc) 2,590 msec user, 16 msec system
; cpu time (gc) 31 msec user, 0 msec system
; cpu time (total) 2,621 msec user, 16 msec system
; real time 2,537 msec
; space allocation:
; 5,734,449 cons cells, 5,153,008 other bytes, 0 static bytes
121941
CL-USER>
実際 CSV の解析等のまともな処理をしようとすると、もっとちゃんと扱う必要がありますが、基本はこんな感じです。
最後に、AllegroCL が備えている simple-stream-read-line を説明します。 これは read-line の気軽さと read-line-into の効率の良さを兼備えた関数です。 バッファを指定して、一行がバッファサイズ以下ならバッファそのものを返します（read-line-into の利点）、バッファサイズを超えた場合には 新しく文字列を確保して返します(read-line の気軽さ)。つまり、read-line-into より効率は多少おちるかわりに :short を気にせずに 「行」単位の処理を簡単に行う事ができます。
CL-USER> (time
(with-open-file (f "KEN_ALL.utf8.CSV" :direction :input :external-format :utf-8)
(let ((buffer (make-string 1024 :element-type 'character :initial-element #\NULL))
(n 0) (m 0))
(loop
(multiple-value-bind (line stop end)
(simple-stream-read-line f nil f buffer)
(when (eq line f)
(return-from nil (values n m)))
(incf n)
(when (eq line buffer) (incf m))))))) ;; バッファが再利用されている回数をカウント
; cpu time (non-gc) 1,981 msec user, 47 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 1,981 msec user, 47 msec system
; real time 2,774 msec
; space allocation:
; 7,194,743 cons cells, 4,888,128 other bytes, 0 static bytes
121941
121941
CL-USER> (time
(with-open-file (f "KEN_ALL.utf8.CSV" :direction :input :external-format :utf-8)
(let ((buffer (make-string 100 :element-type 'character :initial-element #\NULL))
(n 0) (m 0))
(loop
(multiple-value-bind (line stop end)
(simple-stream-read-line f nil f buffer)
(when (eq line f)
(return-from nil (values n m)))
(incf n)
(when (eq line buffer) (incf m))))))) ;; バッファが再利用されている回数をカウント
; cpu time (non-gc) 2,901 msec user, 94 msec system
; cpu time (gc) 32 msec user, 0 msec system
; cpu time (total) 2,933 msec user, 94 msec system
; real time 2,811 msec
; space allocation:
; 7,141,359 cons cells, 6,506,392 other bytes, 0 static bytes
121941
115268
CL-USER> (time
(with-open-file (f "KEN_ALL.utf8.CSV" :direction :input :external-format :utf-8)
(let ((buffer (make-string 50 :element-type 'character :initial-element #\NULL))
(n 0) (m 0))
(loop
(multiple-value-bind (line stop end)
(simple-stream-read-line f nil f buffer)
(when (eq line f)
(return-from nil (values n m)))
(incf n)
(when (eq line buffer) (incf m))))))) ;; バッファが再利用されている回数をカウント
; cpu time (non-gc) 2,512 msec user, 46 msec system
; cpu time (gc) 16 msec user, 0 msec system
; cpu time (total) 2,528 msec user, 46 msec system
; real time 2,495 msec
; space allocation:
; 6,219,216 cons cells, 28,304,008 other bytes, 0 static bytes
121941
0
例に示したように、バッファサイズが十分な場合には read-line-into 並の効率が、サイズが足りない場合は read-line 並の性能に落ちてしまう事が確認できます。
(つづく)
posted: 2007/12/14 00:54 | permanent link to this entry | Tags: LISP