Лучший оценщик производительности F # - PullRequest
Новая
       48

Лучший оценщик производительности F #

0 голосов
/ 22 июня 2011

Я реализовал наивный оценщик некоторых функций.Я только что вошел в мир f #, поэтому он спросит вас, существует ли (и если да, как реализовать) более быстрый оценщик.Я должен получить структуру данных, которая содержит (variableName, (условие + newVariableName)).Эти два поля являются строками.Ниже приведена часть моей версии оценщика: 

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. var1 == "foo1" && var1 == "foo2" ---> Удовлетворительно: false
  2. var2> = 0 && var2> 0 ---> Удовлетворительно: true
  3. (var3 == "foo2" && var3! = null) ||var3 == "foo1" -> выполнимо: true

Ответы [ 2 ]

1 голос
/ 22 июня 2011

Ответ: это зависит.

В некоторых сценариях может быть лучше наивно ходить по дереву, оценивая, как вы идете.Это, вероятно, будет наилучшей стратегией, когда ваши выражения будут маленькими и будут оцениваться один или несколько раз.

Если ваши выражения большие и могут быть оценены, может быть, иногда лучше попытаться выполнить некоторую оптимизацию,Любая оптимизация будет сопряжена с затратами, которые необходимо амортизировать, поэтому лучше всего ориентироваться на большое выражение, которое нужно будет выполнить несколько раз.Есть много типов оптимизации, которые вы можете попробовать, вот несколько предложений (хороший учебник по компиляторам, несомненно, будет иметь гораздо больше и лучше предложений):

  • Проходите по дереву, ищите случаи, которыеможет быть выполнен заранее.Например, если две константы смежны, вы можете выполнить операцию (т.е. сложить их вместе) и создать новое более простое дерево меньшего размера.Точно так же, если вы найдете что-либо, умноженное на нулевую константу, то вы, возможно, замените это просто на ноль, поскольку все, что умножено на ноль, равно нулю.эта ветвь не имеет побочных эффектов, вы можете кэшировать ее результат и выполнить его только один раз (это может быть сделано даже между различными выражениями, если необходимо).
  • Возможно, вы захотите посмотреть на компиляцию структуры данных.В .NET вы можете использовать пространство имен Relection.Emit или сгенерировать код с помощью CodeDom, чтобы сгенерировать код, эквивалентный вашей структуре данных.Это значительно ускорит выполнение, но компиляция будет стоить очень дорого, так что это стратегия, которую нужно бережно использовать.

Любая оптимизация, которую вы реализуете, должна быть тщательно измерена относительно «наивной» базовой линии,в некоторых случаях ваша оптимизация может работать не так, как ожидалось, и может привести к более медленному выполнению.

Что-либо, кроме довольно простых оптимизаций, возможно, будет довольно сложно реализовать, так что удачи!

0 голосов
/ 25 июня 2011

Возможно, самая простая оптимизация вашего кода, которая может принести значительный выигрыш, - это заменить использование (ужасающего) метода расширения 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 #:

  • Объедините ваши два поиска в хеш-таблице в один поиск в хеш-таблице.
  • Замените строки наболее эффективный тип, такой как символы хеширования.
  • Замените внешнюю хеш-таблицу изменяемыми ссылками в каждом символе, давая результат поиска этого символа в словарях value или env.
...