F #: generierter IL-Code für seq {} und andere Berechnungsworkflows

Question

Wenn ich IL Code, den F # für seq{} Ausdrücke für benutzerdefinierte Rechenabläufe generiert, vergleicht, ist es ziemlich offensichtlich, dass seq{} sehr unterschiedlich implementiert ist: es erzeugt einen Zustand Maschine ähnlich wie das, das C# für seine Iterator-Methoden verwendet. Benutzerdefinierte Workflows verwenden dagegen das entsprechende Builder-Objekt wie erwartet.

Also frage ich mich - warum der Unterschied?

Ist dies aus historischen Gründen, z.B. "Seq war da vor Workflows"?
Oder, gibt es eine signifikante Leistung zu gewinnen?
Ein anderer Grund?

Answer 1

Dies ist eine Optimierung, die vom F # -Compiler durchgeführt wird. Soweit ich weiß, wurde es später tatsächlich implementiert - der F # Compiler hatte zuerst eine Listenkomprehension, dann eine allgemeine Version von Berechnungsausdrücken (auch für seq { ... } verwendet), aber das war weniger effizient, daher wurde die Optimierung in einer späteren Version hinzugefügt .

Der Hauptgrund ist, dass dadurch viele Zuweisungen und Umleitungen entfernt werden. Angenommen, Sie haben so etwas wie:

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

Wenn Ausdrücke Berechnung verwendet wird, wird dies wie etwas übersetzt:

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

Es gibt ein paar Funktionszuordnungen und die For Schleife immer die Lambda muss aufrufen Funktion. Die Optimierung verwandelt dies in eine Zustandsmaschine (ähnlich der C# -Zustandsmaschine), so dass die Operation MoveNext() auf dem generierten Enumerator einfach einen Zustand der Klasse mutiert und dann zurückgibt ...

Sie können die Leistung leicht vergleichen, indem Sie definieren eine individuelle Berechnung Builder für Sequenzen:

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 |] 

Jetzt können wir dies testen (#time in F # interaktiv verwenden):

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

auf meinem Computer, nimmt diese 2.644sec, wenn die benutzerdefinierte 012 mitBuilder aber nur 0,065 Sekunden bei Verwendung der integrierten optimierten seq Ausdruck. Die Optimierung macht Sequenz-Ausdrücke somit deutlich effizienter.

Answer 2

In der Vergangenheit waren Berechnungsausdrücke ("Workflows") eine Verallgemeinerung von Sequenzausdrücken: http://blogs.msdn.com/b/dsyme/archive/2007/09/22/some-details-on-f-computation-expressions-aka-monadic-or-workflow-syntax.aspx.

Aber die Antwort ist sicherlich, dass es eine signifikante Leistung zu gewinnen gibt. Ich kann keine festen Links (obwohl es "Optimierungen im Zusammenhang mit 'wenn' in Sequenzausdrücke filtert" in http://blogs.msdn.com/b/dsyme/archive/2007/11/30/full-release-notes-for-f-1-9-3-7.aspx), aber ich erinnere mich, dass dies eine Optimierung war, die seinen Weg in irgendwann in Zeit. Ich möchte sagen, dass der Vorteil offensichtlich ist: Sequenzausdrücke sind ein "Kern" -Sprachmerkmal und verdienen jegliche Optimierungen, die gemacht werden können.

In ähnlicher Weise werden Sie sehen, dass bestimmte tailrekursive Funktionen in Loops anstelle von Tail-Calls optimiert werden.