krの日記： Haskellで速いwcを書いてみよう(10) 6
前回のエントリの続きです。
もうちょっと高速化できないか考えてみます。
どんなプログラムでも、高速化の要は「頻繁に実行される箇所を少しでも速くする」ことです。 そういう点では、tanakh氏が試みていたように、文字入力処理の高速化を図るのは正しい方向性と言えます。 しかし、そこに手をつけると、一通りの入出力処理をすべて再実装することになり、大変な変更が必要になるのは目に見えています。
もっと楽をして速くできる箇所があれば、それに越したことはありません。そんな目で再びprog8を見てみると、 整数の加算やリストの分解と言った、比較的軽い処理の中にあって、なんとなくisSpaceが目立っていることに気付きました。
isSpaceはCのisspace(3)と同様な文字種判定関数ですが、Haskellは建前上Unicode文字を扱うことになっているので、 実際にはUnicode文字に対するiswspace(3)と同様な処理をしていることになります。ちなみにghcではISO-8859-1の範囲の空白文字をHaskellで判定した後、その他の文字をすべて、Cで書かれた判定関数に回してしまいます。ここは外部関数呼び出しになるので、頻繁に呼び出すとそれなりのコストが掛かるのではないかと想像されます(本当かどうかは未確認(_ _))。
どうせ今回のwcは8ビット文字前提ですし、ここを端折った処理にしてしまえば高速化できないでしょうか?
というわけで書いてみたのが以下のコードです。
{-# OPTIONS_GHC -fglasgow-exts #-}
-- prog9
import GHC.Base
wc:: String -> ( Int, Int, Int )
wc = wc' 1# 0# 0# 0#
where
isSpace:: Char -> Bool
isSpace ' ' = True
isSpace '\t' = True
isSpace '\n' = True
isSpace '\r' = True
isSpace '\f' = True
isSpace '\v' = True
isSpace _ = False
wc':: Int# -> Int# -> Int# -> Int# -> String -> (Int, Int, Int)
wc' s# nl# nw# nc# [] = (I# nl#, I# nw#, I# nc#)
wc' s# nl# nw# nc# ('\n' : cs) = wc' 1# (nl# +# 1#) nw# (nc# +# 1#) cs
wc' s# nl# nw# nc# (c : cs)
| isSpace c = wc' 1# nl# nw# (nc# +# 1#) cs
| otherwise = wc' 0# nl# (nw# +# s#) (nc# +# 1#) cs
例によってmainは同じなので省略しています。このプログラムをprog9とします。 isSpaceを、かなり直截的な内部関数に置き換えた以外は、ほぼ何も変わっていません。 isSpaceのためにimportしていたData.Charモジュールは不要になりました。実行時間を測ってみましょう。
% time ./prog9 < /usr/share/doc/en/books/handbook/book.txt
72266 323341 3196121
0.103u 0.023s 0:00.13 92.3% 298+272k 0+0io 0pf+0w
0.105u 0.022s 0:00.13 92.3% 317+286k 0+0io 0pf+0w
0.120u 0.007s 0:00.13 92.3% 317+289k 0+0io 0pf+0w
0.103u 0.023s 0:00.13 92.3% 298+272k 0+0io 0pf+0w
0.110u 0.017s 0:00.13 92.3% 298+269k 0+0io 0pf+0w
実行時間は実時間で0.13秒のようです。prog8がおよそ0.50秒でしたから、 isSpaceの改良だけで案外と速くなるものです。 ところで、C版がおよそ0.18秒でしたから、 おや、どうしたことでしょう、いつの間にかC版より速くなってしまいました。:-)
最初の版prog6と比べてみても、prog9には、さほどびっくりするような変化はありません。 プログラムの基本構造にはほぼ違いはなく、必要な正格評価のための修飾がちりばめられたものの、動作を理解するのは相変わらず簡単です。
もちろん、まだまだチューニングできる箇所は残っています。このエントリの冒頭で挙げた入出力処理の高速化などもその一つでしょう。 その辺りの高速化については、Library/Streamsとして、より一般的で高機能な形で取り組んでいるプロジェクトがあるので、その成果を取り入れてみるのも一案です。
でも、まあ、Cより速くなったということで、個人的にはこの辺りで満足してしまいました。
# 定数オーダとはいえ、メモリフットプリントはCより大きいため、
# 「HaskellがCに勝った」とはまでは言えないかもしれせんが。:-)
一つ心残りは、最初のprog6の時点ですでに少々Haskellらしくないコードになっている点です。気がむいたら、その点もうちょっとどうにかできないか、考えてみたい気もします。でも、まあ今回はここまでです。
長い一連のエントリを読んで下さり有難うございました。
# 初めて/.Jの日記を書いたけど、最初から(だけ)飛ばしすぎだ……。
元データって (スコア:1)
これ [freebsd.org]と大体同じ？
普通のgnu wc って結構遅いと思います。どこが悪いのかあまりわかりませんでしたが。
C++で書くときに、私が気にするのは、どうやって一文字ずつ判断をやめるか。せっかくの32/64bitマシンなんで8bit単位じゃなくて64bitで調べたい。64bitで調べることができれば単純に見て、8bitの8倍速。さらに32bitか64bitの１ワードから1バイトを切り出す余分なコードが不要に。
で、G++/glibc の strcmp, memchr を使うと画期的に早くなります。
ああ、harshellの人には関係ないですね。
Re:元データって (スコア:1)
はい、元データはそれ [freebsd.org]と大体同じです。 たぶんwcの実行速度の傾向に大きな違いが出ることはないでしょう。
# よく考えたら、手元の/usr/share/doc/en/books/handbook/book.txtって、
# マシンに最初にFreeBSDをインストールした時の古いファイルのままupgradeされてません。
# 改めて中見たら、FreeBSD 5.4-RELEASEがどうとかとか書いてある。(古っ)
後で気付いたんですが、テストデータは青空文庫とか Project Gutenberg [gutenberg.org]辺りから持ってくれば良かったかもしれません。
ところで、今回C++版・C版として使ったのはtanakh氏 [hatena.ne.jp]の 「ふらふらと何にも考えないで書いたコード」「適当に書いたコード」とおっしゃっているコードですので、 それぞれちゃんとチューニングしていくと、多分もっと速くなると思います。
ということで、「普通」のwcと比較するとどうなのか試してみました。
速っ。ここで書いたHaskell版より、さらに2倍以上速いです。おそるべしC。:-)# システムにインストールされたバイナリを使って測定したので、
# 最適化オプションが効いてます。
# tanakh氏のCコードも、最適化オプション付きだともっと速くなるかも。
GNU wcは手元に無いので、それと比べてどうかは試してみていません。(ちなみにFreeBSDの標準のwcは、GNU版でなくBSD版のwcです。)
高速化にあたって、なるべくSIMD的に処理するというのは確かに重要でしょうね。
ターゲットアーキテクチャ向けにチューンされた(と期待される) strcmp(3)やmemchr(3)の類というのは、 Haskellを使う場合でも魅力的に思う人が多いようで、 そういう人はHaskellのData.ByteStringモジュールとかを愛用しているようです。 ghcのライブラリマニュアルを見ると、 Data.ByteStringのところには 「この関数はmemchr(3)使うよ」とか「これはmemcpy(3)使うよ」とか書いてあったりします。 それどころか、(たぶん非標準と思いますが)実はmemchrだのmemcpyだの直接呼び出すこともできるようになってます。
実際のところ、Haskellプログラムの高速化というと、 多くの人が「じゃあByteString」と言うので、 今回のwcでは敢えてそういう方向を避けてみました。 「いやいやByteStringでなくても結構イケルよ」と言えたらいいなあと個人的には思います。
とはいえ速度のみを追求するなら、ByteStringでC風の高速化を図るのも避けて通れない道なのかもしれません。 そのうち必要に迫られたら試してみると思います。人生も遅延評価でゴー。:-)
C++の場合の参考です。 (スコア:1)
SIMD の前に重要なのは、文字列の評価回数ですね。それもlisp的な評価じゃなくて、生のbyte stream イメージで。
wc みたいな単純なプログラムの場合、最速 1char/cycleで評価したいじゃないですか。cpu clock が 1GHz なら 1Gchar/sec.
ところが、diskはそんなに早くないし、disk から cpu で生に見えるまでに何回もコピーされてくる。でよくわかならいので、オイラは100Mchar/secを目標においています。それでも一文字を処理するのに10cpu cycle. 本当は 2.2GHz の cpu なんで 22 cycle/char.
長くなるので回数は減らして、オイラ自作 vs GNU wc ( Linux なんで )で、
gnu wc
real 0.09 user 0.08 sys 0.00
real 0.09 user 0.08 sys 0.00
自作
real 0.03 user 0.02 sys 0.00
real 0.03 user 0.01 sys 0.01
うう、オイラのマシンは古いんです。
もっと長いデータ
2147210 8215650 109663607 p1.def
gnu wc
real 2.55 user 2.41 sys 0.11
real 2.54 user 2.38 sys 0.14
自作
real 0.51 user 0.30 sys 0.20
real 0.52 user 0.28 sys 0.23
ちなみに自作は g++ で、strcmp みたいな simd 関数未使用、マルチスレッドです。使ったマシンに core は１つしかないので、スレッドの効果は出ていません。simd も考えたのですが、単語は短いし、目標に到達していたので..
Re:C++の場合の参考です。 (スコア:0)
# ２バイト毎に見てくのは可能なのかなぁ？
Re:C++の場合の参考です。 (スコア:1)
2バイトで見るには、たとえば、short *dst, *src ; for( ; *pnt & 0x00ff != 0 && *pnt & 0xff00 != 0 ; *pnt++=*buf++) ; みたいにするんでしょうね。あるいは、*src & *src >>8みたいに圧縮するか。 アラインしていないデータとか境界部分の処理がめんどうです。
ずっと昔のcomputer today という雑誌にその手の連載がありました。
Re:C++の場合の参考です。 (スコア:0)
# 投稿大のもーた御大のアレ？＞Computer Todayの連載