¿Qué es más rápido: asignación de pila o asignación de montón?
Esta pregunta puede parecer bastante elemental, pero es un debate que tuve con otro desarrollador con el que trabajo.
Me estaba ocupando de asignar cosas en pilas donde pudiera, en lugar de asignarlas en pilas. Él estaba hablando conmigo y mirando por encima de mi hombro y comentó que no era necesario porque son iguales en cuanto a desempeño.
Siempre tuve la impresión de que hacer crecer la pila era un tiempo constante, y que 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 la desasignación (colapsar los agujeros 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 Metrowerks para la arquitectura PPC . Una comprensión de 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 tan alto rendimiento como la asignación de pila? ¿No hay diferencia? ¿O las diferencias son tan pequeñas que la microoptimización se vuelve inútil?
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 utilizar grupos de memoria, puede obtener un rendimiento comparable con la asignación del montón, pero eso conlleva una ligera complejidad adicional y sus propios dolores de cabeza.
Además, pila versus montón no es sólo una consideración de rendimiento; también le dice mucho sobre la vida útil esperada de los objetos.
La pila es mucho más rápida. Literalmente, solo utiliza una única 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, como descubrirás rápidamente si abusas de la asignación de la pila o intentas hacer 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 los que vale.
Mi regla general: si sé que voy a necesitar algunos datos en tiempo de compilación y tienen un tamaño inferior a unos pocos cientos de bytes, los asigno en pila. De lo contrario, lo asigno en 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 la consistencia tonta es el duende de las mentes pequeñas . Aparentemente, los compiladores optimizadores son los duendes de la mente de muchos programadores. Esta discusión solía estar al final de la respuesta, pero aparentemente la gente no se molesta en leer tan lejos, así que la estoy moviendo aquí arriba para evitar recibir preguntas que ya respondí.
Un compilador optimizador puede notar que este código no hace nada y puede optimizarlo por completo. Es trabajo del optimizador hacer cosas así, y luchar contra el optimizador es una tontería.
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 active el optimizador y luego se queje de luchar contra él debería ser objeto de burla pública.
Si me importara la precisión de nanosegundos, no la usaría std::clock(). Si quisiera publicar los resultados como una tesis doctoral, le daría más importancia a esto 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 lleva cientos de veces más tiempo que la asignación de la pila, y no veo nada útil en 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 intentar engañarlo para que no optimice. Pero si viera valor en hacer eso, haría una o más de las siguientes cosas:
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 plegar constantemente y eliminar el bucle; Si solo escribo en el miembro de datos, el optimizador puede omitir todas las iteraciones del ciclo excepto la última. Además, la pregunta no era "asignación de pila y acceso a datos versus asignación de montón y acceso a datos".Declarar
evolatile, perovolatilea menudo se compila incorrectamente (PDF).Tome la dirección
edentro del bucle (y tal vez asígnela a una variable que esté declaradaexterny definida en otro archivo). Pero incluso en este caso, el compilador puede notar que, al menos en la pila,esiempre se asignará en la misma dirección de memoria y luego realizará un plegado constante como en (1) anterior. Obtengo todas las iteraciones del bucle, pero el objeto nunca se asigna.
Más allá de lo obvio, esta prueba tiene el defecto de que 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 está incluida 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) provocar una pérdida de memoria bastante grave, a menos que mantengamos una referencia al nuevo puntero y llamemos deletedespués de haber obtenido nuestra medición del tiempo.
En mi máquina, usando g++ 3.4.4 en Windows, obtengo "0 tics de reloj" para la asignación de pila y de montón para cualquier cantidad menor a 100000 asignaciones, e incluso entonces 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 la pila requiere 31 tics de reloj y la asignación del montón requiere 1562 tics de reloj.
Sí, un compilador de optimización puede evitar la creación de objetos vacíos. Si entiendo correctamente, puede incluso eludir todo el primer ciclo. Cuando aumenté las iteraciones a 10.000.000, la asignación de pila tomó 31 tics de reloj y la asignación de montón tomó 1562 tics de reloj. Creo que es seguro decir que sin decirle a g++ que optimice el ejecutable, g++ no eliminó a los constructores.
En los años transcurridos desde que escribí esto, la preferencia en Stack Overflow ha sido publicar el rendimiento de 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 en realidad no quieres que ese código se optimice. Me parece muy parecido a pagar extra por el servicio de aparcacoches, pero negarse a entregar las llaves. En este caso particular, no quiero que se ejecute el optimizador.
Usar 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 que atravesó el ciclo) y compilar sin optimizaciones pero vinculando a las bibliotecas de lanzamiento (para abordar el punto válido de que no No queremos incluir ninguna desaceleración causada por el enlace 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éntete libre de modificar el punto de referencia tanto como quieras. Cuando activo 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 eso on_stackno hace nada útil y se puede optimizar. GCC en mi computadora portátil Linux también nota 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 versus montón en el procesador Xenon de Xbox 360, 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, de modo que la asignación no No hay conflicto. Por lo tanto, en un circuito cerrado, Stack Allocation era el camino a seguir para matrices de tamaño fijo, ya que evitaba las paradas.
Esta puede ser otra aceleración a considerar 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.
