Cuál es más rápido: asignación de pila o asignación de montón

Esta pregunta puede sonar bastante elemental, pero este es un debate que tuve con otro desarrollador con el que trabajo.

Estaba cuidando de apilar las cosas donde podía, en lugar de apilarlas. Me estaba hablando y mirando por encima de mi hombro y comentó que no era necesario porque son del mismo rendimiento.

Siempre tuve la impresión de que el crecimiento de la pila era un tiempo constante, y el rendimiento de la asignación del montón dependía de la complejidad actual del montón tanto para la asignación (encontrar un agujero del tamaño adecuado) como para desasignar (colapsar agujeros para reducir la fragmentación, como muchas implementaciones de biblioteca estándar toman tiempo para hacer esto durante las eliminaciones si no me equivoco).

Esto me parece algo que probablemente dependerá mucho del compilador. Para este proyecto en particular, estoy usando un compilador Metrowerks para la arquitectura PPC . La información sobre esta combinación sería de gran ayuda, pero en general, para GCC y MSVC ++, ¿cuál es el caso? ¿La asignación de montón no tiene un rendimiento tan alto como la asignación de pila? ¿No hay diferencia? ¿O son las diferencias tan pequeñas que se convierte en micro-optimización sin sentido?

La asignación de la pila es mucho más rápida ya que todo lo que realmente hace es mover el puntero de la pila. Con los grupos de memoria, puede obtener un rendimiento comparable de la asignación de almacenamiento dinámico, pero eso viene con una ligera complejidad adicional y sus propios dolores de cabeza.

Además, stack vs. heap no es solo una consideración de rendimiento; También le informa mucho sobre la vida útil esperada de los objetos.

La pila es mucho más rápida. Literalmente solo usa una sola instrucción en la mayoría de las arquitecturas, en la mayoría de los casos, por ejemplo, en x86:

sub esp, 0x10

(Eso mueve el puntero de la pila hacia abajo en 0x10 bytes y, por lo tanto, "asigna" esos bytes para que los use una variable).

Por supuesto, el tamaño de la pila es muy, muy finito, ya que descubrirá rápidamente si usa en exceso la asignación de la pila o intenta hacer una recursividad :-)

Además, hay pocas razones para optimizar el rendimiento del código que no lo necesita de manera verificable, como lo demuestra la creación de perfiles. La "optimización prematura" a menudo causa más problemas de lo que vale.

Mi regla general: si sé que voy a necesitar algunos datos en tiempo de compilación , y tiene un tamaño de unos pocos cientos de bytes, los apilo. De lo contrario, lo asigno en el montón.

Honestamente, es trivial escribir un programa para comparar el rendimiento:

#include <ctime>
#include <iostream>

namespace {
    class empty { }; // even empty classes take up 1 byte of space, minimum
}

int main()
{
    std::clock_t start = std::clock();
    for (int i = 0; i < 100000; ++i)
        empty e;
    std::clock_t duration = std::clock() - start;
    std::cout << "stack allocation took " << duration << " clock ticks\n";
    start = std::clock();
    for (int i = 0; i < 100000; ++i) {
        empty* e = new empty;
        delete e;
    };
    duration = std::clock() - start;
    std::cout << "heap allocation took " << duration << " clock ticks\n";
}

Se dice que una consistencia tonta es el duende de las mentes pequeñas . Aparentemente, los compiladores optimizadores son los duendes de las mentes de muchos programadores. Esta discusión solía estar en la parte inferior de la respuesta, pero aparentemente las personas no pueden molestarse en leer tan lejos, por lo que me muevo aquí para evitar preguntas que ya he respondido.

Un compilador optimizador puede notar que este código no hace nada y puede optimizarlo todo. El trabajo del optimizador es hacer cosas así, y luchar contra el optimizador es una tarea tonta.

Recomendaría compilar este código con la optimización desactivada porque no hay una buena manera de engañar a todos los optimizadores actualmente en uso o que estarán en uso en el futuro.

Cualquiera que encienda el optimizador y luego se queje de luchar contra él debería estar sujeto al ridículo público.

Si me preocupara la precisión en nanosegundos, no la usaría std::clock(). Si quisiera publicar los resultados como una tesis doctoral, haría un gran trato al respecto, y probablemente compararía GCC, Tendra / Ten15, LLVM, Watcom, Borland, Visual C ++, Digital Mars, ICC y otros compiladores. Tal como están las cosas, la asignación del montón tarda cientos de veces más que la asignación de la pila, y no veo nada útil para investigar más la cuestión.

El optimizador tiene la misión de deshacerse del código que estoy probando. No veo ninguna razón para decirle al optimizador que se ejecute y luego tratar de engañar al optimizador para que no optimice realmente. Pero si veía valor en hacer eso, haría uno o más de los siguientes:

1. Agregue un miembro de datos emptyy acceda a ese miembro de datos en el bucle; pero si solo leo del miembro de datos, el optimizador puede hacer un plegado constante y eliminar el bucle; Si solo escribo al miembro de datos, el optimizador puede omitir todo menos la última iteración del bucle. Además, la pregunta no era "asignación de pila y acceso a datos versus asignación de montón y acceso a datos".

2. Declarar e volatile, pero a volatilemenudo se compila incorrectamente (PDF).

3. Tome la dirección de edentro del bucle (y quizás asígnela a una variable que se declara externy define en otro archivo). Pero incluso en este caso, el compilador puede notar que, al menos en la pila e, siempre se asignará a la misma dirección de memoria, y luego se doblará constantemente como en (1) arriba. Obtengo todas las iteraciones del bucle, pero el objeto nunca está realmente asignado.

Más allá de lo obvio, esta prueba es errónea porque mide tanto la asignación como la desasignación, y la pregunta original no preguntaba sobre la desasignación. Por supuesto, las variables asignadas en la pila se desasignan automáticamente al final de su alcance, por lo que no llamar delete(1) sesgaría los números (la desasignación de la pila se incluye en los números sobre la asignación de la pila, por lo que es justo medir la desasignación del montón) y ( 2) causar una pérdida de memoria bastante mala, a menos que mantengamos una referencia al nuevo puntero y llamemos deletedespués de haber medido el tiempo.

En mi máquina, usando g ++ 3.4.4 en Windows, obtengo "0 ticks de reloj" tanto para la asignación de pila como para el montón para cualquier asignación menor a 100000, e incluso entonces obtengo "0 ticks de reloj" para la asignación de pila y "15 ticks de reloj "para la asignación del montón. Cuando mido 10,000,000 asignaciones, la asignación de pila requiere 31 tics de reloj y la asignación de montón toma 1562 ticks de reloj.

Sí, un compilador de optimización puede eludir la creación de objetos vacíos. Si entiendo correctamente, incluso puede eludir todo el primer bucle. Cuando aumenté las iteraciones a 10,000,000, la asignación de la pila tomó 31 ticks de reloj y la asignación del montón tomó 1562 ticks de reloj. Creo que es seguro decir que sin decirle a g ++ que optimice el ejecutable, g ++ no eludió a los constructores.

En los años transcurridos desde que escribí esto, la preferencia en Stack Overflow ha sido publicar el rendimiento de las compilaciones optimizadas. En general, creo que esto es correcto. Sin embargo, todavía creo que es una tontería pedirle al compilador que optimice el código cuando, de hecho, no desea que ese código esté optimizado. Me parece muy similar a pagar extra por el servicio de aparcacoches, pero se niega a entregar las llaves. En este caso particular, no quiero que se ejecute el optimizador.

Usando una versión ligeramente modificada del punto de referencia (para abordar el punto válido de que el programa original no asignó algo en la pila cada vez a través del ciclo) y compilando sin optimizaciones, pero vinculando a las bibliotecas de lanzamiento (para abordar el punto válido que no usamos no desea incluir ninguna desaceleración causada por enlaces a bibliotecas de depuración):

#include <cstdio>
#include <chrono>

namespace {
    void on_stack()
    {
        int i;
    }

    void on_heap()
    {
        int* i = new int;
        delete i;
    }
}

int main()
{
    auto begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_stack();
    auto end = std::chrono::system_clock::now();

    std::printf("on_stack took %f seconds\n", std::chrono::duration<double>(end - begin).count());

    begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_heap();
    end = std::chrono::system_clock::now();

    std::printf("on_heap took %f seconds\n", std::chrono::duration<double>(end - begin).count());
    return 0;
}

muestra:

on_stack took 2.070003 seconds
on_heap took 57.980081 seconds

en mi sistema cuando se compila con la línea de comando cl foo.cc /Od /MT /EHsc.

Es posible que no esté de acuerdo con mi enfoque para obtener una compilación no optimizada. Está bien: siéntase libre de modificar el punto de referencia tanto como desee. Cuando enciendo la optimización, obtengo:

on_stack took 0.000000 seconds
on_heap took 51.608723 seconds

No porque la asignación de la pila sea realmente instantánea, sino porque cualquier compilador medio decente puede notar que on_stackno hace nada útil y puede optimizarse. GCC en mi computadora portátil Linux también se da cuenta de que on_heapno hace nada útil, y también lo optimiza:

on_stack took 0.000003 seconds
on_heap took 0.000002 seconds

Una cosa interesante que aprendí sobre la asignación de pila frente a montón en el procesador Xbox 360 Xenon, que también puede aplicarse a otros sistemas multinúcleo, es que la asignación en el montón hace que se ingrese una sección crítica para detener todos los demás núcleos para que la asignación no No hay conflicto. Por lo tanto, en un bucle cerrado, la asignación de pila era el camino a seguir para las matrices de tamaño fijo, ya que evitaba las paradas.

Esta puede ser otra aceleración a tener en cuenta si está codificando para multinúcleo / multiproc, ya que su asignación de pila solo será visible para el núcleo que ejecuta su función de alcance, y eso no afectará a ningún otro núcleo / CPU.

Puede escribir un asignador de montón especial para tamaños específicos de objetos que sea muy eficaz. Sin embargo, el asignador general de almacenamiento dinámico no es particularmente eficaz.

También estoy de acuerdo con Torbjörn Gyllebring sobre la vida útil esperada de los objetos. ¡Buen punto!

No creo que la asignación de pila y la asignación de montón sean generalmente intercambiables. También espero que el rendimiento de ambos sea suficiente para uso general.

Recomiendo encarecidamente para artículos pequeños, el que sea más adecuado para el alcance de la asignación. Para artículos grandes, el montón probablemente sea necesario.

En los sistemas operativos de 32 bits que tienen múltiples subprocesos, la pila a menudo es bastante limitada (aunque normalmente es de al menos unos pocos mb), porque el espacio de direcciones debe dividirse y, tarde o temprano, una pila de subprocesos se encontrará con otra. En sistemas de un solo hilo (Linux glibc de un solo hilo de todos modos) la limitación es mucho menor porque la pila puede crecer y crecer.

En los sistemas operativos de 64 bits, hay suficiente espacio de direcciones para que las pilas de hilos sean bastante grandes.

Por lo general, la asignación de la pila solo consiste en restar del registro del puntero de la pila. Esto es mucho más rápido que buscar un montón.

A veces, la asignación de la pila requiere agregar una (s) página (s) de memoria virtual. Agregar una nueva página de memoria puesta a cero no requiere leer una página del disco, por lo que generalmente esto será mucho más rápido que buscar en un montón (especialmente si parte del montón también se paginó). En una situación rara, y usted podría construir un ejemplo de este tipo, solo hay suficiente espacio disponible en parte del montón que ya está en la RAM, pero la asignación de una nueva página para la pila tiene que esperar a que se escriba otra página al disco En esa rara situación, el montón es más rápido.

Además de la ventaja de rendimiento de órdenes de magnitud sobre la asignación de montón, la asignación de pila es preferible para aplicaciones de servidor de larga ejecución. Incluso los montones mejor administrados eventualmente se fragmentan tanto que el rendimiento de la aplicación se degrada.

Una pila tiene una capacidad limitada, mientras que un montón no lo es. La pila típica para un proceso o subproceso es de alrededor de 8K. No puede cambiar el tamaño una vez que está asignado.

Una variable de pila sigue las reglas de alcance, mientras que una de montón no. Si su puntero de instrucción va más allá de una función, todas las nuevas variables asociadas con la función desaparecen.

Lo más importante de todo es que no puede predecir la cadena de llamadas de función general por adelantado. Por lo tanto, una mera asignación de 200 bytes de su parte puede generar un desbordamiento de pila. Esto es especialmente importante si está escribiendo una biblioteca, no una aplicación.

Creo que la vida útil es crucial, y si la cosa asignada tiene que ser construida de una manera compleja. Por ejemplo, en el modelado basado en transacciones, generalmente debe completar y pasar una estructura de transacción con un montón de campos a las funciones de operación. Mire el estándar OSCI SystemC TLM-2.0 para ver un ejemplo.

La asignación de estos en la pila cerca de la llamada a la operación tiende a causar una sobrecarga enorme, ya que la construcción es costosa. La buena manera es asignar en el montón y reutilizar los objetos de transacción, ya sea agrupando o una política simple como "este módulo solo necesita un objeto de transacción".

Esto es muchas veces más rápido que asignar el objeto en cada llamada de operación.

La razón es simplemente que el objeto tiene una construcción costosa y una vida útil bastante larga.

Yo diría: pruebe ambos y vea qué funciona mejor en su caso, porque realmente puede depender del comportamiento de su código.

Probablemente el mayor problema de la asignación del montón versus la asignación del montón, es que la asignación del montón en el caso general es una operación ilimitada y, por lo tanto, no se puede usar donde el tiempo es un problema.

Para otras aplicaciones en las que el tiempo no es un problema, puede que no importe tanto, pero si asigna mucho, esto afectará la velocidad de ejecución. Siempre trate de usar la pila para memoria de corta duración y a menudo asignada (por ejemplo, en bucles), y el mayor tiempo posible: realice la asignación de montón durante el inicio de la aplicación.

No es la asignación de pila jsut lo que es más rápido. También ganas mucho usando variables de pila. Tienen mejor localidad de referencia. Y finalmente, la desasignación también es mucho más barata.

La asignación de la pila es un par de instrucciones, mientras que el asignador de montón de rtos más rápido que conozco (TLSF) usa en promedio del orden de 150 instrucciones. Además, las asignaciones de pila no requieren un bloqueo porque usan almacenamiento local de subprocesos, que es otra gran ganancia de rendimiento. Por lo tanto, las asignaciones de pila pueden ser de 2 a 3 órdenes de magnitud más rápido dependiendo de qué tan multiproceso sea su entorno.

En general, la asignación de almacenamiento dinámico es su último recurso si le importa el rendimiento. Una opción intermedia viable puede ser un asignador de grupo fijo que también es solo un par de instrucciones y tiene muy poca sobrecarga por asignación, por lo que es ideal para objetos pequeños de tamaño fijo. En el lado negativo, solo funciona con objetos de tamaño fijo, no es inherentemente seguro para subprocesos y tiene problemas de fragmentación de bloque.

Preocupaciones específicas del lenguaje C ++

En primer lugar, no hay una asignación denominada "pila" o "montón" ordenada por C ++ . Si está hablando de objetos automáticos en ámbitos de bloque, incluso no están "asignados". (Por cierto, la duración del almacenamiento automático en C definitivamente NO es lo mismo que "asignado"; este último es "dinámico" en el lenguaje C ++.) La memoria asignada dinámicamente está en la tienda libre , no necesariamente en "el montón", aunque el este último es a menudo la implementación (predeterminada) .

Aunque según las reglas semánticas de la máquina abstracta , los objetos automáticos todavía ocupan memoria, una implementación conforme de C ++ puede ignorar este hecho cuando puede probar que esto no importa (cuando no cambia el comportamiento observable del programa). Este permiso lo otorga la regla as-if en ISO C ++, que también es la cláusula general que permite las optimizaciones habituales (y también hay una regla casi igual en ISO C). Además de la regla as-if, ISO C ++ también tiene reglas de copia de elisiónpara permitir la omisión de creaciones específicas de objetos. Las llamadas al constructor y al destructor involucradas se omiten de este modo. Como resultado, los objetos automáticos (si los hay) en estos constructores y destructores también se eliminan, en comparación con la semántica abstracta ingenua que implica el código fuente.

Por otro lado, la asignación gratuita de la tienda es definitivamente "asignación" por diseño. Según las normas ISO C ++, dicha asignación se puede lograr mediante una llamada de una función de asignación . Sin embargo, desde ISO C ++ 14, hay una nueva regla (que no es como si) para permitir la fusión de ::operator newllamadas de función de asignación global (es decir ) en casos específicos. Por lo tanto, partes de las operaciones de asignación dinámica también pueden no funcionar como en el caso de los objetos automáticos.

Las funciones de asignación asignan recursos de memoria. Los objetos pueden asignarse aún más en función de la asignación utilizando asignadores. Para los objetos automáticos, se presentan directamente, aunque se puede acceder a la memoria subyacente y usarla para proporcionar memoria a otros objetos (por ubicación new), pero esto no tiene mucho sentido como la tienda gratuita, porque no hay forma de mover el recursos en otros lugares.

Todas las demás preocupaciones están fuera del alcance de C ++. Sin embargo, pueden seguir siendo significativos.

Acerca de las implementaciones de C ++

C ++ no expone los registros de activación reificados o algunos tipos de continuaciones de primera clase (por ejemplo, por los famosos call/cc), no hay forma de manipular directamente los marcos de registros de activación, donde la implementación necesita colocar los objetos automáticos. Una vez que no hay interoperaciones (no portátiles) con la implementación subyacente (código "nativo" no portátil, como el código de ensamblaje en línea), una omisión de la asignación subyacente de los marcos puede ser bastante trivial. Por ejemplo, cuando la función llamada está en línea, los marcos pueden fusionarse efectivamente en otros, por lo que no hay forma de mostrar cuál es la "asignación".

Sin embargo, una vez que se respetan los interops, las cosas se vuelven complejas. Una implementación típica de C ++ expondrá la capacidad de interoperabilidad en ISA (arquitectura de conjunto de instrucciones) con algunas convenciones de llamada como el límite binario compartido con el código nativo (máquina de nivel ISA). Esto sería explícitamente costoso, especialmente cuando se mantiene el puntero de la pila , que a menudo se mantiene directamente por un registro de nivel ISA (con probablemente instrucciones específicas de máquina para acceder). El puntero de la pila indica el límite del marco superior de la llamada a la función (actualmente activa). Cuando se ingresa una llamada a una función, se necesita un nuevo marco y el puntero de la pila se agrega o resta (según la convención de ISA) por un valor no menor que el tamaño de marco requerido. Entonces se dice el marco asignadocuando el puntero de la pila después de las operaciones. Los parámetros de las funciones también se pueden pasar al marco de la pila, dependiendo de la convención de llamada utilizada para la llamada. El marco puede contener la memoria de objetos automáticos (probablemente incluyendo los parámetros) especificados por el código fuente de C ++. En el sentido de tales implementaciones, estos objetos están "asignados". Cuando el control sale de la llamada a la función, el marco ya no es necesario, por lo general se libera restaurando el puntero de la pila al estado anterior a la llamada (guardado previamente de acuerdo con la convención de llamada). Esto se puede ver como "desasignación". Estas operaciones hacen que el registro de activación sea efectivamente una estructura de datos LIFO, por lo que a menudo se llama " la pila (de llamadas) ".

Debido a que la mayoría de las implementaciones de C ++ (particularmente las que se dirigen al código nativo de nivel ISA y usan el lenguaje ensamblador como salida inmediata) usan estrategias similares como esta, un esquema de "asignación" tan confuso es popular. Dichas asignaciones (así como las desasignaciones) gastan ciclos de máquina, y puede ser costoso cuando las llamadas (no optimizadas) ocurren con frecuencia, a pesar de que las microarquitecturas de CPU modernas pueden tener optimizaciones complejas implementadas por hardware para el patrón de código común (como usar un motor de pila en la implementación PUSH/ POPinstrucciones).

Pero de todos modos, en general, es cierto que el costo de la asignación del marco de la pila es significativamente menor que una llamada a una función de asignación que opera el almacén gratuito (a menos que esté totalmente optimizado) , que en sí mismo puede tener cientos de (si no millones de :-) operaciones para mantener el puntero de la pila y otros estados. Las funciones de asignación generalmente se basan en la API proporcionada por el entorno alojado (por ejemplo, tiempo de ejecución proporcionado por el sistema operativo). Diferente al propósito de mantener objetos automáticos para llamadas a funciones, tales asignaciones son de propósito general, por lo que no tendrán una estructura de marco como una pila. Tradicionalmente, asignan espacio desde el almacenamiento de la agrupación llamado montón (o varios montones). A diferencia de la "pila", el concepto "montón" aquí no indica la estructura de datos que se está utilizando;Se deriva de las primeras implementaciones de lenguaje hace décadas. (Por cierto, la pila de llamadas generalmente se asigna con un tamaño fijo o especificado por el usuario desde el montón por el entorno en el inicio del programa o subproceso). La naturaleza de los casos de uso hace que las asignaciones y las desasignaciones de un montón sean mucho más complicadas (que el empuje o el estallido de stack frames), y difícilmente se puede optimizar directamente por hardware.

Efectos sobre el acceso a la memoria

La asignación de pila habitual siempre coloca el nuevo marco en la parte superior, por lo que tiene una localidad bastante buena. Esto es amigable para el caché. OTOH, la memoria asignada aleatoriamente en la tienda gratuita no tiene esa propiedad. Desde ISO C ++ 17, hay plantillas de recursos de grupo proporcionadas por <memory>. El propósito directo de dicha interfaz es permitir que los resultados de asignaciones consecutivas estén muy juntos en la memoria. Esto reconoce el hecho de que esta estrategia es generalmente buena para el rendimiento con implementaciones contemporáneas, por ejemplo, amigable para el caché en arquitecturas modernas. Sin embargo, se trata del rendimiento del acceso en lugar de la asignación .

Concurrencia

La expectativa de acceso concurrente a la memoria puede tener diferentes efectos entre la pila y los montones. Una pila de llamadas generalmente es propiedad exclusiva de un subproceso de ejecución en una implementación de C ++. OTOH, los montones a menudo se comparten entre los hilos en un proceso. Para tales montones, las funciones de asignación y desasignación deben proteger la estructura de datos administrativos internos compartidos de la carrera de datos. Como resultado, las asignaciones de montón y las desasignaciones pueden tener una sobrecarga adicional debido a las operaciones de sincronización interna.

Eficiencia Espacial

Debido a la naturaleza de los casos de uso y las estructuras de datos internas, los montones pueden sufrir fragmentación de la memoria interna , mientras que la pila no. Esto no tiene un impacto directo en el rendimiento de la asignación de memoria, pero en un sistema con memoria virtual , la baja eficiencia de espacio puede degenerar el rendimiento general del acceso a la memoria. Esto es particularmente horrible cuando HDD se usa como un intercambio de memoria física. Puede causar una latencia bastante larga, a veces miles de millones de ciclos.

Limitaciones de las asignaciones de pila

Aunque las asignaciones de pila son a menudo superiores en rendimiento que las asignaciones de pila en realidad, ciertamente no significa que las asignaciones de pila siempre puedan reemplazar las asignaciones de pila.

Primero, no hay forma de asignar espacio en la pila con un tamaño especificado en tiempo de ejecución de forma portátil con ISO C ++. Hay extensiones proporcionadas por implementaciones como allocaVLA (matriz de longitud variable) de G ++, pero hay razones para evitarlas. (IIRC, la fuente de Linux elimina el uso de VLA recientemente). (También tenga en cuenta que ISO C99 tiene VLA obligatorio, pero ISO C11 hace que el soporte sea opcional).

En segundo lugar, no existe una forma confiable y portátil de detectar el agotamiento del espacio de la pila. Esto a menudo se llama desbordamiento de pila _{(hmm, la etimología de este sitio)} , pero probablemente más exactamente, desbordamiento de pila . En realidad, esto a menudo provoca un acceso no válido a la memoria, y el estado del programa se corrompe (... o, lo que es peor, un agujero de seguridad). De hecho, ISO C ++ no tiene el concepto de "la pila" y lo convierte en un comportamiento indefinido cuando el recurso se agota . Tenga cuidado con la cantidad de espacio que debe dejarse para los objetos automáticos.

Si se agota el espacio de la pila, hay demasiados objetos asignados en la pila, que pueden ser causados ​​por demasiadas llamadas activas de funciones o el uso incorrecto de objetos automáticos. Tales casos pueden sugerir la existencia de errores, por ejemplo, una llamada de función recursiva sin condiciones de salida correctas.

Sin embargo, a veces se desean llamadas recursivas profundas. En implementaciones de lenguajes que requieren soporte de llamadas activas no vinculadas (donde la profundidad de la llamada solo está limitada por la memoria total), es imposible usar la pila de llamadas nativas (contemporáneas) directamente como el registro de activación del lenguaje objetivo como las implementaciones típicas de C ++. Para solucionar el problema, se necesitan formas alternativas de construcción de registros de activación. Por ejemplo, SML / NJ asigna explícitamente marcos en el montón y utiliza pilas de cactus . La complicada asignación de tales marcos de registro de activación generalmente no es tan rápida como los marcos de la pila de llamadas. Sin embargo, si dichos idiomas se implementan aún más con la garantía de adecuada recursión de cola, la asignación directa de la pila en el lenguaje de objetos (es decir, el "objeto" en el lenguaje no se almacena como referencias, pero los valores primitivos nativos que pueden asignarse uno a uno a objetos C ++ no compartidos) es aún más complicado con más pena de desempeño en general. Cuando se usa C ++ para implementar dichos lenguajes, es difícil estimar los impactos en el rendimiento.

Hay un punto general sobre estas optimizaciones.

La optimización que obtiene es proporcional a la cantidad de tiempo que el contador del programa está realmente en ese código.

Si prueba el contador del programa, descubrirá dónde pasa su tiempo, y eso generalmente se encuentra en una pequeña parte del código, y a menudo en las rutinas de la biblioteca sobre las que no tiene control.

Solo si encuentra que pasa mucho tiempo en la asignación de montón de sus objetos, será notablemente más rápido apilarlos.

La asignación de pila casi siempre será tan rápida o más rápida que la asignación de pila, aunque ciertamente es posible que un asignador de pila simplemente use una técnica de asignación basada en pila.

Sin embargo, existen problemas más importantes cuando se trata del rendimiento general de la asignación basada en la pila frente a la pila (o en términos ligeramente mejores, la asignación local frente a la externa). Por lo general, la asignación del montón (externo) es lenta porque se trata de muchos tipos diferentes de asignaciones y patrones de asignación. Reducir el alcance del asignador que está utilizando (haciéndolo local para el algoritmo / código) tenderá a aumentar el rendimiento sin ningún cambio importante. Agregar una mejor estructura a sus patrones de asignación, por ejemplo, forzar un pedido LIFO en pares de asignación y desasignación también puede mejorar el rendimiento de su asignador al usar el asignador de una manera más simple y estructurada. O bien, puede usar o escribir un asignador ajustado para su patrón de asignación particular; la mayoría de los programas asignan algunos tamaños discretos con frecuencia, por lo tanto, un montón que se basa en un búfer lookaside de unos pocos tamaños fijos (preferiblemente conocidos) funcionará extremadamente bien. Windows usa su montón de baja fragmentación por esta misma razón.

Por otro lado, la asignación basada en la pila en un rango de memoria de 32 bits también está llena de peligros si tiene demasiados hilos. Las pilas necesitan un rango de memoria contiguo, por lo que cuantos más subprocesos tenga, más espacio de dirección virtual necesitará para que se ejecuten sin un desbordamiento de pila. Esto no será un problema (por ahora) con 64 bits, pero ciertamente puede causar estragos en programas de larga ejecución con muchos hilos. Quedarse sin espacio de direcciones virtuales debido a la fragmentación siempre es difícil de manejar.

Como otros han dicho, la asignación de la pila es generalmente mucho más rápida.

Sin embargo, si sus objetos son caros de copiar, la asignación en la pila puede conducir a un gran impacto en el rendimiento más tarde cuando use los objetos si no tiene cuidado.

Por ejemplo, si asigna algo en la pila y luego lo coloca en un contenedor, hubiera sido mejor asignarlo en el montón y almacenar el puntero en el contenedor (por ejemplo, con std :: shared_ptr <>). Lo mismo es cierto si está pasando o devolviendo objetos por valor y otros escenarios similares.

El punto es que, aunque la asignación de la pila suele ser mejor que la asignación del montón en muchos casos, a veces si hace todo lo posible para asignar la pila cuando no se ajusta mejor al modelo de cálculo, puede causar más problemas de los que resuelve.

class Foo {
public:
    Foo(int a) {

    }
}
int func() {
    int a1, a2;
    std::cin >> a1;
    std::cin >> a2;

    Foo f1(a1);
    __asm push a1;
    __asm lea ecx, [this];
    __asm call Foo::Foo(int);

    Foo* f2 = new Foo(a2);
    __asm push sizeof(Foo);
    __asm call operator new;//there's a lot instruction here(depends on system)
    __asm push a2;
    __asm call Foo::Foo(int);

    delete f2;
}

Sería así en asm. Cuando estás dentro func, el f1puntero y f2se ha asignado en la pila (almacenamiento automatizado). Y, por cierto, Foo f1(a1)no tiene efectos sobre la instrucción puntero de pila ( esp), se ha asignado, si se funcquiere obtener el miembro f1, que de la instrucción es algo como esto: lea ecx [ebp+f1], call Foo::SomeFunc(). Otra cosa que la asignación de la pila puede hacer que alguien piense que la memoria es algo así FIFO, lo que FIFOsucedió cuando ingresas a alguna función, si estás en la función y asignas algo como int i = 0, no sucedió ningún impulso.

Se ha mencionado antes que la asignación de la pila simplemente mueve el puntero de la pila, es decir, una sola instrucción en la mayoría de las arquitecturas. Compare eso con lo que generalmente sucede en el caso de la asignación del montón.

El sistema operativo mantiene porciones de memoria libre como una lista vinculada con los datos de la carga útil que consisten en el puntero a la dirección inicial de la porción libre y el tamaño de la porción libre. Para asignar X bytes de memoria, se recorre la lista de enlaces y se visita cada nota en secuencia, verificando si su tamaño es al menos X. Cuando se encuentra una porción con tamaño P> = X, P se divide en dos partes con Tallas X y PX. La lista vinculada se actualiza y se devuelve el puntero a la primera parte.

Como puede ver, la asignación de almacenamiento dinámico depende de muchos factores, como la cantidad de memoria que solicita, la fragmentación de la memoria, etc.

En general, la asignación de la pila es más rápida que la asignación del montón como se menciona en casi todas las respuestas anteriores. Un stack stack o pop es O (1), mientras que la asignación o liberación de un montón podría requerir una caminata de asignaciones anteriores. Sin embargo, por lo general no debe asignar en bucles estrechos e intensivos en rendimiento, por lo que la elección generalmente se reducirá a otros factores.

Puede ser bueno hacer esta distinción: puede usar un "asignador de pila" en el montón. Estrictamente hablando, considero que la asignación de pila significa el método real de asignación en lugar de la ubicación de la asignación. Si está asignando muchas cosas en la pila real del programa, eso podría ser malo por varias razones. Por otro lado, usar un método de pila para asignar en el montón cuando sea posible es la mejor opción que puede hacer para un método de asignación.

Como mencionaste Metrowerks y PPC, supongo que te refieres a Wii. En este caso, la memoria es muy importante, y usar un método de asignación de pila siempre que sea posible garantiza que no desperdicie memoria en fragmentos. Por supuesto, hacer esto requiere mucho más cuidado que los métodos de asignación de montón "normales". Es aconsejable evaluar las compensaciones para cada situación.

Observe que, por lo general, las consideraciones no tienen que ver con la velocidad y el rendimiento al elegir la asignación de pila versus pila. La pila actúa como una pila, lo que significa que es adecuada para empujar bloques y hacerlos estallar nuevamente, último en entrar, primero en salir. La ejecución de los procedimientos también es similar a la pila, el último procedimiento ingresado es el primero en salir. En la mayoría de los lenguajes de programación, todas las variables necesarias en un procedimiento solo serán visibles durante la ejecución del procedimiento, por lo tanto, se empujan al ingresar a un procedimiento y se sacan de la pila al salir o regresar.

Ahora para un ejemplo donde la pila no se puede usar:

Proc P
{
  pointer x;
  Proc S
  {
    pointer y;
    y = allocate_some_data();
    x = y;
  }
}

Si asigna algo de memoria en el procedimiento S y la coloca en la pila y luego sale de S, los datos asignados se extraerán de la pila. Pero la variable x en P también apuntó a esos datos, por lo que x ahora apunta a algún lugar debajo del puntero de la pila (suponga que la pila crece hacia abajo) con un contenido desconocido. El contenido aún puede estar allí si el puntero de la pila simplemente se mueve hacia arriba sin borrar los datos debajo de él, pero si comienza a asignar nuevos datos en la pila, el puntero x podría apuntar a esos nuevos datos.

Nunca haga suposiciones prematuras ya que el uso y el código de otras aplicaciones pueden afectar su función. Por lo tanto, mirar la función es que el aislamiento no sirve de nada.

Si usted es serio con la aplicación, VTune o use cualquier herramienta de perfil similar y observe los puntos de acceso.

Ketan

Me gustaría decir que en realidad el código generado por GCC (recuerdo VS también) no tiene gastos generales para la asignación de la pila .

Diga para la siguiente función:

  int f(int i)
  {
      if (i > 0)
      {   
          int array[1000];
      }   
  }

A continuación se muestra el código generado:

  __Z1fi:
  Leh_func_begin1:
      pushq   %rbp
  Ltmp0:
      movq    %rsp, %rbp
  Ltmp1:
      subq    $**3880**, %rsp <--- here we have the array allocated, even the if doesn't excited.
  Ltmp2:
      movl    %edi, -4(%rbp)
      movl    -8(%rbp), %eax
      addq    $3880, %rsp
      popq    %rbp
      ret 
  Leh_func_end1:

Entonces, independientemente de la cantidad de variable local que tenga (incluso dentro si cambia o cambia), solo el 3880 cambiará a otro valor. A menos que no tenga una variable local, esta instrucción solo debe ejecutarse. Asignar variable local no tiene sobrecarga.