Come allineare sia la dimensione della parola che le linee della cache in x86

Per capire in che modo l'allineamento influisce sulle cose, esaminiamo un contesto più ampio.

Innanzitutto, come si nota, 2600 byte di UTF-8 (o qualsiasi tipo di dati) prenderanno effettivamente 2600 byte.

Se assegni 2600 byte dall'heap usando malloc(2600) e.g. in C, dato che malloc non accetta le informazioni di allineamento, non saprà che il tuo intento è quello di archiviare solo i singoli byte - presuppone il caso peggiore, ovvero che stai usando la memoria per il più grande tipo nativo che il processore sostiene. Nel caso di un processore a 64 bit che diventerà 16 byte, che è piuttosto grande.

Quindi, l'allocatore di memoria individua la memoria libera che corrisponde all'allineamento a 16 byte (e almeno 2600 byte di lunghezza). Un'allocazione di memoria successiva tramite malloc verrà arrotondata all'allineamento di 16 byte, quindi ci sarà un piccolo spazio tra il blocco da 2600 byte e il prossimo blocco di memoria restituito da malloc, poiché 2600 è un multiplo esatto di 8 ma non di 16. (Ci sono anche potenzialmente altri overheads associati a ciascun blocco di malloc.)

Sia Linux che amp; Windows offre un malloc allineato; tuttavia, Linux afferma esplicitamente che l'allineamento minimo è la dimensione del puntatore. Anche su Windows, che non dice, è chiaro dalla documentazione che gli autori si aspettano che vengano richiesti allineamenti più grandi, non allineamenti più piccoli.

C creerà strutture con allineamento di campo adeguato per la piattaforma di destinazione, il che significa che inserirà i pad pad inutilizzati all'interno di una struct se i campi precedenti non sono disposti in modo tale da poter disporre del corretto allineamento. Ad esempio:

struct S {
   char c;
   int  i;
}

Struct S dichiara c , come elemento a 1 byte e sarà a offset 0 nella struct. Il campo i è, diciamo, un elemento a 4 byte. Dopo c il prossimo offset disponibile è 1 ma non è adeguatamente allineato per un valore a 4 byte, quindi il compilatore inserirà 3 byte padding e utilizzerà l'offset 4 per i , rendendo la dimensione della struct sizeof(struct S) 8, anche se memorizza solo 5 byte di informazioni.

Parliamo anche di endianità. Se si dispone di una stringa di byte, ciascun byte di successo viene memorizzato all'indirizzo del byte successivo più alto (basta aggiungere 1 all'indirizzo per passare a quello successivo). Tuttavia, le macchine big-endian memorizzano i 4 byte necessari per creare un Parola di 4 byte invertita da macchine little-endian. Quindi, se volessi usare un accesso a dimensione di parola sulla tua stringa "abcd", vedresti una differenza tra una macchina big e little-endian: la macchina big-endian ti darebbe un "abcd" mentre la macchina little-endian darti 'dcba'.

In generale, è generalmente meglio non utilizzare la stessa memoria sia come byte sia come parole (allo stesso tempo): se contiene i byte, quindi usa l'accesso in formato byte e se contiene le parole, usa la parola accesso di dimensioni Nota che questo accadrà naturalmente a meno che tu non faccia "cose cattive" come puntatori lanciati su un tipo diverso da quello a cui inizialmente puntavano. (Ci sono momenti in cui potrebbe essere necessario, e autori di routine come memcpy e memmove giocano alcuni trucchi per le prestazioni.) Possiamo anche notare che non è nemmeno possibile mescolare accessi di dimensioni in byte e word-size (per lo stesso dato / oggetto / array) in un linguaggio come Java (senza ricorrere alla serializzazione) poiché non offre la funzionalità di basso livello dei puntatori di cast.

Il compilatore e il runtime (ad es. malloc) collaborano per assicurarsi che i dati siano allineati correttamente (forse anche se sono sovra-allineati). Ad esempio, lo stack, prima di main , deve essere inizialmente allineato (dal runtime) ad almeno un limite di 16 byte, quindi il compilatore può creare frame di stack arrotondati a una dimensione di 16 byte, quindi lo stack e tutte le variabili locali rimangono allineate durante le chiamate di funzione. Le variabili globali ricevono un trattamento simile e abbiamo già discusso delle allocazioni dell'heap.

Sembra che la tua confusione derivi dal mescolare alcuni livelli architettonici.

La tua architettura del processore può essere a 64 bit, il che rende "facile" lavorare su blocchi che si allineano con i limiti a 64 bit. È come camminare sulle tessere, se il tuo passo corrisponde alle tessere non dovrai cambiare il tuo passo. Cambiare il tuo passo ti rallenterà. Questo vale per l'elaborazione delle strutture del programma, ad esempio i tipi di valore. Se ne hai molti da elaborare, può essere utile aggiungere un byte o due alla fine di una struttura più grande solo per impedire la modifica del passo. Tieni presente che è utile per elaborare i dati letti da una pipeline.

L'allineamento a 4-byte della stringa "abcdef" non risulterebbe in

a---b---c---d---e---f---

ma piuttosto in

abcdef--

La memoria cache è denominata cache per un motivo (dopo il francese caché che significa nascosto). Significa che è trasparente per il programmatore. Lo scopo è di mantenere i dati usati più spesso vicino al processore. Immagino che tu lo sappia già, il punto è che si tratta di un dettaglio hardware a un livello molto basso di cui non dovresti preoccuparti come programmatore, non solo perché non ne vale la pena ma anche perché non hai idea di come sia implementato un particolare processore. Si tratta solo di recuperare, ottenendo blocchi di byte vicino al processore in tempo. La maggior parte di questo sarà fatto in modo asincrono per te da un meccanismo di pre-fetch. Sarà difficile prevedere quale strategia ti darebbe alcun vantaggio. Dipenderebbe dalla piattaforma e funzionerebbe solo per scenari molto specifici, in loop davvero stretti con molte iterazioni e logica molto breve e veloce.

Ora torna al tuo UTF-8. Questo è, rispetto al cache di cui abbiamo appena parlato, livello molto alto. Generalmente è organizzato come un flusso di byte, l'allineamento dei record non si applica. L'elaborazione di testo o xml sarà più lenta di diversi ordini di grandezza rispetto all'ottenimento dei dati dalla memoria. Il processore non si cura della tua codifica, ti dà solo un byte e poi dovrai decidere se è una lettera o un carattere di escape, o la fine della stringa, o l'inizio del prossimo tag elemento. La logica di pre-fetch del processore sarà ormai sbadigliando. La codifica non è solo un problema a livello di processore.

Il principale punto di allineamento è ridurre il numero di richieste di memoria richieste per ciascuna operazione.

I processori di solito recuperano e scrivono memoria in blocchi di dimensioni della linea della cache, quando parlano con la memoria esterna. Allo stesso modo, quando il core di esecuzione sta parlando alla cache, lo fa in blocchi di dimensioni word. Inoltre, a questi blocchi di solito si accede solo a indirizzi che sono multipli della loro dimensione, perché questo semplifica molte cose.

Le regole che citi sono progettate semplicemente per ridurre al minimo il numero di blocchi che ogni oggetto attraversa:

• per singoli byte è irrilevante perché un byte non può attraversare un blocco (perché tutti gli indirizzi sono allineati in byte e tutti i blocchi sono allineati in byte)
• per quantità di due byte, l'uso di indirizzi pari garantisce che non possano attraversare alcun limite
• per quantità di quattro byte, gli indirizzi multipli di quattro non attraversano i confini
• per non potere di due dimensioni, arrotondare per eccesso alla potenza più vicina di due prima.

E così via fino a raggiungere la dimensione di una linea della cache, che è l'ultima cosa che conta (tranne che per oggetti molto grandi, in cui l'allineamento delle pagine può essere d'aiuto, per ragioni simili anche se attraverso un meccanismo diverso).

Riguardo le stringhe e altri array, può essere utile allineare l'inizio del blocco fino alla dimensione della linea della cache (o le dimensioni che ci si aspetta siano se più piccole) ma solo se si prevede di eseguire molte operazioni di massa, per esempio copie del blocco di memoria, confronti di stringhe ottimizzati, ecc. Se tutto ciò che fai è accedere agli articoli uno alla volta, tuttavia è improbabile che tale allineamento sia di aiuto.

Le matrici di elementi che non hanno potenza di due dimensioni potrebbero richiedere un riempimento in modo che ogni elemento sia allineato correttamente. Gli array di caratteri non dovrebbero richiedere alcun riempimento interno.