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

2017-01-21

量産型プログラマとそれ以外のプログラマの違いはどこにあるか?

ふむ。

量産型プログラマを撲滅したい ? kuranuki ? Medium

最近、量産型プログラマに遭遇したのだが、彼らを観察しているうちに、量産型プログラマとそれ以外のプログラマとでは、次の点に違いが見られることに気づいた。

  1. ソースコード・ドキュメント・「『デバッガ上でのプログラムのふるまいや、テストデータを食わせた時の挙動』の観察から得られた知見」などから、対象システムについての一貫性のあるメンタルモデル/概念モデルを、頭の中に構築することができるか否か?
  2. 頭の中に構築したメンタルモデル/概念モデルが、実際のシステムと比較して、妥当なものであるか否か?
  3. 頭の中に構築したメンタルモデル/概念モデルが、実際のシステムのそれなりの範囲をカバーしているか否か?
  4. 頭の中に構築したメンタルモデル/概念モデルに基づいて、理路整然と議論や推測を行うことができるか否か?
  5. 頭の中に構築したメンタルモデル/概念モデルを、ソースコードやドキュメントという形態に変換出力できるか否か?

量産型プログラマ」と言われる人は、上記5項目の多く(時には全て)において、何かしらの問題を抱えているように見える。

例えば、先の記事のこのあたり:

ただ沢山のプログラムを書くだけの量産型プログラマだ。こういう人のプログラミングは、デバッグさせてみて、横で見てるとすぐにわかる。

まず、エラーメッセージを見ない。動かないってことは、どこがおかしいかわからない。パラメータを変えてみたり、手をいっぱい動かす。なんとなく勘で直そうとする。動いたから良いじゃないか、と考える。

量産型プログラマは、対象システムについてのメンタルモデル/概念モデルを構築しようとしないか、もしくは構築することができない。つまり、デバッグの時、先にメンタルモデル/概念モデルという明かりを灯すことなく、暗闇を手探りで突き進もうとする。だから、作業の進め方が行き当たりばったりで、見当違いの方向にフラフラと迷走していってしまうことが多い。

一方、量産型じゃないプログラマは、メンタルモデル/概念モデルを構築した上で、モデルに基づいて理路整然とデバッグしようとする。

例えば通信プログラムで、送信側が送ったデータと受信側で受け取ったデータとで一部が一致しない問題が起きたとする。量産型じゃないプログラマは、例えば:

――といったあたりにモニター(ログ出力やパケットキャプチャ)を仕込んで、問題を再現させて、ログやパケットキャプチャを解析して、どの時点でデータが変化しているか調べることで、バグがあると思われる箇所を絞り込もうとするかもしれない。

(仮に「送信側で、send処理を実行する直前の送信予定データ」の時点で意図せぬ値となっているなら、送信側にバグがある可能性が高いだろう。しかし「受信側で、recv処理を実行した直後の受信済みデータ」まで正しいなら、それ以降に受信側プログラムで行う処理のどこかでデータを壊している可能性が高いだろう。パケットキャプチャの段階で初めて値が壊れているなら、send/recv用のAPIの叩き方を間違えているとか、send/recv用のAPIを提供しているライブラリフレームワークバグがあるとか、いくつかの可能性が考えられるだろう)

すなわち、量産型じゃないプログラマは、その通信プログラムにおける大雑把なデータの流れを把握していて、そのデータフローに基づいて、理路整然と、チェックポイントとして適切な箇所を判断してモニターを仕込もうとするだろう。

これが量産型プログラマとなると、こういった切り分けを一切せずに「送信データと受信データとで、データの一部が一致しないです。どう頑張っても不一致となるんです」という報告を上げる。「いや、そこは問題の切り分けをしようよ……(『どう頑張っても』って、念力じゃバグは直らないよ)」と、量産型じゃないプログラマはため息をつくことになる。

量産型プログラマは、対象システムについて「メンタルモデル/概念モデルを構築し、活用する能力」に欠けている。量産型じゃないプログラマは、メンタルモデル/概念モデルを構築し、活用することで、システムの設計・実装・デバッグなどを進めていく。

(この点は、諸刃の剣でもある。要するに、思い込みに起因する失敗を起こす可能性があるのだ)

私が個人的に興味を抱いているのは、メンタルモデル/概念モデルをめぐる量産型プログラマとそれ以外のプログラマ差異が、どこまで教育で補完できるか、という点だ。

ベテランでも、未経験のプログラミング言語フレームワークで書かれたソースコードに直面した場合には、対象システムについてのメンタルモデル/概念モデルを構築するのに苦労するし、頭の中で構築したイメージをソースコード化するのに難儀するものだ。技術面の知識の有無がモデル構築絡みの作業パフォーマンスに影響を与えるわけだが、この辺は教育でカバーできる余地があるだろう。

では「メンタルモデル/概念モデルを構築し、活用する能力」そのものについてはどうだろうか? この方面の教育や訓練については、まだまだ手探り状態というか、未開の大地であるような気がする。コンピュテーショナルシンキングの一部とかが関係してくるような、そうでもないような……?

現状では、私の周囲の量産型じゃないプログラマは、経験を通じて自然とこの辺の能力を獲得してきた人ばかりだ。なので、少なくとも今までのやり方は、「メンタルモデル/概念モデルを構築し、活用する能力」そのものを育てるという観点では、量産型プログラマが存在するという事実より、あまり成功しているとはいえないだろう。

だから、おそらく、今までとは違うアプローチが必要だと思われるが、まだエビデンスが見当たらないので、効果のほどは定かではない。

たぶん、究極的には、向き不向きがあるのだろうけど――教育でどこまで補完できるのか、仮に補完できるとしたらコストはどの程度なのか(従来のいわゆる「文系プログラマ」が生み出される採用・教育システムにて負担できるコストなのか)。非常に興味深い。

2017-01-14

ppbinについての覚え書き

昨年末にppbinというツールを作ったので、メモを残しておく。

GitHub - eel3/ppbin: Pretty-printer for binary file

ppbinとは何か?

ppbinは、指定した形式でバイナリファイルの16進数ダンプを吐き出すコマンドラインアプリだ。

$ # test.binは44 byteのファイル。
$ # -n 20 --> 1行に20ワード出力する。
$ # -w 1  --> 1ワードの大きさは1バイト(1オクテット)。
$ ppbin -n 20 -w 1 test.bin
52 49 46 46 24 00 00 00 57 41 56 45 66 6D 74 20 10 00 00 00
01 00 02 00 44 AC 00 00 10 B1 02 00 04 00 10 00 64 61 74 61
00 00 00 00
$ _

――が、まあこの程度の機能だったらod(1)やhexdump(1)などを使えば済む話だ。

そもそも実現したかったのは「バイナリファイルの16進数ダンプを、C言語C++配列初期化構文としてソースファイルに埋め込み可能な形式で出力する」ことだ。ppbin自体は多少の汎用性を持たせたツールとして実装されていて、適切なオプションを付与することで、当初の目的を達成できるようになっている。

$ # -a 0x       --> 各ワードにプレフィックス「0x」を付与する。
$ # -b <header> --> ヘッダ行を付与する。
$ # -d ', '     --> ワード間の区切り文字として「, 」を使用する。
$ # -e <footer> --> フッタ行を付与する。
$ # -i 1        --> 各行を1文字インデントする。
$ # -l          --> 各ワードをリトルエンディアンとして解釈する。
$ # -n 4        --> 1行に4ワード出力する。
$ # -t          --> インデント文字としてスペースではなくタブを使用する。
$ # -w 4        --> 1ワードの大きさは4バイト(4オクテット)。
$ ppbin -a 0x \
>       -b 'static const uint32_t test_bin[] = {' \
>       -d ', ' \
>       -e '};' \
>       -i 1 \
>       -l \
>       -n 4 \
>       -t \
>       -w 4 \
>       test.bin
static const uint32_t test_bin[] = {
        0x46464952, 0x00000024, 0x45564157, 0x20746D66,
        0x00000010, 0x00020001, 0x0000AC44, 0x0002B110,
        0x00100004, 0x61746164, 0x00000000,
};
$ _

オプション次第では、こんな出力も可能だ。

$ # -a \\x --> 各ワードにプレフィックス「\x」を付与する。
$ # -d ''  --> ワード間の区切り文字として空文字を使用する(=各ワードをくっつけて表示)。
$ # -l     --> 各ワードをリトルエンディアンとして解釈する。
$ # -n 1   --> 1行に1ワード出力する。
$ # -p 1   --> 1ワードを1バイト(1オクテット)ずつ出力する。
$ # -w 4   --> 1ワードの大きさは4バイト(4オクテット)。
$ ppbin -a \\x -d '' -l -n 1 -p 1 -w 4 test.bin
\x46\x46\x49\x52
\x00\x00\x00\x24
\x45\x56\x41\x57
\x20\x74\x6D\x66
\x00\x00\x00\x10
\x00\x02\x00\x01
\x00\x00\xAC\x44
\x00\x02\xB1\x10
\x00\x10\x00\x04
\x61\x74\x61\x64
\x00\x00\x00\x00
$ _

つまりppbinはメカニズムの提供に徹したエンジンだ。お目当ての出力形式(ポリシー)ごとにシェルスクリプト・バッチファイルなどでラッピングして使うことを想定している。

なぜ自作したのか

先に書いたように、本来の目的は、バイナリファイルの中身をC言語C++配列初期化構文に変換することだった。変換ツールを見繕うにあたり、以下の制約をクリアする必要があった。

  1. Windows上でも使える。
  2. 2バイトや4バイトごとの出力にも対応している。
  3. リトルエンディアンにも対応している。
  4. 「4バイトのリトルエンディアンとして解釈したうえで、MSB側から2バイトずつ出力する」みたいな、ちょっと特殊な要求にも対応できる。
  5. 一度に複数のファイルを処理できる。
  6. 自動化のために、非対話式に使用することができる。

探し方が悪かったからか、上記の制約全てを満たすツールが見つからなかったため、自作に踏み切った。ppbinは、そのためのエンジンとして実装した。

Unix環境で動けば十分だったなら、od(1)やhexdump(1)でダンプしてsed(1)などで出力を加工するシェルスクリプトを書いたかもしれない。

今回はppbinをPythonで実装し、出力形式ごとにppbinを適切なオプション付きで呼び出すバッチファイルを実装した。想定ユーザは全員開発者なので、Python処理系Windowsに入れることぐらいは簡単にできるはずだ。

ちなみに、なぜPythonを使ったかというと、ppbinの前に作成・公開していた別のツールをPythonで実装していたからだ*1。つまり、想定ユーザの大半は、すでにPython処理系インストール済みだったのだ。

ちょっと特殊な出力

ダンプする際、1バイトずつではなく2バイトないし4バイトずつ出力したいことがある。大抵のツールは、その要求に応えてくれる。ppbinも同様だ。

$ # -n 4 --> 1行に4ワード出力する。
$ # -w 4 --> 1ワードの大きさは4バイト(4オクテット)。
$ ppbin -n 4 -w 4 test.bin
52494646 24000000 57415645 666D7420
10000000 01000200 44AC0000 10B10200
04001000 64617461 00000000
$ _

ちなみにppbinは、出力が16進数形式に固定されている代償に、1ワードとして最大16バイト(128ビット)まで指定できる(といっても「1・2・4・8・16」の5種類しか選択できないのだが)。

複数バイトを1ワードとして指定できるようになると、今度は各ワードをリトルエンディアンとして解釈する機能が欲しくなる。ppbinは対応しているが、世の中の既存のツールは、この機能あたりから対応状況が若干怪しくなってくるようだ。

$ # -l   --> 各ワードをリトルエンディアンとして解釈する。
$ # -n 4 --> 1行に4ワード出力する。
$ # -w 4 --> 1ワードの大きさは4バイト(4オクテット)。
$ ppbin -l -n 4 -w 4 test.bin
46464952 00000024 45564157 20746D66
00000010 00020001 0000AC44 0002B110
00100004 61746164 00000000
$ _

では、例えば「4バイトのリトルエンディアンとして解釈したうえで、各ワードをMSB側から2バイトずつ出力する」みたいな、ちょっと特殊な要求はどうだろうか? ppbinには、この要求に応えるためのオプション-pが用意されている。

$ # -l   --> 各ワードをリトルエンディアンとして解釈する。
$ # -n 4 --> 1行に4ワード出力する。
$ # -p 2 --> 1ワードを2バイト(2オクテット)ずつ出力する。
$ # -w 4 --> 1ワードの大きさは4バイト(4オクテット)。
$ ppbin -l -n 4 -p 2 -w 4 test.bin
4646 4952 0000 0024 4556 4157 2074 6D66
0000 0010 0002 0001 0000 AC44 0002 B110
0010 0004 6174 6164 0000 0000
$ _

ファイル先頭の4バイトを順番に読むと「52 49 46 46」だ。これを4バイトのリトルエンディアンとして解釈すると「46 46 49 52」となり、MSB側から2バイトずつ分割すると「4646」と「4952」の2つとなる。

オプション-a-dは、実は-pによって分割された出力ごとに適用される。

$ # -a 0x   --> 各ワードにプレフィックス「0x」を付与する。
$ # -d ', ' --> ワード間の区切り文字として「, 」を使用する。
$ # -l      --> 各ワードをリトルエンディアンとして解釈する。
$ # -n 4    --> 1行に4ワード出力する。
$ # -p 2    --> 1ワードを2バイト(2オクテット)ずつ出力する。
$ # -w 4    --> 1ワードの大きさは4バイト(4オクテット)。
$ ppbin -a 0x -d ', ' -l -n 4 -p 2 -w 4 test.bin
0x4646, 0x4952, 0x0000, 0x0024, 0x4556, 0x4157, 0x2074, 0x6D66,
0x0000, 0x0010, 0x0002, 0x0001, 0x0000, 0xAC44, 0x0002, 0xB110,
0x0010, 0x0004, 0x6174, 0x6164, 0x0000, 0x0000,
$ _

そのため、安心してC言語C++配列初期化構文への変換に使用することができる。

TODO

*1:そのツールはRIFF WAVEファイルを取り扱うものだったので、標準ライブラリWAVEファイル用のモジュールが用意されていたPythonで実装した。

2016-12-25

シェルスクリプトに向いている用途

シェルスクリプトに向いている用途は、大抵の場合、以下の要件を1つ以上満たしているものだ。

  1. 作りたいものが単機能で、あまり複雑ではない。
  2. 対話的な処理である。
  3. 既存のコマンドの羅列/組み合わせで容易に解決できる内容である。
  4. 他の言語でいう「メソッドチェーンによるコレクションからコレクションへの変換」で済む処理である。
  5. 扱うデータが「1行1レコードのテキストデータ」である。もしくは、その形式に容易に変換可能である。
  6. 扱うデータの件数レコード数)が多い。
  7. 事前に扱うデータ群から異常値が取り除かれている。もしくは、異常値や外れ値を単純に取り除くだけでよい(≒エラー処理での高度な「特別扱い」が不要である)。
  8. 実装するにあたり、中間データを作成して使い回したいが、中間データをオンメモリにせずファイルシステム上に置いても問題ない。

作りたいものが単機能で、あまり複雑ではない

シェルスクリプトで作られるツールは、どちらかといえば単機能――特定の機能のみ提供するものだ。これはUnix哲学の影響によるところが大きいのだが、シェルスクリプト自体も、あれもこれも機能を提供するようなツールは実装しにくい。

ただし「コマンドの羅列/組み合わせで容易に解決できる内容」に向いている、という特性より、解決したい課題を整理・分割した際に個々のパーツをコマンドとして実装できるようなら、それらの独自実装コマンドを組み合わせることで複雑な課題を解決できる余地があるし、独自実装コマンド群のラッパースクリプトを書くことで、例えるなら「apt-get(8)にたいするapt(8)」のような関係の、複数の機能を提供するツールを仕立て上げることもできなくはない。

対話的な処理である

シェルスクリプトの王道は、定型処理の自動化である。自動化においては、対話的な部分の排除が発生する。そのため、シェルスクリプトの多くは非対話的なものとなる。

とはいえ、シェルスクリプトでも、ftp(1)のような対話型操作のツールは作れなくもない。もう少し凝ったUIならtput(1)やdialog(1)で実装できるし、GUIダイアログ程度ならXdialogで表示できる。

もっとも、シェルスクリプト内でデータを保持して使い回すのが苦手なこともあり、大抵はraspi-configのように「実際の処理は別のコマンドで実行する。シェルスクリプトはユーザ操作を受け取って個々のコマンドを叩くだけ」という、ある種のラッパースクリプトとして実装される。

既存のコマンドの羅列/組み合わせで容易に解決できる内容である

……まあ、シェルスクリプトはグルー言語の中のグルー言語だから、しかたないね ;)

素のシェルスクリプトは、それ自体の表現力は高くない。bash(1)やzsh(1)の独自拡張機能アリアリなら改善されるものの、それでも他のプログラミング言語と比べれば――お察しください。

今も昔もシェルスクリプトの本業は、職人たち(≒コマンド群)に指示して工事を進める現場監督だろう。

他の言語でいう「メソッドチェーンによるコレクションからコレクションへの変換」で済む処理である

フィルタをパイプで連結してテキストレコードを処理する」とは、つまりそういうことだ。

扱うデータが「1行1レコードのテキストデータ」である。もしくは、その形式に容易に変換可能である

awk(1)はそうでもないが、他のテキストフィルタのことを考えると、「1行1レコード」の形式が圧倒的に扱いやすい。

ということは、元データが他の形式であっても、一旦「1行1レコード」に変換できてしまえば、後はテキストフィルタで活殺自在だといえる。XMLならxmllint(1)、JSONならjq(1)などを駆使して「1行1レコード」のテキストに変換した上でテキストフィルタに流し込むのは常套手段だ。

扱うデータの件数レコード数)が多い

シェルスクリプトが呼び出すコマンドは、それがシェル組み込みコマンドでもない限り、単体のプログラムな訳で――コマンド呼び出しの度にプロセスの生成・削除が発生する。

Unix環境は比較的プロセス生成コストが低いといえども、他の言語における関数メソッド呼び出しと比較すれば、やはりコストは高めだ。同じシェルスクリプト内であっても、シェル組み込みコマンドやシェル関数の呼び出しの方が圧倒的に速い。

(記録のために書いておくと、Cygwinではもっとコストがかかる。というのも、大抵のWindows上ではセキュリティ対策ソフトが動作していて、ヒューリスティック検知機能が有効化されている。その手の機能はWindows APIをフックしていて、プログラム実行時(≒プロセス生成時)にAPIフック経由で検知機能を実行していることが多い。そのため、純粋なプロセス生成コスト+αの時間が必要となる)

複数の外部コマンドをパイプで連結して使う場合、連結した個々のコマンドのプロセスが生成される。コマンドが増えれば増えるほど、プロセス生成コストがかさむ。このコストをペイするには、やはりそこそこの件数レコード数)のデータを処理する必要がある。コマンド10個の処理にたいして元データがたった1件だったなら、赤字確定だ。

だから個人的には、1行分のデータをecho(1)を使って「パイプで連結した複数のフィルタ」に流し込むようなやり方は、好きになれない。そうするしかないことも多いのだが、なんかもにょる。

さらにいえば、while readでテキストを1行ずつ読み込んだ上でecho(1)を使って「パイプで連結した複数のフィルタ」に流し込む方法は、もっと好きになれない。そもそもシェルのループ構文中で外部コマンドを呼び出すこと自体が筋が悪い。大抵のテキストフィルタは勝手に複数行のテキストを処理してくれるものだから、while readを外して一気にフィルタに流し込めないものか、あれこれ考えてしまう。

まあしかし、プロセス生成コストに関しては、もう少し慎重に検討すべき事項だろう。なぜなら大抵のテキストフィルタはシンプルなので、実行ファイルが小さく、プログラム起動時のロード時間が短くて済む傾向にあるからだ。他のスクリプト言語では、処理系自体が大き目でロード時間がかかることがある。この辺は、もう実運用環境で計測してみないと分からない話だ。

事前に扱うデータ群から異常値が取り除かれている。もしくは、異常値や外れ値を単純に取り除くだけでよい(≒エラー処理での高度な「特別扱い」が不要である)

他の言語で「メソッドチェーンによるコレクションからコレクションへの変換」というコードを書いたとき、メソッドチェーンの中にエラー処理をうまい具合に埋め込むことが可能なものか、よく考えてみるべきだ。ちょっと厳しくないだろうか?

つまり、「パイプで連結した複数のフィルタ」にテキストレコードを流し込む前に、事前に異常値を取り除く作業を行う(各種エラー処理はそこで行う)べきなのだ。フィルタには、異常値が取り除かれたデータを送り込むべきである。

あえて言うなら、異常値や外れ値を単純に取り除くだけならば、SQLLINQでいう「Whereによるフィルタリング」のような要領で、そういう役割を果たすフィルタをパイプで連結することで実現できるが……逆に言えば、その程度が限度である。

実装するにあたり、中間データを作成して使い回したいが、中間データをオンメモリにせずファイルシステム上に置いても問題ない

素のシェルスクリプトには言語機能としての配列は存在しない*1bash(1)やzsh(1)などの独自拡張機アリアリなら配列が使えるが、他の言語と比べると制限がある。

じゃけん、一時ファイルを使いましょうね――という話。

シェルスクリプトに向いていないことは?

シェルスクリプトに向いていない(または別のツールの方が向いている)ことは色々とある。

シェルスクリプト自体の表現力は高くないし、変数配列などの「状態を保持する」ための機能は癖が強くて扱いにくい。なので、ゴリゴリとコードを書いてアルゴリズムを実装するような用途には向いていない。

どちらかといえば、そのようなケースでは「コアの部分を独立したコマンドとして別の言語で実装し、シェルスクリプトでラッピングする」というアプローチをとるべきだろう。

例えば、以前XSLT-PFというツールのJava版を作ったときには、中核部分をJavaで実装しつつシェルスクリプトでラッピングして、コマンドのオプション処理などはシェルスクリプト側で行うようにした。

最近だとppbinというツールをPythonで実装したが、これも「コアの部分を独立したコマンドとして別の言語で実装」の一例で、これを他のテキストフィルタ等と組み合わせて、バイナリファイルからある言語の配列形式に変換するツールを作っていたりする。

先に書いたが、シェルスクリプトは基本的に「現場監督」が本業だ。だから、職人たち(≒コマンド群)を連れてくるか、もしくは養成(≒コマンドを自作)したうえで、彼らに作業を割り振って工事を進める(≒コマンドを組み立てて処理をする)のが、もっとも効率がよい。シェルスクリプト自身に職人としての役割を担わせるのは、非効率だ。この点は、作るものが非対話型のコマンドだろうと対話型のツールだろうと同じだ。

もっとも、「現場監督」に徹するケースでも、例えば「ファイルAを入力としてファイルBを生成する」というような作業を大量に行うとか、「途中で失敗したら中断する」とか、そのような要求がある場合にはMakefileの方が向いている。make(1)は、あれはあれで非常に興味深いツールだ。

*1:ただし配列っぽいものをシミュレートすることはできる。

2016-12-18

PythonのwaveモジュールでのPCMデータ読み出しを高速化する

RIFF WAVEファイルからリニアPCMのデータを取り出して、フレーム毎に(正確には各フレーム内のサンプル毎に)加工して出力するツールを作った。

諸事情によりPython 2.xの標準ライブラリwaveモジュールを使ったのだが、Wave_readオブジェクトの扱い方によって速度に差が出たので、メモを残しておく。

環境はCygwin x64上のPython 2.7.12だ。

最初のコード(遅かった)

フレーム毎にデータを加工したかったため、フレーム毎にreadしようとして最初に書いたのは、こんなコードだった。

wr = wave.open(wavfile, 'rb')

for _ in range(wr.getnframes()):
    frame = wr.readframes(1)
    samples = [frame[i:i+wr.getsampwidth()] for i in range(0, len(frame), wr.getsampwidth())]
    # XXX 各サンプルごとに、何らかの処理を行う。

wr.close()

このコードは結構遅くて、4MB弱のWAVEファイルを流し込んで処理を行おうとすると、手元の環境では7〜8秒ほどかかっていた(上記の「各サンプルごとに、何らかの処理を行う」を含めた時間なので注意)。

小手先の改良コード(ちょっと速くなった)

で、小手先の策を弄したコードがこれ。

wr = wave.open(wavfile, 'rb')

nframes = wr.getnframes()
sampwidth = wr.getsampwidth()

for _ in range(nframes):
    frame = wr.readframes(1)
    samples = [frame[i:i+sampwidth] for i in range(0, len(frame), sampwidth)]
    # XXX 各サンプルごとに、何らかの処理を行う。

wr.close()

ループ中で何度もWave_read.getsampwidth()を呼ぶのではなく、ループ前に変数に格納しておいて、それを参照するようにしただけ。しかしこれでも1秒近く短縮された。

もうちょっと改良したコード(もっと速くなった)

もう少し速くならないかと考えて、ループ中で毎度Wave_read.readframes()で1フレームずつreadするのではなく、一度にガッとreadした上で、スライス演算でフレームごとにアクセスするジェネレータ式を使うようにしてみた。

wr = wave.open(wavfile, 'rb')

sampwidth = wr.getsampwidth()
framewidth = sampwidth * wr.getnchannels()

frames = wr.readframes(wr.getnframes())
it = (frames[i:i+framewidth] for i in range(0, len(frames), framewidth))
for frame in it:
    samples = [frame[i:i+sampwidth] for i in range(0, len(frame), sampwidth)]
    # XXX 各サンプルごとに、何らかの処理を行う。

wr.close()

これでさらに2秒ほど短縮された。

ダメ押しの改良コード(さらに速くなった)

もう高速化は無理だろうと思っていたところ、ふと「そういえば、何で1フレーム取り出してサンプルごとに分割してるのだろう?」と気づいてしまった。

今回の加工処理は、「同一フレーム中の各サンプル」という括りで何かする必要はなかった。なので、最初からサンプル単位でアクセスしても問題なかった。

wr = wave.open(wavfile, 'rb')

frames = wr.readframes(wr.getnframes())
sampwidth = wr.getsampwidth()
it = (frames[i:i+sampwidth] for i in range(0, len(frames), sampwidth))
for sample in it:
    # XXX サンプルごとに、何らかの処理を行う。

wr.close()

ダメ押しの1秒短縮。

まとめ

  • 最終的に、最初のコードの2倍ほど高速になった。
  • C/C++の感覚からすると、メソッド呼び出しのコストは少し高めかも。*1
  • スライス演算とジェネレータ式! そういうのもあるのか。

*1:念のため書いておくと、これはPythondisっているわけではなく、Pythonを使っていたにもかかわらず暗黙のうちに他の言語(C/C++)の感覚で判断を行っていた自分への戒めである。PythonPythonとして扱わなければ失敗する、当然のことだ。

2016-12-10

正規表現を使ったテキストフィルタとC/C++による自作ツールではどちらが高速か?

改行区切りのテキストレコードを舐めて、特定の形式に当てはまるものを除外するツールが欲しくなった。形式の判定には正規表現が使えそうだった。

Unix環境で動かすなら、既存のテキストフィルタを使えばよい。だが残念なことに動作環境はWindowsで、しかもスクリプトではなく単体で動作する実行ファイルに仕立て上げる必要があった。

そこで、初めてC++11の正規表現ライブラリを使って、即席のツールを書いた。

で、ふと思ったのだが、Unix環境では、標準のテキストフィルタとCやC++正規表現ライブラリを使って作った即席のツールでは、どちらが高速なのだろうか?

grep(1)などのテキストフィルタは高速に動作するように実装されているはずなので、素人が何も考えずにCやC++で作ったツールより速そうだが、実際はどんな感じなのか、ちょっと実験してみた。

テスト条件

実験はUbuntu 16.04.1 LTS 64bitで行った。テキストフィルタUbuntuリポジトリから入れた(もしくはインストール時に入ってきた)ものを使った。

UbuntuMSI A78M-E35 V2(AMD A78)にAMD A6 7400K BEを載せた自作PCで動かしている。メモリはADATA AX3U2133W8G10-DR(PC3-17000 DDR3-2133)8GB×2枚の16GB。Ubuntu本体はSanDisk SDSSDA-120G-J25Cにインストールしているが、/homeは旧式の2.5インチHDDであるHITACHI HTS545050B9A300に配置している。テストもSSDではなくHDD上で実施している。最近のPCとしては、どちらかと言えば低スペックに該当する環境だろう。

テストデータは、以下のRubyスクリプトで作成した。

#!/usr/bin/env ruby

t = ("0".."9").to_a +
    ("A".."Z").to_a +
    ("a".."z").to_a

10000000.times do
  puts t.join
  t.rotate!
end

次のような内容の62文字のテキストが1000万行。

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0
23456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01
3456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz012
456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123
56789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234
6789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz012345
789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456
89ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567
9ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz012345678
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789
BCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789A
CDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789AB

およそ630MBのテキストファイルがキャッシュに載っている状態で実験した。

次のような内容の正規表現にマッチした行を取り除くことにした。

^ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789$

今考えると、あまりよくない内容の正規表現だと思うのだが、結果として意外な知見が得られた(気がする)。

よくあるテキストフィルタの場合

トップバッターはGNU grep 2.25。grep(1)にはマッチしなかった行を出力するオプション-vがあるので、それを使う。ついでに行マッチ用のオプション-xなんてのもあったので、使ってみた。

#!/bin/sh
export LC_ALL=C LANG=C
exec grep -v -x 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789' ${@+"$@"}

で、実験。本来は/dev/nullにリダイレクトするべきなのだろうが、正しくマッチしているか簡易判定するために、wc(1)で行数をカウントしている。

$ time sh grep/filter <data.txt | wc -l
9838709

real	0m1.122s
user	0m1.228s
sys	0m0.588s
$ _

速い! grep(1)はよく使われるツールなので、この値を基準とする。

次はGNU sed 4.2.2。そのものズバリなコマンドdを使い、マッチした行を削除すればよい。

#!/bin/sh
export LC_ALL=C LANG=C
exec sed '/^ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789$/d' ${@+"$@"}
$ time sh sed/filter <data.txt | wc -l
9838709

real	0m3.565s
user	0m3.428s
sys	0m0.784s
$ _

ふむ、grep(1)の3倍ちょっと遅いようだ。

最後にmawk 1.3.3。GNU awkでない点がどれだけ影響するか?

#!/bin/sh
export LC_ALL=C LANG=C
exec awk '$0 !~ /^ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789$/' ${@+"$@"}
$ time sh awk/filter <data.txt | wc -l
9838709

real	0m2.022s
user	0m1.688s
sys	0m0.868s
$ _

grep(1)の2倍弱。sed(1)より高速だ――が、GNU awkだったらそうはいかない気がしないでもない。

C言語の場合

Unix環境なので、POSIXregex(3)とgetline(3)を使うことにする。コンパイラgcc 5.4.0だ。

#ifdef __linux__
#	ifndef _POSIX_C_SOURCE
#		define _POSIX_C_SOURCE 200809L
#	endif /* ndef _POSIX_C_SOURCE */
#endif /* def __linux__ */

#ifdef __FreeBSD__
#	define _WITH_GETLINE
#endif /* def __FreeBSD__ */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include <sys/types.h>
#include <regex.h>

/* ---------------------------------------------------------------------- */
/*  */
/* ---------------------------------------------------------------------- */
static void
regex_perror(regex_t * const re, const int errcode)
{
	size_t len;
	char *msg;

	assert(re != NULL);

	if (errcode == 0) {
		return;         /* No error */
	}

	len = regerror(errcode, re, NULL, 0);
	if (len == 0) {
		return;         /* XXX */
	}
	msg = malloc(len);
	if (msg == NULL) {
		return;         /* XXX */
	}

	if (regerror(errcode, re, msg, len) > 0) {
		(void) fprintf(stderr, "%s\n", msg);
	}

	free(msg);
}

/* ---------------------------------------------------------------------- */
/*  */
/* ---------------------------------------------------------------------- */
int
main(int argc, char *argv[])
{
	int errcode;
	regex_t regex;
	char *line;
	size_t len;

	errcode = regcomp(&regex,
	                  "^ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789$",
	                  REG_EXTENDED | REG_NEWLINE | REG_NOSUB);
	if (errcode != 0) {
		regex_perror(&regex, errcode);
		return EXIT_FAILURE;
	}

	line = NULL;
	len = 0;

	while (getline(&line, &len, stdin) != -1) {
		if (regexec(&regex, line, 0, NULL, 0) != 0) {
			(void) fputs(line, stdout);
		}
	}

	free(line);
	regfree(&regex);

	return EXIT_SUCCESS;
}

では、いざ実験。

$ time c/filter <data.txt | wc -l
9838709

real	0m3.466s
user	0m3.340s
sys	0m0.768s
$ _

ちょっと遅い。GNU sed版のテキストフィルタと100msecほどしか違わない。

どこがボトルネックだろうか? 思いつくポイントは入出力か正規表現エンジンぐらいだが、入力部のgetline(3)は十分高速だろうから、正規表現エンジンを疑ってみる。

試しにregex(3)ではなくstrcmp(3)を使った版を作成して、再実験。

#ifdef __linux__
#	ifndef _POSIX_C_SOURCE
#		define _POSIX_C_SOURCE 200809L
#	endif /* ndef _POSIX_C_SOURCE */
#endif /* def __linux__ */

#ifdef __FreeBSD__
#	define _WITH_GETLINE
#endif /* def __FreeBSD__ */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* ---------------------------------------------------------------------- */
/*  */
/* ---------------------------------------------------------------------- */
int
main(int argc, char *argv[])
{
	char *line = NULL;
	size_t len = 0;

	while (getline(&line, &len, stdin) != -1) {
		if (strcmp(line, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n") != 0) {
			(void) fputs(line, stdout);
		}
	}

	free(line);

	return EXIT_SUCCESS;
}
$ time c/filter_strcmp <data.txt | wc -l
9838709

real	0m1.406s
user	0m1.356s
sys	0m0.800s
$ _

元コードの半分以下の時間で済んだ。

grep(1)との速度差は、純粋な正規表現エンジンの性能差によるものなのか、それともテキストフィルタによっては正規表現の内容次第でstrcmp(3)での比較と同等の処理に切り替えたりするものなのか、気になるところだ。入出力の足回りも工夫されているかもしれない。

なお蛇足だが、regex(3)はビルド済みのライブラリとして提供されているので、コンパイラ最適化オプションは(純粋なregex(3)による処理部分に関しては)効果がない。

先に挙げたのは最適化なしバイナリでの計測結果だったので、同じgccにて-O3ビルドしたバイナリでの計測結果:

$ time c/filter_o3 <data.txt | wc -l
9838709

real	0m3.610s
user	0m3.660s
sys	0m0.636s
$ _

最適化なしの場合とほぼ同じ。むしろ100msecちょっと遅くなった?

C++の場合

C言語版ではPOSIX由来の機能を使ったが、C++では標準ライブラリの範囲内で賄える。そこで、ひとまずC++11の範囲内で実装してみた。なおコンパイラはg++ 5.4.0だ。

#include <iostream>
#include <regex>
#include <string>

int main()
{
	static const std::regex re("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789");

	std::string line;
	while (std::getline(std::cin, line)) {
		if (!std::regex_match(line, re)) {
			std::cout << line << std::endl;
		}
	}
}

いざ実験。

$ time cpp/filter <data.txt | wc -l
9838709

real	1m9.467s
user	1m3.700s
sys	0m35.220s
$ _

遅い! なんか一気に遅くなったぞ。なせだ?

試しに入力をPOSIXのgetline(3)に差し替えてみた。

#ifdef __linux__
#	ifndef _POSIX_C_SOURCE
#		define _POSIX_C_SOURCE 200809L
#	endif /* ndef _POSIX_C_SOURCE */
#endif /* def __linux__ */

#ifdef __FreeBSD__
#	define _WITH_GETLINE
#endif /* def __FreeBSD__ */

#include <cstdio>
#include <iostream>
#include <regex>

int main()
{
	static const std::regex re("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n");

	char *line = NULL;
	size_t len = 0;

	while (getline(&line, &len, stdin) != -1) {
		if (!std::regex_match(line, re)) {
			std::cout << line;
		}
	}

	free(line);
}

気を取り直して再実験。

$ time cpp/filter_getline <data.txt | wc -l
9838709

real	0m26.366s
user	0m26.032s
sys	0m0.964s
$ _

40秒ちょっと短縮された。入力部分の見直しは効果があるようだ。が、それでもまだまだ結構遅い。

Ubuntu付属のg++を使っているのだが、付属の正規表現ライブラリの性能はこんなものなのか、それともまだ調整不足(なのでバージョンアップすると改善されるもの)なのか……?

std::regexは十中八九テンプレートライブラリとして提供されているので、POSIXregex(3)とは異なり、最適化オプションは効果がある。

POSIXのgetline(3)に差し替えた版の「26秒ちょっと」という結果は、最適化なしで計測したものだ。試しに-O3ビルドした場合は:

$ time cpp/filter_getline_o3 <data.txt | wc -l
9838709

real	0m6.509s
user	0m6.360s
sys	0m0.812s
$ _

20秒も短縮された! すごい効果だ。まあ、正規表現を定数で渡しているので、正規表現コンパイルまで含めてビルド時に処理されている可能性も否定できないのかもしれない。

では、元バージョンを-O3ビルドするとどうなるか?

$ time cpp/filter_o3 <data.txt | wc -l
9838709

real	0m48.178s
user	0m41.868s
sys	0m36.912s
$ _

短縮された時間は20秒……。

少なくともstd::regex最適化オプションが効くようだが、std::getlineにはあまり効果がないようだ。

flexを使った場合

ここまで実験した範囲では、下手にCやC++で実装するよりも、テキストフィルタを使った方がよさそうな雰囲気だ。実装が楽な上に、動作も高速だ。

ところで、POSIXregex(3)やC++のstd::regexを使う場合、実行時に正規表現コンパイルが発生する。コンパイルが1回だけなら影響は少なそうだが、実行時に何度もコンパイルされるケースでは、実行速度に無視できない影響がでることもあるようだ。

では、実行時ではなく、予め準備しておいたらどうか?

――ということで、本日のダークホースflex 2.6.0の登場である。

%{
#include <stdio.h>
#include <stdlib.h>
%}

REGEX   ^ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n
%%
{REGEX}
%%

int yywrap(void) { return 1; }

int main(void)
{
	yylex();

	return EXIT_SUCCESS;
}

frex(1)が吐き出すソース次第だが、どうか?

$ time flex/filter <data.txt | wc -l
9838709

real	0m26.838s
user	0m26.284s
sys	0m0.936s
$ _

うーん、遅い。

frex(1)が吐き出したソースには字句解析器のコードがガッツリ書かれているので、吐き出されたソースへの最適化オプション適用は、それなりに効果がある。

試しに-O3ビルドした場合の計測結果:

$ time flex/filter_o3 <data.txt | wc -l
9838709

real	0m17.869s
user	0m17.772s
sys	0m0.660s
$ _

9秒ほど速くなった。とはいえC++のstd::regexほどには、最適化オプション付与による効果は得られないようだ。

入力部分などを色々弄れば改善できるかもしれないが、肝心の弄り方がよく分からない。

結論

環境次第であるとは思うが、最近のUnixユーザランド作業するのなら、テキストフィルタは十分に高速だ。なので、安心して素直にテキストフィルタを使っておけば、大抵は問題ない。

POSIXregex(3)は、素の状態でそこそこ高速なようだが、regex(3)そのものを高速化することは難しい。C++11のstd::regexは、(少なくともgcc付属のものは)最適化オプションの併用を検討した方がよさそうだ。

あえてCやC++正規表現する場合は、正規表現エンジンよりも先に、入出力のコストに注意を払うほうがよいだろう。

flex(1)は……字句解析器が欲しくなるようなケースで使うべき(≒他のケースでは、少なくとも性能面のメリットはない)かな?