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.
Creo que te refieres a ACM ** ICPC **. –
¿Has probado esto con optimizaciones habilitadas? – jalf
¿Cuál es el rendimiento si agrega un constructor no-arg a 'Cell'? – outis