2009-10-22 16 views
28

En un ejemplo de ACM, tuve que crear una gran tabla para la programación dinámica. Tuve que almacenar dos enteros en cada celda, así que decidí optar por un std::pair<int, int>. Sin embargo, la asignación de una enorme variedad de ellos tomó 1.5 segundos:std :: pair <int, int> vs struct con dos int

std::pair<int, int> table[1001][1001]; 

Después, he cambiado el código de

struct Cell { 
    int first; 
    int second; 
} 

Cell table[1001][1001]; 

y la asignación tomó 0 segundos.

¿Qué explica esta gran diferencia en el tiempo?

+2

Creo que te refieres a ACM ** ICPC **. –

+2

¿Has probado esto con optimizaciones habilitadas? – jalf

+2

¿Cuál es el rendimiento si agrega un constructor no-arg a 'Cell'? – outis

Respuesta

34

std::pair<int, int>::pair() constructor inicializa los campos con los valores por defecto (cero en caso de int) y su struct Cell no (ya que sólo tiene un constructor por defecto generada automáticamente que no hace nada).

Inicializar requiere escribir en cada campo que requiere una gran cantidad de accesos de memoria que consumen mucho tiempo. Con struct Cell no se hace nada en su lugar y no hacer nada es un poco más rápido.

+4

¿lleva 1,5 segundos configurar unos 8 MB a cero? – Etan

+1

No olvides errores de caché. – sharptooth

+7

No, el problema es que la función llama al constructor. Si su matriz es global, se inicializa a cero de todos modos. Probablemente el compilador no optimiza las llamadas al constructor. –

1

Supongo que es la forma en que se crea std :: pair. Hay más sobrecarga durante invocar un constructor de par 1001x1001 veces que cuando asigna un rango de memoria.

-1

es realmente un buen ejemplo de que uno debe escribir C++ y usar STL con cuidado. ¿Alguna idea?

mi proyecto está trabajando en C & herramienta de prueba de referencia de nivel de código C++ en la que haremos muchos ejemplos de código para descubrir qué es código "bueno" y qué es un hábito de codificación "malo". vea http://effodevel.googlecode.com para aprender más sobre C9B.M. planificación. cualquier persona si ha experimentado muchos de estos casos, por favor amablemente únase al proyecto para ayudarnos.

+0

Esta no es una respuesta a la pregunta. –

+0

¿Alguna idea? Sí. Su proyecto parece comprender la idea general de que la optimización se trata * de optimización de bajo nivel * (y big-O). Sugiero que el problema es mucho más grande que eso, a saber, * generalidad galopante *, y eso podría considerar un alcance más amplio. http://stackoverflow.com/questions/926266/performance-optimization-strategies-of-last-resort/927773#927773 –

+0

No hay plan para hacer una más grande aún en la actualidad. progresar paso a paso, su ch como nivel de código, nivel de algo y nivel de arquitectura, etc. estamos entendiendo el lenguaje y los compiladores ahora. gracias por sus comentarios – Test

25

Las respuestas hasta ahora no explican la magnitud completa del problema.

Como sharptooth ha señalado, la solución de par inicializa los valores a cero. Como señaló Lemurik, la solución de pares no solo está inicializando un bloque contiguo de memoria, sino que llama al constructor de pares para cada elemento de la tabla. Sin embargo, incluso eso no explica que tome 1.5 segundos. Algo más está sucediendo.

Aquí es mi lógica:

Suponiendo que estaban en una máquina antigua, digamos funcionando a 1,33 GHz, entonces es de 1,5 segundos ciclos de reloj 2E9. Tienes 2e6 pares para construir, por lo que de alguna manera cada constructor de pares está tomando 1000 ciclos. No se requieren 1000 ciclos para llamar a un constructor que simplemente establece dos enteros a cero. No puedo ver cómo el caché falla podría hacer que tome tanto tiempo. Lo creería si el número fuera menos de 100 ciclos.

Pensé que sería interesante ver a dónde más van todos estos ciclos de CPU. Usé el compilador de C++ más antiguo que pude encontrar para ver si podía alcanzar el nivel de desperdicio requerido. Ese compilador era VC++ v6. En modo de depuración, hace algo que no entiendo. Tiene un gran bucle que llama al constructor de pares para cada elemento de la tabla, es suficiente. Ese constructor establece los dos valores a cero, es suficiente. Pero justo antes de hacer eso, establece todos los bytes en una región de 68 bytes en 0xcc. Esa región está justo antes del comienzo de la gran mesa. Luego sobrescribe el último elemento de esa región con 0x28F61200. Cada llamada del constructor de par repite esto.Presumiblemente, este es un tipo de contabilidad por parte del compilador, por lo que sabe qué regiones se inicializan cuando se buscan errores de puntero en tiempo de ejecución. Me encantaría saber exactamente para qué es esto.

De todos modos, eso explicaría hacia dónde se dirige el tiempo extra. Obviamente, otro compilador puede no ser tan malo. Y ciertamente una versión de lanzamiento optimizada no lo sería.

+4

Esto no es culpa de VC++ V6 por ejemplo. En el modo de depuración, todos los compiladores de VC inicializarán todos los bytes asignados en la pila a un valor de captura (0xCC por defecto) y toda la memoria de pila asignada se inicializará de manera similar a 0xCD.El propósito es doble: hacer que un código que esté operando en variables sin inicializar (asumido por cero) falle ruidosamente y le permita ver la pila no inicializada en el depurador de memoria. El último valor que ve escrito es un "valor canario de pila" utilizado para detectar el desbordamiento de pila (.com * risita *) s. –

1

Todas estas son muy buenas conjeturas, pero como todos saben, las conjeturas no son confiables.

Yo diría que al azar pause it dentro de ese 1,5 segundos, pero tendrías que ser bastante rápido. Si aumentaste cada dimensión por un factor de aproximadamente 3, podrías hacerlo demorar más de 10 segundos, por lo que sería más fácil hacer una pausa.

O bien, podría obtenerlo en un depurador, descomponerlo en el código de constructor de par, y luego un solo paso para ver lo que está haciendo.

De cualquier manera, obtendrías una respuesta firme a la pregunta, no solo una conjetura.