F # "bucle" optimización

Question

Código ejemplo:

let foo1 (arr : int[]) = 
    for i = 0 to arr.Length-1 do 
     arr.[i] <- i 

let foo2 (arr : int[]) = 
    for i in [0..arr.Length-1] do 
     arr.[i] <- i 

pensé que estas funciones deben ser equivalentes entre sí (en términos de rendimiento). Pero si nos fijamos en IL perfil, vamos a ver:

Primera función, 15 líneas, no hay asignaciones dinámicas, sin try operador, sin vocación virtual:

IL_0000: nop 
IL_0001: ldc.i4.0 
IL_0002: stloc.0 
IL_0003: br.s IL_0011 
// loop start (head: IL_0011) 
    IL_0005: ldarg.0 
    IL_0006: ldloc.0 
    IL_0007: ldloc.0 
    IL_0008: stelem.any [mscorlib]System.Int32 
    IL_000d: ldloc.0 
    IL_000e: ldc.i4.1 
    IL_000f: add 
    IL_0010: stloc.0 

    IL_0011: ldloc.0 
    IL_0012: ldarg.0 
    IL_0013: ldlen 
    IL_0014: conv.i4 
    IL_0015: blt.s IL_0005 
// end loop 

IL_0017: ret 

y segundo - casi 100 líneas, un montón de asignaciones/cancelaciones de asignación, el llamamiento de las funciones virtuales, un montón de try/Dispose:

IL_0000: nop 
IL_0001: ldc.i4.0 
IL_0002: ldc.i4.1 
IL_0003: ldarg.0 
IL_0004: ldlen 
IL_0005: conv.i4 
IL_0006: ldc.i4.1 
IL_0007: sub 
IL_0008: call class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> [FSharp.Core]Microsoft.FSharp.Core.Operators/OperatorIntrinsics::RangeInt32(int32, int32, int32) 
IL_000d: call class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0> [FSharp.Core]Microsoft.FSharp.Core.Operators::CreateSequence<int32>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>) 
IL_0012: call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!0> [FSharp.Core]Microsoft.FSharp.Collections.SeqModule::ToList<int32>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>) 
IL_0017: stloc.0 
IL_0018: ldloc.0 
IL_0019: unbox.any class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> 
IL_001e: callvirt instance class [mscorlib]System.Collections.Generic.IEnumerator`1<!0> class [mscorlib]System.Collections.Generic.IEnumerable`1<int32>::GetEnumerator() 
IL_0023: stloc.1 
.try 
{ 
    // loop start (head: IL_0024) 
     IL_0024: ldloc.1 
     IL_0025: callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext() 
     IL_002a: brfalse.s IL_003e 

     IL_002c: ldloc.1 
     IL_002d: callvirt instance !0 class [mscorlib]System.Collections.Generic.IEnumerator`1<int32>::get_Current() 
     IL_0032: stloc.3 
     IL_0033: ldarg.0 
     IL_0034: ldloc.3 
     IL_0035: ldloc.3 
     IL_0036: stelem.any [mscorlib]System.Int32 
     IL_003b: nop 
     IL_003c: br.s IL_0024 
    // end loop 

    IL_003e: ldnull 
    IL_003f: stloc.2 
    IL_0040: leave.s IL_005b 
} // end .try 
finally 
{ 
    IL_0042: ldloc.1 
    IL_0043: isinst [mscorlib]System.IDisposable 
    IL_0048: stloc.s 4 
    IL_004a: ldloc.s 4 
    IL_004c: brfalse.s IL_0058 

    IL_004e: ldloc.s 4 
    IL_0050: callvirt instance void [mscorlib]System.IDisposable::Dispose() 
    IL_0055: ldnull 
    IL_0056: pop 
    IL_0057: endfinally 

    IL_0058: ldnull 
    IL_0059: pop 
    IL_005a: endfinally 
} // end handler 

IL_005b: ldloc.2 
IL_005c: pop 
IL_005d: ret 

Mi pregunta es ¿por qué F # compilador utiliza código tan complicado para foo2? ¿Por qué usa un IEnumerable para implementar un bucle tan trivial?

Answer 1

En el segundo ejemplo, si utiliza la expresión rango, se puede convertir en bucle normal de for:

let foo2 (arr : int[]) = 
    for i in 0..arr.Length-1 do 
     arr.[i] <- i 

y se convierten en equivalente a foo1.

cito Section 6.3.12 Range Expressions in F# language specs:

Una secuencia de iteración expresión de la forma para var en expr1 .. expr2 do expr3 hecho a veces se elaboró ​​como un simple bucle for-expresión (§6.5.7).

Sin embargo, el segundo ejemplo es más como:

let foo2 (arr : int[]) = 
    let xs = [0..arr.Length-1] (* A new list is created *) 
    for i in xs do 
     arr.[i] <- i 

donde se ha creado una nueva lista de forma explícita.

Answer 2

Lo que su visión es la diferencia entre usar un estándar de enumeración basada en el índice y una enumeración basada IEnumerable (o en C# términos for vs foreach).

En la segunda muestra, la expresión [0..arr.Length-1] está creando una colección y F # está utilizando IEnumerable<T> para enumerar los valores. Parte de este estilo de enumeración implica el uso de IEnumerator<T> que implementa IDisposable. El bloque try/finally que está viendo se genera para garantizar que se llame al método IDisposable::Dispose al final de la enumeración incluso frente a una excepción.

¿Podría F # optimizar el segundo ejemplo en el primero y evitar toda la sobrecarga adicional? Es posible que puedan hacer esta optimización. Esencialmente vistazo a través de la expresión de rango, no se trata de un simple rango numérico y, por lo tanto, generar el equivalente for código.

Debe F # optimizar el segundo ejemplo. Mi voto sería no. Características como esta a menudo parecen triviales desde el exterior, pero implementarlas y, lo que es más importante, mantenerlas, puede ser bastante costosas. Un usuario astuto siempre podría convertir su código de nuevo a la versión estándar for y evitar la sobrecarga IEnumerable<T> (si el generador de perfiles lo revelara como un problema).No implementar la optimización libera al equipo de F # para implementar otras características increíbles.