haskell-jp / questions #43

お疲れ様です。
https://qiita.com/mod_poppo/items/03fc14f693b601e0a00f
なぜIORefだと遅いのでしょうか。
自分でベンチマークとるのが一番かもしれませんが。
あと既出だったらすみません。
:man-bowing:
IORefだとヒープで、StateTだとスタックにのるとかあるのでしょうか。
この程度のコードであれば GHC の最適化によって i と acc が正格評価 & unbox 化されることが期待でき1、 C言語での普通のローカル変数を使ったようなアセンブリコードが(たぶん)出力されます。

とあるとおり、やっぱりGHCにとって普通の引数の方が最適化を利かせやすいところにあるんじゃないっすかね。(その最適化の詳細を知りたいんだよ!という意味であればすみません、わかりません... :bow:)
記事にも書いてありますが, IORef の場合余分なポインタによる Boxing が挟まるからです.
通常は,そのままデータにアクセスすればいいですが, IORef の場合一度 IORef データのポインタから実際の IORef データにアクセスし,さらにそこに格納されているポインタからデータにアクセスする必要が出てきます.

特に今回の記事の内容だと,Stateの場合もインライン展開と正確性解析によるwrapper変換がうまく入ります(GHC 8.6.3 ではうまく最適化されていることを確認しました)が, IORef はうまく上記の方法で最適化できないため Boxing のままになっているのが大きな差を生んでる原因だと思います
ありがとうございます
いくつかベンチマークをしての追記なのですが, IORef で書かれたコードはインライン展開からの変換による最適化が入りにくいようです.例えば, readIORef などを readMutVar# などのプリミティブ命令に変換した後特に最適化が入りにくいのに対し, State はタプルを使った単純な関数の場合が多く, IORef を使ったコードに比べかなりのレベルまでインライン展開され joinrec を使った loop optimization がかなり入りやすいようです.もちろん,今回の記事のように wrapper 変換も入りにくいため,一般には IORef より State の方が最適化が入りやすいため高速な処理が期待できそうです.

なので, IORef の Boxing によるオーバーヘッドというよりは最適化がうまく入らないデメリットが大きそうですね
あ,ついでに上の話は GHC 8.6.3 で調べたので,他のバージョンだと違った結果になるかもしれません(おそらく,他のバージョンも同じ状況だとは思うんですが)
ついでに, wrapper 変換を避けるために書き直したベンチマークコードを上げておきます
https://gist.github.com/mizunashi-mana/1de1f69f2723d7cef51c9a57c506fdcf
@tech has joined the channel
someCalculationWithFastMutInt :: IO Int
someCalculationWithFastMutInt = do
  sumRef <- newFastMutInt
  writeFastMutInt sumRef 0
  forM_ [0..10000 * 10000] $ \i -> do
    s <- readFastMutInt sumRef
    writeFastMutInt sumRef $! s + (i `rem` 3)
  readFastMutInt sumRef

http://hackage.haskell.org/package/ghc-8.6.1/docs/FastMutInt.html
これだとunboxされるのですね。
微妙に納得いかないですね。
別件でSTRefもIORefと同様でした。
次の疑問はなぜIORefがunboxされないのかというところです。
http://hackage.haskell.org/package/unboxed-ref
すでにそういうパッケージがありますね。
GHC ではスタックとヒープどちらに割り当てるかなどを扱うような段階より,ずっと以前の表層の部分で多くの最適化が行われます.特に worker/wrapper 変換は Haskell のプログラムをより効率の良いプログラムに変換するような最適化で(厳密には, Core-2-Core ですが),単純に Int や Char などの unbox 型をラップした Boxing な型に対して書かれた幾つかの制約を満たす関数をアンラップする関数と unbox 型に対して処理を行う関数に分解することで,wrap/unwrap のオーバーヘッドを無くし不要なヒープ確保を抑えるといったものです.

例えば,

sumInt :: [Int] -> Int
sumInt = go 0
  where
    go acc []     = acc
    go acc (x:xs) = go (acc + x) xs


という関数を考えてみた時, (+) :: Int -> Int -> IntI# i1 + I# i2 = I# (i1 +# i2) と定義されますから (+) 演算をする分だけ unwrap/wrap を繰り返すことになりますが,以下のように変形できればその操作を抑えることができます.

sumInt :: [Int] -> Int
sumInt = go 0
  where
     go (I# i) = goWork i

     goWork acc []        = I# acc
     goWork acc (I# x:xs) = goWork (acc +# x) xs


この変形をより一般的に自動で行うのが worker/wrapper 変換による unbox 化です.もちろん,この後の段階で unbox 型の引数はヒープ確保を起こさない形に翻訳される可能性が高いです.ただこの変換は,見ての通りどの部分で I# の unwrap/wrap が起きるか分かっていないとその部分を削減できないため,インライン展開がうまく行われるかどうかに強く依存します.

さて,本題の IORef がなぜ unbox されないかですが,厳密には IORef が unbox 化されないというより, IORef を使ったコードは最終的に IORef を操作するランタイム命令 readMutVar# / writeMutVar# までしかインライン展開されないため, unwrap/wrap の処理がインライン展開後も自動的に構文だけからは判断できず, worker/wrapper 変換が適用されないというのが大きいと思います. readMutVar# / writeMutVar# の動作特性を情報として別に持っておいて worker/wrapper 変換を適用できるようにするのは可能ではありますが,かなりヒューリスティックな部分となるのでおそらく実装されていないのだと思います.もちろん,これは STRef でも同じ話になります.
ついでにですが,実行性能の差の要因は追記でも述べた通り unbox 化だけではないようです.なので,上の unboxed-ref を使えば worker/wrapper 変換は入るようになると思いますが,他の最適化が入りにくくなり結局 State の方が速くなるんじゃないかと思います(これは未検証なので,後でやってみたいと思います)
-O: State < IORefU < Rec < IORef
-O2: Rec < State < IORefU << IORef
となりました.そこまで有意差ではないと思いますが IORefU の方が State より遅い傾向が見られましたね.中間コード自体はほぼ同じでしたが,やることによっては差が出る場合もあるかもしれません.
https://gist.github.com/mizunashi-mana/176875a0af98578d0d9bafd2dabdf876
ありがとうございます!これって、計測はそれぞれの someCalculation* を適当な main 関数に含めて実行ファイル作ってtimeコマンドでやったんですかね?
それともcriterionかなにか使ったんすか?
time コマンドでやりました
criterion でやる場合は,もっと繰り返し数少なくした方が良いと思いますね
@imawaki_k has joined the channel
標準出力に文字列を出力するIO ()の振舞いをHspecでテストするにはどうすればよいでしょうか?.たとえば標準出力に指定の文字列"Hello, world."が,確かに出力されることを確認したいとき,どうすればいいでしょう.
手前味噌で恐縮ですが、 https://haskell.jp/blog/posts/2018/main-tester.html とかいかがでしょうか?
おお.ありがとうございます.まさにこれです.
Cabalが作ってくれるPaths_hogeの詳しい仕様とか使い方ってどう検索すれば出てきますかね……もしくは公式をよく読めばある?
アッめっちゃ書いてある。ちゃんと読まないとダメですね……。ありがとうございます
@talw10 has joined the channel
@furu.furu.kk.204 has joined the channel
@ytk.nishimura has joined the channel
@sleepy.st818 has joined the channel
@3bmnltlllpn has joined the channel
@yukimemi has joined the channel
数独を解くコードを書いてみました。変な所があればご指摘いただけると嬉しいです。
https://gist.github.com/gaxiiiiiiiiiiii/0fab7374d7c3ef8f2a0801972aa0aea5
ぱっと見て気づいたところを。
- length empties == 0null で置き換えられるかと。
- data Tree = Node Board [Tree]http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Tree.htmlTree で表すことができるかと(型定義だけしか要らなければ特に必要はないかと思いますが、もし便利な関数があれば使ってみるのも良いかと
classifydiv で代用できそう
head es のところは、その前のパターンマッチで e:_ とでも書けば取り出せると思います
tree のところで毎回 empties を生成しているのはもったいないですね
終了の判定を treeisSolved の実質二ヶ所でやってるのももったいないです。
細かいスタイルのお話ですがもう3点ほど。

- (==) (row c) は「セクション」という (== (row c)) と置き換えられるはずです。
- さらに、「関数呼び出しは一番結合の優先順位が高い」という事実を利用すれば、 (== row c) と書けます。ほかにも同様に括弧を取り除ける箇所があるはずですので、探してみてください。
- overWrite (Cell _ r c b) n = Cell n r c b は、せっかくレコード型を使っているんですし、 c { num = n } と書いてはいかがでしょうか?

加えて、この手の細かいスタイルに関する指摘は、大抵HLintというツールが自動でやってくれるはずです。
参考: https://haskell.e-bigmoon.com/posts/2018-01-29-awesome-hlint.html
みなさん、ありがとうございます!修正してみます!!
細かい話。
https://gist.github.com/gaxiiiiiiiiiiii/0fab7374d7c3ef8f2a0801972aa0aea5#file-sudoku-hs-L10
Showのインスタンスはあまり変えないほうがいいと思う。詳しくは
http://www.stephendiehl.com/posts/strings.html


-- Ummm
instance Show Cell where
    show (Cell n _ _ _) = show n


-- Do this instead
showNum :: Cell -> String
showNum (Cell n _ _ _) = show n
あとは実務レベルのコードにするならコードの整形とHaddockコメントがほしいね。コメントがないから頭が弱い自分にはそれぞれのデータ型、関数がなにをしてるのかよくわからない。。
見て頂く立場なのに、読みにくくて申し訳ないです。読みやすさも心がけます。。。
stack 経由で使われている ghc や haddock のバージョン番号を調べるにはどうしたらいいのでしょうか? stack 自体のバージョン番号は stack --version ででてくるのですが… (しょうがないので ~/.stack/programs を直接見て確認したりしているのですが)
stack exec ghc -- --version
stack exec haddock -- --version のことですか?
をを、 exec をつければよかったのですね。 stack haddock --version とかしても出てこなかったので気付かなかったです^^;
あれ、でもだめっぽいですね…
% stack exec ghc --version                              ~/haskelltest/hoge
Invalid option `--version'

Usage: stack exec CMD [-- ARGS (e.g. stack exec -- ghc-pkg describe base)]
                  ([--plain] | [--[no-]ghc-package-path] [--[no-]stack-exe]
                  [--package ARG] [--rts-options RTSFLAG] [--cwd DIR]) [--help]
  Execute a command
あ -- がいるのか!
https://employment.en-japan.com/engineerhub/entry/2017/08/25/110000#%E8%A9%A6%E3%81%97%E3%81%AB%E4%BD%BF%E3%81%A3%E3%81%A6%E3%81%BF%E3%81%BE%E3%81%97%E3%82%87%E3%81%86Haskell%E3%81%A7%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%A8%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97 より。
これはstackの残念な仕様で、stackコマンド経由でghcに--versionなどのオプションを渡そうとした場合、意図に反してstackコマンドが(正確には、stackコマンドのサブコマンドであるstack ghcが)--versionオプションを解釈してしまうことによるエラーです。 これを回避するには、--versionオプションより前に--を渡します。
ありがとうございます、やっとわかりました。 :slightly_smiling_face: