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
元データって (スコア: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の連載