パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

Haskellで速いwcを書いてみよう(10)」記事へのコメント

  • どこにあります?興味あるな。
    これ [freebsd.org]と大体同じ?
    普通のgnu wc って結構遅いと思います。どこが悪いのかあまりわかりませんでしたが。
    C++で書くときに、私が気にするのは、どうやって一文字ずつ判断をやめるか。せっかくの32/64bitマシンなんで8bit単位じゃなくて64bitで調べたい。64bitで調べることができれば単純に見て、8bitの8倍速。さらに32bitか64bitの1ワードから1バイトを切り出す余分なコードが不要に。
    で、G++/glibc の strcmp, memchr を使うと画期的に早くなります。

    ああ、harshellの人には関係ないですね。
    • by kr (10950) on 2007年10月31日 0時43分 (#1242203) 日記

      はい、元データはそれ [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と比較するとどうなのか試してみました。

      % ident /usr/bin/wc
      /usr/bin/wc:
           $FreeBSD: src/lib/csu/i386-elf/crti.S,v 1.7 2005/05/19 07:31:06 dfr Exp $
           $FreeBSD: src/lib/csu/i386-elf/crtn.S,v 1.6 2005/05/19 07:31:06 dfr Exp $
           $FreeBSD: src/lib/csu/common/crtbrand.c,v 1.4 2003/10/17 15:43:13 peter Exp $
           $FreeBSD: src/lib/csu/i386-elf/crt1.c,v 1.14 2005/05/19 07:36:07 dfr Exp $
           $FreeBSD: src/usr.bin/wc/wc.c,v 1.21 2004/12/27 22:27:56 josef Exp $
      % time /usr/bin/wc < /usr/share/doc/en/books/handbook/book.txt
         72266  323341 3196121
      0.059u 0.000s 0:00.06 83.3%     9+158k 0+0io 0pf+0w
      0.051u 0.007s 0:00.06 83.3%     12+212k 0+0io 0pf+0w
      0.059u 0.000s 0:00.06 83.3%     12+211k 0+0io 0pf+0w
      0.059u 0.000s 0:00.05 100.0%    11+184k 0+0io 0pf+0w
      0.059u 0.000s 0:00.06 83.3%     11+184k 0+0io 0pf+0w
      速っ。ここで書いた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風の高速化を図るのも避けて通れない道なのかもしれません。 そのうち必要に迫られたら試してみると思います。人生も遅延評価でゴー。:-)

      親コメント
      • strcmp 等は本当にチューンされています。始めは自作でいいじゃん と思っていましたが、とても全部のアセンブラ命令を知っていないと真似できないレベルで手が入っています。
        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 は1つしかないので、スレッドの効果は出ていません。simd も考えたのですが、単語は短いし、目標に到達していたので..
        親コメント
        • ispace()相当の事を、テーブル引きや巨大switch文にすると速くなりそうですね。

          # 2バイト毎に見てくのは可能なのかなぁ?
          • テーブル化は難しいです。コード書くのは簡単だけど、テーブルが大きすぎると、キャッシュに入りきらない。小さく切り詰めると、切り詰めるための、オーバーヘッドがでる。

            2バイトで見るには、たとえば、short *dst, *src ; for( ; *pnt & 0x00ff != 0 && *pnt & 0xff00 != 0 ; *pnt++=*buf++) ; みたいにするんでしょうね。あるいは、*src & *src >>8みたいに圧縮するか。 アラインしていないデータとか境界部分の処理がめんどうです。
            ずっと昔のcomputer today という雑誌にその手の連載がありました。
            親コメント
            • キャッシュは…1バイトずつ見る場合ならともかく、2バイトずつ見る場合を1次キャッシュに全部納めるのは難しそうですね(Athlon 64なら収まるかな?)。

              # 投稿大のもーた御大のアレ?>Computer Todayの連載

人生unstable -- あるハッカー

処理中...