performance - 最高のパフォーマンス評価者 f#

Question

いくつかの関数の単純な評価器を実装しました。f# の世界に入ったばかりなので、より高速なエバリュエーターが存在するか (存在する場合は実装方法) を尋ねられます。(variableName, (condition + newVariableName)) を含むデータ構造を取得する必要があります。これら 2 つのフィールドは文字列です。以下は、私のバージョンのエバリュエーターの一部です。

let env = new Dictionary<_,_>(HashIdentity.Structural)
//eval: expr -> Prop
let rec eval = function
//Val of string -- is a variable name or a string value
| Val e -> if e.Equals("TRUE") then True       // True is a Prop type used for BDD Algorithm
           elif e.Equals("FALSE") then False   // False is a Prop type used for BDD Algorithm
           else var e    //var of string --- is a Prop type used for BDD Algorithm
| Int i -> var (i.ToString())
| Float e -> var (e.ToString()) 
| Const c -> var c //Const of string --- is a constant name (ex. "$foo" is a constant)
| Path (e, s) -> var ((eval e).ToString() + "." + s)
| Lookup(s, el) -> var s
| Integer(ex) -> eval ex 
| FromTo (e, el) ->var ((eval e).ToString() + (eval el.Head).ToString() + (eval el.Tail.Head).ToString())
| Str(e) -> eval e
| Equality (v, e) -> let evalV = eval  v
                     let evalE = eval  e
                     match evalE with
                     | Var e -> 
                            let sndKey = "Equality" + evalE.ToString()
                            if env.ContainsKey (evalV.ToString()) then 
                                if env.[(evalV.ToString())].Equals(sndKey) then
                                    var env.[(evalV.ToString())]
                                else ~~~ (var env.[(evalV.ToString())]) 
                            else
                                env.Add((evalV.ToString()), (evalV.ToString()) + sndKey)
                                var ((evalV.ToString()) + sndKey)
                     | _ as k -> if bddBuilder.Equiv k False then
                                    let sndKey = "Equality" + "False"
                                    if env.ContainsKey (evalV.ToString()) then 
                                         if env.[(evalV.ToString())].Equals(sndKey) then
                                             var env.[(evalV.ToString())]
                                         else ~~~ (var env.[(evalV.ToString())]) 
                                    else
                                        env.Add((evalV.ToString()), (evalV.ToString()) + sndKey)
                                        var ((evalV.ToString()) + sndKey)
                                 else let sndKey = "Equality" + "True"
                                      if env.ContainsKey (evalV.ToString()) then 
                                          if env.[(evalV.ToString())].Equals(sndKey) then
                                                var env.[(evalV.ToString())]
                                          else ~~~ (var env.[(evalV.ToString())]) 
                                      else
                                          env.Add((evalV.ToString()), (evalV.ToString()) + sndKey)
                                          var ((evalV.ToString()) + sndKey)
| Inequality (v, e) -> let evaluatedV = (eval  v).ToString()
                       let evaluatedE = (eval  e).ToString()
                       let sndKey = "Inequality" + evaluatedE
                       if env.ContainsKey (evaluatedV.ToString()) then 
                            if env.[(evaluatedV.ToString())].Equals(sndKey) then
                                   var env.[(evaluatedV.ToString())]
                            else ~~~ (var env.[(evaluatedV.ToString())]) 
                       else env.Add((evaluatedV.ToString()), (evaluatedV.ToString()) + sndKey)
                            var ((evaluatedV.ToString()) + sndKey)
| IfThenElse (e1, e2, e3) -> (eval e1 &&& eval e2) ||| ((~~~ (eval e1)) &&& eval e3)
| FindString(e1, e2) -> var ("FS" + (eval e1).ToString() + (eval e2).ToString())
| GreaterThan(e1, e2) -> let evaluatedV = (eval  e1).ToString()
                         let evaluatedE = (eval  e2).ToString()
                         let sndKey = "GreaterThan" + evaluatedE
                         if env.ContainsKey (evaluatedV.ToString()) then 
                             if env.[(evaluatedV.ToString())].Equals(sndKey) then
                                    var env.[(evaluatedV.ToString())]
                             else ~~~ (var env.[(evaluatedV.ToString())]) 
                         else env.Add((evaluatedV.ToString()), (evaluatedV.ToString()) + sndKey)
                              var ((evaluatedV.ToString()) + sndKey)
| GreaterThanOrEqual(e1, e2) -> let evaluatedV = (eval  e1).ToString()
                                let evaluatedE = (eval  e2).ToString()
                                let sndKey = "GreaterThanOrEqual" + evaluatedE
                                if env.ContainsKey (evaluatedV.ToString()) then 
                                    if env.[(evaluatedV.ToString())].Equals(sndKey) then
                                        var env.[(evaluatedV.ToString())]
                                    else ~~~ (var env.[(evaluatedV.ToString())]) 
                                else env.Add((evaluatedV.ToString()), (evaluatedV.ToString()) + sndKey)
                                     var ((evaluatedV.ToString()) + sndKey)
| Null(e) -> var ("Null" + (eval e).ToString())
| GetToken(e1, e2, e3) -> var ((eval e1).ToString() + (eval e2).ToString())
| Mod(e1, e2) -> var ((eval e1).ToString() + (eval e2).ToString())
| Match(e1, e2) -> let evaluatedV = (eval  e1).ToString()
                   let evaluatedE = (eval  e2).ToString()
                   let sndKey = "Match" + evaluatedE
                   if env.ContainsKey (evaluatedV.ToString()) then 
                        if env.[(evaluatedV.ToString())].Equals(sndKey) then
                               var env.[(evaluatedV.ToString())]
                        else ~~~ (var env.[(evaluatedV.ToString())]) 
                   else env.Add((evaluatedV.ToString()), (evaluatedV.ToString()) + sndKey)
                        var ((evaluatedV.ToString()) + sndKey)
| LessThenOrEqual(e1, e2) -> let evaluatedV = (eval  e1).ToString()
                             let evaluatedE = (eval  e2).ToString()
                             let sndKey = "LessThen" + evaluatedE
                             if env.ContainsKey (evaluatedV.ToString()) then 
                                if env.[(evaluatedV.ToString())].Equals(sndKey) then
                                    var env.[(evaluatedV.ToString())]
                                else ~~~ (var env.[(evaluatedV.ToString())]) 
                             else env.Add((evaluatedV.ToString()), (evaluatedV.ToString()) + sndKey)
                                  var ((evaluatedV.ToString()) + sndKey)
| LessThen(e1, e2) -> let evaluatedV = (eval  e1).ToString()
                      let evaluatedE = (eval  e2).ToString()
                      let sndKey = "LessThen" + evaluatedE
                      if env.ContainsKey (evaluatedV.ToString()) then 
                            if env.[(evaluatedV.ToString())].Equals(sndKey) then
                                   var env.[(evaluatedV.ToString())]
                            else ~~~ (var env.[(evaluatedV.ToString())]) 
                      else env.Add((evaluatedV.ToString()), (evaluatedV.ToString()) + sndKey)
                           var ((evaluatedV.ToString()) + sndKey)
| Length(e) -> var ("Len" + (eval e).ToString())
| Full(e) -> var ("Full" + (eval e).ToString())
| Minus(e1, e2) -> var ((eval e1).ToString() + (eval e2).ToString())
| Times(e1, e2) -> var ((eval e1).ToString() + (eval e2).ToString())
| Plus (e1, e2) -> var ((eval e1).ToString() + (eval e2).ToString())
| Duration(e) -> eval e
| Minutes(e) -> eval e
| Trim(e) -> var ("Tri" + (eval e).ToString())
| Reverse(e) -> var ("Rev" + (eval e).ToString())
| Ast.And (v1, v2) -> eval v1 &&& eval v2
| Ast.Or (v1, v2) -> eval v1 ||| eval v2
| Ast.Not(v1) -> ~~~ (eval v1)
| _ as a-> failwithf "Expression %A not found" a

編集: このエバリュエーターは、ブール条件を検証するために使用されます。このバージョンでは、ディクショナリが 1 つしかなく、パフォーマンスが向上していますが、次のような状況をモデル化するにはどうすればよいですか。

1. var1 == "foo1" && var1=="foo2" ---> 満足: false
2. var2>=0 && var2>0 ---> 満足: true
3. (var3 == "foo2" && var3 != null) || var3 == "foo1" --> 満足できる: true

Answer 1

答えは、場合によります。

いくつかのシナリオでは、ツリーを単純にたどって評価するのが最善かもしれません。これは、式が小さく、1 回または数回しか評価されない場合に最適な戦略です。

式が大きく、おそらく何度も評価される場合は、最適化を試みて実行するのが最善です。最適化には、償却する必要のある関連コストが伴うため、数回実行する必要がある大きな式をターゲットにするのが最善です。試すことができる最適化には多くの種類があります。ここにいくつかの提案を示します (優れたコンパイラの教科書には、より多くのより優れた提案が含まれていることは間違いありません)。

• 事前に実行できるケースを探しているツリーを歩きます。たとえば、2 つの定数が隣接している場合、操作を実行 (つまり、それらを一緒に追加) して、より小さく単純な新しいツリーを作成できる場合があります。同様に、ゼロの定数が乗算されているものを見つけた場合は、ゼロを乗算したものはすべてゼロであるため、これを単純にゼロに置き換えることができます。
• まったく同等のブランチを探してツリーをたどることができます。このブランチに副作用がない場合は、結果をキャッシュして一度だけ実行することができます (必要に応じて、異なる式間で実行することもできます)。
• データ構造のコンパイルを検討することをお勧めします。.NET では、Relection.Emit 名前空間を使用するか、CodeDom を介してコードを生成して、データ構造と同等のコードを生成できます。これにより実行が大幅に高速化されますが、コンパイルのコストが非常に高くなるため、慎重に使用する必要があります。

実装する最適化は、「単純な」ベースラインに対して慎重に測定する必要があります。場合によっては、最適化が期待どおりに動作せず、実行が遅くなる可能性があります。

非常に単純な最適化以外のものは、おそらく実装が非常に難しいので、頑張ってください!

Answer 2

おそらく、大幅な利益をもたらす可能性が高いコードの最も簡単な最適化は、検索用の (恐ろしい) F# 拡張メソッドの使用を、Dictionary割り当てを行わない .NET の代替手段に置き換えることです。したがって、この：

match env.TryGetValue evaluatedV with
| true, v1 ->
    match v1.TryGetValue sndKey with
    | true, v2 -> v2
    | _ ->
        v1.[sndKey] <- evaluetedV + sndKey
        env.[evaluatedV] <- v1
        evaluatedV + sndKey
| _ ->
    if value.Count <> 0 then value.Clear()
    value.[sndKey] <- evaluetedV + sndKey
    env.[evaluatedV] <- value
    evaluatedV + sndKey

になります：

let mutable v1 = Unchecked.defaultof<_>
if env.TryGetValue(evaluatedV, &v1) then
  let mutable v2 = Unchecked.defaultof<_>
  if v1.TryGetValue(sndKey, &v2) then v2 else
    v1.[sndKey] <- evaluetedV + sndKey
    env.[evaluatedV] <- v1
    evaluatedV + sndKey
else
  if value.Count <> 0 then value.Clear()
  value.[sndKey] <- evaluetedV + sndKey
  env.[evaluatedV] <- value
  evaluatedV + sndKey

ただし、これらのハッシュ テーブル ルックアップはおそらくパフォーマンスを低下させます。このような問題を回避できるさまざまな手法がありますが、F# 固有のものではありません。

• 2 つのハッシュ テーブル ルックアップを 1 つのハッシュ テーブル ルックアップに結合します。
• 文字列をハッシュ consed シンボルなどのより効率的な型に置き換えます。
• 外部ハッシュ テーブルを各シンボルの変更可能な参照に置き換えて、valueまたはenv辞書でそのシンボルを検索した結果を提供します。