新・日々録 by TRASH BOX@Eel このページをアンテナに追加 RSSフィード

2015-11-02

8つの言語でテキストフィルタを書き比べた

※2015/11/15追記:現段階では8言語から12言語に増えている。

その昔 id:eel3:20120129:1327845759 なんてことをやったのだが、性懲りもなくまた同じようなことをやってみた。

作ったものはこちらに置いてある。

どんなツールを作ったかというと、テキストファイルの先頭から指定したbyte数(または文字数)だけ出力し、改行を出力し、先頭から1byte(または1文字)シフトした位置から同じように出力し、改行を出力し、再びシフトし――ということをファイル終端まで繰り返すコンソールアプリだ。例えばこんな感じ。

$ echo -n abcd | hcasl -n 1
a
b
c
d
$ echo -n abcd | hcasl -n 2
ab
bc
cd
$ echo -n abcd | hcasl -n 3
abc
bcd
$ echo -n abcd | hcasl -n 4
abcd
$ echo -n abcd | hcasl -n 5
$ _

byte数でシフトするのがhcaslで、文字数でシフトするのがhcasl-charとなる。

実装する上での約束事

対象プログラミング言語

次の言語で書いてみた。

  1. C言語(C89)
  2. C++11
  3. Go 1.4.2, 1.5.1
  4. Perl 5.14.2, 5.22.0
  5. Python 2.7.3, 2.7.10
  6. Ruby 1.9.3p0, 2.2.2p95
  7. Gauche 0.9.4
  8. Tcl 8.6.4-5

hcaslの元ネタとして、2007年にC言語で実装したmakerecというツールが存在する。makerecの仕様をより汎用的にしたのが、hcaslとhcasl-charになる。

その流れて、再びC言語で書くことは決めていた。ただ「FIFO(キュー)を自前で実装するのは面倒だ」ということで、比較対象としてC言語よりも標準ライブラリが充実しているC++でも実装することにした。

Go言語は、C++との比較対象であり、Pythonあたりの軽量プログラミング言語スクリプト言語)との比較対象でもある。異なる2つの世界の言語から比較対象とされるのも珍しい。

PerlPythonRubyは、テキストフィルタをさくっと書くのに使う人が多そうな言語からの選択。実際、私が最初にhcaslを書いた言語はRubyだ。

Gaucheはテキスト処理仲間として追加。あと、SchemeというかLispに何となく憧れを感じるプログラミング中二病患者だから、という点もある。

なおTclはレギュレーション違反(後述)のため、参考出品扱いだ。

言語選択のポイント

使用する機能に縛りを入れているので、言語を選択する上で、次の点がポイントとなってくる:

  • オプション引数を解析するライブラリ等を持っていること。
    • 自前で解析したくないから。
  • 入力ストリームから比較的簡単に1byte(または1文字)ずつreadできること。
    • 入力として「改行を含まない数百MBのファイル」とかを想定すると、1行ずつreadするしかない言語はNG。

残念ながら、C言語C++の標準ライブラリには、オプション解析用のルーチンがない。そこでgetopt(3)を使っている*2。一応、POSIX関数だから、勘弁してほしい。代わりにbasename(3)は自作している。

Tclがレギュレーション違反なのは、オプション引数の解析にStandard Tcl Library(Tcllib)のcmdlineを使っているため。名前から受ける印象とは異なり、Tcl標準の機能ではない。

コード規模の比較

リポジトリのソースの行数を単純に数えると、こんな感じ。

c/hcasl.c569
cpp/hcasl.cpp257
go/hcasl.go122
go/hcasl-char.go120
perl/hcasl100
python/2/hcasl67
ruby/hcasl45
ruby/hcasl-char45
scheme/gauche/hcasl75
scheme/gauche/hcasl-char74
tcl/hcasl-char80
tcl/hcasl-char-recur73

もっともC言語C++のソースにはキッチリとコメントを書いているのに対して、他のソースではろくなコメントを書いてない。これは不公平なので、不要なコメント行を削り、2行以上連続する空白行を1行に圧縮した上で、再度行数を数えると、こんな感じ。

c/hcasl.c359
cpp/hcasl.cpp179
go/hcasl.go108
go/hcasl-char.go106
perl/hcasl88
python/2/hcasl64
ruby/hcasl42
ruby/hcasl-char42
scheme/gauche/hcasl72
scheme/gauche/hcasl-char71
tcl/hcasl-char77
tcl/hcasl-char-recur70

あとC言語C++で実装した関数my_basename()は過剰品質なので、簡易実装(インタフェース部分を除くと12行)に置きかえると、こんな感じ。

c/hcasl.c288
cpp/hcasl.cpp151

さて、最も短い行数同士で比較するとして――やはりC言語が最も行数が多い。何しろFIFO(キュー)を自前で実装せざるをえなかったから。C言語の標準ライブラリは貧弱だ。自称Cプログラマとして、C言語プログラミング入門するのは止めた方がよいと忠告させてもらおう。

C++C言語よりも短くなったが、それでも行数は多め。充実しているとはいえC++の標準ライブラリはプリミティブだった――というよりは、今回は何というか、要所要所で微妙に冗長な書き方になり、それが積み重なった結果のような気がする(まあ実際のところ、C++の標準ライブラリはプリミティブ気味なのだが)。

Go言語は、やはり要所要所で微妙に冗長な書き方になった。それでもC++よりはスリムだし、書きやすい。

Perlはさらに短くなった。なるほど、C言語シェルスクリプトの時代にPerlが出た際のインパクトは大きかったのだろう――と想像できる程度には短くなったが、しかし後発のPythonRubyほどではない。

Pythonも短くなったが、fileinputにfile.read()と同様の機能が用意されていたら、もっと短くなったと思う。これがなかったために、入力ファイルを順番に開いて処理を実行するコードを書かなくてはならなくなった。

最も短かったのはRuby。勝因はARGFの存在だろう。

GauchePerlPythonの中間ぐらい。もっともSchemeの素人が書いたコードなので冗長かもしれない。パラダイムの差異に悩んだが、便利なライブラリ機能が揃っているので、意外とやりやすかった。

Tclで普通に書くとPerlGaucheの間で、Gaucheより少し長い程度だった。書いていて、どうにも要所要所で微妙に冗長な書き方になった。少々Tclらしからぬ書き方をすることで、もう少し短くなった。

実行速度の比較(ただし不正確)

試しに手元のCygwin 64bit(Windows 7 64bit版上)で実行時間を計測してみた。計測方法は、安直にこんな感じで。3回連続で実行した3回目の値を見てみた。

$ time perl -e 'print("a" x 1000000)' | ./hcasl >/dev/null

計測したのだが、以下の通り処理系出自カオスなため、意味のあるデータではないと思う。とりあえずtime(1)のrealの値を書き出す。

c/hcasl.c0m40.763sTDM64-GCCビルドした64bitバイナリ最適化なし
cpp/hcasl.cpp0m46.847sTDM64-GCCビルドした64bitバイナリ最適化なし
go/hcasl.go0m3.063sGo 1.5.1 Windows 64bit版でビルドしたバイナリ
go/hcasl-char.go0m9.856sGo 1.5.1 Windows 64bit版でビルドしたバイナリ
perl/hcasl0m1.763sCygwinPerl 5.22.0
python/2/hcasl0m4.399sCygwinPython 2.7.10
ruby/hcasl0m2.730sCygwinRuby 2.2.2p95
ruby/hcasl-char0m2.746sCygwinRuby 2.2.2p95
scheme/gauche/hcasl0m9.469sGauche 0.9.4 公式Windowsバイナリ
scheme/gauche/hcasl-char0m5.819sGauche 0.9.4 公式Windowsバイナリ
tcl/hcasl-char0m2.012stclsh 8.6.4-5 tombert版64bitバイナリ
tcl/hcasl-char-recur0m2.980stclsh 8.6.4-5 tombert版64bitバイナリ

C言語C++の実装が妙に遅い。入出力が無茶苦茶非効率な実装ではあるが、それ以外の外部要因があるような気がしてならない。実際、Celeron 847上で動かしているUbuntu 12.04.5 LTS 32bit上のGCCC言語版をビルドして実行すると、概ね0.5秒程度だ。うーん、この遅さは何だろう?

他の言語による実装を見ると、入力だけでなく出力も1byte(1文字)単位であるコードは遅い。例えばGo言語のhcasl-charPythonのhcasl、Gaucheのhcaslは、どれも1byte(1文字)単位で出力している。

Gaucheのhcasl-charは、1文字読む度にリストを2つ生成していたりと非効率な実装なのだが、それにしては意外と速い。どう考えても処理系のおかげだろう。

Tclは末尾再帰したら遅くなった。とはいえ全体的にはそれほど遅くないのかもしれない。

1byteか1文字か

(特定の文字エンコーディング縛りだったりするが)標準の機能の範囲で1byteではなく1文字の読み書きが可能だったのはGo言語、RubyGauche、Tclの4つ。

Go言語はUTF-8縛りに徹したためか、UTF-8であるなら1文字単位でreadとwriteができた。まあ、よく考えれば、Go言語の設計・開発を進めている面々は、Plan 9の研究開発にてUTF-8を考案した面々でもあるんだよなあ。

RubyGaucheは……マルチバイト対応の賜物? 少なくともja_JP.UTF-8の環境でUTF-8のテキストを扱う分には、1文字単位でのreadとwriteは問題ない。

Tclは、手元の環境では1文字単位での読み込みしかできなかった。チャネルバイナリモードにすれば、byte単位でreadできるのではないかと思うのだが、肝心のバイナリモードにできない。何だコレは。

その他、雑感

自分はCプログラマで、C言語のコードを書くことで生計を立てているし、世の中にはC言語でしか書けないソフトウェアもあれば、どうにもならない技術的理由でC言語を選択せざるをえないことがあることも知っている。

知ってる上で言うが、そういった特別な事情がないのなら、もう新しいソフトウェアC言語で書くべきではないよね。開発も保守も、時間的コストが掛かりすぎる。

――という主張は、hcaslの言語ごとのコード規模を比較すると「一理あるな」と思っていただけるかと思う。Cプログラマだけど、C言語の前にC++で実装したし、更に言えば真っ先にRubyで実装した――という程度には面倒で逃げ回ってたのよ、C言語版の実装から。

C++は(暗黒面に足を踏み入れなければ)C言語より実装が楽なのだが、やはり冗長ではある。標準ライブラリも、コンテナのデータ構造が多種多様なあたり、システム・プログラミングか、アプリケーションのコアや特定のコンポーネントをガリガリ書く場合向きに感じる。それってつまり、開発するソフトウェア特性に合わせて適切なデータ構造を選択しましょう、ということだよね。

Go言語はC++D言語・Rustと比較されることもあれば、Python(たまにRuby)と比較されることもある、不思議なポジションの言語だが*3、本質的にはシステム・プログラミング向きの言語だろう。それゆえの、記述の(若干の)冗長さではないか。あとgofmtの存在など、Pythonほどではないがスタイルを強制される部分がある。

PerlPythonRubyはテキスト処理が得意なこともあり、テキストフィルタを書きやすい。この3つ、やはりコードを書いていると違いを感じる。Perlは比較的伝統的な「命令*4」を呼び出すスタイルで記述する*5上に、何となくC言語っぽいような、awkのような、sedのような、シェルスクリプトのような感じ。Rubyではオブジェクト主体となる記述となるが、時々Perlの影響が見られる。Pythonはlazyなスタイルが許されず、整然と記述する必要がある。個人的には、PythonにはPerlの影響が見られない気がする。

Gaucheはテキストフィルタを書くのに便利なライブラリが揃っている。ただ、私のような手続き型で副作用バリバリな世界の住人の場合、若干の工夫が必要となる。それは、状態を変化させるのではなく、「次の状態」を保持するリストなり何なりを新たに生成する、ということ。実際に、他の言語ではFIFO代わりのデータ構造を操作して状態を変更しているが、Gauche版では新しい状態を保持したリストを生成することで対応している。

Tclは進化していた。例外処理用のtryや、末尾呼び出しの最適化用のtailcallは、どちらもTcl 8.6で追加されたコマンドだ。というかややClojure風とはいえスタックを気にせず末尾再帰できるようになるとは思わなかった。Tclは制御構文を含めて全てコマンドで、どのコマンドも値を返すので、頑張れば「副作用バリバリのLisp」風に記述できなくもないかもしれない。

まとめ

だれか、まともな環境上で実行速度を計測・比較してくれないだろうか? 処理系を用意するのが面倒だから……。

2015/11/07追記

この文書を公開した後に、リポジトリに以下の変更を加えた。

  • C言語版・C++版の実装がWindows上で非常に遅かった問題に対応。
  • はてぶのコメントを元に、Perl 5版の実装を書き換えた。
  • Python版にて、入力ファイルを開けなかった際にエラーコードを返すように修正。
  • Ruby版にて、入力ファイルを開けなかった際に、次の入力ファイルの処理に移るように修正。
  • bash版の実装を追加。

bash版の実装は2つある。hcaslは、bash固有の機能を結構使って実装している。一方のhcasl-posix-likeは、なるべくPOSIXの範囲の機能を使うように実装している。どちらも1byteずつ読み込むためにコマンドreadのオプションnを使用しているが、これはbashの独自拡張機能だ。本当は全てPOSIXの範囲内で実装してみたかったが、1byte読み込むのにこの方法しか思い浮かばなかった。

C言語C++の実装は行数が増えたが、誰も興味ないだろうから*6省略するとして、その他の実装での行数の変化を書き記す。

まず、行数を単純に数えた場合。

perl/hcasl100 84
python/2/hcasl67 71
ruby/hcasl45 54
ruby/hcasl-char45 54
shell/bash/hcasl85
shell/bash/hcasl-posix-like83

次に、不要なコメント行を削り、2行以上連続する空白行を1行に圧縮した上での行数。

perl/hcasl88 72
python/2/hcasl64 68
ruby/hcasl42 51
ruby/hcasl-char42 51
shell/bash/hcasl78
shell/bash/hcasl-posix-like76

Perl版は結構短くなった。コメント削除版での行数はTcl版(普通に実装したもの)よりも短く、Gauche版と同じくらいになった。

Python版は微増した。それでもPerl版よりわずかに短い。

Ruby版は結構行数が増えたものの、依然として最も短い。

bash版は、Perlなどのスクリプト言語による実装よりも少し多い程度の行数になった。

行数の次に、実行速度を書き記す。先に書いたが、意味のあるデータではないはず。

c/hcasl.c0m40.763s 0m2.516sTDM64-GCCビルドした64bitバイナリ最適化なし
cpp/hcasl.cpp0m46.847s 0m2.629sTDM64-GCCビルドした64bitバイナリ最適化なし
shell/bash/hcasl0m34.554sCygwinbash 4.3.39(2)-release
shell/bash/hcasl-posix-like0m28.907sCygwinbash 4.3.39(2)-release

C言語版とC++版は、ようやく本来の値を計測できた、という感じだ。

bash版は、やはり遅かった。単純には比較できないものの、同じようにCygwin処理系を使用しているPerlPythonRuby版よりも遥かに遅い点は、参考になるだろう。hcaslとhcasl-posix-likeで計測値に差異がある点は、while readループ内にifによる条件分岐があるか否かに起因すると思われる。

2015/11/15追記

Gauche開発者のShiro KawaiさんによるGauche版の別解を取り込んだ。ありがとうございます)

リポジトリに以下の変更を加えた。

  • bash版を改造して、スクリプト自体のファイル名がhcasl-charで始まっていたならhcasl-charとして振る舞うようにした。
  • D言語版の実装を追加。
  • Groovy版の実装を追加。
  • sh版(Bourne shell版)の実装を追加。

bash版は、スクリプト自身のファイル名が正規表現「^hcasl-char」にマッチしない場合にのみ環境変数LC_ALLLANGCを設定するようにした。

bashの組み込みコマンドreadはロケールの影響を受ける。「read -n 1 -r c」でUTF-8の「あ」を読み込んだとき、ロケールがja_JP.UTF-8なら$cの中身は「あ」となる。一方、ロケールがCなら$cの中身は「あ」を構成する3byteのうちの1byteとなる。

この挙動を利用して、スクリプト名がhcaslならロケールをCにすることでreadで1byte読み込むようにし、hcasl-charなら実行環境のロケールをそのまま使うことでロケールに応じた1文字を読み込むようにした。典型的な使い方として「hcaslのインストール後に、hcasl-charという名前でシンボリックリンクを張る」というものを想定している。

D言語版は、C++版やGo言語版との比較用に実装した。D言語で「hello, world」以外の何かを実装するのは初めてだが、出自出自だけにC言語C++に慣れている人にとって割と書きやすい言語だ。個人的には、Go言語よりもD言語のほうがシンタックスを含めてC・C++に近いと思う。

Groovy版を実装した理由は特にない。あえて書くならば、JVMで実行する言語のうち、私でも知っている有名どころで、コンパイルせずにソースファイルをスクリプトとして実行できて、かつ「言語選択のポイント」で挙げた「オプション引数を解析するライブラリ等を持っていること」(標準ライブラリ処理系付属のライブラリ縛り)に該当する言語として、Groovyしか思いつかなかった。

sh版は、bash版のhcasl-posix-likeのリベンジだ。どうしてもPOSIXの範囲で実現してみたくて、頑張ってみた。その結果、while readループが消えて高速化されるという、当初は全く想定していなかったものができあがった。

ではソースの行数を記す。まず、行数を単純に数えた場合。

d/hcasl.d96
groovy/hcasl87
groovy/hcasl-char91
shell/bash/hcasl85 87
shell/bash/hcasl-posix-like83 85
shell/sh/hcasl89

次に、不要なコメント行を削り、2行以上連続する空白行を1行に圧縮した上での行数。

d/hcasl.d85
groovy/hcasl85
groovy/hcasl-char89
shell/bash/hcasl78 80
shell/bash/hcasl-posix-like76 78
shell/sh/hcasl82

D言語版は、C言語C++・Go言語版よりも短い。これら3言語とスクリプト言語による実装の中間ぐらいの大きさだ。

Groovy版はD言語版よりわずかに大きい程度になった。個人的には「思ったよりも短くならなかった」という印象を受けた(書いた本人がGroovy素人で不慣れなこともあるだろうが)。確かにJavaで書くよりは簡潔で短いのだろうが、もう少しスクリプト言語寄りの短さになることを期待していたのだ。

bash版はそれぞれ2行ずつ増えている。

sh版はbash版とほぼ同じ大きさだ。ソースコードの4分の3がbash版のhcasl-posix-likeとほぼ同一で、残り4分の1の中核部分を書き換えたのだが、長さ的にはさほど変化しなかった。

行数の次に、実行速度を書き記す。

d/hcasl.d0m1.685sDMD32 2.069.0でビルドした32bitバイナリ最適化なし
groovy/hcasl0m5.869sGroovy 2.4.5 + Java 1.8.0_66 64bit
groovy/hcasl-char0m4.271sGroovy 2.4.5 + Java 1.8.0_66 64bit
shell/bash/hcasl0m34.554s 0m34.507sCygwinbash 4.3.39(2)-release
shell/bash/hcasl (hcasl-char)0m40.139sCygwinbash 4.3.39(2)-release
shell/bash/hcasl-posix-like0m28.907s 0m28.642sCygwinbash 4.3.39(2)-release
shell/bash/hcasl-posix-like (hcasl-char-posix-like)0m32.370sCygwinbash 4.3.39(2)-release
shell/sh/hcasl0m6.474sCygwinbash 4.3.39(2)-release + GNU Awk 4.1.3

D言語版は、手元の環境でネイティブな実行ファイルを吐かせた実装(C言語C++D言語・Go言語)の中では、最も速かった。

Groovy版は、スクリプトが実行開始されるまでに時間がかかっているようだ。例えば、何も入力しない(標準入力を/dev/nullにする)ケースでtime(1)のreal値を計測したところ、次の結果になった。

time groovy ./hcasl </dev/null/dev/null0m2.140s
time groovy ./hcasl-char </dev/null0m2.218s

bash版は、普通に実行する分には以前と変わらなかった。hcasl-charとして実行した場合は遅くなっている。シェルスクリプト高速化ネタで「LANG=Cでsort(1)する」というものがあるが、なるほど、文字列を扱う場合に「単なるバイト列」ではなく「ロケールに準じた1文字」として扱おうとすると、その分のコストがかさむようだ。

sh版はbash版よりも高速になった。シェルスクリプトでループするのを止めて、パイプでawk(1)に流し込むように変更した影響だろう。もっともawk(1)単体では、少なくともPOSIXの範囲では、1byte/1文字ずつ入力を読み込む手段がない。前準備として、複数の外部コマンドを駆使してawk(1)でも容易に扱える形式に変換していて、その分のオーバヘッドが発生している。

sh版の実行速度はawk(1)の速さで決まる。例えば手元のUbuntu 12.04 LTS 32bitでは、awk(1)の実体がgawk(1)ではなくmawk(1)である場合の方が遥かに高速になる。

*1:「エラーメッセージを表示する」という挙動は、順守する必要がある。

*2:この影響で、WindowsではMinGWビルドするか、getopt(3)のコードをどこかから持ってきて一緒にビルドする必要がある。

*3C++D言語その他とはシステム・プログラミング繋がりで比較されるのだろう、という点は理解できる。PythonRubyとは……最近Webアプリケーションのバックエンドで使われるようになって、利用領域がかぶっているから?

*4:組み込み関数とサブルーチン。

*5:もちろん、オブジェクト指向プログラミングするなら話は別だ。しかし標準の機能を使う限りは……。

*6:既に行数が多いことが分かっているため。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証