Allocatori di heap personalizzati

Ogni volta che si dispone di un'applicazione con un percorso critico intensivo delle prestazioni, si dovrebbe essere preoccupati di come si tratti la memoria. La maggior parte delle applicazioni lato client lato utente non rientrano in questa categoria perché sono guidate dagli eventi primari e la maggior parte degli eventi proviene da interazioni con l'utente, e questo non ha molti vincoli prestazionali (se non del tutto). / p>

Tuttavia, molti software di back-end dovrebbero concentrarsi su come viene gestita la memoria, perché molti di questi software possono scalare per gestire un numero maggiore di client, un numero maggiore di transazioni, più fonti di dati .... Una volta che inizi a spingere i limiti, puoi iniziare ad analizzare come gli utenti del tuo software memorizzano e scrivere schemi di allocazione personalizzati su misura per il tuo software piuttosto che affidarti a un allocatore di memoria completamente generico che è stato scritto per gestire qualsiasi caso d'uso immaginabile.

Per darvi qualche esempio ... nella mia prima azienda ho lavorato su un pacchetto Historian, software responsabile della raccolta / archiviazione / archiviazione dei dati di controllo del processo (pensate a una fabbrica, una centrale nucleare o una raffineria di petrolio con 10 milioni di milioni di sensori, memorizziamo tali dati). Ogni volta che analizzavamo un collo di bottiglia delle prestazioni che impediva allo storico di elaborare più dati, il più delle volte il problema era relativo al modo in cui la memoria veniva gestita. Abbiamo fatto di tutto per assicurarci che malloc / free non venisse chiamato a meno che non fossero assolutamente necessari.

Nel mio attuale lavoro, lavoro su video registratore digitale e pacchetto di analisi. A 30 fps, ogni canale riceve un fotogramma video ogni 33 millisecondi. Sull'hardware che vendiamo, possiamo registrare facilmente 100 canali video. Ecco un altro caso per accertarci che nel percorso critico (network call = > capture components = > software di gestione del registratore = > storage components = > disk) non ci siano allocazioni di memoria dinamica. Abbiamo un allocatore di frame personalizzato, che contiene bucket di buffer di dimensioni fisse e utilizza LIFO per riutilizzare i buffer allocati in precedenza. Se hai bisogno di 600Kb di spazio di archiviazione, potresti finire con un buffer da 1024Kb, che spreca spazio, ma poiché è fatto su misura per il nostro uso in cui ogni allocazione ha vita molto breve, funziona molto bene perché il buffer è usato, libero e riutilizzato per il prossimo canale senza chiamate all'heap API.

Nel tipo di applicazioni che ho descritto (lo spostamento di molti dati da A a B e la gestione di un gran numero di richieste client), l'heap e il ritorno rappresentano una fonte importante di colli di bottiglia nelle prestazioni della CPU. Mantenere al minimo la frammentazione dell'heap è un vantaggio secondario, tuttavia per quanto ne so, la maggior parte dei moderni sistemi operativi implementa già heap a bassa frammentazione (almeno so che Windows lo fa, e spero che anche gli altri lo facciano). Personalmente, in oltre 12 anni di lavoro in questi tipi di ambienti, ho riscontrato problemi di utilizzo della CPU correlati all'heap abbastanza frequentemente, mentre mai una volta ho visto un sistema che effettivamente soffriva di heap frammentato.

Elaborazione video, VFX, sistemi operativi, ecc. Spesso però le persone li usano eccessivamente. La struttura dei dati e l'allocatore non devono essere separati per ottenere un'allocazione efficiente.

Ad esempio, sta introducendo un sacco di complessità in più per dividere l'allocazione efficiente dei nodi degli alberi in un angolo lontano dall'occhiello stesso e fare affidamento su un allocatore esterno. Non è necessariamente una violazione di SRP fondere insieme queste due preoccupazioni e rendere la responsabilità dell'ottimo allocare molti nodi contemporaneamente in modo contiguo, in quanto ciò non aumenta il numero di ragioni per cambiare. Potrebbe, in pratica, ridurlo.

In C ++, ad esempio, uno degli effetti collaterali ritardati di avere contenitori standard basati su un allocatore esterno ha reso strutture collegate come std::map e std::list considerate quasi inutili dalla comunità C ++, dal momento che le stanno valutando contro std::allocator mentre queste strutture dati allocano un nodo alla volta. Naturalmente in questo caso le vostre strutture collegate avranno un rendimento scarso, ma le cose sarebbero andate diversamente in modo diverso se l'allocazione efficiente dei nodi per le strutture collegate fosse considerata una responsabilità della struttura dei dati piuttosto che quella di un allocatore. Potrebbero ancora utilizzare un'assegnazione personalizzata per altri motivi come il tracciamento / profilazione della memoria, ma affidarsi all'allocatore per rendere efficienti le strutture collegate mentre tentano di allocare i nodi uno alla volta li rende tutti, per impostazione predefinita, estremamente inefficienti, che andrebbe bene se venisse fornito con un avvertimento ben noto che le strutture collegate ora necessitano di un allocatore personalizzato, come la lista libera, per essere ragionevolmente efficiente ed evitare l'attivazione di errori di cache a destra ea sinistra. Molto più praticamente applicabile potrebbe essere stato qualcosa come std::list<T, BlockSize, Alloc> , dove BlockSize indica il numero di nodi contigui da allocare in una sola volta per la lista libera (specificando 1 sarebbe effettivamente portare a std::list come lo è ora).

Ma non c'è un avvertimento del genere, che poi porta a un'intera comunità di teste di pietra che fa eco a un mantra di culto secondo cui le liste collegate sono inutili, ad es.

Un'altra area in cui si potrebbe desiderare un allocatore personalizzato è impedire la frammentazione dell'heap . Nel tempo il tuo heap può allocare piccoli oggetti frammentati in tutto l'heap. Se il tuo programma non può tenere insieme la memoria heap, quando il tuo programma va ad allocare un oggetto più grande, deve rivendicare più memoria dal sistema in quanto non riesce a trovare un blocco libero tra l'heap esistente, frammentato (troppi piccoli gli oggetti sono sulla strada). L'utilizzo totale della memoria del tuo programma aumenterà nel tempo e consumerai inutilmente ulteriori pagine di memoria. Quindi questo è un grosso problema per i programmi che dovrebbero funzionare per lunghi periodi di tempo (pensate a database, server, ecc.).

Where, apart from games, are custom allocators heavily used?

Facebook

Controlla jemalloc che Facebook sta iniziando a utilizzare per migliorare le prestazioni dell'heap e ridurre la frammentazione.