ASTのハッシュコードをキャッシュするにはどうすればよいですか？

Question

私はF＃の言語に取り組んでいますが、テストでは、ランタイムは時間の90％以上を平等のために費やしています。そのため、言語は使用できなくなるほど遅いです。計測中、GetHashCode関数はオーバーヘッドの原因としてリスト上でかなり高い値を示しています。何が起きているのかは、メソッド呼び出し中に、メソッド本体（Expr）を呼び出し引数とともに辞書のキーとして使用し、ASTセグメントに対して繰り返しトラバーサルをトリガーすることです。

パフォーマンスを向上させるために、ASTにメモ化ノードを追加したいと考えています。上記の簡単な例で

type Expr = 
| Add of Expr * Expr 
| Lit of int 
| HashNode of int * Expr 

、私が希望することはGetHashCodeはそれを計算するために、ASTのいずれかのより深いを移動する必要がないようにHashNodeは、そのexprのハッシュを表していることです。

これは、私がGetHashCodeメソッドをどのようにオーバーライドすべきかわかりません。理想的には、組み込みのハッシュメソッドを再利用して、何とかHashNodeだけを無視するようにしたいと思いますが、どうやってそれを行うのかはわかりません。

私は自分のハッシュ関数を作成する必要がありますが、残念ながらハッシュ関数については何も知らないので、今は少し失われています。

ハッシュ関数をそのままにして、ノードを一意のIDで置き換えることが考えられますが、そうしないとコードに複雑性が増します。

Answer 1

私は非常に頻繁に再作成される依存グラフ（ASTのようなもの）を構築するTheGamma（GitHub）で同様のことが最近必要でした（エディタでコードを変更して再解析されます）。ライブプレビューでは計算に時間がかかることがあるので、できるだけ前のグラフを再利用したいと思っていました。

私がやっていることは、各ノードに「シンボル」を付けることです。キーは、いくつかのノードの種類のコードAddについて（0、1である -

type Expr = 
    | Add of ExprNode * ExprNode 
    | Lit of int 

and ExprNode(expr:Expr, symbol:int) = 
    member x.Expression = expr 
    member x.Symbol = symbol 
    override x.GetHashCode() = symbol 
    override x.Equals(y) = 
    match y with 
    | :? ExprNode as y -> y.Symbol = x.Symbol 
    | _ -> false 

私は、ノードのキャッシュを保持し実行します。同じシンボルを持つ2つのノードが、私はあなたが効率的な等価性のテストに使用できると思いますこれは、同じですLitなど）、およびすべてのネストされたノードのシンボルリテラルでは、数値自体も追加します。つまり、同じリテラルを2回作成すると同じノードが得られます。だから、ノードを作成することは次のようになります。

let node expr ctx = 
    // Get the key from the kind of the expression 
    // and symbols of all nested node in this expression 
    let key = 
    match expr with 
    | Lit n -> [0; n] 
    | Add(e1, e2) -> [1; e1.Symbol; e2.Symbol] 
    // Return either a node from cache or create a new one 
    match ListDictionary.tryFind key ctx with 
    | Some res -> res 
    | None -> 
     let res = ExprNode(expr, nextId()) 
     ListDictionary.set key res ctx 
     res 

ListDictionaryモジュールは、キーが整数のリストであるとnextIdは次のIDを生成するための通常の機能である可変辞書です：だから、

type ListDictionaryNode<'K, 'T> = 
    { mutable Result : 'T option 
    Nested : Dictionary<'K, ListDictionaryNode<'K, 'T>> } 

type ListDictionary<'K, 'V> = Dictionary<'K, ListDictionaryNode<'K, 'V>> 

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>] 
module ListDictionary = 
    let tryFind ks dict = 
    let rec loop ks node = 
     match ks, node with 
     | [], { Result = Some r } -> Some r 
     | k::ks, { Nested = d } when d.ContainsKey k -> loop ks (d.[k]) 
     | _ -> None 
    loop ks { Nested = dict; Result = None } 

    let set ks v dict = 
    let rec loop ks (dict:ListDictionary<_, _>) = 
     match ks with 
     | [] -> failwith "Empty key not supported" 
     | k::ks -> 
      if not (dict.ContainsKey k) then 
      dict.[k] <- { Nested = Dictionary<_, _>(); Result = None } 
      if List.isEmpty ks then dict.[k].Result <- Some v 
      else loop ks (dict.[k].Nested) 
    loop ks dict 


let nextId = 
    let mutable id = 0 
    fun() -> id <- id + 1; id 

私はあなた自身のキャッシュメカニズムを実装する必要があると言っていると思いますが、これは私のためにはうまくいきましたし、あなたのケースでこれを行う方法をヒントするかもしれません！