std :: set veloce e lento, cosa sta succedendo?

Question

Mi sono imbattuto in uno strano comportamento di std :: set.

Ecco il codice:

#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; 
} 

Sono in esecuzione su Windows XP.

Ecco la parte interessante: questa prima volta stampata è di circa 3500 ms, mentre tutti i successivi sono oltre 9000 ms! Perché sta succedendo?

Oh, e questo accade solo nella versione di rilascio (ottimizzazione -O2).

Non succede su Linux (dopo aver modificato il codice per compilare lì).

Un'ultima cosa: quando lo eseguo mentre eseguo il profiling con Intel VTune ci vogliono sempre circa 3000 ms, quindi è così che dovrebbe essere.

UPDATE: Ecco il codice nuovo:

#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; 
} 

Questo è lo stesso problema. Quello che succede è che alloco molti molti piccoli oggetti e poi li elimini in ordine casuale - quindi è simile a come appare in std :: set. Quindi questo è un problema di gestione della memoria di Windows. Non può davvero gestire bene molti piccoli allocazioni e cancellazioni.

Answer 1

Non riesco a spiegare esattamente perché questo sta accadendo, ma potrei proporre una soluzione. Sono stato in grado di riprodurlo sul mio PC quando eseguo la versione di rilascio sotto il debugger (con F5). Quando eseguo la compilazione dalla riga di comando o con Ctrl-F5 non ho questo tipo di comportamento.

Questo ha qualcosa a che fare con l'heap di debug che è attivo per impostazione predefinita quando si avvia sotto il debugger. È descritto in dettaglio here. Per evitare che ciò accada o

1. Eseguire dalla riga di comando o con Ctrl-F5 (Debug -> Avvia senza debug).
2. Vai a Progetto -> Proprietà -> Debug -> Ambiente e aggiungi _NO_DEBUG_HEAP=1.

Se dovessi indovinare, direi che ha qualcosa a che fare con l'implementazione del tracciamento dell'allocazione di memoria nel runtime Windows/VS. Probabilmente alcune liste interne si riempiono e si riallocano o qualcos'altro su queste linee.

Answer 2

Penso che std::set sia implementato come un albero di ricerca binario. Dal momento che stai aumentando di 1 unità ogni volta, in sostanza stai creando uno scenario perversariale (caso peggiore) per questo tipo di dati (il ribilanciamento dell'albero è richiesto su quasi tutti gli inserti).

Inoltre, sono 50 milioni di inserimenti, quindi è previsto un certo tempo, anche se non penserei che sarebbe 5 ms.

Inoltre, vorrei fare il tuo "clear" dopo aver stampato il tuo tempo, in quanto non vedo il motivo per cui avresti benchmark sia l'inserimento e la rimozione di elementi.