std :: establecido rápido y lento, ¿qué está pasando?

Question

He encontrado un comportamiento extraño de std :: set.

Aquí está el código:

#include <cstdio> 
#include <windows.h> 
#include <stdlib.h> 

#include <vector> 
#include <set> 

using namespace std; 

int main(int argc, char *argv[]) 
{ 
    set<int> b[100]; 

    for (int o=0; o<10; o++) 
    { 
     int tt = GetTickCount(); 

     for (int i=0; i<5000000; i++) 
     { 
      b[o].insert(i); 
     } 

     tt = GetTickCount() - tt; 

     b[o].clear(); 

     printf("%d\n", tt); 
    } 

    return 0; 
} 

estoy corriendo en Windows XP.

Aquí está la parte interesante: este primer tiempo impreso es de aproximadamente 3500 ms, ¡mientras que todos los siguientes son más de 9000 ms! ¿Por qué está sucediendo eso?

Ah, y esto solo ocurre en la versión de lanzamiento (optimización de -O2).

No ocurre en Linux (después de cambiar el código para compilar allí).

Una cosa más: cuando lo ejecuto durante el perfilado con Intel VTune, siempre lleva unos 3000 ms, así es como debería ser.

ACTUALIZACIÓN: Aquí hay un código nuevo:

#include <cstdio> 
#include <windows.h> 
#include <stdlib.h> 

int main(int argc, char *argv[]) 
{ 
const int count = 10000000; 
int **a = new int*[count]; 

for (int o=0; o<10; o++) 
{ 
    int ttt = GetTickCount(); 

    for (int i=0; i<count; i++) 
    { 
     a[i] = new int; 

     *a[i] = i; 
    } 

    int ttt2 = GetTickCount(); 

    for (int i=0; i<count; i++) 
    { 
     int r1 = rand() * 10000 + rand(); 
     int r2 = rand() * 10000 + rand(); 
     r1 = r1%count; 
     r2 = r2%count; 

     int *e = a[r1]; 
     a[r1] = a[r2]; 
     a[r2] = e; 
    } 

    int ttt3 = GetTickCount(); 

    for (int i=0; i<count; i++) 
    { 
     delete a[i]; 
    } 

    int ttt4 = GetTickCount(); 

    printf("%d %d\n", ttt2-ttt, ttt4-ttt3); 
} 

return 0; 
} 

Este es el mismo problema. Lo que sucede es que asigno muchos objetos pequeños y luego los elimino en orden aleatorio, por lo que es similar a como se ve en std :: set. Este es un problema de administración de memoria de Windows. Realmente no puede manejar bien muchos pequeños allocs y elimina.

Answer 1

No puedo explicar exactamente por qué sucede esto, pero podría proponer una solución. Pude reproducir esto en mi PC cuando ejecuto la compilación de lanzamiento en el depurador (con F5). Cuando ejecuto la compilación desde la línea de comandos o con Ctrl-F5 no obtengo ese tipo de comportamiento.

Esto tiene algo que ver con el montón de depuración que está activado de forma predeterminada cuando se inicia bajo el depurador. Se describe en gran detalle here. Para evitar que esto ocurra,

1. Ejecutar desde la línea de comandos o con Ctrl-F5 (Depurar -> Iniciar sin depurar).
2. Vaya a Proyecto -> Propiedades -> Depuración -> Entorno y agregue _NO_DEBUG_HEAP=1.

Si tuviera que adivinar, diría que tiene algo que ver con la implementación del seguimiento de asignación de memoria en el tiempo de ejecución de Windows/VS. Probablemente algunas listas internas se llenan y reasignan o algo más en esta línea.

Answer 2

Creo que std::set se implementa como un árbol de búsqueda binaria. Como está aumentando i por 1 cada vez, básicamente está creando un escenario adversarial (peor caso) para este tipo de estructura de datos (se requiere reequilibrar el árbol en casi todos los insertos).

Además, tiene 50 millones de insertos, por lo que se espera un tiempo, aunque no creo que sea de 5 ms.

Además, me gustaría hacer su "claro" después de imprimir su tiempo, ya que no veo la razón por la que compararía tanto la inserción como la eliminación de elementos.