std :: pair <int, int> vs struct with two int's

Question

In un esempio ACM, ho dovuto creare una grande tabella per la programmazione dinamica. Ho dovuto memorizzare due numeri interi in ogni cella, così ho deciso di andare per un std::pair<int, int>. Tuttavia, l'assegnazione di una vasta gamma di loro ha 1,5 secondi:

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

In seguito, ho cambiato il codice per

struct Cell { 
    int first; 
    int second; 
} 

Cell table[1001][1001]; 

e l'assegnazione prese 0 secondi.

Che cosa spiega questa enorme differenza nel tempo?

Answer 1

std::pair<int, int>::pair() costruttore inizializza i campi con valori di default (zero nel caso di int) e il vostro struct Cell non lo fa (dal momento che hai solo un costruttore di default generato automaticamente che non fa nulla).

L'inizializzazione richiede la scrittura in ogni campo che richiede un sacco di accessi alla memoria che sono relativamente lunghi. Con struct Cell invece non si fa nulla e non fare nulla è un po 'più veloce.

Answer 2

La mia ipotesi è il modo in cui viene creato std :: pair. C'è un sovraccarico maggiore durante il richiamo di un costruttore di coppie 1001x1001 volte rispetto a quando si assegna solo un intervallo di memoria.

Answer 3

è davvero un buon esempio di uno dovrebbe scrivere C++ e utilizzare STL con attenzione. qualche idea?

il mio progetto sta lavorando a uno strumento di test C33 di livello codice C & in cui faremo molti esempi di codice per scoprire cosa è il codice "buono" e quale è un'abitudine di codifica "cattiva". vedi http://effodevel.googlecode.com per ulteriori informazioni su C9B.M. pianificazione. chiunque se tu abbia avuto esperienza di molti di questi casi, per favore unisciti al progetto per aiutarci.

Answer 4

Le risposte finora non spiegano l'intera portata del problema.

Come sottolineato da Sharptooth, la soluzione di coppia inizializza i valori a zero. Come ha sottolineato Lemurik, la soluzione coppia non sta solo inizializzando un blocco contiguo di memoria, ma chiama il costruttore della coppia per ogni elemento della tabella. Tuttavia, anche questo non tiene conto che ci vogliono 1,5 secondi. Sta succedendo qualcos'altro

Ecco la mia logica:

Supponendo tu fossi su una macchina antica, dire in esecuzione a 1,33 GHz, quindi 1,5 secondi sono cicli di clock 2E9. Hai 2e6 coppie da costruire, quindi in qualche modo ogni costruttore di coppie impiega 1000 cicli. Non ci vogliono 1000 cicli per chiamare un costruttore che imposta solo due numeri interi a zero. Non riesco a vedere come la mancanza di cache potrebbe richiedere così tanto tempo. Lo crederei se il numero fosse inferiore a 100 cicli.

Ho pensato che sarebbe stato interessante vedere dove stanno andando tutti questi cicli della CPU. Ho usato il compilatore C++ più vecchio e più scadente che potessi trovare per vedere se potevo raggiungere il livello di spreco richiesto. Quel compilatore era VC++ v6. In modalità di debug, fa qualcosa che non capisco. Ha un grande ciclo che chiama il costruttore della coppia per ogni oggetto nella tabella - abbastanza giusto. Quel costruttore imposta i due valori a zero - abbastanza giusto. Ma appena prima di farlo, imposta tutti i byte in una regione da 68 byte a 0xcc. Quella regione è appena prima dell'inizio del grande tavolo. Quindi sovrascrive l'ultimo elemento di quella regione con 0x28F61200. Ogni chiamata del costruttore della coppia lo ripete.Presumibilmente questa è una sorta di conservazione del libro da parte del compilatore in modo che sappia quali regioni sono inizializzate quando si controllano gli errori del puntatore in fase di esecuzione. Mi piacerebbe sapere esattamente a cosa serve.

In ogni caso, questo spiegherebbe dove sta andando il tempo extra. Ovviamente un altro compilatore potrebbe non essere così male. E certamente una build di rilascio ottimizzata non lo sarebbe.

Answer 5

Queste sono tutte ipotesi molto buone, ma come tutti sanno, le ipotesi non sono affidabili.

Direi solo in modo casuale pause it entro 1,5 secondi, ma dovresti essere piuttosto veloce. Se aumentassi ogni dimensione di un fattore di circa 3, potresti farla impiegare più di 10+ secondi, quindi sarebbe più facile mettere in pausa.

Oppure, è possibile ottenerlo in un debugger, interromperlo nel codice del costruttore di coppie e quindi eseguire un singolo passaggio per vedere cosa sta facendo.

In entrambi i casi, si otterrebbe una risposta decisa alla domanda, non solo una supposizione.