Ho appena letto uno article di Rico Mariani che riguarda le prestazioni dell'accesso alla memoria a seconda della località, dell'architettura, dell'allineamento e della densità.Cosa causa questo strano calo delle prestazioni con un numero * medio * di articoli?
L'autore ha creato un array di dimensioni variabili contenente un elenco doppiamente collegato con un payload int, che è stato mischiato a una certa percentuale. Ha sperimentato questo elenco e ha trovato risultati coerenti sulla sua macchina.
Citando uno della tabella dei risultati:
Pointer implementation with no changes
sizeof(int*)=4 sizeof(T)=12
shuffle 0% 1% 10% 25% 50% 100%
1000 1.99 1.99 1.99 1.99 1.99 1.99
2000 1.99 1.85 1.99 1.99 1.99 1.99
4000 1.99 2.28 2.77 2.92 3.06 3.34
8000 1.96 2.03 2.49 3.27 4.05 4.59
16000 1.97 2.04 2.67 3.57 4.57 5.16
32000 1.97 2.18 3.74 5.93 8.76 10.64
64000 1.99 2.24 3.99 5.99 6.78 7.35
128000 2.01 2.13 3.64 4.44 4.72 4.80
256000 1.98 2.27 3.14 3.35 3.30 3.31
512000 2.06 2.21 2.93 2.74 2.90 2.99
1024000 2.27 3.02 2.92 2.97 2.95 3.02
2048000 2.45 2.91 3.00 3.10 3.09 3.10
4096000 2.56 2.84 2.83 2.83 2.84 2.85
8192000 2.54 2.68 2.69 2.69 2.69 2.68
16384000 2.55 2.62 2.63 2.61 2.62 2.62
32768000 2.54 2.58 2.58 2.58 2.59 2.60
65536000 2.55 2.56 2.58 2.57 2.56 2.56
L'autore spiega:
Questa è la misurazione di riferimento. Puoi vedere che la struttura è un bel giro di 12 byte e si allinea bene su x86. Guardando la prima colonna, senza shuffling, come previsto le cose peggiorano e peggiorano man mano che la matrice diventa più grande fino a che la cache non aiuta molto e si ha il peggio che si ottiene, che è di circa 2,55ns su media per articolo.
Ma qualcosa di molto strano può essere visto in giro 32k articoli:
I risultati per rimescolamento non sono esattamente quello che mi aspettavo. A piccole dimensioni, non fa differenza. Mi aspettavo questo perché fondamentalmente l'intera tabella è rimasta calda nella cache e quindi la località non conta. Poi, man mano che la tabella cresce, vedi che il mescolamento ha un grande impatto a circa 32000 elementi. Sono 384k di dati. Probabilmente perché abbiamo superato il limite di 256k.
Ora la cosa bizzarra è questa: dopo di ciò il costo dello shuffling in realtà scende, al punto che in seguito difficilmente conta nulla. Ora posso capire che a un certo punto mescolato o non mescolato in realtà non dovrebbe fare alcuna differenza perché la matrice è così grande che il runtime è ampiamente controllato dalla larghezza di banda della memoria, indipendentemente dall'ordine. Tuttavia ... ci sono punti nel mezzo in cui il costo della non-località è in realtà molto peggiore di quello che sarà nel finale.
Quello che mi aspettavo di vedere era che il rimescolamento ci ha indotti a raggiungere il massimo disagio prima e rimanere lì. Quello che succede in realtà è che le medie dimensioni non località sembrano causare cose molto pessime ... E non so perché :)
Quindi la domanda è: cosa potrebbe aver causato questo comportamento inaspettato?
Ci ho pensato per un po 'di tempo, ma non ho trovato nessuna spiegazione. Il codice di prova mi sta bene. Non credo che la predizione del ramo CPU sia il colpevole in questo caso, in quanto dovrebbe essere osservabile molto prima di 32k e mostrare un picco molto più basso.
Ho confermato questo comportamento sul mio box, sembra praticamente lo stesso.
Ho pensato che potrebbe essere causato dall'inoltro dello stato della CPU, quindi ho cambiato l'ordine di righe e/o generazione di colonne - quasi nessuna differenza nell'output. Per essere sicuro, ho generato i dati per un campione continuo più grande.Per facile di visualizzazione, l'ho messo in Excel:
And another independent run for good measure, negligible difference
