Perché struct con i campi di imbottitura opere più veloce

Question

Ho appena trovato questa biblioteca, che fornisce l'anello senza blocchi, che funziona modo più veloce quindi canali: https://github.com/textnode/gringo (e funziona davvero più veloce soprattutto con GOMAXPROCS> 1)

Ma una parte interessante è struct per la gestione dello stato della coda:

type Gringo struct { 
    padding1 [8]uint64 
    lastCommittedIndex uint64 
    padding2 [8]uint64 
    nextFreeIndex uint64 
    padding3 [8]uint64 
    readerIndex uint64 
    padding4 [8]uint64 
    contents [queueSize]Payload 
    padding5 [8]uint64 
} 

Se rimuovo "paddingX [8] uint64" campi funziona più lento di circa il 20%. Come può essere?

Apprezzo anche se qualcuno ha spiegato perché questo algoritmo lock-free è molto più veloce dei canali, persino bufferizzato?

Answer 1

Il riempimento elimina false sharing mettendo ciascuna struttura sulla propria linea di cache. Se due variabili condividono una linea di cache, una lettura di una variabile non modificata sarà costosa come una lettura di una variabile modificata se c'è una scrittura interveniente all'altra variabile.

Quando una variabile viene letta su più core e non modificata, la linea della cache viene condivisa dai core. Questo rende le letture molto economiche. Prima che qualsiasi core possa scrivere su qualsiasi parte di quella linea cache, deve invalidare la linea cache su altri core. Se un core successivo legge da quella linea della cache, troverà la linea della cache invalidata e dovrà tornare a condividerla. Questo rende doloroso il traffico extra di coerenza della cache quando una variabile viene frequentemente modificata e l'altra viene letta frequentemente.

Answer 2

Funziona più velocemente perché non richiede serrature. This è un'implementazione in Java (chiamata Disruptor) che funziona molto bene e sembra essere l'ispirazione per gringo. Spiegano il costo delle serrature e come è possibile aumentare il throughput here.

Per quanto riguarda l'imbottitura, la carta suggerisce anche alcuni dei motivi. Fondamentalmente: cache del processore. This paper lo spiega bene. È possibile ottenere un enorme guadagno di prestazioni facendo in modo che il processore acceda alla propria cache di Livello 1 invece di passare attraverso la memoria o le cache esterne il più spesso possibile. Ma questo richiede di prendere ulteriori precauzioni poiché il processore caricherà completamente la sua cache e la ricaricherà (dalla memoria o dalle cache di livello 2-3) ogni volta che sarà necessario. Nel caso della struttura di dati concorrenti, come ha detto @David Schwartz, la condivisione errata costringerà il processore a ricaricare la cache molto più spesso, poiché alcuni dati potrebbero essere caricati nel resto della linea di memoria, essere modificati e forzare il tutta la cache per essere caricata di nuovo.