haskell-jp / questions #101 at 2022-07-28 18:30:52 +0900

再帰的な型をキーとする要素数の少ないMapに対して頻繁にlookupをかけるコードを書いており、高速化したいです。はじめはHashMapを使おうと思っていたのですが、hashWithSaltをプリミティブな演算のみで実装しても再帰のオーバーヘッドが大きかったのか、かえって遅くなってしまいました

どんなキーなのか気になりますね

直観主義命題論理の命題を表す次の型Exprをキーとして持っています：

data Expr =
    ExprVar Int
  | ExprBottom
  | Implies Expr Expr
  | And Expr Expr
  | Or Expr Expr
  deriving (Eq, Ord)

なるほど
ハッシュの計算が重いなら HashMap よりも containers の Data.Map.Strict.Map の方が軽いかもしれませんね
（こちらは Ord の比較を使う

結局比較したら`Data.Map.Map` を使うのが一番はやかったみたいです、プロファイリングするとcompareが無視できない時間走ってるみたいですが、`deriving Ord` のcompareってけっこうはやいんですかね、

ハッシュの計算が（ハッシュ関数の設計にもよりますが）`Expr` の値を全部なめるのに対して、`compare` は違いがあった時点で打ち切るのが効いてるのかもしれませんね
計測してみないとなんともですが

たとえば、`Expr` のハッシュを先に計算して、それ以降`type ExprWithHash = ExprWithHash Expr Int` みたいな形で扱うのって有効なやり口ですかね

キャッシュも試してみる価値ありそうですね IntMap が使えれば効率よさそうですし（実装までは見てませんが

ハッシュのキャッシュを取るようにしてみたところ、結局`HashMap` も`HashSet` はこの条件下だと`Map` と`Set` より遅かったのですが、`IntMap` と`IntSet` に変えたら最速になりました

後思い浮かぶところとしては、 hashWithSalt を末尾再帰で計算してみるってところでしょうか。すでにやっていれば恐縮ですが

遅かった頃の実装だとhashWithSaltを以下のように計算していたのですが、計算が二股に別れるような再帰は末尾再帰に変換できますか？

lcgs i =
  (48271 * i) `remInt` 0xffff

hashWithSalt' :: Int -> Expr -> Int
hashWithSalt' salt expr =
  case expr of
    ExprVar t      -> lcgs (salt + t) 
    ExprBottom     -> lcgs salt
    Implies e1 e2  -> lcgs (hashWithSalt' salt e1 * 5 + hashWithSalt' salt e2) * 3 + 0
    And     e1 e2  -> lcgs (hashWithSalt' salt e1 * 5 + hashWithSalt' salt e2) * 3 + 1
    Or      e1 e2  -> lcgs (hashWithSalt' salt e1 * 5 + hashWithSalt' salt e2) * 3 + 2

はい。できるはずです。相互末尾再帰が必要かも知れませんし、結構面倒くさくなるとは思いますが...

Generics版の実装を見ると、そもそも枝分かれさせるような実装になってないですね。
https://hackage.haskell.org/package/hashable-1.4.0.2/docs/src/Data.Hashable.Generic.Instances.html#line-38

ちなみにGenericsでのインスタンスは試したんですか？

試しましたが、かなり遅かったです