LISPUSER

LISPMEMOQ: How can you tell when you've reached Lisp Enlightenment?
A: The parentheses disappear. -- Anonymous

(top)  (memo)  (rss)

Common Lisp による日常作業 CSV ファイルを読む (read-line, read-line-into, simple-stream-read-line とか)

以前のエントリ 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 vs 大量のデータ

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 は読み取ったバイト数と、読み取りが完了した理由を返します。

  • NIL => 改行があったから
  • :SHORT => バッファを全部埋めてしまったから
  • :EOF => ファイルの終端

典型的な 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

(top)  (memo)  (rss)