Почему создание / объединение цитат F # происходит так медленно? - PullRequest
Новая
       105

Почему создание / объединение цитат F # происходит так медленно?

2 голосов
/ 13 июля 2020

Кажется, что построение цитат с использованием синтаксиса <@ @> ужасно неэффективно. Например, создание списка целых чисел 

let q1 = List.foldBack (fun n acc -> <@ n :: %acc @>) [1..100000] <@ [] @>
Real: 00:00:05.714, CPU: 00:00:05.937, GC gen0: 234, gen1: 47, gen2: 1

Мало того, что приведенный выше код работает очень медленно, но и производительность памяти также низкая

Напротив, следующее быстрее, но все еще плохо с точки зрения памяти 

let q2 = 
    let (NewUnionCase (cons, [_;NewUnionCase (nil, [])])) = <@ [1] @>
    List.foldBack (fun n acc -> Expr.NewUnionCase(cons, [ <@ n @>; acc])) [1..100000] (Expr.NewUnionCase(nil, []))
Real: 00:00:02.352, CPU: 00:00:02.343, GC gen0: 296, gen1: 10, gen2: 0

Наконец, использование простого старого Expr значительно лучше (хотя и не так быстро, как я ожидал) 

let q3 = 
    let (NewUnionCase (cons, [_;NewUnionCase (nil, [])])) = <@ [1] @>
    List.foldBack (fun n acc -> Expr.NewUnionCase(cons, [ Expr.Value(n, typeof<int>); acc])) [1..100000] (Expr.NewUnionCase(nil, []))
Real: 00:00:00.370, CPU: 00:00:00.375, GC gen0: 8, gen1: 3, gen2: 0

1 Ответ

2 голосов
/ 14 июля 2020

Для сравнения я попытался определить свой собственный Expr -подобный тип объединения и посмотреть, насколько быстро это будет: 

type MExpr = 
  | MUnionCase of Reflection.UnionCaseInfo * A list
  | MValue of int * System.Type
  | MUnit

Теперь мы можем сравнить только создание объектов и списков DU , с фактическим построением выражения. 

List.foldBack (fun n acc -> 
  MUnionCase(cons, [MValue(n, typeof<int>); acc])) [1..100000] MUnit
// ~30ms

List.foldBack (fun n acc -> 
  Expr.NewUnionCase(cons, [ Expr.Value(n, typeof<int>); acc])) 
    [1..100000] (Expr.NewUnionCase(nil, []))
// ~200ms

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

Могли бы вы использовать массив вместо списка? Следующее занимает всего около 45 мс, потому что выделяется намного меньше, а проверка типов также упрощается: 

Expr.NewArray(typeof<int>, List.init 100000 (fun i -> 
  Expr.Value(i, typeof<int>)))

Если вы хотите построить цитату, которая создает список, вы все равно можете это сделать: 

let a = Expr.NewArray(typeof<int>, List.init 100000 (fun i -> 
  Expr.Value(i, typeof<int>)))
<@ List.ofArray (%%a) @>
...