haskell-jp / questions #98 at 2021-09-19 15:28:42 +0900

はじめまして。


このリポジトリを見つけ、Haskellだけ妙に遅いのが気になり高速化してみようと思ったのですが、それ以前にわからないところもあり質問させてください。

mapM_ print $ filter (\i -> isMunchausen i i 0 cache) [0 .. 440000000]
なぜこれで順次数値が表示されるのでしょうか?
filterのイメージではTrueの要素だけか格納された[0,1,3435,438579088]というものがまず生成されて、その後いっぺんにprintされると思ったのですが。

{-# LANGUAGE Strict #-}
{-# LANGUAGE StrictData #-}
を有効にし、cacheをData.Vector.Unboxedにしてみたところ最初2分のものが1分くらいになったのですが、Goは8秒切り、Zigは4秒を切ります。
Haskellとはこのくらいの速度差があるものなのでしょうか?

よろしくお願いします。

これ以上高速化する術はわかりませんが、「なぜこれで順次数値が表示されるのでしょうか?」については一言で言うと「遅延評価のおかげ」です。
遅延評価のおかげで filter 関数が isMunchausen i i 0 cache が True を返す度に該当する値を一つずつ返すような振る舞いになります。

高速化についてですが、Haskellのdiv/modはquot/remに比べて遅いので、結果が変わらない場合（引数が非負である場合）はquot/remを使うという手がありますね

遅延評価のイメージが理解できていないのですが、StrictとStrictDataをファイル先頭に書いたので遅延評価はなくなっているのだと思っていました。

quotRemというものを使ってみたところ40秒になり結果の数値も変わりませんでした。

igrepさん、mod_poppoさんありがとうございます。

Strict 拡張はあらゆる処理から遅延評価をなくしてくれる、というものではなく、 Strict を有効にしたモジュール内で定義した関数における、名前のついた各引数について ! を付けて一段正格に評価する、というものなので、実際にはこの場合

isMunchausen number n total cache

を

isMunchausen !number !n !total !cache

に書き換えたり、

(\i -> isMunchausen i i 0 cache)

を

(\!i -> isMunchausen i i 0 cache)

に書き換えたりするまでの効果しかありません。（あと、 let cache = ... も let !cache = ... に変わるはず）。
※ちなみに、 Strict 拡張を有効にすると StrictData も同時に有効になります。
詳しくは手前味噌ですが https://haskell.jp/blog/posts/2020/strict-gotchas.html をご覧ください。

ありがとうございます。
これから読ませていただきます。

ncgとllvmでアセンブリコードがどう変わるかまで追っていませんが
• div/modからquot/remに換える
• cacheをunboxed vectorに換える
• llvmバックエンドを使う
の3つで他の言語並みに速くなります。
手元では-O2でビルドすると

% hyperfine ./haskell/dist-newstyle/build/x86_64-osx/ghc-8.10.7/haskell-0.1.0.0/x/haskell/opt/build/haskell/haskell ./rust/target/release/rust
Benchmark #1: ./haskell/dist-newstyle/build/x86_64-osx/ghc-8.10.7/haskell-0.1.0.0/x/haskell/opt/build/haskell/haskell
  Time (mean ± σ):      3.277 s ±  0.080 s    [User: 3.241 s, System: 0.026 s]
  Range (min … max):    3.170 s …  3.403 s    10 runs

Benchmark #2: ./rust/target/release/rust
  Time (mean ± σ):      2.543 s ±  0.073 s    [User: 2.522 s, System: 0.017 s]
  Range (min … max):    2.443 s …  2.669 s    10 runs

Summary
  './rust/target/release/rust' ran
    1.29 ± 0.05 times faster than './haskell/dist-newstyle/build/x86_64-osx/ghc-8.10.7/haskell-0.1.0.0/x/haskell/opt/build/haskell/haskell'

https://github.com/jabbalaci/SpeedTests/compare/master...maoe:haskell にpushしました

よく見たらgenerateの一つ目の引数は+1しないとダメそうですね。あとで時間があるときに直します。

READMEいわく「If you know how to make something faster, let me know!」とのことなんでPull requestを送ってみてはいかがでしょうか！

-fllvmがWindowsで試せず、-fllvmをmacでやってみたところ、44.8秒が5.26秒になりました。
-fllvm -O2だと3.95秒でした。

ここまで変わるとは思っていませんでした。
ありがとうございます。

Wikipedia曰くZigもLLVMを使っているらしいので、やっぱLLVMすごいですね... :open_mouth:

PR送っておきました https://github.com/jabbalaci/SpeedTests/pull/16

余談ですが
アルゴリズム上は10進数なら割り算をシフトで置き換えられるので、（それで割り算をなくせる）
このコードのように10倍くらい高速化できるはずです。
https://gist.github.com/junjihashimoto/fe75780dba77ef3e33e8be605b3cf0c5

なので問題にあったData.Decimalのようなものをつくれればいいかと思ったのですが、
まだできてないです。

https://hackage.haskell.org/package/Decimal-0.5.2/docs/Data-Decimal.html
こちらは固定小数点で内部の表現はIntegerですね。