F #: codice IL generato per seq {} vs altri flussi di calcolo computazionale

Question

Quando si confronta il codice IL che F # genera per le espressioni seq{} rispetto a quello per flussi di calcolo computazionali definiti dall'utente, è ovvio che lo seq{} è implementato in modo molto diverso: genera uno stato macchina simile alla volta che C# usa per i suoi metodi di iteratore. I flussi di lavoro definiti dall'utente, d'altra parte, usano l'oggetto costruttore corrispondente come ci si aspetterebbe.

Quindi mi chiedo: perché la differenza?

È questo per ragioni storiche, ad es. "seq era lì prima dei flussi di lavoro"?
Oppure, c'è una prestazione significativa da guadagnare?
Qualche altro motivo?

Answer 1

Questa è un'ottimizzazione eseguita dal compilatore F #. Per quanto ne so, è stato implementato in un secondo momento: il compilatore F # aveva prima le list comprehensions, quindi una versione general-purpose delle espressioni di calcolo (usata anche per seq { ... }) ma meno efficiente, quindi l'ottimizzazione è stata aggiunta in qualche versione successiva .

Il motivo principale è che questo rimuove molte allocazioni e riferimenti indiretti. Diciamo che hai qualcosa di simile:

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

Quando si utilizzano le espressioni di calcolo, questo si traduce in qualcosa di simile:

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

C'è un paio di allocazioni di funzione e il ciclo For ha sempre bisogno di invocare il lambda funzione. L'ottimizzazione lo trasforma in una macchina a stati (simile alla macchina a stati C#), quindi l'operazione MoveNext() sull'enumeratore generato modifica semplicemente alcuni stati della classe e quindi restituisce ...

È possibile confrontare facilmente le prestazioni definendo un costruttore personalizzato di calcolo per le sequenze:

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

Ora possiamo testare questo (utilizzando #time in F # interattivo):

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

Sul mio computer, questo prende 2.644sec quando si utilizza l'usanza 012 Generatorema solo 0,065 secondi se si utilizza l'espressione integrata seq ottimizzata. Quindi l'ottimizzazione rende le espressioni di sequenza significativamente più efficienti.

Answer 2

Storicamente, le espressioni di calcolo ("flussi di lavoro") erano una generalizzazione delle espressioni di sequenza: http://blogs.msdn.com/b/dsyme/archive/2007/09/22/some-details-on-f-computation-expressions-aka-monadic-or-workflow-syntax.aspx.

Ma la risposta è certamente che c'è una prestazione significativa da ottenere. Non riesco a visualizzare nessun collegamento solido (anche se si parla di "ottimizzazioni correlate a" quando "filtra in espressioni di sequenza" in http://blogs.msdn.com/b/dsyme/archive/2007/11/30/full-release-notes-for-f-1-9-3-7.aspx), ma ricordo che si trattava di un'ottimizzazione che si faceva strada ad un certo punto in tempo. Mi piacerebbe dire che il vantaggio è evidente: le espressioni di sequenza sono una caratteristica linguistica "core" e meritano tutte le ottimizzazioni che possono essere fatte.

Analogamente, si vedrà che alcune funzioni di coda ricorsive saranno ottimizzate nei loop, piuttosto che nelle chiamate tail.