F #: wygenerowany kod IL dla seq {} względem innych przepływów obliczeniowych

Question

Kiedy porównasz kod IL, który F # generuje dla wyrażeń seq{} w stosunku do zdefiniowanych dla zdefiniowanych przez użytkownika przepływów pracy, jest całkiem oczywiste, że seq{} jest implementowane bardzo różnie: generuje stan maszyna podobna do tej, którą kiedyś używa C# do swoich metod iteracyjnych. Zdefiniowane przez użytkownika przepływy pracy wykorzystują odpowiedni obiekt budowania zgodnie z oczekiwaniami.

Zastanawiam się - dlaczego różnica?

Czy to ze względów historycznych, np. "seq był tam przed workflow"?
Czy można uzyskać znaczącą wydajność?
Jakiś inny powód?

Answer 1

To jest optymalizacja przeprowadzona przez kompilator F #. O ile mi wiadomo, został on faktycznie zaimplementowany później - kompilator F # najpierw miał listę zrozumiałą, następnie wersję ogólnego przeznaczenia wyrażeń obliczeniowych (również używanych dla seq { ... }), ale to było mniej wydajne, więc optymalizacja została dodana w późniejszej wersji .

Głównym powodem jest to, że usuwa wiele alokacji i alokacji. Powiedzmy, że masz coś takiego:

seq { for i in input do 
     yield i 
     yield i * 10 } 

Kiedy za pomocą wyrażeń obliczeniowych, to zostanie przetłumaczone na coś w stylu:

seq.Delay(fun() -> seq.For(input, fun i -> 
    seq.Combine(seq.Yield(i), seq.Delay(fun() -> seq.Yield(i * 10))))) 

Istnieje kilka alokacji funkcyjnych i pętla For zawsze musi wywołać lambda funkcjonować. Optymalizacja przekształca to w maszynę stanu (podobną do maszyny stanu C#), więc operacja MoveNext() na wygenerowanym module wyliczającym powoduje tylko mutację pewnego stanu klasy, a następnie zwraca ...

Możesz łatwo porównać wydajność, definiując zwyczaj budowniczy obliczenia dla sekwencji:

type MSeqBuilder() = 
    member x.For(en, f) = Seq.collect f en 
    member x.Yield(v) = Seq.singleton v 
    member x.Delay(f) = Seq.delay f 
    member x.Combine(a, b) = Seq.concat [a; b] 
let mseq = MSeqBuilder() 
let input = [| 1 .. 100 |] 

teraz możemy przetestować (używając #time w F # Interactive):

for i in 0 .. 10000 do 
    mseq { for x in input do 
      yield x 
      yield x * 10 } 
    |> Seq.length |> ignore 

na moim komputerze, to bierze 2.644sec przy użyciu niestandardowego mseq program budujący, ale tylko 0,065 s przy użyciu wbudowanego, zoptymalizowanego wyrażenia seq. Optymalizacja sprawia, że ​​wyrażenia sekwencji są znacznie wydajniejsze.

Answer 2

Historycznie, wyrażenia obliczeniowe ("przepływy pracy") były uogólnieniem wyrażeń sekwencji: http://blogs.msdn.com/b/dsyme/archive/2007/09/22/some-details-on-f-computation-expressions-aka-monadic-or-workflow-syntax.aspx.

Ale odpowiedź brzmi na pewno, że można osiągnąć znaczące wyniki. Nie mogę znaleźć żadnych stałych linków (chociaż jest mowa o "optymalizacjach związanych z", gdy "filtry w wyrażeniach sekwencji" w http://blogs.msdn.com/b/dsyme/archive/2007/11/30/full-release-notes-for-f-1-9-3-7.aspx), ale pamiętam, że była to optymalizacja, która weszła w pewnym momencie czas. Chciałbym powiedzieć, że korzyści są oczywiste: wyrażenia sekwencji są "podstawową" cechą językową i zasługują na dowolne optymalizacje, które można wprowadzić.

Podobnie, niektóre funkcje rekurencyjne będą optymalizowane do pętli, a nie do wywołań tylnych.