risposta-alla-domanda-sullo-sviluppo-web-bd.com

Cos'è un codice "cache-friendly"?

Qual è la differenza tra " cache unfriendly code " e il codice " cache friendly "?

Come posso assicurarmi di scrivere codice efficiente per la cache?

675
Alex

Preliminari

Nei computer moderni, solo le strutture di memoria di livello più basso (i registers ) 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 migliaio byte in totale). All'altra estremità dello spettro di memoria (DRAM), la memoria è molto economica (cioè letteralmente milioni di volte più economica) ma richiede centinaia di cicli dopo una richiesta per ricevere i dati. Per colmare questo divario tra super veloce e costoso e super lento ed economico sono le memorie cache , denominate L1, L2, L3 in velocità e costo decrescenti. 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. Se no, allora cache L3, e se non lì, 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 di latenza. Per parafrasare Herb Sutter (vedi link sotto): aumentare la larghezza di banda è facile, ma non possiamo comprare la nostra uscita dalla latenza .

I dati vengono sempre recuperati attraverso la gerarchia di memoria (il più piccolo == il più veloce al più lento). A cache hit/miss di solito si riferisce a un hit/miss nel più alto livello di cache nella CPU - per il livello più alto intendo il più == il più lento. Il tasso di hit della cache è cruciale per le prestazioni, poiché ogni errore di cache risulta nel recupero dei dati da RAM (o peggio ...) che richiedeun lottodi 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 il die della CPU (ad esempio, accedendo a RAM o successivo). 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% della matrice in cache e fino al 99% nella memorizzazione/spostamento dei dati!

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

Concetti principali per codice cache-friendly

Un aspetto molto importante del codice cache-friendly è tutto suil principio di localizzazione, il cui scopo è quello di mettere i dati correlati in memoria per consentire un caching efficiente. Per quanto riguarda la 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 dei dati correlati vicini tra loro. 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 cache lines è importante.

Usa appropriato c ++ contenitori

Un semplice esempio di cache-friendly versus cache-unfriendly è c ++ 's std::vector contro std::list. Gli elementi di un std::vector sono archiviati nella memoria contigua e, in quanto tale, accedervi è much più cache-friendly dell'accesso agli elementi in un 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 possibile, 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 riguardo è cache blocking(Archive.org version) , che è di estrema importanza nel calcolo ad alte prestazioni (cfr. Per 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 (es. 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 come 1 2 3 4; nell'ordine delle colonne questo sarebbe stato 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 come questa very 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 riga della cache. Se l'ordinamento è sfruttato, ciò comporterà un minor numero di accessi alla memoria (perché i prossimi valori che sono 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 somma su tutti gli elementi nell'esempio 2x2 matrice sopra (chiamiamola M):

Sfruttare l'ordine (ad esempio cambiando 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 esempio cambiando l'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 impossibile precedere i dati. Ciò condurrà indirettamente a più errori di cache.

Questo è spiegato very 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 di c ++ , i metodi virtual rappresentano un problema controverso per quanto riguarda i fallimenti della cache (esiste un consenso generale sul fatto che dovrebbero essere evitati laddove possibile 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 informazioni su questo problema, consultare: Qual è il costo delle prestazioni di avere un metodo virtuale in una classe C++?

Problemi comuni

Un problema comune nelle architetture moderne con cache multiprocessore è chiamato false 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 linea 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 reciprocamente 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 della scarsa memorizzazione nella cache di RAM memoria (che probabilmente non è ciò che intendi 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.

875
Marc Claesen

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 riga sono anche adiacenti in memoria, quindi accedervi in ​​sequenza significa accedervi in ​​ordine di memoria ascendente; questo è cache-friendly, poiché la cache tende a precedere i 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<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

a

// Cache-unfriendly version - jumps around in memory for no good reason
for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

Questo effetto può essere piuttosto drammatico (di diversi ordini di grandezza in velocità) in sistemi con piccole cache e/o lavorare con grandi matrici (ad esempio, 10+ megapixel con immagini a 24 bpp sulle 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.

130
Matteo Italia

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

Località di riferimento

Il primo fattore (a cui altri hanno già fatto riferimento) è 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 nodi 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 tocco un byte, la cache potrebbe caricare 128 o 256 byte vicino a quello. Per trarne vantaggio, in genere si desidera disporre i dati in modo da massimizzare la probabilità che vengano utilizzati anche gli altri dati caricati nello stesso momento.

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ù possibile) eseguire tutte le operazioni su quei dati contemporaneamente.

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

Il problema con questo è che attraversa una coppia di input, mette i risultati in un temporaneo, 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 come (a[n] + b[n]) * (c[n] + d[n]);, preferiremmo generalmente leggere ogni 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 della linea

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 nella 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 chiamate "set associative". Ad esempio, in una cache associativa set a 4 vie, qualsiasi elemento dalla memoria principale può essere memorizzato in uno dei 4 diversi punti della cache. Quindi, quando la cache sta per caricare un elemento, cerca la meno recente utilizzata3 elemento tra questi quattro, lo scarica nella memoria principale e carica il nuovo oggetto al suo posto.

Il problema è probabilmente abbastanza ovvio: per una cache mappata diretta, due operandi che si verificano mappare nella stessa posizione della cache possono portare a un comportamento errato. Una cache associativa-set di N-way 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 di 8192 vie è raramente una buona soluzione.

In definitiva, questo fattore è più difficile da controllare nel codice portatile. Il controllo su dove vengono posizionati i dati è in genere abbastanza limitato. Peggio ancora, la mappatura 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. Ciò impone ai due processori/core di 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) modificino i dati che potrebbero essere nella stessa riga della cache (con gli stessi avvertimenti sulla difficoltà di controllare gli indirizzi a cui 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ì, si potrebbe fare e se lo fosse, sarebbe probabilmente una vittoria piuttosto consistente. 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 chiede come valarray (progettato specificamente per le prestazioni) potrebbe essere così gravemente sbagliato, si riduce a una cosa: è stato 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 usato meno di recente, ma usa un certo euristico che è inteso per essere vicino a quello senza dover mantenere un timestamp completo per ogni accesso.

81
Jerry Coffin

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 l'obbligatorio tipico C++ Bullshit . Anche Tony Albrecht's Pitfalls of Object Oriented Programming è una grande introduzione all'argomento.

30
arul

Semplicemente accumulando: il classico esempio di cache-unfriendly rispetto al codice cache-friendly è il "blocco della cache" della matrice moltiplicata.

Sembra moltiplicarsi la matrice ingenua

for(i=0;i<N;i++) {
   for(j=0;j<N;j++) {
      dest[i][j] = 0;
      for( k==;k<N;i++) {
         dest[i][j] += src1[i][k] * src2[k][j];
      }
   }
}

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

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

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj+) {
         dest[i][j+jj] = 0;
      }
      for( k==;k<N;i++) {
         for(jj=0;jj<itemsPerCacheLine; jj+) {
            dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
         }
      }
   }
}

Se la dimensione della linea della cache è 64 byte e stiamo operando su float 32 bit (4 byte), allora ci sono 16 elementi per riga della cache. E il numero di errori di cache tramite 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

21
Krazy Glew

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 ogni uno più lento accesso (e più grande) rispetto al prossimo, fino ad arrivare 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 indirizzi virtuali. 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.

13
Rafael Baptista

È necessario chiarire che non solo i dati devono essere adattati alla cache, è altrettanto importante per il codice. Questo è in aggiunta alla previsione delle branche, al riordino delle istruzioni, alla prevenzione di 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, poiché 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 in un indirizzo di allineamento della riga della cache. Sebbene ci siano switch (gcc) per il compilatore per questo, 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ù spesso rientrano in una riga di cache da 64 byte, ciò è meno dispendioso di se ognuna ha una propria linea e produce 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.

4
Olof Forshell

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 amichevole della cache è: cambiare il modo in cui i nostri dati vengono archiviati; 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 modi di base per memorizzare le tuple di una tabella, ad esempio archivio di righe e archivio di colonne. Nel negozio di riga, come suggerisce il nome, le tuple sono archiviate in fila. Supponiamo che una tabella denominata Product in 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 riga 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 simile a:

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. */

Allo stesso modo, possiamo 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), nella nostra tabella sono presenti Product row nella 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<N; i++)
   sum = sum + table[i].price;

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

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + price[i];

Il codice per l'archivio colonne sarà più veloce del codice per il layout di riga in questa query poiché richiede solo un sottoinsieme di attributi e nel layout di colonna stiamo facendo proprio questo, cioè accedendo solo 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 solo 1 (cacheline_size/product_struct_size = 64/64 = 1) Tuple, perché la nostra struct size di 64 byte e riempie l'intera riga della cache, quindi per ogni Tuple si verifica una mancanza di cache in caso di un layout di riga.

Nel caso del layout di una colonna quando viene letta una riga di cache, viene letto il valore di prezzo di tuple di 16 (cacheline_size/price_int_size = 64/4 = 16), poiché 16 valori di prezzo contigui memorizzati nella memoria vengono portati nella cache, quindi per ogni sedicesima Tuple viene rilevata una mancanza di cache nel caso del layout della 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. È possibile provare questo tipo di esperimento utilizzando i dati di TPC-H benchmark e confrontare i tempi di esecuzione per entrambi i layout. Anche l'articolo wikipedia sui sistemi di database orientati a 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 somma in modo che diventasse cache-friendly.

2
user2603796

Essere consapevoli del fatto che le cache non nascondono solo la memoria continua. Hanno più righe (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 misurato miglioramento.

0
Tuntable