パスワードを忘れた? アカウント作成

krさんのトモダチの日記みんなの日記も見てね。 スラドのストーリを選ぶための補助をお願いします。

481248 journal

krの日記: Haskellで速いwcを書いてみよう(10) 6

日記 by kr

前回のエントリの続きです。

もうちょっと高速化できないか考えてみます。

どんなプログラムでも、高速化の要は「頻繁に実行される箇所を少しでも速くする」ことです。 そういう点では、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の日記を書いたけど、最初から(だけ)飛ばしすぎだ……。

481250 journal

krの日記: Haskellで速いwcを書いてみよう(9)

日記 by kr

前回のエントリの続きです。

ここで、念のため、メモリリーク等が起こっていないか確認してみようと思います。 最初に書いたprog6のように、 イタレーションの途中でどこか気付かぬ内にメモリを消費していっているかもしれません。 小さなファイルを与えても気付かないリークが、大きなファイルを入力として与えた時に発覚してしまうかもしれません。

ということで、ここでは、4倍量の入力を与えて、使用メモリが変化するかどうか確認してみました。

安直に、これまでの評価に使っていたhandbook.txtを、4つ並べた入力を喰わせてみます。 使用メモリサイズは、安直にtime(1)で調べました。

% cat /usr/share/doc/en/books/handbook/book.txt | /usr/bin/time -l ./prog8
     72266 323341 3196121
        0.50 real         0.47 user         0.00 sys
      1872  maximum resident set size
       260  average shared memory size
        76  average unshared data size
       128  average unshared stack size
       228  page reclaims
         0  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
         9  signals received
         1  voluntary context switches
       166  involuntary context switches

% cat /usr/share/doc/en/books/handbook/book.txt /usr/share/doc/en/books/handbook/book.txt /usr/share/doc/en/books/handbook/book.txt /usr/share/doc/en/books/handbook/book.txt | /usr/bin/time -l ./prog8
289064 1293364 12784484
        2.01 real         1.89 user         0.01 sys
      1872  maximum resident set size
       261  average shared memory size
        76  average unshared data size
       128  average unshared stack size
       228  page reclaims
         0  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
        38  signals received
         1  voluntary context switches
       676  involuntary context switches

ということで結果を見ると、入力が4倍になっているのに比例して実行時間も4倍になっている一方、メモリ使用量はまったく変わっていません。 期待通り、入力データの長さnに対して、時間コストO(n)、空間コストO(1)になっているようです。

大雑把な確認ではありますが、特に問題はなさそうなので、再び更なる速度向上が見込めないか試みてみます。

もうちょっとだけ続きます。

481252 journal

krの日記: Haskellで速いwcを書いてみよう(8) 2

日記 by kr

前回のエントリの続きです。

前回のprog7はそれなりの速度で走りましたが、もっと速くできないでしょうか。 いくつかの改善点を思い付きますが、ここではまずwc'のイタレーションを高速化することを考えてみます。

で、まあちょっと反則気味ではあるのですが、ここでghcの独自仕様部分を使ってみることにします。具体的には、unboxed typeを使って、 wc'の引数処理を高速化を試みます。これはてっとり早く言えば、HaskellのInt型でなく、Cのintと同様のビット表現を使うことにしちゃえということです。

{-# OPTIONS_GHC -fglasgow-exts #-}
-- prog8
import Data.Char
import GHC.Base

wc:: String -> ( Int, Int, Int )
wc = wc' 1# 0# 0# 0#
    where
      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は変わらないので今回も省略です。このプログラムをprog8とします。

このプログラム、前回のprog7よりむしろ最初に書いたprog6に似ています。 wc'の最初の4つの引数について、unbox型にしたおかげ(?)で、正格適用オペレータを使わずに、却って(見掛け上)簡単になりました。 その分、整数の加算などに特別な演算子を使わなくてはならなくなりましたが、例えばOCaml使いの人にとっては、むしろ親近感の湧く(?)コードになったかもしれません。:-)

実行時間を測定すると、こんなです。

% time ./prog8 < /usr/share/doc/en/books/handbook/book.txt
72266 323341 3196121
0.478u 0.007s 0:00.50 94.0%     337+264k 0+0io 0pf+0w
0.484u 0.001s 0:00.50 96.0%     346+272k 0+0io 0pf+0w
0.463u 0.022s 0:00.50 96.0%     346+272k 0+0io 0pf+0w
0.478u 0.007s 0:00.50 94.0%     342+268k 0+0io 0pf+0w
0.484u 0.002s 0:00.50 96.0%     346+272k 0+0io 0pf+0w

ということで、実時間でおよそ0.50秒です。C版の約0.18秒には及ばないものの、 C++版の約0.71秒は追い抜いて、Haskell版の方が速くなってしまいました。

もっと速くすることもできるでしょうか? まだいくつか速くできるポイントがありますが、それは一先ず置いておいて、ここでちょっと別の確認をしておきます。

ということで、更に続きます。

481254 journal

krの日記: Haskellで速いwcを書いてみよう(7)

日記 by kr

前のエントリの続きです。

前回のプログラムは、メモリ不足に陥って動きませんでした。何が悪かったかと言うと、wc'の各引数の評価が遅延され、 ファイルを読み込んでいる間、1文字毎に

(((( …… )+ 1) + 1) + 1)

という調子で未評価の式が溜ったまま延びていたのです。この式は、プログラムの最後で行数・単語数・文字数を表示する際に、 一気に評価されるハズではあるのですが、そこまで遅延されると未評価の式を保持するメモリが足りなくなります。

というわけで、ここで最初のチューニングは、「遅延させたくない部分を先に評価させる」ようにすることです。

-- prog7
import Data.Char

wc:: String -> ( Int, Int, Int )
wc = wc' !$ 1 !$ 0 !$ 0 !$ 0
    where
      infixl 0 !$               -- left-associative version of $!
      (!$):: (a -> b) -> a -> b
      f !$ x = x `seq` f x
      wc':: Int -> Int -> Int -> Int -> String -> (Int, Int, Int)
      wc' s nl nw nc [] = (nl, nw, 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関数はまったく変わらないので、省略しています。このプログラムをprog7とします。

普通の正則評価オペレータは$!ですが、 これは右結合で、今回は具合が悪いので、wcの中でだけ左結合のオペレータを定義しています。 また、wc'の引数の内、最後の引数は値渡しにしていないことに注意しましょう。 ここは遅延評価の利点を使って、余分な入力をメモリに読み込まないようにしなくてはいけません。

では実行時間を測ってみましょう。

% time ./prog7 < /usr/share/doc/en/books/handbook/book.txt
72266 323341 3196121
0.769u 0.001s 0:00.80 95.0%     338+265k 0+0io 0pf+0w
0.763u 0.007s 0:00.80 95.0%     345+271k 0+0io 0pf+0w
0.769u 0.001s 0:00.79 96.2%     338+265k 0+0io 0pf+0w
0.762u 0.008s 0:00.79 96.2%     321+252k 0+0io 0pf+0w
0.762u 0.007s 0:00.79 96.2%     335+263k 0+0io 0pf+0w

実時間でおよそ0.79秒というところでしょうか。 C++版がおよそ0.71秒でしたから、それには惜しくも及びませんでしたが、 tanakh氏のHaskellチューニング版がおよそ3.79秒だったのと比べれば、 かなり良い成績と言えるかと思います。もっとも、tanakh氏は「チューニングしないといけない部分を分離」したいとおっしゃっていますので、 もしかすると、速度は犠牲にしても何かHaskellらしい実装方法はないかと模索していたのかもしれません。とはいえ、とりあえず速く走らせたいだけなら、難しいことは考えずに、素直に簡単なアプローチを採るのが(少なくとも今回は)良かったようです。

第2版でそれなりに性能向上したのに味をしめ、更に高速化できないか試みてみます。

ということで、続きます。

481255 journal

krの日記: Haskellで速いwcを書いてみよう(6)

日記 by kr

前のエントリの続きです。

ここからが本番で、気持も新たにHaskell版のwcを作り始めます。 まず、せっかくHaskellの標準モジュールにwordsとかlinesとかあるので、 できればこれらを使いたいところではありますが、すでに見た通り、 同じ入力をwordslinesに順に与えるやり方では、メモリがいくらあっても足りません。 入力を読みながら、行数・単語数・文字数を同時に数えていく必要がありそうです。

とっさに良い方法は思いつかないので、ここはwordslinesの使用をすっぱり諦め、 自前で行数や単語数を数えることにします。 これはtanakh氏の改良版や、C・C++版でも同様でした。

深いことは考えず、関数型言語でよくやる末尾再帰のパターンで第1版を書いてみましょう。

-- prog6
import Data.Char

wc:: String -> ( Int, Int, Int )
wc = wc' 1 0 0 0
    where
      wc':: Int -> Int -> Int -> Int -> String -> (Int, Int, Int)
      wc' s nl nw nc [] = (nl, nw, 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 = do
  cs <- getContents
  let (nl, nw, nc) = wc cs
  putStrLn $ (show nl) ++ " " ++ (show nw) ++ " " ++ (show nc)

このプログラムをprog6とします。アルゴリズムは、tanakh氏のC・C++版にほぼ倣いました。 ベタに再帰を書くのはイマイチHaskellらしくない気もしますが、OCamlやSchemeなどの関数型言語に慣れた人ならば、Haskellを知らなくても却って素直に読めるコードになっているんじゃないでしょうか。

さて、コンパイルして実行してみると……

% ./prog6 < /usr/share/doc/en/books/handbook/book.txt
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.

ということで、実は大きなファイルを喰わすと動きません。

さて何故でしょう、ということで、ここに正格評価型には無いちょっとした罠があったりします。

その続きは次のエントリで。

481260 journal

krの日記: Haskellで速いwcを書いてみよう(5)

日記 by kr

前のエントリの続きです。

tanakh氏は続いてC++とCのプログラムを示します。こちらでも同様に実行時間を測定してみましょう。ちなみにこちらで使ったのは、以下のようなコンパイラです。

% c++ --version
c++ (GCC) 3.4.6 [FreeBSD] 20060305
Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

% cc --version
cc (GCC) 3.4.6 [FreeBSD] 20060305
Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

最適化オプションは付けずに、defaultのままコンパイルしました。(ghcの方も同様です。)

C++版をprog4、C版をprog5として測定してみます。

% time ./prog4 < /usr/share/doc/en/books/handbook/book.txt
72266 323341 3196121
0.671u 0.015s 0:00.71 95.7%     5+185k 0+0io 0pf+0w
0.678u 0.008s 0:00.71 94.3%     5+177k 0+0io 0pf+0w
0.678u 0.007s 0:00.71 94.3%     5+181k 0+0io 0pf+0w
0.687u 0.000s 0:00.70 97.1%     5+183k 0+0io 0pf+0w
0.679u 0.007s 0:00.71 94.3%     5+185k 0+0io 0pf+0w
% time ./prog5 < /usr/share/doc/en/books/handbook/book.txt
72266 323341 3196121
0.180u 0.000s 0:00.18 100.0%    5+178k 0+0io 0pf+0w
0.180u 0.000s 0:00.18 100.0%    4+171k 0+0io 0pf+0w
0.180u 0.000s 0:00.18 100.0%    4+171k 0+0io 0pf+0w
0.180u 0.000s 0:00.18 100.0%    5+178k 0+0io 0pf+0w
0.157u 0.022s 0:00.18 94.4%     5+197k 0+0io 0pf+0w

ということで、C++版の平均実行実時間でおよそ0.71秒、C版でおよそ0.18秒となっています。 tanakh氏の「チューニングした」Haskell版がおよそ3.79秒でしたから、桁が違います。 さすがにCは速いですね。

ということで、「速いHaskell版のwcを書く」のは、ここからが本題です。

続きます。

481263 journal

krの日記: Haskellで速いwcを書いてみよう(4)

日記 by kr

前のエントリの続きです。

tanakh氏は、次に一部の処理を正則処理することで高速化を図ったようです。 ということで、前回のprog2の一部、foldFの定義を、「ここを速くしてみる」とある改良版のfoldFと置き換えました。 また、いくつか名前解決できなかったので、それらしいモジュールを探して追加しました。追加したのは以下のモジュールで、それ以外は氏のページにあるものをコピーしました。

import Data.Array.MArray
import Data.Array.Base
import Data.Array.IO
import Data.Word
import Control.Monad

ということでこれをprog3として測定してみると、

% time ./prog3 < /usr/share/doc/en/books/handbook/book.txt
72266 323341 3196121
3.653u 0.002s 0:03.78 96.5%     359+235k 0+0io 0pf+0w
3.653u 0.001s 0:03.81 95.8%     362+238k 0+0io 0pf+0w
3.629u 0.023s 0:03.78 96.2%     357+235k 0+0io 0pf+0w
3.651u 0.002s 0:03.78 96.5%     359+235k 0+0io 0pf+0w
3.638u 0.015s 0:03.79 96.0%     361+237k 0+0io 0pf+0w

という結果がでました。実時間の平均は3.79秒くらいでしょうか。改良前のprog2が約4.81秒でしたので、確かに少し速くなっています。

氏はここでHaskell版の改良を止めて(少なくともリンク先のページに有る限りは)、次にC++とCを試しています。その結果も再現してみましょう。

続きます。

481265 journal

krの日記: Haskellで速いwcを書いてみよう(3)

日記 by kr

前のエントリからの続きです。

tanakh氏のページの2番目のHaskellプログラムも、一度に入力全体を保持するコードになっているようですので、試してみるのは省略します。そこで氏の3番目のHaskellコード、「そんなことを考えつつ適当にコードを書いていたらこんなものが出来た」とあるプログラム(ここではprog2と呼ぶことにします)を試してみます。

% time ./prog2 < /usr/share/doc/en/books/handbook/book.txt
72266 323341 3196121
4.606u 0.015s 0:04.82 95.6%     334+231k 0+0io 0pf+0w
4.605u 0.015s 0:04.79 96.2%     331+229k 0+0io 0pf+0w
4.613u 0.007s 0:04.78 96.4%     332+229k 0+0io 0pf+0w
4.598u 0.023s 0:04.79 96.2%     334+231k 0+0io 0pf+0w
4.609u 0.015s 0:04.86 94.8%     336+239k 0+0io 0pf+0w

平均して実時間で4.81秒というところでしょうか。 単語数のみ計算する簡単版が約0.80秒でしたから、これはかなりがっかりな結果です。

氏はこのコードを改良して、更に高速にしたということなので、次にはそれを試してみましょう。

続きます。

481269 journal

krの日記: Haskellで速いwcを書いてみよう(2)

日記 by kr

前のエントリからの続きです。

まずはtanakh氏の跡を追ってみようということで、 氏の書いたHaskell版、C++版、C版のwcの実行速度を、手元のマシンで計測してみます。

まずはHaskell版。使ったコンパイラは、

% ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.6.1

というものです。

早速、氏の「7月27日あたりで書いた全く直截的なコード」とあるものをそのままコピーして、コンパイルしました。 テスト用入力としては、手元にあってそこそこ大きいテキストファイルということで、 /usr/share/doc/en/books/handbook/book.txt(FreeBSD handbook)を喰わせてみました。

……が、いきなり挫折で、Stack space overflowと出て動きません。

実はこの結果は予想していました。読み込んだテキストをすべてメモリに保持して、行数・単語数・文字数をそれぞれ計算しているので、 まあ当然かなと。(ちなみにHaskellは文字列をUnicode文字のリストとして保持するので、そういうことをすると、やたらメモリを食います。)

念のため書いておくと、例えば単語数だけ表示するプログラムだったら、同じように書いてもちゃんと動きます。

-- prog1
main = getContents >>= putStrLn . show . length . words

一応この速度を測っておくと、以下のようでした。(2回目以降のコマンドラインと出力結果は省略)

% time ./prog1 < /usr/share/doc/en/books/handbook/book.txt
323341
0.767u 0.007s 0:00.80 95.0%     345+271k 0+0io 0pf+0w
0.758u 0.016s 0:00.80 95.0%     328+257k 0+0io 0pf+0w
0.772u 0.001s 0:00.80 96.2%     314+246k 0+0io 0pf+0w
0.766u 0.007s 0:00.80 95.0%     331+260k 0+0io 0pf+0w
0.752u 0.022s 0:00.80 96.2%     344+269k 0+0io 0pf+0w

実時間で0.80秒ですね。 一見、ファイルを全部読み込んでいるようにも見えますが、実際には1単語分の文字列を構築しては捨てていくので、最長単語が保持できるメモリさえあれば動きます。遅延評価万歳。

ただし行数と文字数を表示しない点で、今回のお題に合わないので、これはあくまで参考ということで。

続きます。

481273 journal

krの日記: Haskellで速いwcを書いてみよう(1)

日記 by kr

このコメントで言及されているページを見て、 Haskellのパフォーマンスチューニングというのは実際に難しいのかどうか、自分でも試してみることにしました。

お題は「Haskellで速いwcコマンドを書く」です。上記tanakh氏のページに倣い、ここで書くwcコマンドは、

  • いつも標準入力からのみ読む。(ファイル名の指定とかは省略)
  • 行数、単語数、文字数を表示する。
  • 文字はCのchar相当。(Unicodeとか複雑なことは考えない)
  • 単語は空白区切りで数える。(punctuation等も(空白でないので)単語内の文字とする)
  • 行数は改行文字の数を数える。(各行の最後は必ず改行で終わると仮定する)

という仕様にしておきます。

なお、実行時間の測定は以下の環境で行ないました(dmesgより)。

OS:
FreeBSD 6.2-STABLE
CPU:
Intel(R) Pentium(R) M processor 1.10GHz (1097.26-MHz 686-class CPU)
real memory =
1324679168 (1263 MB)
avail memory =
1288232960 (1228 MB)

実行時間測定方法は、安直にtcsh組み込みのtime(1)で5回ほど測定してみるということで。

長くなりそうなので、適宜エントリを分けながら続きます。

関連エントリの全目次

  1. はじめに (このエントリ)
  2. まずは先人の足跡を辿る
  3. 先人の到達点その1
  4. 先人の到達点その2
  5. C++版とC版の実行時間
  6. とりあえず第1版 (ここからチューニングを始めます)
  7. 最初の改良 (C++版の背中が見えたかな?)
  8. 第2の改良 (C++版より速くなりました)
  9. ちょっと一休み (メモリ使用量を大雑把に確認)
  10. とりあえず完成 (C版より速くなりました)
typodupeerror

一つのことを行い、またそれをうまくやるプログラムを書け -- Malcolm Douglas McIlroy

読み込み中...