Wie cache ich Hash-Codes für eine AST?

Question

Ich arbeite an einer Sprache in F # und beim Testen finde ich, dass die Laufzeit über 90% ihrer Zeit im Vergleich zu Gleichheit ausgibt. Deswegen ist die Sprache so langsam, dass sie unbrauchbar ist. Während der Instrumentierung wird die GetHashCode-Funktion ziemlich weit oben auf der Liste als Overhead-Quelle angezeigt. Was passiert, ist, dass ich während Methodenaufrufen die Methodenkörper (Expr) zusammen mit den Aufrufargumenten als Schlüssel in einem Wörterbuch verwende und wiederholte Überquerungen über die AST-Segmente auslöst.

Um die Leistung zu verbessern, möchte ich Memoknoten im AST hinzufügen.

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

In dem obigen vereinfachten Beispiel, was ich möchte, ist, dass die HashNode den Hash seiner Expr darstellen, so dass die GetHashCode nicht tiefer in dem AST, um sie zu berechnen reisen muss.

Das gesagt, ich bin mir nicht sicher, wie ich die GetHashCode Methode überschreiben sollte. Im Idealfall möchte ich die eingebaute Hash-Methode wiederverwenden und sie nur die HashNode irgendwie ignorieren lassen, aber ich bin nicht sicher, wie man das macht.

Eher wahrscheinlich, ich werde meine eigene Hash-Funktion machen müssen, aber leider weiß ich nichts über Hash-Funktionen, also bin ich jetzt ein bisschen verloren. Eine alternative Idee, die ich habe, wäre, Knoten mit eindeutigen IDs zu ersetzen, während diese Hash-Funktion beibehalten wird, aber das würde zusätzliche Komplexität in den Code einführen, die ich lieber vermeiden würde, wenn es nicht nötig wäre.

Answer 1

Ich brauchte eine ähnliche Sache kürzlich in TheGamma (GitHub), wo ich ein Abhängigkeitsdiagramm (Art von AST) erstellen, die sehr oft neu erstellt wird (wenn Sie Code im Editor ändern und es erneut geparst wird), aber ich habe Live-Vorschauen, deren Berechnung einige Zeit in Anspruch nehmen kann, daher wollte ich so viel wie möglich vom vorherigen Diagramm verwenden.

Die Art, wie ich das tue ist, dass ich ein "Symbol" an jeden Knoten anschließe. Zwei Knoten mit dem gleichen Symbol gleich sind, was ich denke, Sie für eine effiziente Gleichheit Tests verwenden:

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 

Ich halte tun einen Cache von Knoten - der Schlüssel ist ein Code des Knotens Art (0 für Add, 1 für Lit, usw.) und Symbole aller verschachtelten Knoten. Für Literale füge ich auch die Zahl selbst hinzu, was bedeutet, dass das gleiche Literal zweimal erzeugt wird. So sieht wie folgt aus einem Knoten erstellen:

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 

Das ListDictionary Modul ein veränderliches Wörterbuch ist, wo der Schlüssel eine Liste von ganzen Zahlen und nextId ist die übliche Funktion nächste ID zu generieren:

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 

So, Ich denke, dass Sie Ihren eigenen Caching-Mechanismus implementieren müssen, aber das funktionierte ziemlich gut für mich und könnte Ihnen zeigen, wie Sie das in Ihrem Fall tun können!