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