Come produrre l'effetto cache della CPU in C e Java?

Questa risposta non è una risposta, ma piuttosto un insieme di note.

Innanzitutto, la CPU tende a operare su linee di cache, non su singoli byte/parole/dword. Ciò significa che se si legge/scrive in sequenza un array di numeri interi, il primo accesso a una riga della cache potrebbe causare un fallimento della cache, ma gli accessi successivi a numeri interi diversi nella stessa riga della cache non lo faranno. Per le righe della cache a 64 byte e gli interi a 4 byte ciò significa che si otterrebbe un errore nella cache solo una volta ogni 16 accessi; che diluirà i risultati.

In secondo luogo, la CPU dispone di un "prefetcher hardware". Se rileva che le righe della cache vengono lette in sequenza, il prefetcher dell'hardware preleverà automaticamente le righe della cache che prevede saranno necessarie in seguito (nel tentativo di recuperarle nella cache prima che siano necessarie).

Terzo, la CPU fa altre cose (come "esecuzione fuori servizio") per nascondere i costi di recupero. La differenza di tempo (tra cache hit e cache miss) che puoi misurare è il tempo che la CPU non è riuscita a nascondere e non il costo totale del recupero.

Queste 3 cose combinate significano che; per leggere in sequenza un array di numeri interi, è probabile che la CPU prelevi la riga della cache successiva mentre stai eseguendo 16 letture dalla riga della cache precedente; e tutti i costi mancati nella cache non saranno evidenti e potrebbero essere completamente nascosti. Per evitare questo; vorresti accedere "casualmente" a ciascuna riga della cache una volta, per massimizzare la differenza di prestazioni misurata tra "il working set si adatta alla cache/s" e "il working set non si adatta alla cache/s."

Infine, ci sono altri fattori che possono influenzare le misurazioni. Ad esempio, per un sistema operativo che utilizza il paging (ad esempio Linux e quasi tutti gli altri sistemi operativi moderni) c'è un intero livello di memorizzazione nella cache sopra tutto questo (TLB/Translation Look-aside Buffers) e TLB manca una volta che il set di lavoro supera una certa dimensione; che dovrebbe essere visibile come un quarto "passo" nel grafico. Ci sono anche interferenze dal kernel (IRQ, errori di pagina, cambi di attività, più CPU, ecc.); che potrebbe essere visibile come statico/errore casuale nel grafico (a meno che i test non vengano ripetuti spesso e gli outlier scartati). Esistono anche artefatti del design della cache (associatività della cache) che possono ridurre l'efficacia della cache in modi che dipendono dall'indirizzo fisico o dagli indirizzi fisici assegnati dal kernel; che potrebbero essere visti come i "passi" nel grafico che si spostano in punti diversi.

C'è qualcosa che non va nel mio metodo?

Forse, ma senza vedere il tuo codice effettivo a cui non è possibile rispondere.

• La tua descrizione di cosa sta facendo il tuo codice non dice se stai leggendo l'array una o più volte.

• L'array potrebbe non essere abbastanza grande ... a seconda del tuo hardware. (Alcuni chip moderni non hanno una cache di 3° livello di pochi megabyte?)

• Nel caso di Java, in particolare, devi fare molte cose nel modo giusto per implementare un micro-benchmark significativo.

Nel caso C:

• Potresti provare a regolare le opzioni di ottimizzazione del compilatore C.

• Poiché il tuo codice accede all'array in modo seriale, il compilatore potrebbe essere in grado di ordinare le istruzioni in modo che la CPU possa tenere il passo, oppure la CPU potrebbe eseguire ottimisticamente il precaricamento o eseguire recuperi ampi. Potresti provare a leggere gli elementi dell'array in un ordine meno prevedibile.

• È anche possibile che il compilatore abbia completamente ottimizzato il ciclo perché il risultato del calcolo del ciclo non viene utilizzato per nulla.

(Secondo questa domanda e risposta - Quanto tempo ci vuole per recuperare una parola dalla memoria?, un recupero dalla cache L2 è ~ 7 nanosecondi e un recupero dalla memoria principale è ~ 100 nanosecondi. Ma stai ottenendo ~ 2 nanosecondi. Qualcosa di intelligente deve continuare qui per farlo funzionare alla velocità che stai osservando.)