f# - ¿Puede/hace el operador de tuberías(hacia adelante) prevenir la optimización de llamadas de cola?

stack-overflow tail-recursion

Question

Para un problema de optimización de parámetros en el trabajo, escribí un algoritmo genético para encontrar algunas configuraciones buenas porque una solución de fuerza bruta no es factible. Desafortunadamente, cuando vuelvo por la mañana, la mayoría de las veces me presentan una StackOverflowException .

He estado usando F # desde hace bastante tiempo, así que estoy al tanto del TCO y la necesidad de funciones con argumentos del acumulador y generalmente uso esa forma.

Después de mucho buscar, creo que pude encontrar el código que desencadenó la excepción:

breedPopulation alive |> simulate (generation + 1) lastTime ewma

breedPopulation genera una nueva generación a partir de los individuos en la corriente actual. Luego se inicia la siguiente ronda / generación con la llamada a simulate . Cuando miro el desmontaje (noob total) veo un pop y un ret , por lo que no me parece una llamada normal (sin cola).

mov         rcx,qword ptr [rbp+10h]  
mov         rcx,qword ptr [rcx+8]  
mov         rdx,qword ptr [rbp-40h]  
cmp         dword ptr [rcx],ecx  
call        00007FFA3E4905C0  
mov         qword ptr [rbp-0F0h],rax  
mov         r8,qword ptr [rbp-0F0h]  
mov         qword ptr [rbp-80h],r8  
mov         r8,qword ptr [rbp-78h]  
mov         qword ptr [rsp+20h],r8  
mov         r8d,dword ptr [rbp+18h]  
inc         r8d  
mov         rdx,qword ptr [rbp+10h]  
mov         r9,qword ptr [rbp-20h]  
mov         rcx,7FFA3E525960h  
call        00007FFA3E4A5040  
mov         qword ptr [rbp-0F8h],rax  
mov         rcx,qword ptr [rbp-0F8h]  
mov         rdx,qword ptr [rbp-80h]  
mov         rax,qword ptr [rbp-0F8h]  
mov         rax,qword ptr [rax]  
mov         rax,qword ptr [rax+40h]  
call        qword ptr [rax+20h]  
mov         qword ptr [rbp-100h],rax  
mov         rax,qword ptr [rbp-100h]  
lea         rsp,[rbp-10h]  
pop         rsi  
pop         rdi  
pop         rbp  
ret

Después de desechar el operador de la tubería y colocar la cría en una posición de parámetro normal, el desmontaje es diferente.

//    simulate (generation + 1) lastTime ewma (breedPopulation alive)
mov         ecx,dword ptr [rbp+18h]  
inc         ecx  
mov         dword ptr [rbp-30h],ecx  
mov         rcx,qword ptr [rbp-20h]  
mov         qword ptr [rbp-38h],rcx  
mov         rcx,qword ptr [rbp-80h]  
mov         qword ptr [rbp-0F0h],rcx  
mov         rcx,qword ptr [rbp+10h]  
mov         rcx,qword ptr [rcx+8]  
mov         rdx,qword ptr [rbp-48h]  
cmp         dword ptr [rcx],ecx  
call        00007FFA3E4605C0  
mov         qword ptr [rbp-0F8h],rax  
mov         rax,qword ptr [rbp-0F8h]  
mov         qword ptr [rbp+30h],rax  
mov         rax,qword ptr [rbp-0F0h]  
mov         qword ptr [rbp+28h],rax  
mov         rax,qword ptr [rbp-38h]  
mov         qword ptr [rbp+20h],rax  
mov         eax,dword ptr [rbp-30h]  
mov         dword ptr [rbp+18h],eax  
nop  
jmp         00007FFA3E47585B

Eso es definitivamente más corto y con el jmp final aún mejor que una llamada de cola.

Por lo tanto, quiero entender si y por qué el problema parece ser el problema y cuándo marca la diferencia; después de todo, esta es la primera vez que me muerde después de años. ¿En qué circunstancias ocurre y a qué debemos prestar atención?

Actualización: después de que Guy señaló que mis listas no son IL, sino ensamblador, primero reescribí la pregunta. Esto es lo que descubrí con ILSpy :

Con el operador |>

Mirando el C # descompilado, el código parece saltar de un lado a otro entre

internal static FSharpFunc<Types.Genome[], System.Tuple<System.Tuple<float, float>, LbpArea[]>[]> simulate@265-1(Universe x, System.Threading.ManualResetEvent pleaseStop, int generation, System.DateTime lastTime, FSharpOption<double> ewma)
{
    return new $Universe.simulate@267-2(x, pleaseStop, generation, lastTime, ewma);
}

y

// internal class simulate@267-2
public override System.Tuple<System.Tuple<float, float>, LbpArea[]>[] Invoke(Types.Genome[] population)
{
    LbpArea[][] array = ArrayModule.Parallel.Map<Types.Genome, LbpArea[]>(this.x.genomeToArray, population);
    FSharpFunc<System.Tuple<System.Tuple<float, float>, LbpArea[]>, float> accessFitness = this.x.accessFitness;
    System.Tuple<System.Tuple<float, float>, LbpArea[]>[] array2 = ArrayModule.Filter<System.Tuple<System.Tuple<float, float>, LbpArea[]>>(new $Universe.alive@274(accessFitness), ArrayModule.Parallel.Map<LbpArea[], System.Tuple<System.Tuple<float, float>, LbpArea[]>>(new $Universe.alive@273-1(this.x), array));
    if (array2 == null)
    {
        throw new System.ArgumentNullException("array");
    }
    System.Tuple<System.Tuple<float, float>, LbpArea[]>[] array3 = ArrayModule.SortWith<System.Tuple<System.Tuple<float, float>, LbpArea[]>>(new $Universe.alive@275-2(), array2);
    this.x.Population = array3;
    System.Tuple<System.DateTime, FSharpOption<double>> tuple = this.x.printProgress<float, LbpArea[]>(this.lastTime, this.ewma, this.generation, array3);
    System.DateTime item = tuple.Item1;
    FSharpOption<double> item2 = tuple.Item2;
    if (this.pleaseStop.WaitOne(0))
    {
        return array3;
    }
    Types.Genome[] func = this.x.breedPopulation(array3);
    return $Universe.simulate@265-1(this.x, this.pleaseStop, this.generation + 1, item, item2).Invoke(func);
}

En la IL de la new convocatoria no hay tail. op para ser encontrado. Por otro lado, el IL de las últimas líneas del Invoke lee.

IL_00d3: call class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<class BioID.GeneticLbp.Types/Genome[], class [mscorlib]System.Tuple`2<class [mscorlib]System.Tuple`2<float32, float32>, valuetype [BioID.Operations.Biometrics]BioID.Operations.Biometrics.LbpArea[]>[]> ''<StartupCode$BioID-GeneticLbp>.$Universe''::''simulate@265-1''(class BioID.GeneticLbp.Universe, class [mscorlib]System.Threading.ManualResetEvent, int32, valuetype [mscorlib]System.DateTime, class [FSharp.Core]Microsoft.FSharp.Core.FSharpOption`1<float64>)
IL_00d8: ldloc.s 7
IL_00da: tail.
IL_00dc: callvirt instance !1 class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<class BioID.GeneticLbp.Types/Genome[], class [mscorlib]System.Tuple`2<class [mscorlib]System.Tuple`2<float32, float32>, valuetype [BioID.Operations.Biometrics]BioID.Operations.Biometrics.LbpArea[]>[]>::Invoke(!0)
IL_00e1: ret

No sé qué hacer con eso.

Sin |> operador

La otra versión es de hecho muy diferente. Empezando con

internal static System.Tuple<System.Tuple<float, float>, LbpArea[]>[] simulate@264(Universe x, System.Threading.ManualResetEvent pleaseStop, Unit unitVar0)
{
    FSharpFunc<int, FSharpFunc<System.DateTime, FSharpFunc<FSharpOption<double>, FSharpFunc<Types.Genome[], System.Tuple<System.Tuple<float, float>, LbpArea[]>[]>>>> fSharpFunc = new $Universe.simulate@265-2(x, pleaseStop);
    (($Universe.simulate@265-2)fSharpFunc).x = x;
    (($Universe.simulate@265-2)fSharpFunc).pleaseStop = pleaseStop;
    System.Tuple<System.Tuple<float, float>, LbpArea[]>[] population = x.Population;
    Types.Genome[] func;
    if (population != null && population.Length == 0)
    {
        func = x.lengthRandomlyIncreasing([email protected]@);
        return FSharpFunc<int, System.DateTime>.InvokeFast<FSharpOption<double>, FSharpFunc<Types.Genome[], System.Tuple<System.Tuple<float, float>, LbpArea[]>[]>>(fSharpFunc, 0, System.DateTime.Now, null).Invoke(func);
    }
    FSharpFunc<LbpArea[], Types.Genome> arrayToGenome = x.arrayToGenome;
    func = ArrayModule.Parallel.Map<System.Tuple<System.Tuple<float, float>, LbpArea[]>, Types.Genome>(new $Universe.simulate@296-3(arrayToGenome), population);
    return FSharpFunc<int, System.DateTime>.InvokeFast<FSharpOption<double>, FSharpFunc<Types.Genome[], System.Tuple<System.Tuple<float, float>, LbpArea[]>[]>>(fSharpFunc, 0, System.DateTime.Now, null).Invoke(func);
}

va a

// internal class simulate@265-2
public override System.Tuple<System.Tuple<float, float>, LbpArea[]>[] Invoke(int generation, System.DateTime lastTime, FSharpOption<double> ewma, Types.Genome[] population)
{
    return $Universe.simulate@265-1(this.x, this.pleaseStop, generation, lastTime, ewma, population);
}

y finalmente

internal static System.Tuple<System.Tuple<float, float>, LbpArea[]>[] simulate@265-1(Universe x, System.Threading.ManualResetEvent pleaseStop, int generation, System.DateTime lastTime, FSharpOption<double> ewma, Types.Genome[] population)
{
    while (true)
    {
        // Playing evolution...
        if (pleaseStop.WaitOne(0))
        {
            return array3;
        }
        // Setting up parameters for next loop...
    }
    throw new System.ArgumentNullException("array");
}

tl; dr

Definitivamente, el uso del operador de tuberías cambió drásticamente el flujo del programa. Mi conjetura es que el ir y venir entre las dos funciones es lo que eventualmente causa la excepción.

Ya había leído Tail Calls en F # pero no creo que se aplique a esta situación, ya que no estoy usando una función de primera clase que devuelva una unidad como valor (en mi código F #).

Así que la pregunta sigue siendo: ¿Por qué el operador de tuberías tiene este efecto destructivo aquí? ¿Cómo podría haberlo sabido de antemano / a qué debo tener cuidado?

Actualización 2:

Puedes encontrar una versión reducida del ejemplo en GitHub . Comprueba por ti mismo que el operador en inline |> cambia el IL produce, que no es lo que yo esperaría.

Mientras reducía el ejemplo, con un poco de suerte pude encontrar la fuente real de la excepción. Puede comprobar la branch para la variante mucho más mínima. Después de todo, no tiene nada que ver con la tubería, pero todavía no lo entiendo porque, en mi humilde opinión, hay una recursión de la cola.

Pero mis preguntas originales permanecen. Solo estoy agregando uno más . :)

Answer 1

En función del caso mínimo que se proporciona, si el código se ejecuta en modo de lanzamiento en 64 bits, falla con un desbordamiento de pila. Si el código se ejecuta en modo de liberación en modo de 32 bits, se realiza correctamente.

Nota: La opción para elegir entre 32 y 64 bits es Prefer 32-bit como se ve en las imágenes a continuación.

Al aumentar el tamaño de la pila, el código tendrá éxito en el modo de lanzamiento en 64 bits. Esto se hace mediante el uso del constructor Thread .

[<EntryPoint>]
let main _ =

    let test () =
        let r = KissRandom()
        let n = r.Normal()
        Seq.item 20000 n |> printfn "%f"

    /// The greatest maximum-stack-size that should be used
    /// with the ''runWithStackFrame'' function.
    let STACK_LIMIT = 16777216

    /// Run a function with a custom maximum stack size.
    /// This is necessary for some functions to execute
    /// without raising a Exception.
    let runWithCustomStackSize maxStackSize fn =
        // Preconditions
        if maxStackSize < 1048576 then
            invalidArg "stackSize" "Functions should not be executed with a /
                maximum stack size of less than 1048576 bytes (1MB)."
        elif maxStackSize > STACK_LIMIT then
            invalidArg "stackSize" "The maximum size of the stack frame should /
                not exceed 16777216 bytes (16MB)."

        /// Holds the return value of the function.
        let result = ref Unchecked.defaultof<''T>

        // Create a thread with the specified maximum stack size,
        // then immediately execute the function on it.
        let thread = System.Threading.Thread ((fun () -> result := fn()), maxStackSize)
        thread.Start ()

        // Wait for the function/thread to finish and return the result.
        thread.Join ()
        !result

    /// Runs a function within a thread which has an enlarged maximum-stack-size.
    let inline runWithEnlargedStack fn =
        runWithCustomStackSize STACK_LIMIT fn


//    test ()       // Fails with  in 64-bit mode, Release
                    // Runs successfully in 32-bit mode, Release

    runWithEnlargedStack test

    printf "Press any key to exit: "
    System.Console.ReadKey() |> ignore
    printfn ""

    0

Este código es de FSharp-logic-examples y, en particular, de Anh-Dung Phan.

Si bien no he comprobado la causa raíz, sospecho que es debido a que el tamaño de los elementos para 64 bits es mayor que el tamaño de los elementos para 32 bits y aunque la cantidad de elementos colocados en la pila y la el tamaño de la pila sigue siendo el mismo para ambas versiones, el aumento del tamaño del elemento empuja la memoria necesaria para la pila por encima del límite de 1 megabyte.

TL; DR

Esta ha sido una pregunta divertida e iluminadora para responder. Me alegro que me lo pidieran.

Originalmente, el problema parecía estar relacionado con el uso de |> y TCO y, dado que todavía es de valor, lo dejo en la respuesta. También me gustaría agradecer al OP por ser una respuesta y ayuda, es un placer ayudar a alguien que trabaja con usted y no contra usted.

En el siguiente código, que es recursivo y se ejecuta en modo de depuración dentro de Visual Studio, causa un .

Si se inicia desde la línea de comandos desde el directorio bin/release , NO causa un .

Usando la comunidad de Visual Studio 15

[<EntryPoint>]
let main argv = 

    let largeList = 
        printfn "Creating large list"
        [
            for i in 1 .. 100000000 do
                yield i
        ]

    // causes  in Debug
    // No  in Release
    let sum4 l =
        printfn "testing sum4"
        let rec sumInner4 l acc =
            match l with
            | h::t -> 
                let acc = acc + h
                acc |> sumInner4 t
            | [] -> acc
        sumInner4 l 0

    let result4 = sum4 largeList
    printfn "result4: %A" result4

Donde la versión o la depuración se establece en la barra de herramientas de Visual Studio

y las opciones para el proyecto en modo Debug son

y las opciones para el proyecto en modo Release son

tldr;

En el proceso de prueba, creé 16 pruebas diferentes y las construí tanto en el modo de depuración como en el modo de lanzamiento, y verifiqué si se ejecutaron hasta el final o si arrojaron un desbordamiento de pila. Los 16 se dividen en un conjunto de 4 con 4 casos cada uno. Los casos 1,5,9,13 son negativos y producen un desbordamiento de pila para garantizar que se pueda crear un desbordamiento de pila. Los casos 2,6,10,14 son positivos para mostrar que la llamada de cola está funcionando y no está causando un desbordamiento de pila. Los casos 3,7,11,15 muestran una llamada de cola con una operación realizada en la misma declaración que la llamada de cola, y están a una factorización de los casos de prueba usando |> ; estos funcionan como se espera. Los casos 4,8,12,16 usan |> y muestran cuándo funciona y no funciona en modo de depuración, lo que probablemente sea una sorpresa para muchos. Los casos 1-4 y 9-12 usan una función de la forma fxy , los casos 8-11 usan una función de la forma fx y los casos 12-16 usan una función de la forma fxyz . Originalmente hice los primeros 8 casos de prueba, pero después del comentario de Keith, hice 4 más que no usan una lista, pero aún así usan una función de la de fxy y presentan el resultado inesperado y luego hice 4 más que usan una función de la forma fxyz .

Para ejecutar una prueba, tendrá que comentar todas las pruebas excepto la que planea ejecutar y compilarla una vez en el modo de depuración, que luego se puede ejecutar desde Visual Studio, y luego volver a compilarla en el modo de lanzamiento y ejecutarla. Lo ejecuto desde una línea de comandos para asegurarme de que estoy ejecutando la versión de lanzamiento.

[<EntryPoint>]
let main argv = 

    let largeList = 
        printfn "Creating large list"
        [
            for i in 1 .. 100000000 do
                yield i
        ]

    // causes  in Debug
    // causes  in Release
    //   Negative confirmation
    //   A supposed tail call that DOES cause a  in both debug and release mode
    //   options: f x y
    let sum1 l = 
        printfn "test 01: "
        let rec sum1Inner l acc =
            match l with
            | h::t -> 
                let acc = acc + h
                1 + sum1Inner t acc
            | [] -> acc
        sum1Inner l 0

    // No  in Debug
    // No  in Release
    //   Positive confirmation
    //   A tail call that DOES NOT cause a  in both debug and release mode
    //   options: f x y
    let sum2 l =
        printfn "test 02: "
        let rec sum2Inner l acc =
            match l with
            | h::t -> 
                let acc = acc + h
                sum2Inner t acc
            | [] -> acc
        sum2Inner l 0

    // No  in Debug
    // No  in Release
    //   A test case
    //   options: f x y and no |>
    let sum3 l =
        printfn "test 03: "
        let rec sum3Inner l acc =
            match l with
            | h::t -> 
                sum3Inner t (acc + h)
            | [] -> acc
        sum3Inner l 0

    // causes  in Debug
    // No  in Release
    //   A test case
    //   options: f x y and |>
    let sum4 l =
        printfn "test 04: "
        let rec sum4Inner l acc =
            match l with
            | h::t -> 
                let acc = acc + h
                acc |> sum4Inner t
            | [] -> acc
        sum4Inner l 0

    // causes  in Debug
    // causes  in Release
    //   Negative confirmation
    //   A supposed tail call that DOES cause a  in both debug and release mode
    //   options: f x
    let sum5 () =
        printfn "test 05: "
        let rec sum5Inner x =
            match x with 
            | 10000000 -> x
            | _ -> 
                let acc = x + 1
                1 + sum5Inner acc
        sum5Inner 0

    // No  in Debug
    // No  in Release
    //   Positive confirmation
    //   A tail call that DOES NOT cause a  in both debug and release mode
    //   options: f x
    let sum6 () =
        printfn "test 06: "
        let rec sum6Inner x =
            match x with 
            | 10000000 -> x
            | _ -> 
                let acc = x + 1
                sum6Inner acc
        sum6Inner 0

    // No  in Debug
    // No  in Release
    //  A test case
    //  options: f x and no |>
    let sum7 l =
        printfn "test 07: "
        let rec sum7Inner x =
            match x with 
            | 10000000 -> x
            | _ -> sum7Inner (x + 1)
        sum7Inner 0

    // No  in Debug
    // No  in Release
    //   A test case
    //   options: f x and |>
    let sum8 () =
        printfn "test 07: "
        let rec sumInner8 x =
            match x with
            | 10000000 -> x
            | _ -> 
                let acc = x + 1
                acc |> sumInner8 
        sumInner8 0

    // causes  in Debug
    // causes  in Release
    //   Negative confirmation"
    //   A supposed tail call that DOES cause a  in both debug and release mode"
    //   options: f x y"
    let sum9 () = 
        printfn "test 09: "
        let rec sum9Inner x y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                1 + sum9Inner x acc
        sum9Inner 1 0   

    // No  in Debug
    // No  in Release
    //   Positive confirmation
    //   A tail call that DOES NOT cause a  in both debug and release mode
    //   options: f x y
    let sum10 () =
        printfn "test 10: "
        let rec sum10Inner x y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                sum10Inner x acc
        sum10Inner 1 0

    // No  in Debug
    // No  in Release
    //   A test case
    //   options: f x y and no |>
    let sum11 () =
        printfn "test 11: "
        let rec sum11Inner x y =
            match y with
            | 10000000 -> y
            | _ -> 
                sum11Inner x (x + y) 
        sum11Inner 1 0

    // causes  in Debug
    // No  in Release
    //   A test case
    //   options: f x y and |>
    let sum12 () =
        printfn "test 12: "
        let rec sum12Inner x y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                acc |> sum12Inner x
        sum12Inner 1 0

    // causes  in Debug
    // No  in Release
    //   A test case"
    //   options: f x y and |>"
    let sum12 () =
        printfn "test 12: "
        let rec sum12Inner x y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                acc |> sum12Inner x
        sum12Inner 1 0

    // causes  in Debug
    // causes  in Release
    //   Negative confirmation"
    //   A supposed tail call that DOES cause a  in both debug and release mode"
    //   options: f x y"
    let sum13 () = 
        printfn "test 13: "
        let rec sum13Inner x z y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                1 + sum13Inner x z acc 
        sum13Inner 1 "z" 0

    // No  in Debug
    // No  in Release
    //   Positive confirmation"
    //   A tail call that DOES NOT cause a  in both debug and release mode"
    //   options: f x y"
    let sum14 () =
        printfn "test 14: "
        let rec sum14Inner x z y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                sum14Inner x z acc
        sum14Inner 1 "z" 0

    // No  in Debug
    // No  in Release
    //   A test case"
    //   options: f x y and no |>"
    let sum15 () =
        printfn "test 15: "
        let rec sum15Inner x z y =
            match y with
            | 10000000 -> y
            | _ -> 
                sum15Inner x z (x + y) 
        sum15Inner 1 "z" 0

    // causes  in Debug
    // No  in Release
    //   A test case"
    //   options: f x y and |>"
    let sum16 () =
        printfn "test 16: "
        let rec sum16Inner x z y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                acc |> sum16Inner x z
        sum16Inner 1 "z" 0

    let result1 = sum1 largeList
    printfn "result1: %A" result1

    let result2 = sum2 largeList
    printfn "result2: %A" result2

    let result3 = sum3 largeList
    printfn "result3: %A" result3

    let result4 = sum4 largeList
    printfn "result4: %A" result4

    let result5 = sum5 ()
    printfn "result5: %A" result5

    let result6 = sum6 ()
    printfn "result6: %A" result6

    let result7 = sum7 ()
    printfn "result7: %A" result7

    let result8 = sum8 ()
    printfn "result8: %A" result8

    let result9 = sum9 ()
    printfn "result9: %A" result9

    let result10 = sum10 ()
    printfn "result10: %A" result10

    let result11 = sum11 ()
    printfn "result11: %A" result11

    let result12 = sum12 ()
    printfn "result12: %A" result12

    let result13 = sum13 ()
    printfn "result13: %A" result13

    let result14 = sum14 ()
    printfn "result14: %A" result14

    let result15 = sum15 ()
    printfn "result15: %A" result15

    let result16 = sum16 ()
    printfn "result16: %A" result16

    printf "Press any key to exit: "
    System.Console.ReadKey() |> ignore
    printfn ""

    0 // return an integer exit code