Cos’è un codice “cache-friendly”?

Qual è la differenza tra ” cache unfriendly code ” e il codicecache friendly “?

Come posso assicurarmi di scrivere codice efficiente per la cache?

Preliminari

Nei computer moderni, solo le strutture di memoria di livello più basso (i registri ) possono spostare i dati in giro in cicli di clock singoli. Tuttavia, i registri sono molto costosi e la maggior parte dei core di computer ha meno di qualche dozzina di registri (da poche centinaia a forse un totale di mille byte ). All’altra estremità dello spettro di memoria ( DRAM ), la memoria è molto economica (vale a dire letteralmente milioni di volte in meno ) ma richiede centinaia di cicli dopo una richiesta di ricezione dei dati. Per colmare questo divario tra super veloce e costoso e super lento ed economico sono le memorie cache , denominate L1, L2, L3 in decrescente velocità e costo. L’idea è che la maggior parte del codice in esecuzione raggiungerà spesso un piccolo insieme di variabili e il resto (un insieme molto più grande di variabili) raramente. Se il processore non riesce a trovare i dati nella cache L1, appare nella cache L2. In caso contrario, la cache L3 e, se non presente, la memoria principale. Ognuna di queste “miss” è costosa nel tempo.

(L’analogia è che la memoria cache si trova nella memoria di sistema, poiché la memoria di sistema si trova nella memoria del disco rigido. L’archiviazione del disco rigido è molto economica, ma molto lenta).

Il caching è uno dei metodi principali per ridurre l’impatto della latenza . Per parafrasare Herb Sutter (vedi link sotto): aumentare la larghezza di banda è facile, ma non possiamo comprare la nostra via d’uscita dalla latenza .

I dati vengono sempre recuperati attraverso la gerarchia di memoria (il più piccolo == il più veloce al più lento). Un hit / miss cache di solito si riferisce a un hit / miss nel più alto livello di cache nella CPU: per livello più alto intendo il più == il più lento. Il tasso di hit della cache è cruciale per le prestazioni, dal momento che ogni errore di cache risulta nel recupero dei dati dalla RAM (o peggio …) che richiede molto tempo (centinaia di cicli per RAM, decine di milioni di cicli per HDD). In confronto, la lettura dei dati dalla cache (di livello più alto) richiede in genere solo una manciata di cicli.

Nelle moderne architetture di computer, il collo di bottiglia delle prestazioni lascia la CPU morire (ad esempio, accedere alla RAM o superiore). Questo peggiorerà nel tempo. L’aumento della frequenza del processore non è attualmente più rilevante per aumentare le prestazioni. Il problema è l’accesso alla memoria. Gli sforzi di progettazione hardware nelle CPU pertanto si concentrano attualmente sull’ottimizzazione di cache, prefetch, pipeline e concorrenza. Ad esempio, le moderne CPU spendono circa l’85% del die sulle cache e fino al 99% per memorizzare / spostare i dati!

C’è molto da dire sull’argomento. Ecco alcuni grandi riferimenti su cache, gerarchie di memoria e programmazione corretta:

  • La pagina di Agner Fog . Nei suoi eccellenti documenti, puoi trovare esempi dettagliati di lingue che vanno dal assembly al C ++.
  • Se ti piacciono i video, consiglio vivamente di dare un’occhiata al discorso di Herb Sutter sull’architettura della macchina (youtube) (in particolare, controlla le 12:00 e oltre!).
  • Diapositive sull’ottimizzazione della memoria di Christer Ericson (direttore della tecnologia @ Sony)
  • L’articolo di LWN.net ” Quello che ogni programmatore dovrebbe sapere sulla memoria

Concetti principali per codice cache-friendly

Un aspetto molto importante del codice cache-friendly riguarda tutto il principio di località , il cui objective è quello di mettere i dati correlati in memoria per consentire un caching efficiente. In termini di cache della CPU, è importante conoscere le linee della cache per capire come funziona: come funzionano le linee della cache?

I seguenti aspetti particolari sono di grande importanza per ottimizzare il caching:

  1. Località temporale : quando si accede a una determinata posizione di memoria, è probabile che la stessa posizione venga nuovamente aperta nel prossimo futuro. Idealmente, queste informazioni saranno ancora memorizzate nella cache in quel punto.
  2. Località spaziale : si riferisce alla collocazione di dati correlati vicini l’uno all’altro. Il caching avviene su molti livelli, non solo nella CPU. Ad esempio, quando si legge dalla RAM, in genere viene recuperata una parte più grande della memoria rispetto a quanto richiesto in modo specifico, poiché molto spesso il programma richiederà presto tali dati. Le cache dell’HDD seguono la stessa linea di pensiero. In particolare per le cache della CPU, la nozione di linee della cache è importante.

Utilizzare contenitori c ++ appropriati

Un semplice esempio di cache-friendly contro cache-unfriendly è std::vector c ++ rispetto a std::list . Gli elementi di un std::vector sono memorizzati in una memoria contigua e, in quanto tale, accedervi sono molto più facili da usare nella cache rispetto all’accesso agli elementi in una std::list , che memorizza il suo contenuto dappertutto. Ciò è dovuto alla località spaziale.

Una bella illustrazione di questo è data da Bjarne Stroustrup in questa clip di youtube (grazie a @Mohammad Ali Baydoun per il link!).

Non trascurare la cache nella struttura dei dati e nella progettazione dell’algoritmo

Quando ansible, cerca di adattare le strutture dei dati e l’ordine dei calcoli in modo da consentire il massimo utilizzo della cache. Una tecnica comune a questo proposito è il blocco della cache (versione Archive.org) , che è di estrema importanza nel calcolo ad alte prestazioni (cfr. Ad esempio ATLAS ).

Conoscere e sfruttare la struttura implicita dei dati

Un altro semplice esempio, che molte persone nel campo a volte dimenticano è column-major (ad esempio fortran , matlab ) rispetto a row-major ordering (ad esempio c , c ++ ) per la memorizzazione di array bidimensionali. Ad esempio, considera la seguente matrice:

 1 2 3 4 

In ordine di riga principale, questo è memorizzato in memoria come 1 2 3 4 ; nell’ordine delle colonne questo sarebbe memorizzato come 1 3 2 4 . È facile vedere che le implementazioni che non sfruttano questo ordine si imbatteranno rapidamente in problemi di cache facilmente evitabili! Sfortunatamente, vedo cose del genere molto spesso nel mio dominio (machine learning). @MatteoItalia ha mostrato questo esempio in modo più dettagliato nella sua risposta.

Quando si recupera dalla memoria un determinato elemento di una matrice, anche gli elementi vicini verranno recuperati e memorizzati in una linea della cache. Se l’ordinamento è sfruttato, ciò comporterà un minor numero di accessi alla memoria (poiché i prossimi valori necessari per i calcoli successivi sono già in una linea della cache).

Per semplicità, supponiamo che la cache comprenda una singola linea di cache che può contenere 2 elementi di matrice e che quando un dato elemento viene prelevato dalla memoria, anche il prossimo è troppo. Diciamo che vogliamo prendere la sum su tutti gli elementi nell’esempio 2×2 matrice sopra (chiamiamola M ):

Sfruttare l’ordine (ad es. Cambiare l’indice della colonna prima in c ++ ):

 M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached) = 1 + 2 + 3 + 4 --> 2 cache hits, 2 memory accesses 

Non sfruttando l’ordine (ad es. Modifica dell’indice di riga prima in c ++ ):

 M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory) = 1 + 3 + 2 + 4 --> 0 cache hits, 4 memory accesses 

In questo semplice esempio, sfruttare l’ordine raddoppia la velocità di esecuzione (poiché l’accesso alla memoria richiede molti più cicli rispetto al calcolo delle somme). In pratica, la differenza di prestazioni può essere molto più grande.

Evita i rami imprevedibili

Le moderne architetture presentano condotte e i compilatori stanno diventando molto bravi a riordinare il codice per minimizzare i ritardi dovuti all’accesso alla memoria. Quando il codice critico contiene rami (imprevedibili), è difficile o imansible precedere i dati. Ciò porterà indirettamente ad altri errori nella cache.

Questo è spiegato molto bene qui (grazie a @ 0x90 per il collegamento): Perché è più veloce elaborare una matrice ordinata rispetto ad una matrice non ordinata?

Evita le funzioni virtuali

Nel contesto del c ++ , virtual metodi virtual rappresentano un problema controverso per quanto riguarda i fallimenti della cache (esiste un consenso generale sul fatto che dovrebbero essere evitati laddove ansible in termini di prestazioni). Le funzioni virtuali possono causare errori di cache durante la ricerca, ma ciò accade solo se la funzione specifica non viene chiamata spesso (altrimenti potrebbe essere memorizzata nella cache), quindi è considerata da alcuni un problema. Per riferimento a questo problema, consultare: Qual è il costo delle prestazioni di avere un metodo virtuale in una class C ++?

Problemi comuni

Un problema comune nelle architetture moderne con cache multiprocessore si chiama falso sharing . Ciò si verifica quando ogni singolo processore sta tentando di utilizzare i dati in un’altra area di memoria e tenta di memorizzarlo nella stessa riga della cache . Ciò causa la sovrascrittura della riga di cache, che contiene dati che può essere utilizzata da un altro processore, ancora e ancora. In effetti, diversi thread si attendono a vicenda inducendo errori di cache in questa situazione. Vedi anche (grazie a @Matt per il collegamento): come e quando allineare alla dimensione della linea della cache?

Un sintomo estremo di scarsa memorizzazione nella memoria RAM (che probabilmente non è ciò che intendete in questo contesto) è il cosiddetto thrashing . Ciò si verifica quando il processo genera continuamente errori di pagina (ad esempio, accede alla memoria che non si trova nella pagina corrente) che richiede l’accesso al disco.

Oltre alla risposta di @Marc Claesen, penso che un classico esempio istruttivo di codice cache-unfriendly sia il codice che analizza una matrice bidimensionale C (ad esempio un’immagine bitmap) a livello di colonna anziché di riga.

Gli elementi che sono adiacenti in una fila sono anche adiacenti in memoria, quindi accedervi in ​​sequenza significa accedervi in ​​ordine di memoria ascendente; questo è cache-friendly, dal momento che la cache tende a prefetch blocchi contigui di memoria.

Invece, l’accesso a tali elementi a livello di colonna non è favorevole alla cache, poiché gli elementi della stessa colonna sono distanti tra loro in memoria (in particolare, la loro distanza è uguale alla dimensione della riga), quindi quando si utilizza questo modello di accesso si stanno saltando in giro nella memoria, potenzialmente sprecando lo sforzo della cache di recuperare gli elementi nelle vicinanze in memoria.

E tutto quello che serve per rovinare la performance è di andare da

 // Cache-friendly version - processes pixels which are adjacent in memory for(unsigned int y=0; y 

a

 // Cache-unfriendly version - jumps around in memory for no good reason for(unsigned int x=0; x 

Questo effetto può essere piuttosto drammatico (di diversi ordini di grandezza in termini di velocità) in sistemi con piccole cache e / o lavorare con grandi array (ad esempio, 10+ megapixel con immagini a 24 bpp su macchine attuali); per questo motivo, se devi eseguire molte scansioni verticali, spesso è meglio ruotare prima l'immagine di 90 gradi ed eseguire successivamente le varie analisi, limitando il codice poco ostile alla cache solo alla rotazione.

L’ottimizzazione dell’uso della cache dipende in gran parte da due fattori.

Località di riferimento

Il primo fattore (a cui altri hanno già alluso) è la località di riferimento. La località di riferimento ha però due dimensioni: spazio e tempo.

  • Spaziale

La dimensione spaziale si riduce anche a due cose: innanzitutto, vogliamo impacchettare le nostre informazioni in modo denso, in modo che più informazioni si adattino a quella memoria limitata. Ciò significa (per esempio) che è necessario un notevole miglioramento della complessità computazionale per giustificare strutture dati basate su piccoli nodes uniti da puntatori.

In secondo luogo, desideriamo che le informazioni vengano elaborate insieme anche localizzate insieme. Una cache tipica funziona in “linee”, il che significa che quando si accede ad alcune informazioni, altre informazioni agli indirizzi vicini verranno caricate nella cache con la parte che abbiamo toccato. Ad esempio, quando touch un byte, la cache potrebbe caricare 128 o 256 byte vicino a quello. Per approfittare di questo, in genere si desidera disporre i dati per massimizzare la probabilità che vengano utilizzati anche gli altri dati caricati contemporaneamente.

Solo per un esempio davvero banale, questo può significare che una ricerca lineare può essere molto più competitiva con una ricerca binaria di quanto ci si aspetterebbe. Una volta caricato un elemento da una linea della cache, l’utilizzo del resto dei dati in quella linea della cache è quasi gratuito. Una ricerca binaria diventa notevolmente più veloce solo quando i dati sono abbastanza grandi da consentire alla ricerca binaria di ridurre il numero di linee della cache a cui si accede.

  • Tempo

La dimensione temporale indica che quando si eseguono alcune operazioni su alcuni dati, si desidera (il più ansible) eseguire tutte le operazioni su quei dati contemporaneamente.

Dal momento che hai taggato questo come C ++, std::valarray un classico esempio di design relativamente poco cache-unfriendly: std::valarray . valarray sovraccarica la maggior parte degli operatori aritmetici, quindi posso (per esempio) dire a = b + c + d; (dove a , b , cd sono tutti valarray) per fare l’aggiunta di elementi di quegli array.

Il problema è che attraversa una coppia di input, mette i risultati in una temporanea, cammina attraverso un’altra coppia di input e così via. Con molti dati, il risultato di un calcolo può scomparire dalla cache prima che venga utilizzato nel calcolo successivo, quindi finiamo per leggere (e scrivere) i dati ripetutamente prima di ottenere il nostro risultato finale. Se ogni elemento del risultato finale sarà qualcosa di simile (a[n] + b[n]) * (c[n] + d[n]); , preferiremmo generalmente leggere ognuno a[n] , b[n] , c[n] e d[n] una volta, fare il calcolo, scrivere il risultato, incrementare n e ripetere ‘finchè non abbiamo finito. 2

Condivisione delle linee

Il secondo fattore principale è evitare la condivisione della linea. Per capirlo, probabilmente dobbiamo eseguire il backup e osservare un po ‘come sono organizzate le cache. La forma più semplice di cache è mappata direttamente. Ciò significa che un indirizzo nella memoria principale può essere memorizzato solo in un punto specifico della cache. Se utilizziamo due elementi di dati che si associano allo stesso punto nella cache, funziona male – ogni volta che usiamo un elemento di dati, l’altro deve essere svuotato dalla cache per fare spazio all’altro. Il resto della cache potrebbe essere vuoto, ma quegli elementi non utilizzeranno altre parti della cache.

Per evitare ciò, la maggior parte delle cache sono quelle che vengono definite “set associative”. Ad esempio, in una cache associativa set a 4 vie, qualsiasi elemento della memoria principale può essere memorizzato in uno dei 4 diversi punti della cache. Quindi, quando la cache carica un object, cerca l’elemento 3 utilizzato meno di recente tra questi quattro, lo scarica nella memoria principale e carica il nuovo object al suo posto.

Il problema è probabilmente abbastanza ovvio: per una cache con mapping diretta, due operandi che si verificano mappare nella stessa posizione della cache possono portare a un comportamento errato. Una cache associativa-set a N aumenta il numero da 2 a N + 1. Organizzare una cache in più “modi” richiede circuiti extra e generalmente funziona più lentamente, quindi (per esempio) una cache associativa a 8192 vie è raramente una buona soluzione.

In definitiva, questo fattore è più difficile da controllare nel codice portatile. Il controllo su dove vengono collocati i dati è in genere abbastanza limitato. Peggio ancora, la mapping esatta dall’indirizzo alla cache varia tra processori altrimenti simili. In alcuni casi, tuttavia, può valere la pena fare cose come allocare un buffer di grandi dimensioni e quindi utilizzare solo parti di ciò che è stato assegnato per garantire che i dati condividano le stesse linee di cache (anche se probabilmente sarà necessario rilevare il processore esatto e agire di conseguenza per fare questo).

  • False Condivisione

C’è un altro articolo correlato chiamato “false sharing”. Ciò si verifica in un sistema multiprocessore o multicore, in cui due (o più) processori / core hanno dati separati, ma che cadono nella stessa riga della cache. Questo costringe i due processori / core a coordinare il loro accesso ai dati, anche se ognuno ha il proprio elemento di dati separato. Soprattutto se i due modificano i dati in alternanza, questo può portare ad un enorme rallentamento in quanto i dati devono essere costantemente spostati tra i processori. Questo non può essere facilmente risolto organizzando la cache in più “modi” o qualcosa del genere. Il modo principale per prevenirlo è quello di garantire che due thread raramente (preferibilmente mai) modificano i dati che potrebbero essere nella stessa riga della cache (con gli stessi avvertimenti sulla difficoltà di controllare gli indirizzi ai quali i dati sono allocati).


  1. Chi conosce bene il C ++ potrebbe chiedersi se questo è aperto all’ottimizzazione tramite qualcosa come i modelli di espressioni. Sono abbastanza sicuro che la risposta è che sì, potrebbe essere fatto e se lo fosse, sarebbe probabilmente una vittoria piuttosto sostanziale. Comunque non sono a conoscenza di nessuno, e visto quanto poco valarray viene usato, sarei almeno un po ‘sorpreso nel vedere qualcuno che lo faccia.

  2. Nel caso in cui qualcuno si valarray come valarray (progettato specificamente per le prestazioni) potrebbe essere così gravemente sbagliato, si tratta di una cosa: è stato davvero progettato per macchine come il vecchio Crays, che utilizzava una memoria principale veloce e nessuna cache. Per loro, questo era davvero un design quasi ideale.

  3. Sì, sto semplificando: la maggior parte delle cache non misura in modo preciso l’elemento utilizzato meno di recente, ma utilizza un certo valore euristico che è destinato a essere vicino a quello senza dover mantenere un contrassegno orario completo per ogni accesso.

Benvenuti nel mondo di Data Oriented Design. Il mantra di base è ordinare, eliminare rami, batch, eliminare chiamate virtual : tutti i passaggi verso una località migliore.

Dato che hai taggato la domanda con C ++, ecco la tipica C ++ Bullshit obbligatoria. Le insidie ​​di Tony Albrecht su Object Oriented Programming sono anche una grande introduzione all’argomento.

Semplicemente accumulando: il classico esempio di cache-unfriendly contro codice cache-friendly è il “blocco della cache” della matrice moltiplicata.

La moltiplicazione della matrice ingenua è simile

 for(i=0;i 

Se N è grande, ad esempio se N * sizeof(elemType) è maggiore della dimensione della cache, allora ogni singolo accesso a src2[k][j] sarà un src2[k][j] cache.

Esistono molti modi diversi per ottimizzare questo per una cache. Ecco un esempio molto semplice: invece di leggere un elemento per riga di cache nel loop interno, usa tutti gli elementi:

 int itemsPerCacheLine = CacheLineSize / sizeof(elemType); for(i=0;i 

Se la dimensione della linea cache è 64 byte e stiamo operando su float a 32 bit (4 byte), allora ci sono 16 elementi per riga cache. E il numero di errori di cache attraverso questa semplice trasformazione è ridotto di circa 16 volte.

Le trasformazioni di Fancier operano su riquadri 2D, ottimizzano per più cache (L1, L2, TLB) e così via.

Alcuni risultati di googling "cache blocking":

http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf

http://software.intel.com/en-us/articles/cache-blocking-techniques

Una bella animazione video di un algoritmo di blocco della cache ottimizzato.

http://www.youtube.com/watch?v=IFWgwGMMrh0

La piastrellatura ad anello è strettamente correlata:

http://en.wikipedia.org/wiki/Loop_tiling

I processori oggi funzionano con molti livelli di aree di memoria a cascata. Quindi la CPU avrà un mucchio di memoria che si trova sul chip della CPU stessa. Ha un accesso molto veloce a questa memoria. Ci sono diversi livelli di cache ciascuno più lento (e più grande) rispetto al successivo, finché non si arriva alla memoria di sistema che non è nella CPU ed è relativamente più lenta ad accedere.

Logicamente, per il set di istruzioni della CPU si fa semplicemente riferimento agli indirizzi di memoria in un gigantesco spazio di indirizzamento virtuale. Quando accedi a un singolo indirizzo di memoria, la CPU la preleva. in passato avrebbe recuperato solo quell’indirizzo singolo. Ma oggi la CPU recupera un po ‘di memoria attorno al bit che hai richiesto e la copia nella cache. Si presuppone che se hai chiesto un indirizzo particolare è molto probabile che stai per chiedere un indirizzo nelle vicinanze molto presto. Ad esempio, se si stava copiando un buffer, si leggeva e si scriveva da indirizzi consecutivi, uno subito dopo l’altro.

Così oggi, quando recuperi un indirizzo, controlla il primo livello di cache per vedere se ha già letto quell’indirizzo nella cache, se non lo trova, allora questo è un errore di cache e deve passare al livello successivo di cache per trovarlo, fino a quando alla fine deve uscire nella memoria principale.

Il codice amichevole della cache tenta di mantenere gli accessi ravvicinati in memoria in modo da ridurre al minimo gli errori di cache.

Quindi un esempio potrebbe essere immaginare di voler copiare un gigantesco tavolo bidimensionale. È organizzato con fila di raggi in consecutivi in ​​memoria e una riga segue la successiva subito dopo.

Se hai copiato gli elementi una riga alla volta da sinistra a destra, questo sarebbe compatibile con la cache. Se decidessi di copiare la tabella una colonna alla volta, dovresti copiare esattamente la stessa quantità di memoria, ma la cache sarebbe ostile.

È necessario chiarire che non solo i dati dovrebbero essere adattati alla cache, è altrettanto importante per il codice. Ciò si aggiunge alla previsione delle branche, al riordino delle istruzioni, all’evitare divisioni effettive e altre tecniche.

In genere, più denso è il codice, meno righe della cache saranno necessarie per memorizzarlo. Ciò si traduce in più linee di cache disponibili per i dati.

Il codice non deve richiamare le funzioni ovunque, in quanto in genere richiedono una o più linee di cache, risultando in un minor numero di linee di cache per i dati.

Una funzione dovrebbe iniziare da un indirizzo di allineamento della riga della cache. Sebbene ci siano switch (gcc) per il compilatore, sappiate che se le funzioni sono molto brevi potrebbe essere uno spreco per ognuna occupare un’intera linea di cache. Ad esempio, se tre delle funzioni utilizzate più frequentemente si inseriscono in una riga della cache da 64 byte, ciò è meno dispendioso che se ognuna abbia una propria linea e produca due linee di cache meno disponibili per altri usi. Un valore di allineamento tipico potrebbe essere 32 o 16.

Quindi dedica un po ‘di tempo in più per rendere il codice denso. Prova diversi costrutti, compila e rivedi le dimensioni e il profilo del codice generato.

Come @Marc Claesen ha detto che uno dei modi per scrivere codice cache-friendly è quello di sfruttare la struttura in cui sono archiviati i nostri dati. In aggiunta a ciò un altro modo per scrivere codice cache friendly è: cambiare il modo in cui i nostri dati vengono memorizzati; quindi scrivere un nuovo codice per accedere ai dati memorizzati in questa nuova struttura.

Ciò ha senso nel caso in cui i sistemi di database linearizzano le tuple di una tabella e le memorizzano. Esistono due metodi di base per memorizzare le tuple di una tabella, ad esempio archivio righe e archivio colonne. Nel negozio di riga, come suggerisce il nome, le tuple vengono memorizzate in ordine di riga. Supponiamo che una tabella denominata Product fase di memorizzazione abbia 3 attributi, ad esempio int32_t key, char name[56] e int32_t price , quindi la dimensione totale di una tupla è 64 byte.

Possiamo simulare un’esecuzione di query di archivio di righe molto semplice nella memoria principale creando una matrice di strutture Product con dimensione N, dove N è il numero di righe nella tabella. Tale layout di memoria è anche chiamato matrice di strutture. Quindi la struttura per il prodotto può essere come:

 struct Product { int32_t key; char name[56]; int32_t price' } /* create an array of structs */ Product* table = new Product[N]; /* now load this array of structs, from a file etc. */ 

Analogamente, è ansible simulare un’esecuzione di query di archivio di colonne molto semplice nella memoria principale creando un array di 3 dimensioni N, un array per ogni attributo della tabella Product . Tale layout di memoria è anche chiamato struct of matrici. Quindi i 3 array per ogni attributo di prodotto possono essere come:

 /* create separate arrays for each attribute */ int32_t* key = new int32_t[N]; char* name = new char[56*N]; int32_t* price = new int32_t[N]; /* now load these arrays, from a file etc. */ 

Ora dopo aver caricato sia la matrice di structs (Row Layout) che i 3 array separati (Column Layout), abbiamo il row store e il column store sulla nostra tabella Product presente nella nostra memoria.

Ora passiamo alla parte del codice di cache friendly. Supponiamo che il carico di lavoro sulla nostra tabella sia tale che abbiamo una query di aggregazione sull’attributo price. Ad esempio

 SELECT SUM(price) FROM PRODUCT 

Per l’archivio di righe possiamo convertire la query SQL sopra in

 int sum = 0; for (int i=0; i 

Per l'archivio colonne possiamo convertire la query SQL sopra in

 int sum = 0; for (int i=0; i 

Il codice per l'archivio colonne sarà più veloce del codice per il layout di riga in questa query in quanto richiede solo un sottoinsieme di attributi e nel layout di colonna stiamo facendo proprio questo, cioè solo accedendo alla colonna del prezzo.

Supponiamo che la dimensione della linea della cache sia 64 byte.

Nel caso del layout di riga quando viene letta una riga di cache, viene letto il valore di prezzo di 1 cacheline_size/product_struct_size = 64/64 = 1 ( cacheline_size/product_struct_size = 64/64 = 1 ), perché la nostra dimensione di struttura di 64 byte e riempie l'intera riga della cache, quindi per ogni tupla si verifica un errore di cache in caso di layout di riga.

Nel caso di layout di colonne quando viene letta una riga di cache, viene letto il valore di prezzo di cacheline_size/price_int_size = 64/4 = 16 di 16 ( cacheline_size/price_int_size = 64/4 = 16 ), perché 16 valori di prezzo contigui memorizzati nella memoria vengono portati nella cache, quindi per ogni sedicesima tupla a cache miss ocurs in caso di layout di colonna.

Quindi il layout della colonna sarà più veloce nel caso di una determinata query, ed è più veloce in tali query di aggregazione su un sottoinsieme di colonne della tabella. Puoi provare questo tipo di esperimento utilizzando i dati del benchmark TPC-H e confrontare i tempi di esecuzione per entrambi i layout. Anche l'articolo di Wikipedia sui sistemi di database orientati alle colonne è buono.

Pertanto, nei sistemi di database, se il carico di lavoro della query è noto in anticipo, possiamo archiviare i nostri dati in layout che si adattano alle query nel carico di lavoro e ai dati di accesso da questi layout. Nel caso dell'esempio precedente abbiamo creato un layout di colonna e modificato il nostro codice per calcolare la sum in modo che diventasse cache-friendly.

Essere consapevoli del fatto che le cache non nascondono solo la memoria continua. Hanno più linee (almeno 4) in modo che la memoria discontinua e sovrapposta possa spesso essere archiviata con la stessa efficienza.

Quello che manca a tutti gli esempi sopra è misurato benchmark. Ci sono molti miti sulle prestazioni. A meno che non lo misuri, non lo sai. Non complicare il codice a meno che tu non abbia un miglioramento misurato .