haskell-jp / questions #107 at 2025-01-28 21:34:06 +0900

ダメ元の質問です。 C++ ライブラリの写経モジュールが、元 (C++ 実装) の 10 倍遅くて悩んでいます。 Lct.hs のどこが遅いか、良ければエスパーお願いします :pray: 。質問用のリポジトリ全体はこちらです:
https://github.com/toyboot4e/lct-bench
ぱっと見の印象なのでアレですけど、PrimMonadをフル活用するとインライン化あるいは特殊化が働かなかった時に破滅しそうですね。その辺がボトルネックになっているかの確認はしましたか?
ああ、適宜 stToPrim を使っているんですね。
ありがとうございます! ちょうど全体の感想をお伺いしたかったところです。
Lct.hs の全ての関数を INLINE 化したところ 1.64 秒になりました。
(INLINE 以外の関数に stToPrim を付けのは当てずっぽうです)
特殊化がボトルネックになっているか、他に調べる方法はありますか?
-ddump-prep で最適化後のCoreを見てみる、とかですかね
ありがとうございます。 Core は僕の手に余るので、具体的な型に置き換えて型パラメータを削除してみます。
手元で触った感触としては、要素の型(`Sum Int`)についての特殊化を発動させるのが重要そうです。`splay` と rotate にINLINABLEをつけてやると高速になりました。
ウオオオオ INLINABLE0.678 秒になりました。爆速です!!!
これまでの経験では`INLINABLE` にはほぼ効果が無かったのですが、特に private な関数に INLINABLE を付けると良いのかもしれませんね。
今回も本当にありがとうございました。他のライブラリも同様に高速化して行きます! :haskell: :haskell:
rotate, splay に INLINE を付けた場合、よく見るとエラー表示があったので、インライン化に失敗していたかもしれません (添付)
後学のためにCoreの見方について軽く説明しておくと、GHCに -ddump-to-file -ddump-prep を渡すと最適化後のCoreがファイルとしてどこかに書き出されます(cabalのプロジェクトに適用した場合は、`dist-newstyle/` のどこかに *.dump-prep というファイルができるので探してください)。特殊化されているかを見たい関数名で検索して、いかにも辞書渡しな感じがしたら特殊化されてないでしょう(例えば、 Lct.splay @GHC.Types.IO @(Data.Semigroup.Internal.Sum ) Control.Monad.Primitive.$fPrimMonadIO $dMonoid_r9JA $dUnbox_r9JB ipv63_s9Rp sat_sagy が見つかったら $fPrimMonadIO, $dMonoid_r9JA, $dUnbox_r9JB が辞書)。一方で、特殊化が起こった場合は今回は
Main.$w$ssplay [InlPrag=INLINABLE[2]]
  :: 
     -> GHC.Prim.MutableByteArray# GHC.Prim.RealWorld
     -> Data.Vector.Unboxed.Base.MVector
          (Control.Monad.Primitive.PrimState ) Lct.IndexLct
     -> Data.Vector.Unboxed.Base.MVector
          (Control.Monad.Primitive.PrimState ) Lct.IndexLct
     -> Data.Vector.Unboxed.Base.MVector
          (Control.Monad.Primitive.PrimState ) 
     -> Data.Vector.Unboxed.Base.MVector
          (Control.Monad.Primitive.PrimState )
          Data.Bit.Internal.Bit
     -> Data.Vector.Unboxed.Base.MVector
          (Control.Monad.Primitive.PrimState )
          (Data.Semigroup.Internal.Sum )
     -> Data.Vector.Unboxed.Base.MVector
          (Control.Monad.Primitive.PrimState )
          (Data.Semigroup.Internal.Sum )
     -> Data.Vector.Unboxed.Base.MVector
          (Control.Monad.Primitive.PrimState )
          (Data.Semigroup.Internal.Sum )
     -> 
     -> GHC.Prim.State# GHC.Prim.RealWorld
     -> GHC.Prim.State# GHC.Prim.RealWorld

という関数が生成されました。
でかい関数はインライン化しづらいと考えて、適宜SPECIALIZEやINLINABLEを使っていくのが重要そうです。今回は私が試した感じでは Lct.hsSPECIALIZE ... (Sum Int) ... を書いてもあまり高速にはなりませんでしたが……。
僕でも認識できる違いで驚きました。 dump を見たところ、 INLINABLE を付けた場合のみ lct-test.dump-prep (実行ファイル側の dump) に Main.$w$ssplay のような関数が生成されており、もしやこれが特殊化なのかと思いました。この辺りの知識を付けると、エスパーと言わず自分で調査できそうですね。非常に助かります!