c++ - romualfons - Que es más rápido: asignación de pila o asignación de montón

romuald seo (23)

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

Me estaba cuidando de apilar las cosas donde podría, en lugar de acumularlas. Me estaba hablando y mirando por encima de mi hombro y comentó que no era necesario porque tienen el mismo rendimiento.

Siempre tuve la impresión de que hacer crecer 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 (para encontrar un agujero del tamaño adecuado) como para la desasignación (agujeros de colapso para reducir la fragmentación, como muchas implementaciones de bibliotecas estándar toman tiempo para hacer esto durante las eliminaciones si no me equivoco).

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

Preocupaciones específicas del lenguaje C ++

En primer lugar, no hay una asignación llamada "pila" o "montón" ordenada por C ++ . Si está hablando de objetos automáticos en el ámbito 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 ++). Y la memoria asignada dinámicamente está en la tienda gratuita , no necesariamente en "el montón", sin embargo este último es a menudo la implementación (por defecto).

Aunque según las reglas semánticas abstractas, los objetos automáticos aún ocupan memoria, una implementación de C ++ conforme puede ignorar este hecho cuando puede probar que esto no importa (cuando no cambia el comportamiento observable del programa). Este permiso es otorgado por 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 "como si", ISO C ++ también tiene reglas de elección de copia para permitir la omisión de creaciones específicas de objetos. De este modo se omiten las llamadas de constructor y destructor involucradas. 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 de tienda libre es definitivamente "asignación" por diseño. Bajo las reglas ISO C ++, tal asignación puede lograrse mediante una llamada de una función de asignación . Sin embargo, desde ISO C ++ 14, hay una nueva regla (no como si) para permitir la fusión de llamadas de función de asignación global (es decir, ::operator new ) en casos específicos. Por lo tanto, partes de las operaciones de asignación dinámica también pueden ser no operativas como 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 tienda gratuita, porque no hay manera de moverse. Los recursos en otra parte.

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

Sobre Implementaciones de C ++

C ++ no expone registros de activación reificados o algún tipo de continuación de primera clase (por ejemplo, por el famoso call/cc ), no hay manera de manipular directamente los marcos de registro de activación, donde la implementación debe colocar los objetos automáticos. Una vez que no haya interoperaciones (no portátiles) con la implementación subyacente (código no portátil "nativo", 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, las tramas pueden fusionarse efectivamente con otras, por lo que no hay forma de mostrar qué 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 pila , que a menudo se mantiene directamente en un registro de nivel ISA (probablemente con instrucciones específicas de la máquina para acceder). El puntero de pila indica el límite del marco superior de la llamada de función (actualmente activa). Cuando se ingresa una llamada de función, se necesita un nuevo marco y el puntero de la pila se agrega o se resta (según la convención de ISA) por un valor no menor al tamaño de marco requerido. El marco se dice entonces asignado cuando el puntero de 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 de función, el marco ya no es necesario, por lo general se libera restaurando el puntero de 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 denomina " la pila (de llamada) ". El puntero de pila indica efectivamente la posición superior de la pila.

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 su salida inmediata) utilizan estrategias similares como esta, tal esquema de "asignación" confuso es popular. Dichas asignaciones (así como las desasignaciones) consumen ciclos de máquina, y pueden ser costosas cuando las llamadas (no optimizadas) ocurren con frecuencia, aunque las microarquitecturas modernas de la CPU pueden tener optimizaciones complejas implementadas por el hardware para el patrón de código común (como usar una apilar el motor en la implementación de las instrucciones PUSH / POP ).

Pero de todos modos, en general, es cierto que el costo de la asignación de tramas de pila es significativamente menor que una llamada a una función de asignación que opera la tienda gratuita (a menos que esté totalmente optimizada) , que en sí misma puede tener cientos de (si no millones de :-) operaciones para mantener el puntero de pila y otros estados. Las funciones de asignación generalmente se basan en la API proporcionada por el entorno alojado (por ejemplo, el tiempo de ejecución proporcionado por el sistema operativo).A diferencia del propósito de mantener objetos automáticos para llamadas de funciones, tales asignaciones son de propósito general, por lo que no tendrán una estructura de cuadro como una pila. Tradicionalmente, asignan espacio desde el almacenamiento del grupo llamado heap (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 entorno en el inicio del programa o del subproceso). apilar marcos), y difícilmente puede ser optimizado 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 ubicación bastante buena. Esto es amigable para el caché. OTOH, la memoria asignada al azar en la tienda libre no tiene tal 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 las asignaciones consecutivas estén juntas en la memoria. Esto reconoce el hecho de que esta estrategia es generalmente buena para el rendimiento con implementaciones contemporáneas, por ejemplo, ser amigable al caché en las arquitecturas modernas. Sin embargo, se trata del rendimiento del acceso en lugar de la asignación .

Concurrencia

La expectativa de acceso simultáneo 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 subprocesos en un proceso. Para tales montones, las funciones de asignación y desasignación tienen que proteger la estructura de datos administrativos internos compartidos de la carrera de datos. Como resultado, las asignaciones de montón y desasignaciones pueden tener una sobrecarga adicional debido a las operaciones de sincronización internas.

Eficiencia del espacio

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 se utiliza HDD como 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 a menudo son superiores en rendimiento que las asignaciones de pila en realidad, ciertamente no significa que las asignaciones de pila siempre pueden reemplazar las asignaciones de pila.

Primero, no hay manera de asignar espacio en la pila con un tamaño especificado en tiempo de ejecución de manera portátil con ISO C ++. Existen extensiones proporcionadas por implementaciones como allocay VLA (matriz de longitud variable) de G ++, pero hay razones para evitar su uso. (IIRC, fuente de Linux elimina el uso de VLA recientemente). (También tenga en cuenta que ISO C99 tiene VLA, 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 pila. A menudo, esto se denomina desbordamiento de pila (hmm, etimología de este sitio), pero probablemente de manera más general, "saturación de pila". En realidad, esto a menudo provoca un acceso no válido a la memoria y el estado del programa se corrompe (... o quizás peor, un agujero de seguridad). De hecho, ISO C ++ no tiene un concepto de pila y lo convierte en un comportamiento indefinido cuando se agota el recurso . Tenga cuidado con la cantidad de espacio que se debe dejar para los objetos automáticos.

Si el espacio de la pila se agota, hay demasiados objetos asignados en la pila, que pueden ser causados por demasiadas llamadas de funciones activas o el uso inadecuado de objetos automáticos. Tales casos pueden sugerir la existencia de errores, por ejemplo, una llamada de función recursiva sin las 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 (la profundidad de la llamada solo está limitada por la memoria total), es imposible usar la pila de llamadas nativas directamente como el registro de activación del idioma de destino, como las implementaciones típicas de C ++. Por ejemplo, SML/NJ asigna explícitamente marcos en el montón y utiliza pilas de cactus . La asignación complicada de dichos marcos de registro de activación generalmente no es tan rápida como los marcos de pila de llamadas. Sin embargo, cuando se implementan idiomas con una recursión de cola adecuadaLa 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 que pueden asignarse uno a uno a objetos C ++ sin compartir) son aún más complicados con una mayor penalización de rendimiento en general. Cuando se utiliza C ++ para implementar dichos lenguajes, es difícil estimar los impactos en el rendimiento.

Aparte de la ventaja de rendimiento de órdenes de magnitud sobre la asignación de pila, 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.

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

Sin embargo, si sus objetos son costosos de copiar, la asignación en la pila puede provocar un gran impacto en el rendimiento más adelante cuando utilice los objetos si no tiene cuidado.

Por ejemplo, si asigna algo en la pila y luego lo coloca en un contenedor, habría sido mejor asignar en el montón y almacenar el puntero en el contenedor (por ejemplo, con un 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 pila suele ser mejor que la asignación de pila en muchos casos, a veces, si se desvía de la asignación de pila cuando no se ajusta mejor al modelo de cálculo, puede causar más problemas de los que resuelve.

Creo que la vida es crucial, y si la cosa que se asigna tiene que construirse de una manera compleja. Por ejemplo, en el modelado basado en transacciones, normalmente tiene que completar y pasar una estructura de transacción con un montón de campos a las funciones de operación. Mira 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 de hacerlo es asignar en el montón y reutilizar los objetos de transacción mediante la agrupación 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.

En general, la asignación de pila es más rápida que la asignación de pila, como se menciona en casi todas las respuestas anteriores. Un empuje o pop de pila es O (1), mientras que asignar o liberar de un montón puede requerir un paseo de asignaciones anteriores. Sin embargo, por lo general, no debería estar asignando bucles ajustados que requieran un alto rendimiento, por lo que la elección generalmente se reducirá a otros factores.

Podría ser bueno hacer esta distinción: puede usar un "asignador de pila" en el montón. Estrictamente hablando, tomo la asignación de pila para significar el método real de asignación en lugar de la ubicación de la asignación. Si está asignando un montón de cosas en la pila del programa real, eso podría ser malo por una variedad de 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 una ventaja, y usar un método de asignación de pila siempre que sea posible garantiza que no desperdicie la memoria en fragmentos. Por supuesto, hacer esto requiere mucho más cuidado que los métodos de asignación de pila "normales". Es aconsejable evaluar las compensaciones para cada situación.

Hay un punto general que se debe hacer acerca de tales 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 almacenamiento dinámico de sus objetos, será notablemente más rápido asignarlos en la pila.

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, la optimización de los compiladores es el problema de muchos programadores. Esta discusión solía estar en la parte inferior de la respuesta, pero al parecer a las personas no les molesta leer tan lejos, por lo que me estoy moviendo aquí para evitar recibir preguntas que ya he respondido.

Un compilador optimizado 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 de tontos.

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 se usarán 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 importara la precisión de nanosegundos no usaría std::clock() . Si quisiera publicar los resultados como una tesis doctoral, me gustaría hacer un gran esfuerzo al respecto, y probablemente compararía GCC, Tendra / Ten15, LLVM, Watcom, Borland, Visual C ++, Digital Mars, ICC y otros compiladores. Tal como está, la asignación de pilas lleva cientos de veces más que la asignación de pilas, y no veo nada útil sobre la investigación de la pregunta.

El optimizador tiene la misión de deshacerse del código que estoy probando. No veo ninguna razón para decirle al optimizador que 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:

Agregue un miembro de datos a empty y acceda a ese miembro de datos en el bucle; pero si solo leo del miembro de datos, el optimizador puede hacer plegado constante y eliminar el bucle; si solo escribo al miembro de datos, el optimizador puede omitir todo, excepto la última iteración del bucle. Además, la pregunta no era "asignación de pila y acceso a datos frente a asignación de montón y acceso a datos".
Declare e volatile , pero volatile menudo se compila incorrectamente (PDF).
Tome la dirección de e dentro del bucle (y tal vez asigne una variable que se declare extern y que esté definida 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 realizará el plegado constante como en (1) arriba. Obtengo todas las iteraciones del bucle, pero el objeto nunca se asigna realmente.

Más allá de lo obvio, esta prueba tiene fallas en que mide la asignación y la desasignación, y la pregunta original no se refería a 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 a delete (1) sesgar 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 a delete después de que tengamos nuestra medición de tiempo.

En mi máquina, al usar g ++ 3.4.4 en Windows, obtengo "0 tics de reloj" tanto para la asignación de pila como para el montón para menos de 100000 asignaciones, y aún así obtengo "0 tics de reloj" para la asignación de pila y "15 tics de reloj "para la asignación del montón. Cuando mido 10,000,000 de asignaciones, la asignación de pila toma 31 tics de reloj y la asignación de pila toma 1562 tics de reloj.

Sí, un compilador de optimización puede evitar crear los objetos vacíos. Si lo comprendo correctamente, incluso puede ocultar todo el primer bucle. Cuando subí las iteraciones a 10,000,000, la asignación de pila tomó 31 tics de reloj y la asignación de heap tomó 1562 tics de reloj. Creo que es seguro decir que sin decirle a g ++ que optimice el ejecutable, g ++ no elidió a los constructores.

En los años transcurridos desde que escribí esto, la preferencia por el desbordamiento de pila ha sido publicar el rendimiento de las compilaciones optimizadas. En general, creo que esto es correcto. Sin embargo, sigo pensando que es una tontería pedirle al compilador que optimice el código cuando, de hecho, usted no quiere que ese código sea optimizado. Me parece que es 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 que el programa original no asignó algo en la pila cada vez a través del bucle) y compilar sin optimizaciones pero enlazando con bibliotecas de lanzamiento (para abordar el punto válido que no utilizamos). No quiero incluir ninguna desaceleración causada por la vinculación 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 versión no optimizada. Eso está bien: no dude en 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 pila sea realmente instantánea, sino porque cualquier compilador medio decente puede notar que on_stack no hace nada útil y puede optimizarse. GCC en mi computadora portátil Linux también se da cuenta de que on_heap no hace nada útil, y también lo optimiza:

on_stack took 0.000003 seconds on_heap took 0.000002 seconds

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. Al usar 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, pila contra pila no es solo una consideración de rendimiento; También le dice mucho sobre la vida útil esperada de los objetos.

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 utilice simplemente una técnica de asignación basada en pila.

Sin embargo, hay problemas mayores cuando se trata del rendimiento general de la asignación basada en pila vs. pila (o en términos ligeramente mejores, asignación local frente a externa). Por lo general, la asignación de pila (externa) es lenta porque trata con muchos tipos diferentes de asignaciones y patrones de asignación. La reducción del alcance del asignador que está utilizando (haciéndolo local al 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 una orden de LIFO en los 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, puede usar o escribir un asignador sintonizado para su patrón de asignación particular; la mayoría de los programas asignan unos pocos tamaños discretos con frecuencia, por lo que un montón que se basa en un búfer interno de unos pocos tamaños fijos (preferiblemente conocidos) se desempeñará 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, de modo que cuantos más subprocesos tenga, más espacio de direcciones virtuales 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 duración con muchos subprocesos. Quedarse sin espacio de direcciones virtuales debido a la fragmentación siempre es un problema.

La asignación de pila es un par de instrucciones, mientras que el asignador de pila rtos más rápido que conozco (TLSF) se usa en promedio en el orden de 150 instrucciones. Además, las asignaciones de pila no requieren un bloqueo porque utilizan 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ápidas, dependiendo de cuán multitarea sea su entorno.

En general, la asignación de pilas 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 bloques.

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 utilice una variable.)

Por supuesto, el tamaño de la pila es muy, muy finito, ya que rápidamente descubrirá si se sobreutiliza la asignación de pila o trata de hacer una recursión :-)

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

Mi regla de oro: 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 apilaré.

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

Lo recomendaría 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 es probablemente necesario.

En los sistemas operativos de 32 bits que tienen varios subprocesos, la pila a menudo es bastante limitada (aunque típicamente a al menos unos pocos mb), porque el espacio de direcciones debe dividirse y, tarde o temprano, una pila de subprocesos se ejecutará en otro. En sistemas de un solo hilo (Linux glibc solo un hilo de todos modos) la limitación es mucho menor porque la pila solo puede crecer y crecer.

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

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

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

A veces, la asignación de pila requiere agregar una página o páginas de memoria virtual. Agregar una nueva página de memoria puesta a cero no requiere leer una página desde el disco, por lo que normalmente esto será mucho más rápido que buscar un montón (especialmente si parte del montón también se pagó). En una situación rara, y podría construir un ejemplo de este tipo, el espacio suficiente está disponible para una 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.

Probablemente el mayor problema de la asignación de almacenamiento dinámico frente a la asignación de pila, es que la asignación de almacenamiento dinámico en el caso general es una operación ilimitada y, por lo tanto, no puede usarla cuando la sincronización es un problema.

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

Puede escribir un asignador de pila especial para tamaños específicos de objetos que sea muy eficaz. Sin embargo, el asignador de pila general no es particularmente eficaz.

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

Se ha mencionado anteriormente que la asignación de pila es simplemente mover el puntero de pila, es decir, una sola instrucción en la mayoría de las arquitecturas. Compare eso con lo que generalmente ocurre en el caso de la asignación de almacenamiento dinámico.

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

Como puede ver, la asignación del montón depende de varios factores, como la cantidad de memoria que solicita, la fragmentación de la memoria, etc.

Tenga en cuenta que las consideraciones generalmente no tienen que ver con la velocidad y el rendimiento al elegir la asignación de pila frente a pila. La pila actúa como una pila, lo que significa que es adecuada para empujar bloques y reventarlos nuevamente, por último, por primera vez. La ejecución de procedimientos también es similar a una 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 que se presionan al ingresar en un procedimiento y se extraen de la pila al salir o regresar.

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

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 quitarán de la pila. Pero la variable x en P también apunta a esos datos, por lo que x ahora apunta a algún lugar debajo del puntero de la pila (suponiendo que la pila crece hacia abajo) con un contenido desconocido. El contenido aún podría estar allí si el puntero de la pila simplemente se mueve hacia arriba sin borrar los datos que se encuentran debajo de él, pero si comienza a asignar nuevos datos en la pila, el puntero x podría apuntar a esos nuevos datos.

Una cosa interesante que aprendí sobre la Asignación de Pila vs. Pila en el procesador Xenon de Xbox 360, que también puede aplicarse a otros sistemas multinúcleo, es que la asignación en la Pila hace que se ingrese una Sección Crítica para detener todos los otros núcleos para que la asignación no se haga. No hay conflicto. Por lo tanto, en un circuito cerrado, la Asignación de pila era el camino a seguir para arreglos de tamaño fijo, ya que evitaba las paradas.

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

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

Una variable de pila sigue las reglas de alcance, mientras que una pila no lo hace. 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 se puede predecir de antemano la cadena de llamadas de la función general. Por lo tanto, una simple asignación de 200 bytes de su parte puede provocar un desbordamiento de pila. Esto es especialmente importante si está escribiendo una biblioteca, no una aplicación.

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

Decir para la siguiente función:

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

A continuación se genera el código:

__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 de si o interruptor), solo el 3880 cambiará a otro valor. A menos que no tenga una variable local, esta instrucción solo debe ejecutarse. Así que asignar variable local no tiene gastos generales.

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

Si es serio con la aplicación, entonces VTune o use una herramienta de creación de perfiles similar y observe los puntos de acceso.

Ketan

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 en func , el f1 y el puntero f2 se han asignado en la pila (almacenamiento automatizado). Y, por cierto, Foo f1(a1) no tiene efectos de instrucción en el puntero de pila ( esp ), se ha asignado, si la func quiere obtener el miembro f1 , su instrucción es algo como esto: lea ecx [ebp+f1], call Foo::SomeFunc() . Otra cosa que la asignación de pila puede hacer que alguien piense que la memoria es algo como FIFO , el FIFO acaba de suceder cuando entra en alguna función, si está en la función y asigna algo como int i = 0 , no sucedió ningún empuje.