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

Question

In un esempio di ACM, ho dovuto costruire una grande tabella per la programmazione dinamica. Ho dovuto memorizzare due numeri interi in ogni cella, quindi ho deciso di scegliere un std :: pair < int, int > . Tuttavia, l'allocazione di una vasta gamma di essi ha richiesto 1,5 secondi:

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

Successivamente, ho modificato questo codice in

struct Cell {
    int first;
    int second;
}

Cell table[1001][1001];

e l'assegnazione ha richiesto 0 secondi.

Cosa spiega questa enorme differenza nel tempo?

Answer 1

Il costruttore

std :: pair < int, int > :: pair () inizializza i campi con valori predefiniti (zero nel caso di int ) e il tuo struct Cell no (poiché hai solo un costruttore predefinito generato automaticamente che non fa nulla).

L'inizializzazione richiede la scrittura su ogni campo che richiede un sacco di accessi alla memoria che richiedono relativamente tempo. Con struct Cell invece non si fa nulla e non si fa nulla di più veloce.

Answer 2

Le risposte finora non spiegano l'entità del problema.

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

Ecco la mia logica:

Supponendo che tu fossi su una macchina antica, diciamo che funziona a 1,33 Ghz, quindi 1,5 secondi è 2e9 cicli di clock. Hai 2 coppie di 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 su zero. Non riesco a vedere come i mancati errori nella cache richiederebbero così tanto tempo. Ci crederei se il numero fosse inferiore a 100 cicli.

Ho pensato che sarebbe interessante vedere dove stanno andando tutti questi cicli della CPU. Ho usato il più vecchio compilatore C ++ più vecchio che ho trovato per vedere se riuscissi a raggiungere il livello di spreco richiesto. Quel compilatore era VC ++ v6. In modalità debug, fa qualcosa che non capisco. Ha un grande ciclo che chiama il costruttore di coppie per ogni elemento nella tabella - abbastanza giusto. Quel costruttore imposta i due valori su zero - abbastanza giusto. Ma poco prima di farlo, imposta tutti i byte in una regione di 68 byte su 0xcc. Quella regione è poco 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 si tratta di una sorta di tenuta dei libri da parte del compilatore, in modo che sappia quali regioni vengono inizializzate quando si verificano errori del puntatore in fase di esecuzione. Mi piacerebbe sapere esattamente a cosa serve.

Comunque, ciò spiegherebbe dove sta andando il tempo extra. Ovviamente un altro compilatore potrebbe non essere così male. E certamente una build di rilascio ottimizzata non sarebbe.

Answer 3

Suppongo sia il modo in cui viene creato std :: pair. C'è un overhead maggiore durante l'invocazione di un costruttore di coppie 1001x1001 volte rispetto a quando si assegna un intervallo di memoria.

Answer 4

Sono tutte ipotesi molto valide, ma come tutti sanno, le ipotesi non sono affidabili.

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

In alternativa, potresti trovarlo in un debugger, romperlo nel codice del costruttore della coppia e quindi fare un singolo passo per vedere cosa sta facendo.

Ad ogni modo, otterresti una risposta ferma alla domanda, non solo un'ipotesi.

Answer 5

è davvero un buon esempio di come si dovrebbe scrivere C ++ e usare STL con attenzione. qualche pensiero?

il mio progetto sta lavorando a uno strumento di test benchmark a livello di codice C & amp; C ++ in cui faremo molti esempi di codice per scoprire cosa è "buono" codice e cosa è un "cattivo" abitudine di codifica. vedi http://effodevel.googlecode.com per saperne di più su C9B.M. pianificazione. chiunque abbia avuto molti di questi casi, si prega gentilmente di unirsi al progetto per aiutarci.