.net recursion f# mono

.net - Tamaño de pila bajo Mono



recursion f# (3)

Opción 1: cambiar el tamaño de pila mono

Una explicación obvia es que Mono no obedecerá el segundo argumento de Thread si es demasiado grande. ¿Alguien sabe cómo convencer a Mono de asignar una gran pila?

Tiene razón en que Mono limitará el tamaño de la pila, incluso si transfiere un valor grande. Por ejemplo, en mi máquina de prueba Cent OS de 64 bits, el tamaño máximo de pila que Mono asignará es de 2 megabytes. El archivo fuente de Mono C # Thread.cs nos muestra lo que ocurre cuando creas un hilo Mono :

public Thread (ThreadStart start, int maxStackSize) { if (start == null) throw new ArgumentNullException ("start"); threadstart = start; Internal.stack_size = CheckStackSize (maxStackSize); } static int CheckStackSize (int maxStackSize) { if (maxStackSize < 0) throw new ArgumentOutOfRangeException ("less than zero", "maxStackSize"); if (maxStackSize < 131072) // make sure stack is at least 128k big return 131072; int page_size = Environment.GetPageSize (); if ((maxStackSize % page_size) != 0) // round up to a divisible of page size maxStackSize = (maxStackSize / (page_size - 1)) * page_size; int default_stack_size = (IntPtr.Size / 4) * 1024 * 1024; // from wthreads.c if (maxStackSize > default_stack_size) return default_stack_size; return maxStackSize; }

El código anterior pone un límite estricto al tamaño de la pila.

En teoría, podría cambiar el código en una o ambas de las funciones anteriores ( líneas en negrita ) para que se asigne un mayor tamaño de pila. Una vez que hiciste esto, tendrías que construir el tiempo de ejecución Mono y luego ejecutar tu función para ver si el cambio hace la diferencia.

Debo enfatizar que no sé lo suficiente acerca de Mono para entender si la asignación de una pila más grande ayudará en su caso específico. Solo haría esto como último recurso (si ninguna de mis otras respuestas funciona).

He escrito un pequeño fragmento recursivo de código F # para ver cuántos niveles de recursión puedo incluir en la pila en .NET / Mono. Simplemente imprime la profundidad de recursión siempre que sea una potencia exacta de 2, así que descubro la profundidad máxima dentro de un factor 2.

Comienzo el código en un hilo con una cantidad definida de espacio de pila usando System.Threading.Thread (ThreadStart, int) . Bajo .Net parece tomar aproximadamente 100 bytes por nivel de recursión, y puedo obtener alrededor de 16 millones de niveles en una pila de 2G. El uso de memoria es muy similar en Mono, sin embargo, solo puedo obtener unos 30 mil niveles. Aumentar el valor de tamaño de pila pasado a Thread pasado por alrededor de 600000 no aumenta la profundidad de recursión.

ulimit informa que el límite de tamaño de pila es 1G.

Una explicación obvia es que Mono no obedecerá el segundo argumento de Thread si es demasiado grande. ¿Alguien sabe cómo convencer a Mono de asignar una gran pila?

El código es trivial, pero está debajo solo en caso de que alguien se preocupe:

let rec f i = if popcount i = 1 then // population count is one on exact powers of 2 printf "Got up to %d/n" i stdout.Flush () if i = 1000000000 then 0 else 1 + f (i+1)

Opción 3: hacerlo iterativo

Una opción es volver a escribir su método para que no sea recursivo, sino iterativo. Es decir, cambia el método para que sea un ciclo que calcule los resultados:

let f i = let mutable acc = 0 for counter in i .. 1000000000 do // display progress every 10k iterations let j = counter % 10000 if j = 0 then printf "Got up to %d/n" counter stdout.Flush () if counter < 1000000000 then acc <- acc + 1 acc

Para el valor de entrada 1:

let result = f 1 printf "result %d/n" result

La salida:

Got up to 10000 Got up to 20000 Got up to 30000 ... Got up to 999980000 Got up to 999990000 Got up to 1000000000 result 999999999

Para el valor de entrada 999,999,998:

let result = f 999999998 printf "result %d/n" result

La salida:

Got up to 1000000000 result 2

El código anterior usa dos variables para realizar un seguimiento del progreso:

acc - the accumulater, que almacena el resultado del cálculo

counter - es simplemente el número de llamadas iterativas (número de bucles)

Dado que estamos utilizando un bucle para calcular el resultado, no hay ninguna pila adicional asignada.

Opción 2: llamadas F # Tail

Una opción es volver a escribir su método para que use llamadas de cola recursivas. Desde el enlace anterior (Wikipedia):

Una función recursiva de cola es un caso especial de recursión en el que la última instrucción ejecutada en el método es la llamada recursiva. F # y muchos otros lenguajes funcionales pueden optimizar las funciones recursivas de la cola; dado que no se realiza ningún trabajo adicional después de la llamada recursiva, no es necesario que la función recuerde de dónde vino, y por lo tanto no hay razón para asignar memoria adicional en la pila.

F # optimiza las funciones recursivas de cola al decirle al CLR que deje caer el marco de pila actual antes de ejecutar la función objetivo. Como resultado, las funciones recursivas de cola pueden repetirse indefinidamente sin consumir espacio de pila.

Hay una advertencia: Mono no es totalmente compatible con las llamadas recursivas de cola ; lo que debes hacer es probar primero en el tiempo de ejecución de .Net y luego ver si el código se ejecutará en Mono.

Aquí está la función de muestra reescrita usando una llamada recursiva de cola: funciona tanto en .NET (usando Visual Studio 2010) como en Mono (versión de Mono 3.2.0, F # 3.0):

let f i = let rec loop acc counter = // display progress every 10k iterations let j = counter % 10000 if j = 0 then printf "Got up to %d/n" counter stdout.Flush () if counter < 1000000000 then // tail recursive loop (acc + 1) (counter + 1) else acc loop 0 i

Para el valor de entrada 1:

let result = f 1 printf "result %d/n" result

La salida:

Got up to 10000 Got up to 20000 Got up to 30000 ... Got up to 999980000 Got up to 999990000 Got up to 1000000000 result 999999999

Para el valor de entrada 999,999,998:

let result = f 999999998 printf "result %d/n" result

La salida:

Got up to 1000000000 result 2

El código anterior usa dos variables para realizar un seguimiento del progreso:

acc - el acumulador, que almacena el resultado del cálculo

counter - es simplemente el número de llamadas recursivas

¿Por qué su código de muestra no es recursivo?

Parafraseando la sección Cómo escribir las funciones recursivas de la cola del artículo de Wikipedia, podemos reescribir esta línea de su código :

if i = 1000000000 then 0 else 1 + f (i+1)

como

if i = 1000000000 then 0 else let intermediate = f (i+1) // recursion let result = 1 + intermediate // additional operations result

La misma definición de recursividad de cola dice que no puede haber operaciones adicionales después de la llamada recursiva. Como podemos ver en la versión reescrita de su código, se requieren operaciones adicionales para producir el resultado.

Recursos