333 votos

C++, Que es más rápido: la asignación de Pila o Montón de asignación de

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

Yo estaba cuidando a la pila de asignar las cosas donde podía, en lugar de un montón de asignación de los mismos. Él me estaba hablando y mirando por encima de mi hombro y me dijo que no era necesario, porque son el mismo rendimiento que los sabios.

Yo siempre estaba bajo la impresión de que el cultivo de la pila era constante en el tiempo, y el montón de asignación de desempeño dependía de la complejidad actual de la pila de asignación (encontrar un agujero del tamaño adecuado) y de la asignación (colapso de los agujeros para reducir la fragmentación, como muchos de la biblioteca estándar de implementaciones de tomar el tiempo para hacer esto durante la elimina, si no me equivoco).

Esto me parece algo que probablemente iba a ser muy dependiente del compilador. Para este proyecto en particular estoy usando un Metrowerks compilador para el PPC de la arquitectura. La penetración en esta combinación sería más útil, pero en general, para el GCC, y MSVC++, cuál es el caso? Es la asignación del montón no tan alto rendimiento como la asignación de pila? No hay diferencia? O son las diferencias tan minuto se convierte en inútil micro-optimización.

348voto

Torbjörn Gyllebring Puntos 8180

La asignación de pila es mucho más rápido ya que todo lo que realmente hace es mover el puntero de la pila. El uso de grupos de memoria, usted puede obtener un rendimiento comparable de la asignación del montón, pero que viene con un leve agregado de la complejidad y de sus propios dolores de cabeza.

También, pila vs. montón no es sólo un rendimiento consideración; también nos dice mucho acerca de la vida útil de los objetos.

112voto

Dan Puntos 18831

La pila es mucho más rápido. Es, literalmente, sólo se utiliza una única instrucción en la mayoría de arquitecturas, en la mayoría de los casos, por ejemplo. en x86:

sub esp, 0x10

(Mueve el puntero de la pila hacia abajo por 0x10 bytes y de ese modo se "asigna" esos bytes para su uso por una variable.)

Por supuesto, la de la pila de tamaño es muy, muy finito, como usted tendrá de forma rápida de averiguar si el uso excesivo de la asignación de pila o tratar de hacer una recursión infinita :-)

También, hay pocas razones para optimizar el rendimiento de código que no haya necesidad de ella, como se demuestra por la generación de perfiles. "Prematuro optimización" a menudo causa más problemas de lo que vale.

Mi regla de oro: si sé que voy a necesitar algunos datos en tiempo de compilación, y es en virtud de unos pocos cientos de bytes de tamaño, yo la pila-asignar. De lo contrario me montón de asignar.

83voto

Max Lybbert Puntos 11822

Honestamente, es trivial para 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 a un tonto de coherencia es el hobgoblin de las mentes pequeñas. Al parecer, la optimización de compiladores son los duendes de muchos de los programadores de la mente. Esta discusión se utiliza para estar en la parte inferior de la respuesta, pero la gente al parecer no puede ser molestado en leer que ahora, así que me estoy moviendo de aquí para evitar hacerse preguntas que he contestado ya.

Un compilador de optimización puede notar que este código no hace nada, y puede optimizar la distancia. Es trabajo del optimizador para hacer cosas como esa, y la lucha contra el optimizador es un tonto, absurdo.

Yo recomendaría la elaboración de este código con la optimización de apagado, porque no hay una buena manera de engañar a todos los optimizador actualmente en uso o que se esté en uso en el futuro.

Cualquiera que convierte el optimizador de en y, a continuación, se queja acerca de la lucha que debe ser objeto de escarnio público.

Si me importaba precisión de nanosegundos yo no usaría std::clock(). Si quería publicar los resultados de una tesis doctoral me gustaría hacer un reparto más grande acerca de esto, y probablemente voy a comparar GCC, Tendra/Ten15, LLVM, Watcom, Borland, Visual C++, Digital Mars, ICC y otros compiladores. Como es, la asignación del montón lleva cientos de veces más que la asignación de pila, y no veo nada útil acerca de la investigación de la pregunta.

El optimizador tiene una misión para deshacerse del código que lo estoy probando. No veo ninguna razón para decir que el optimizador de ejecutar y, a continuación, intentar engañar a la optimizador en realidad, no de la optimización. Pero si he visto el valor de hacer eso, me gustaría hacer uno o más de los siguientes:

  1. Agregar a un miembro de datos a empty, y el acceso a los datos miembro en el lazo; pero si yo sólo he leído a partir de los datos miembro, el optimizador puede hacer el doblado de constantes y eliminar el bucle; si sólo nunca escribir a los datos de los miembros, el optimizador puede omitir todas, pero la última iteración del bucle. Además, la pregunta no era "la asignación de pila y los datos de acceso vs. montón de asignación y acceso a los datos.

  2. Declarar e volatile, pero volatile es a menudo compilado incorrectamente (PDF).

  3. Tomar la dirección de e dentro del bucle (y tal vez de asignarlo a una variable que se declara extern y definida en otro archivo). Pero incluso en este caso, el compilador puede notar que -- en la pila por lo menos -- e siempre va a ser asignado a la misma dirección de memoria, y luego hacer el doblado de constantes como en (1) anterior. Tengo todas las iteraciones del bucle, pero el objeto no es nunca en realidad asignados.

Más allá de lo obvio, esta prueba es deficiente en que las medidas de asignación y desasignación, y a la pregunta original, no preguntar acerca de cancelación. Por supuesto, las variables asignadas en la pila automáticamente se cancela la asignación al final de su alcance, por lo tanto, no llamando delete (1) sesgo de los números (pila de desasignación se incluyen en las cifras acerca de la asignación de pila, por lo que es justo para medir montón de desasignación) y (2) hacer un muy mal pérdida de memoria, a menos que se guarde en una referencia para el nuevo puntero y llame delete después tenemos nuestra medición del tiempo.

En mi máquina, el uso de g++ 3.4.4 en Windows, me sale "0 clock ticks" tanto de la pila y el heap de la asignación de cualquier cosa menos de 100000 asignaciones, e incluso entonces me sale "0 clock ticks" para la asignación de pila y "15 de impulsos de reloj" para la asignación del montón. Cuando yo medida de 10.000.000 de asignaciones, la asignación de pila lleva a 31 de impulsos de reloj y el montón de asignación de toma de 1562 impulsos de reloj.


Sí, un compilador de optimización puede eludir la creación de los objetos vacíos. Si entiendo correctamente, incluso se puede eludir la totalidad del primer bucle. Cuando me encontré con el iteraciones a 10.000.000 de asignación de pila tomó el 31 de impulsos de reloj y de la asignación del montón tomó el año 1562, el reloj avanza. Creo que es seguro decir que sin decirle g++ para optimizar el ejecutable, g++ no eludir los constructores.


En los años desde que escribí esto, la preferencia por Stack Overflow ha sido el post de rendimiento de la optimización se basa. En general, creo que esto es correcto. Sin embargo, aún creo que es tonto pedir el compilador para optimizar el código cuando en realidad no quiera que el código optimizado. Me parece de ser muy similar a la de tener que pagar extra por el servicio de valet parking, pero se niega a entregar las llaves. En este caso particular, no quiero que el optimizador de ejecución.

El uso de una versión ligeramente modificada de la referencia (a abordar el punto válido que el programa original no asignar algo en la pila en cada iteración del bucle) y compilar sin optimizaciones, pero la vinculación a la liberación de las bibliotecas (para abordar el punto válido que no queremos incluir cualquier 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 comandos cl foo.cc /Od /MT /EHsc.

Usted puede no estar de acuerdo con mi enfoque para obtener una optimizado no construir. Eso está bien: siéntete libre de modificar el punto de referencia tanto como usted desea. Cuando me doy la vuelta en la optimización, me sale:

on_stack took 0.000000 seconds
on_heap took 51.608723 seconds

No porque la asignación de pila es realmente instantáneo, pero debido a que cualquier medio decente compilador puede notar que on_stack de no hacer nada útil y puede ser optimizado de distancia. GCC en mi Linux portátil también los avisos que on_heap de no hacer nada útil, y optimiza así:

on_stack took 0.000003 seconds
on_heap took 0.000002 seconds

22voto

Furious Coder Puntos 609

Una cosa interesante que he aprendido acerca de la Pila vs. Montón de Asignación en la Xbox 360 Xenon procesador, que también se pueden aplicar a otros sistemas multinúcleo, es que la asignación en el Montón provoca una Sección Crítica para ser ingresados para detener todos los demás núcleos, de manera que la asignación no entra en conflicto. Por lo tanto, en un bucle estrecho, la Asignación de Pila era el camino a seguir para fijar el tamaño de las matrices se lo impidió casillas.

Esta puede ser otra de las speedup para tener en cuenta si estás de codificación para multinúcleo/multiproc, en que la pila de asignación sólo será visible por el núcleo del funcionamiento de su ámbito de función, y que no afectará a ninguna otra núcleos/Cpu.

12voto

Chris Jester-Young Puntos 102876

Usted puede escribir una especial asignador de montón de tamaños específicos de los objetos, que es muy eficiente. Sin embargo, el general asignador de montón no es particularmente eficiente.

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

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X