std :: pair < int, int > vs struct con dos int

Question

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

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

Después, he cambiado este código a

struct Cell {
    int first;
    int second;
}

Cell table[1001][1001];

y la asignación tomó 0 segundos.

¿Qué explica esta enorme diferencia en el tiempo?

Answer 1

std :: pair < int, int > :: pair () el constructor inicializa los campos con valores predeterminados (cero en el caso de int ) y su struct Cell no lo hace (ya que solo tiene un constructor predeterminado generado automáticamente que no hace nada).

La inicialización requiere escritura en cada campo, lo que requiere una gran cantidad de accesos a la memoria que requieren relativamente mucho tiempo. Con struct Cell no se hace nada y hacer nada es un poco más rápido.

Answer 2

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

Como Sharptooth ha señalado, la solución de par inicializa los valores a cero. Como Lemurik señaló, la solución de par no es solo inicializar un bloque de memoria contiguo, sino que está llamando al constructor de par para cada elemento de la tabla. Sin embargo, incluso eso no tiene en cuenta que tarda 1,5 segundos. Algo más está sucediendo.

Aquí está mi lógica:

Suponiendo que estaba en una máquina antigua, digamos que funciona a 1.33ghz, entonces 1.5 segundos son 2e9 ciclos de reloj. Tienes 2e6 pares para construir, así que de alguna manera cada constructor de pares está tomando 1000 ciclos. No se necesitan 1000 ciclos para llamar a un constructor que solo establece dos enteros en cero. No puedo ver cómo las fallas en la memoria caché hacen que tome tanto tiempo. Lo creería si el número fuera menor de 100 ciclos.

Pensé que sería interesante ver a dónde más van todos estos ciclos de CPU. Utilicé el compilador de C ++ más antiguo y horrible que pude encontrar para ver si podía alcanzar el nivel de desperdicio requerido. Ese compilador fue VC ++ v6. En el 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, lo suficientemente justo. Ese constructor establece los dos valores en cero, lo suficientemente justo. 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 pares repite esto. Es de suponer que este es un tipo de contabilidad por parte del compilador, por lo que sabe qué regiones se inicializan al verificar los errores de puntero en el tiempo de ejecución. Me encantaría saber exactamente para qué es esto.

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

Answer 3

Creo que es la forma en que se crea std :: pair. Hay más sobrecarga durante la invocación de un constructor de pares 1001x1001 veces que cuando simplemente asigna un rango de memoria.

Answer 4

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

Diría aleatoriamente deténgalo dentro de esos 1,5 segundos, pero tendría que ser bastante rápido. Si aumentara cada dimensión en un factor de aproximadamente 3, podría hacer que tomara más de 10 segundos, por lo que sería más fácil hacer una pausa.

O, puedes obtenerlo bajo un depurador, dividirlo en el código del constructor de pares y luego en un solo paso para ver qué está haciendo.

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

Answer 5

es realmente un buen ejemplo de cómo se debe escribir C ++ y usar STL con cuidado. algún pensamiento?

mi proyecto está trabajando en una herramienta de prueba de referencia de nivel de código C & amp; C ++ en la que haremos muchos ejemplos de código para descubrir qué es " bueno " código y qué es un " mal " hábito de codificación. consulte http://effodevel.googlecode.com para obtener más información sobre C9B.M. planificación. Si ha experimentado muchos de estos casos, únase al proyecto para ayudarnos.