c# - Generar código de operación de cola

recursion f#

Question

Por curiosidad, estaba tratando de generar un código de operación de llamada de cola usando C #. Fibinacci es fácil, así que mi ejemplo c # se ve así:

    private static void Main(string[] args)
    {
        Console.WriteLine(Fib(int.MaxValue, 0));
    }

    public static int Fib(int i, int acc)
    {
        if (i == 0)
        {
            return acc;
        }

        return Fib(i - 1, acc + i);
    }

Si lo construyo en versión y lo ejecuto sin depuración, no obtengo un desbordamiento de pila. Depurarlo o ejecutarlo sin optimizaciones y obtengo un desbordamiento de pila, lo que implica que la llamada final funciona cuando está en lanzamiento con las optimizaciones activadas (que es lo que esperaba).

El MSIL para esto se ve así:

.method public hidebysig static int32 Fib(int32 i, int32 acc) cil managed
{
    // Method Start RVA 0x205e
    // Code Size 17 (0x11)
    .maxstack 8
    L_0000: ldarg.0 
    L_0001: brtrue.s L_0005
    L_0003: ldarg.1 
    L_0004: ret 
    L_0005: ldarg.0 
    L_0006: ldc.i4.1 
    L_0007: sub 
    L_0008: ldarg.1 
    L_0009: ldarg.0 
    L_000a: add 
    L_000b: call int32 [ConsoleApplication2]ConsoleApplication2.Program::Fib(int32,int32)
    L_0010: ret 
}

msdn ver un código de operación de la cola, según el msdn , pero no está allí. Esto me hizo preguntarme si el compilador de JIT era responsable de ponerlo allí. Intenté agregar el ensamblado (usando ngen install <exe> , navegando a la lista de ensamblajes de Windows para obtenerlo) y lo volví a cargar en ILSpy, pero a mí me parece lo mismo:

.method public hidebysig static int32 Fib(int32 i, int32 acc) cil managed
{
    // Method Start RVA 0x3bfe
    // Code Size 17 (0x11)
    .maxstack 8
    L_0000: ldarg.0 
    L_0001: brtrue.s L_0005
    L_0003: ldarg.1 
    L_0004: ret 
    L_0005: ldarg.0 
    L_0006: ldc.i4.1 
    L_0007: sub 
    L_0008: ldarg.1 
    L_0009: ldarg.0 
    L_000a: add 
    L_000b: call int32 [ConsoleApplication2]ConsoleApplication2.Program::Fib(int32,int32)
    L_0010: ret 
}

Todavía no lo veo

Sé que F # maneja bien la llamada final, así que quise comparar lo que F # hizo con lo que C # hizo. Mi ejemplo F # se ve así:

let rec fibb i acc =  
    if i = 0 then
        acc
    else 
        fibb (i-1) (acc + i)


Console.WriteLine (fibb 3 0)

Y el IL generado para el método fib se ve así:

.method public static int32 fibb(int32 i, int32 acc) cil managed
{
    // Method Start RVA 0x2068
    // Code Size 18 (0x12)
    .custom instance void [FSharp.Core]Microsoft.FSharp.Core.CompilationArgumentCountsAttribute::.ctor(int32[]) = { int32[](Mono.Cecil.CustomAttributeArgument[]) }
    .maxstack 5
    L_0000: nop 
    L_0001: ldarg.0 
    L_0002: brtrue.s L_0006
    L_0004: ldarg.1 
    L_0005: ret 
    L_0006: ldarg.0 
    L_0007: ldc.i4.1 
    L_0008: sub 
    L_0009: ldarg.1 
    L_000a: ldarg.0 
    L_000b: add 
    L_000c: starg.s acc
    L_000e: starg.s i
    L_0010: br.s L_0000
}

Lo cual, según ILSpy, es equivalente a esto:

[Microsoft.FSharp.Core.CompilationArgumentCounts(Mono.Cecil.CustomAttributeArgument[])]
public static int32 fibb(int32 i, int32 acc)
{
    label1:
    if !(((i != 0))) 
    {
        return acc;
    }
    (i - 1);
    i = acc = (acc + i);;
    goto label1;
}

¿Entonces F # generó una llamada de cola usando declaraciones goto? Esto no es lo que esperaba.

No estoy tratando de confiar en la llamada de cola en cualquier lugar, pero solo tengo curiosidad de dónde exactamente se establece ese código de operación. ¿Cómo está C # haciendo esto?

Answer 1

Al igual que todas las optimizaciones realizadas en .NET (idiomas de Roslyn), la optimización de llamadas de cola es un trabajo realizado por el jitter, no el compilador. La filosofía es que poner el trabajo en jitter es útil, ya que cualquier lenguaje se beneficiará de ello y el trabajo normalmente difícil de escribir y depurar un optimizador de código tiene que hacerse solo una vez por arquitectura.

Tienes que mirar el código de la máquina generado para ver que se hace, Debug + Windows + Desmontaje. Con el requisito adicional de hacerlo, mirando el código de versión de la versión que se genera con las Herramientas + Opciones, Depuración, General, Suprimir la optimización de JIT no seleccionada.

El código x64 se ve así:

        public static int Fib(int i, int acc) {
            if (i == 0) {
00000000  test        ecx,ecx 
00000002  jne         0000000000000008 
                return acc;
00000004  mov         eax,edx 
00000006  jmp         0000000000000011 
            }

            return Fib(i - 1, acc + i);
00000008  lea         eax,[rcx-1] 
0000000b  add         edx,ecx 
0000000d  mov         ecx,eax 
0000000f  jmp         0000000000000000              // <== here!!!
00000011  rep ret  

Tenga en cuenta las instrucciones marcadas, un salto en lugar de una llamada. Esa es la optimización de la cola de llamada en el trabajo. Una peculiaridad en .NET es que el jitter x86 de 32 bits no realiza esta optimización. Simplemente un elemento de tareas pendientes que probablemente nunca podrán realizar. Lo que requería que los escritores del compilador de F # no ignoraran el problema y emitieran Opcodes.Tailcall. Encontrará otras optimizaciones realizadas por la fluctuación de fase documentada en esta respuesta .

Answer 2

La situación con optimización de llamadas de cola en .Net es bastante complicada. Hasta donde yo sé, es así:

• El compilador de C # nunca emitirá la tail. opcode y nunca hará la optimización de la cola de llamadas solo.
• El compilador F # a veces emite la tail. código de operación y, a veces hace la optimización de la cola de llamadas por sí mismo mediante la emisión de IL que no es recursiva.
• El CLR honrará la tail. código de operación si está presente y el CLR de 64 bits algunas veces hará la optimización de la cola de llamadas incluso cuando el código de operación no está presente.

Entonces, en tu caso, no viste la tail. código de operación en el IL generado por el compilador de C #, porque no hace eso. Pero el método fue optimización de la cola de llamada, porque el CLR algunas veces lo hace incluso sin el código de operación.

Y en el caso F #, observaste que el compilador f # hizo la optimización por sí mismo.

Answer 3

El compilador C # no ofrece ninguna garantía sobre las optimizaciones de la cola de llamada porque los programas C # generalmente usan bucles y por lo tanto no dependen de las optimizaciones de la cola de llamadas. Entonces, en C #, esto es simplemente una optimización de JIT que puede o no ocurrir (y no puede confiar en ella).

El compilador F # está diseñado para manejar código funcional que usa recursión y por lo tanto le brinda ciertas garantías sobre las llamadas finales. Esto se hace de dos maneras:

• si escribes una función recursiva que se llama a sí misma (como tu fib ), el compilador la convierte en una función que usa loop en el cuerpo (esta es una optimización simple y el código producido es más rápido que usar un tail-call)

• si usa una llamada recursiva en una posición más compleja (cuando usa el estilo de paso de continuación donde la función se pasa como argumento), el compilador genera una instrucción de seguimiento de llamada que le dice al JIT que debe usar una llamada final.

Como ejemplo del segundo caso, compile la siguiente función simple F # (F # no hace esto en el modo de depuración para simplificar la depuración, por lo que puede necesitar el modo de liberación o agregar --tailcalls+ ):

let foo a cont = cont (a + 1)

La función simplemente llama a la función cont con el primer argumento incrementado en uno. En el estilo de paso de continuación, tiene una larga secuencia de llamadas, por lo que la optimización es crucial (simplemente no puede usar este estilo sin un cierto manejo de las llamadas finales). El código genera IL se ve así:

IL_0000: ldarg.1
IL_0001: ldarg.0
IL_0002: ldc.i4.1
IL_0003: add
IL_0004: tail.                          // Here is the ''tail'' opcode!
IL_0006: callvirt instance !1 
  class [FSharp.Core] Microsoft.FSharp.Core.FSharpFunc`2<int32, !!a>::Invoke(!0)
IL_000b: ret