Qualunque sistema operativo implementa il buffering per malloc()?

Question

Un sacco di c/malloc() in un for/while/do può consumare molto tempo quindi sono curioso di sapere se qualsiasi sistema operativo memorizza memoria per malloc veloci.

Ho riflettuto se potevo accelerare Malloc's scrivendo un involucro "avido" per malloc. Per esempio. quando richiedo 1MB di memoria, l'allocatore iniziale assegnerebbe 10MB e sul 2 °, 3 °, 4 ° ecc ... la funzione malloc restituirebbe semplicemente la memoria dal blocco che prima assegnava il modo "normale". Ovviamente, se non c'è abbastanza memoria disponibile, è necessario allocare un nuovo bel pezzo di memoria.

In qualche modo penso che qualcuno debba aver fatto questo o qualcosa di simile prima. Quindi la mia domanda è semplicemente: è qualcosa che accelera il processo di allocazione della memoria in modo significativo. (sì, avrei potuto provarlo prima di fare la domanda ma sono solo pigro per scrivere una cosa del genere se non c'è bisogno di farlo)

Answer 1

Tutte le versioni di malloc() eseguono il buffering del tipo che si descrive in una certa misura: accetteranno un blocco più grande rispetto alla richiesta corrente e utilizzeranno il grosso blocco per soddisfare più richieste, ma solo fino ad alcune dimensioni della richiesta. Ciò significa che più richieste per 16 byte alla volta richiederanno solo più memoria dall'o/s una volta ogni 50-100 chiamate o qualcosa di simile su quelle linee generali.

Ciò che è meno chiaro è la dimensione del contorno. Potrebbe anche essere che allocano un multiplo relativamente piccolo di 4 KiB alla volta. Richieste più grandi - Richieste di dimensione MiB - torneranno al sistema per più memoria ogni volta che la richiesta non può essere soddisfatta da ciò che è nella lista libera. Questa soglia è in genere considerevolmente più piccola di 1 MiB, però.

Alcune versioni di malloc() consentono di adattare le loro caratteristiche di allocazione, a estensioni maggiori o minori. È stata una zona di ricerca fertile: molti sistemi diversi. Vedi Knuth 'The Art of Computer Programming' Vol 1 (Algoritmi fondamentali) per una serie di discussioni.

Answer 2

Mentre stavo navigando nel codice di Google Chrome qualche tempo fa, ho trovato http://www.canonware.com/jemalloc/ . Si tratta di un'implementazione malloc gratuita, general-purpose e scalabile.

Apparentemente, viene utilizzato in numerosi progetti, poiché di solito supera le implementazioni standard di malloc in molti scenari del mondo reale (molte piccole allocazioni invece di poche grandi).

Vale la pena dare un'occhiata!

Answer 3

Quello che stai dicendo è probabilmente fatto, non lo so davvero. Tuttavia, non so se la latenza nel buffering del tuo malloc() a livello di sistema ridurrebbe molto la latenza. Devi ancora prendere il tempo per entrare in privato. modalità per una chiamata di sistema, potenzialmente bloccare le strutture a livello di kernel (che significa più chiamate di sistema e WAITING per i blocchi) e cose di questa natura.

Se è possibile scrivere il proprio gestore memoria nello spazio utente per il proprio programma e chiamare solo malloc() quando è necessaria più memoria per il pool, è probabile che si verifichi una diminuzione della latenza.

Answer 4

Questa tecnica è denominata Slab Allocator e la maggior parte dei sistemi operativi lo supporta, ma non riesco a trovare informazioni disponibili per il malloc degli utenti, solo per le allocazioni del kernel.

È possibile trovare la carta di Jeff Bonwick here, che descrive la tecnica originale su Solaris.

Answer 5

Google ha una golosa implementazione di malloc() che fa grosso modo quello che stai pensando. Ha alcuni inconvenienti, ma è molto veloce in molti casi d'uso.