ずいぶん前に、Python で CRC-16 を算出するために以下のようなコードを書いたのだが、入力データが数十KB になると、算出に 10秒以上掛かり、非常に遅いのが気になっていた。あまりに遅いので、C で拡張モジュールを作って使っていた。
def calc_crc16(data_bytes):
BYTE_BIT = 8
crc_table = (
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,
...
0x6E17, 0x7E36, 0x4E55, 0x5E74, 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0,
)
r = 0
for c in data_bytes:
r = (r << BYTE_BIT) ^ crc_table[((r >> (16 - BYTE_BIT)) ^ ord(c)) & 0xFF]
return r & 0xFFFF
ふと気付いて、算出処理を以下のように書き換えたところ、劇的に速度が向上した。
for c in data_bytes:
r = ((r << BYTE_BIT) ^ crc_table[((r >> (16 - BYTE_BIT)) ^ ord(c)) & 0xFF]) & 0xFFFF
return r
C だと、左シフトで整数型からあふれたビットはそのまま無視して問題なかったが、Python では長整数型で全ビットが保存されていたためにデータが増えるに従って指数関数的に遅くなっていた。
次のようにして、256bytes のデータの CRC-16 計算時間 (10000回) を計ってみた。
import timeit
timeit.Timer('import crc\ncrc.calc_crc16("a" * 256)').timeit(10000)
せっかくなので、最近出た PyPy 1.6 release c でも実行してみた。改善後のコードが特に PyPy で顕著に高速化されており、C に迫る速度が出ている。
| 環境 | 時間（秒） |
|---|---|
| Python 2.7.2 （改善前） | 5.982 |
| Python 2.7.2 （改善後） | 1.982 |
| PyPy 1.6-c （改善前） | 3.854 |
| PyPy 1.6-c （改善後） | 0.126 |
| Python 2.7.2 （C モジュール） | 0.046 |
Windows 版 PyPy 1.6 では、Python 2.7 用に作った C の拡張モジュールは使えなかったのだが、他のプラットフォームではどうなのだろう。wxPython などが使えれば使い道がずいぶん広がるのだが。
Makefile (nmake) の中で、cl.exe のバージョンをチェックする方法はないかと考えてみた。
cl.exe が VC++ 2002 以降 (_MSC_VER >= 1300) ならば、コンパイルオプションに、-GL を付加する例を示す。作業ファイルとして mscver.c を作成し、プリプロセッサに通した結果を for コマンドで読み取り、cmd.exe の内部コマンドの if で比較し、その結果を nmake の !if で判定する。（cf. プリプロセスでのプログラムの実行）
!if [(echo _MSC_VER>mscver.c) && for /f %i in ('cmd /c "$(CC) /EP mscver.c 2>nul"') do @(del mscver.c && if %i GEQ 1300 exit 1)]
CFLAGS = $(CFLAGS) -GL
!endif
数値の比較を cmd.exe で行い、その結果を exit で返している部分が分かりにくいので、もう少し手を加えてみた。_MSC_VER の値をエラーコードとして返し、!if で比較する。
!if [for /f %i in ('cmd /c "(echo _MSC_VER>mscver.c) && ($(CC) /EP mscver.c 2>nul) && del mscver.c"') do @exit %i] >= 1300
CFLAGS = $(CFLAGS) -GL
!endif
まだ分かりにくいので、さらに修正してみた。
_MSC_VER = [for /f %i in ('cmd /c "(echo _MSC_VER>mscver.c) && ($(CC) /EP mscver.c 2>nul) && del mscver.c"') do @exit %i]
!if $(_MSC_VER) >= 1300
CFLAGS = $(CFLAGS) -GL
!endif
cl.exe の _MSC_VER の値を、nmake の _MSC_VER の値に設定しているように見えるかもしれないが、実際には nmake の _MSC_VER の値は [for 〜] という文字列である。!if を評価する段階で、[for 〜] のコマンドが実行される。従って、!if による cl.exe のバージョン判定を複数回記述すると、その回数だけコマンドが実行されてしまう点に注意が必要である。
ActivePerl 5.14 の wperl で LWP::Simple を使うと、一瞬コマンドプロンプトが表示される。気になったので原因を調べてみた。
LWP::Simple → LWP::UserAgent::env_proxy → Encode::Locale と呼び出されて、現在のコードページを取得しようとするところに原因があった。\Perl\lib\Encode\Locale.pm を見ると、Win32::Console::InputCP() でコードページが取得できなかった場合、次のように chcp コマンドを実行して現在のコードページを取得しようとしている。
if (!$ENCODING_CONSOLE_IN && qx(chcp) =~ /^Active code page: (\d+)/) {
$ENCODING_CONSOLE_IN = "cp$1";
}
日本語 Windows 環境で chcp を実行すると次のようになる。
C:\>chcp 現在のコード ページ: 932
英語環境以外では全く役に立たない上に余計なコマンドプロンプトまで表示して、本当にひどいコードだ。
小迫氏の blog で鬼車関連の記事を読み直してみると、いろいろおもしろいことが書いてある。
Onigmo (Oniguruma-mod) の最適化に使えそうなネタがあればと思い、x86/x64最適化勉強会1に参加してきた。条件分岐の最適化や、SSE4.2 の文字列処理命令などが Onigmo にも使えそう。ただし、今日の話を聞いた感じでは文字列処理命令は結構難しそう。以前から会ってみたいと思っていた方たちにも会えてよかった。