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

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

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

    ああ、harshellの人には関係ないですね。
    • はい、元データは それ [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]の 「ふらふらと何にも考えないで書いたコード」「適当に書いたコー

      • 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の連載

「科学者は100%安全だと保証できないものは動かしてはならない」、科学者「えっ」、プログラマ「えっ」

処理中...