una - que significa i++ en c++

¿La función recursiva máxima llama en C/C++ antes de que la pila esté llena y da un error de segmentación?

Question

Estaba haciendo una pregunta en la que usé una función recursiva para crear un árbol de segmentos. Para valores más grandes comenzó a dar falla de segmentación. Así que pensé que podría ser debido al valor del índice de matriz fuera de límite, pero más tarde pensé que podría deberse a que la pila de programas iba a ser demasiado grande. Escribí este código para contar cuál es la cantidad máxima de llamadas recursivas permitidas antes de que el sistema dé seg-fault.

#include<iostream>
using namespace std;
void recur(long long int);
int main()
{
recur(0);
return 0;
}
void recur(long long int v)
{
v++;
cout<<v<<endl;
recur(v);
}

Después de ejecutar el código anterior, obtuve el valor de v para ser 261926 y 261893 y 261816 antes de obtener un error de segmentación y todos los valores estaban cerca de estos.

Ahora sé que esto dependerá de la máquina a la máquina, y el tamaño de la pila de la función que se llama, pero ¿alguien puede explicar los conceptos básicos de cómo mantenerse a salvo de seg-fallas y qué es un límite suave que uno puede tener en cuenta .

Answer 1

La cantidad de niveles de recursión que puede hacer depende del tamaño de la pila de llamadas combinado con el tamaño de las variables locales y los argumentos que se colocan en dicha pila. Además de "cómo se escribe el código", al igual que muchas otras cosas relacionadas con la memoria, esto depende en gran medida del sistema en el que se ejecuta, qué compilador está utilizando, nivel de optimización [1], etc. Algunos sistemas integrados en los que he trabajado, la pila sería de unos cientos de bytes, mi primera computadora doméstica tenía 256 bytes de pila, donde los escritorios modernos tienen megabytes de pila (y puedes ajustarlo, pero finalmente se te acabará)

Hacer recursiones a profundidad ilimitada no es una buena idea, y debería considerar cambiar su código para que "no haga eso". Debe comprender el algoritmo y comprender a qué profundidad recurrirá, y si eso es aceptable en su sistema. Desafortunadamente, no hay nada que alguien pueda hacer en el momento en que se agota la pila (en el mejor de los casos, su programa se bloquea, en el peor no lo hace, pero provoca que algo más salga mal, como la pila o el montón de alguna otra aplicación). )

En una máquina de escritorio, creo que es aceptable tener una profundidad de recursión de entre cientos y miles, pero no mucho más que esto, y eso es si tienes un uso pequeño de la pila en cada llamada, si cada llamada está usando hasta kilobytes de pila, debe limitar aún más el nivel de llamada o reducir la necesidad de espacio de pila.

Si necesita tener más profundidad de recursión, necesita volver a organizar el código, por ejemplo, utilizando una pila de software para almacenar el estado y un bucle en el código.

[1] Usando g ++ -O2 en tu código publicado, llegué a 50 millones y seguí contando, y espero que si lo dejo el tiempo suficiente, se reiniciará en cero porque continúa para siempre, esto desde que g ++ detecta que esta recursión puede ser convertido en un bucle, y lo hace. El mismo programa compilado con -O0 o -O1 realmente se detiene en poco más de 200000. Con clang ++ -O1 simplemente continúa. El código compilado de clang aún se está ejecutando cuando terminé de escribir el resto del código, en 185 millones de "recursiones".

Answer 2

No hay (AFAIK) ningún límite bien establecido. (Estoy respondiendo desde un punto de vista de escritorio de Linux).

En computadoras de escritorio, laptops, el tamaño de pila predeterminado es de unos pocos megabytes en 2015. En Linux puede usar setrlimit (2) para cambiarlo (a una cifra razonable, no espere poder configurarlo en un gigabyte en estos días) - y puede usar getrlimit (2) o analizar /proc/self/limits (ver proc (5) ) para consultarlo. En los microcontroladores integrados, o dentro del kernel de Linux, toda la pila puede ser mucho más limitada (a unos pocos kilobytes en total).

Cuando creas un hilo usando pthread_create (3) puedes usar un pthread_attr_t explícito y usar pthread_attr_setstack (3) para establecer el espacio de la pila.

Por cierto, con GCC reciente, puede compilar todo su software ( incluida la biblioteca C estándar) con stacks divididos (así que pase -fsplit-stack a gcc o g++ )

Por fin, su ejemplo es una llamada final, y GCC podría optimizar eso (en un salto con argumentos). Comprobé que si compila con g++ -O2 (usando GCC 4.9.2 en Linux / x86-64 / Debian) la recursión se transformaría en un bucle genuino y ninguna asignación de pila crecería indefinidamente (su programa se ejecuta para casi 40 millones de llamadas) recur a recur en un minuto, luego lo interrumpí) En mejores lenguajes como Scheme u Ocaml hay una garantía de que las llamadas de cola se compilan de manera iterativa (entonces la llamada recursiva de cola se convierte en el constructo usualmente -o incluso el único- de bucles).

CyberSpok es excesivo en su comentario (dando pistas para evitar recurrencias). Las recursiones son muy útiles, pero debe limitarlas a una profundidad razonable (por ejemplo, algunos miles), y debe tener cuidado de que los marcos de llamada en la pila de llamadas sean pequeños (menos de un kilobyte cada uno), así que prácticamente asigne y desasigne la mayor parte los datos en el montón C Las opciones de uso de GCC -fstack son realmente útiles para informar el uso de la pila de cada función compilada. Ver esto y esas respuestas.

Tenga en cuenta que el estilo de continuación de paso es una forma canónica de transformar las repeticiones en iteraciones (luego intercambia las tramas de pila con cierres asignados dinámicamente).

Algunos algoritmos inteligentes reemplazan una recursión con iteraciones de modificación sofisticadas, por ejemplo, el algoritmo de marcado de gráficos Deutche-Shorr-Waite .

Answer 3

Para las aplicaciones basadas en Linux, podemos usar las API getrlimit y setrlimit para conocer los diversos límites de recursos del núcleo, como el tamaño del archivo central, el tiempo de la CPU, el tamaño de la pila, los valores agradables, máx. no. de procesos, etc. ''RLIMIT_STACK'' es el nombre del recurso para la pila definida en el kernel de Linux. A continuación se muestra un programa simple para recuperar el tamaño de la pila:

#include <iostream>
#include <sys/time.h>
#include <sys/resource.h>
#include <errno.h>
using namespace std;
int main()
{
struct rlimit sl;
int returnVal = getrlimit(RLIMIT_STACK, &sl);
if (returnVal == -1)
{
cout << "Error. errno: " << errno << endl;
}
else if (returnVal == 0)
{
cout << "stackLimit soft - max : " << sl.rlim_cur << " - " << sl.rlim_max << endl;
}
}