Vergelijking van Arena-architectuur in malloc()

Problemen bij geheugenallocatie

malloc (libc) is de slechtste API voor geheugenallocatie om te gebruiken. Programma's zouden, indien mogelijk, het vaak alloceren en dealloceren van geheugen moeten vermijden, in het bijzonder op het moment dat er een pakket wordt ontvangen.

In de Linux-kernel zijn er kernel/driver-patches beschikbaar voor het recyclen van skbuff (geheugen in de kernel dat wordt gebruikt voor het opslaan van inkomende en uitgaande pakketten). Het gebruik van PF_RING (in de driver) voor het kopiëren van pakketten van de NIC naar de circulaire buffer zonder geheugenallocatie verhoogt de capture-prestaties (met ongeveer 10%) en vermindert congestieproblemen.

Evolutie van het ontwerp

Het basisontwerp van malloc() is om dynamisch een pool van geheugen van het besturingssysteem (OS) te pre-alloceren, waar applicaties vervolgens kleinere stukken uit kunnen nemen. malloc() is een standaard API met een keuze uit verschillende allocatie-algoritmen om de kostbare OS-systeemoproepen (die doorgaans plaatsvinden tijdens de initialisatie van het programma) tijdens de allocatie van systeemgeheugen te beperken.

De evolutie van de allocatieschema's verliep als volgt:

1. Het begon met een stack-gebaseerde geheugenallocatie.
2. Daarna volgde het dynamisch-gebaseerde allocatieschema, waarbij linked-list en bucket-heap mechanismen worden gebruikt om de private-heap te verdelen via een size class benadering.
3. Kort daarna introduceerde het garbage collection-algoritme de initiële backend van het allocatieschema. De frontend omvat de gebruikelijke malloc() API en aanverwante functies.
4. In 2006 werd een derde pool geïntroduceerd (naast de OS-geheugenpool en de library-gebaseerde geheugenpool), genaamd de "arena". Arena is een term uit jemalloc en is bedoeld om om te gaan met verschillende geheugentypen, zoals geheugenbanken met verschillende snelheden of NUMA-architecturen, alsook geheugen dat specifiek is gekoppeld aan elk van de meerdere CPU-cores of zelfs CPU-affinity.

Evolutie van de Frontend

De frontend beheert het geheugen dat aan de applicatie wordt gegeven. Binnen de frontend van het allocatiesysteem volgde de evolutie deze volgorde:

• Link-list vrije ruimte
• Heap-bucket size classes (eliminatie van een object header)
• (Process) Owner encoding
• Single core local allocation buffers (CLABs)
• Epoch encoding
• Large-size class geheugenblokken via directe mmap()
• Hazard pointers (veilige geheugenreclamatie voor lock-free objecten) (M.M. Michael, 2004)
• Arena memory pool (gescheiden per CPU/core en thread)
• Thread-specific local allocation buffers (TLABs)
• Constant-time modulo synchronisatie (vroegtijdige teruggave aan de OS-pool, of FreeBSD madvise call)

Evolutie van de Backend

De backend van het allocatiesysteem beheert het teruggeven van lege, verspreide, gefragmenteerde of niet langer gebruikte geheugenblokken aan het OS (om zo de RSS te verminderen).

De evolutie omvatte:

• Pool semantiek: Remote f-list encoding, gebruikmakend van de Treiber stack (R.K. Treiber, 1986)
• Buddy algoritme
• Binair buddy algoritme
• BIPOP Table (span-based allocator) (S. Schneider, 2006), ook bekend als local free list en remote free list
• Segment queue (Quasi-linearizability, Y. Afek, 2010)
• Multi-core distributed queue (A. Haas, 2013)
• k-FIFO queue (T.A. Henzinger, 2013)

Concurrentie

Er zijn betere allocators beschikbaar die niet verslechteren naarmate meer threads of processen systeemoproepen voor geheugenallocatie uitvoeren. Deze zijn hieronder gerangschikt van beste naar goede prestaties.

Vergelijking van malloc-ontwerpen

Allocator	Oorsprong / Onderhoud	Thread Safe	Per-Thread Cache	Multi-Arena / Heaps	Lock-Free Fast Path	NUMA Aware	Fragmentatie Controle	Notities
dlmalloc	Doug Lea	Nee	Nee	Nee	Nee	Laag	Enkele globale heap; basis voor latere allocators
ptmalloc2 / 3	glibc	Ja	Beperkt	Ja	Nee	Medium	glibc standaard; arena locks veroorzaken contentie
glibc malloc	GNU	Ja	Beperkt	Ja	Nee	Medium	Wrapper rond ptmalloc met instelbare parameters
jemalloc	FreeBSD / Meta	Ja	Ja	Ja	Gedeeltelijk	Hoog	Thread-arena affiniteit vermindert CAS-contentie
tcmalloc	Google	Ja	Ja	Ja	Gedeeltelijk	Medium-Hoog	Per-CPU caches; centrale freelists bestaan nog steeds
mimalloc	Microsoft	Ja	Ja	Ja	Ja	Hoog	Ontworpen om atomische operaties en false sharing te minimaliseren
Hoard	Emery Berger	Ja	Ja	Ja	Gedeeltelijk	Medium	Focus op schaalbaarheid en vermijden van false-sharing
nedmalloc	NEDMALLOC	Ja	Ja	Ja	Nee	Medium	Afgeleid van dlmalloc met thread caching
phkmalloc	FreeBSD	Ja	Ja	Ja	Nee	Medium	Vroege FreeBSD allocator familie
libumem	Solaris	Ja	Ja	Ja	Ja	Medium-Hoog	Solaris allocator met debugging en locality support
mtmalloc	Solaris	Ja	Ja	Ja	Ja	Medium	Solaris multithreaded allocator
snmalloc	MS Research	Ja	Ja	Ja	Ja	Hoog	NUMA-aware; focus op security en schaalbaarheid
lockless malloc	Academisch	Varieert	Ja	Varieert	Ja	Laag	Vaak CAS-heavy; niet productieklaar

CAS / Atomische Contentie Kenmerken

Allocator	Geschatte Atomics per alloc/free	Risico op Shared Cacheline	CAS Contentie Gevoeligheid	Notities
dlmalloc	Hoog	Hoog	Zeer Hoog	Globale structuren en locks domineren
ptmalloc2 / 3	Medium-Hoog	Hoog	Hoog	Arena locks veroorzaken cacheline bouncing
glibc malloc	Medium-Hoog	Hoog	Hoog	Wrapper rond ptmalloc
jemalloc	Laag	Laag	Laag	Arena-lokale metadata; minimale gedeelde CAS
tcmalloc	Laag-Medium	Medium	Medium	Per-CPU caches; centrale freelist CAS
mimalloc	Zeer Laag	Zeer Laag	Zeer Laag	Ontworpen om atomische operaties te minimaliseren
Hoard	Medium	Medium	Medium	Vermindert false sharing maar blijft gesynchroniseerd
nedmalloc	Medium	Medium	Medium	Thread caches verminderen maar elimineren CAS niet
phkmalloc	Medium	Medium	Medium	Ouder FreeBSD ontwerp
libumem	Laag	Laag	Laag	Lock-free fast paths op Solaris
mtmalloc	Laag	Laag	Laag	Per-thread structuren verminderen atomisch delen
snmalloc	Zeer Laag	Zeer Laag	Zeer Laag	Message-passing model vermijdt gedeelde CAS
lockless malloc	Hoog	Hoog	Hoog	Vaak CAS-heavy ondanks afwezigheid van locks

NUMA / Geheugenlokaliteit Kenmerken

Allocator	Expliciete NUMA Support	First-Touch Friendly	Risico Cross-NUMA Traffic	Behoud van Lokaliteit	Notities
dlmalloc	Nee	Ja	Zeer Hoog	Slecht	Enkele heap over alle nodes
ptmalloc2 / 3	Nee	Gedeeltelijk	Hoog	Redelijk	Arenas zijn niet NUMA-gebonden
glibc malloc	Nee	Gedeeltelijk	Hoog	Redelijk	Vertrouwt op OS-plaatsing
jemalloc	Gedeeltelijk	Ja	Medium	Goed	Optionele NUMA arena tuning
tcmalloc	Beperkt	Ja	Medium	Redelijk	CPU caches zijn niet NUMA-aware
mimalloc	Nee	Ja	Laag	Zeer Goed	Sterke thread lokaliteit
Hoard	Nee	Ja	Medium	Goed	Per-processor heaps helpen
nedmalloc	Nee	Ja	Medium	Redelijk	Thread caches maar globale fallback
phkmalloc	Gedeeltelijk	Ja	Medium	Redelijk	Vroege lokaliteitsoptimalisaties
libumem	Ja	Ja	Laag	Zeer Goed	Solaris NUMA policies
mtmalloc	Ja	Ja	Laag	Zeer Goed	Ontworpen voor NUMA Solaris systemen
snmalloc	Ja	Ja	Zeer Laag	Excellent	NUMA-first architectuur
lockless malloc	Nee	Varieert	Hoog	Slecht	Lokaliteit wordt zelden geadresseerd

Praktische Prestaties (Benchmark-georiënteerd)

Allocator	Small Alloc Throughput	Large Alloc Throughput	Latency bij Contentie	Geheugen Overhead	Fragmentatie Risico	Notities
dlmalloc	Laag	Medium	Slecht	Laag	Hoog	Niet geschikt voor multithreaded loads
ptmalloc2 / 3	Medium	Medium	Slecht	Medium	Medium	glibc standaard
glibc malloc	Medium	Medium	Slecht	Medium	Medium	Instelbaar maar beperkt
jemalloc	Hoog	Hoog	Zeer Goed	Medium-Laag	Laag	Uitstekende all-round allocator
tcmalloc	Zeer Hoog	Medium	Goed	Medium	Medium	Geoptimaliseerd voor kleine objecten
mimalloc	Hoog	Hoog	Excellent	Laag	Laag	Grote voorspelbaarheid in latency
Hoard	Medium	Medium	Goed	Medium	Laag	Ontworpen voor schaalbaarheid
nedmalloc	Medium	Medium	Redelijk	Medium	Medium	Ouder maar bruikbaar
phkmalloc	Medium	Medium	Redelijk	Medium	Medium	Historische FreeBSD allocator
libumem	Hoog	Medium	Zeer Goed	Medium	Laag	Sterke debugging support
mtmalloc	Hoog	Medium	Zeer Goed	Medium	Laag	Enterprise Solaris workloads
snmalloc	Hoog	Hoog	Excellent	Laag	Zeer Laag	Focus op security + schaalbaarheid
lockless malloc	Varieert	Varieert	Slecht	Laag	Hoog	Vaak onstabiel in de praktijk

Aanbevelingen voor Allocators

Workload Type	Primaire Bottleneck	Belangrijkste Risico's	Aanbevolen Allocator	Waarom deze past	Alternatieven	Vermijden
Highly Contended Multithreaded	Atomic/CAS latency	Cacheline bouncing	jemalloc	Multi-arena + thread affiniteit minimaliseert gedeelde CAS	mimalloc	snmalloc, dlmalloc, ptmalloc
Low-Latency / Tail-Sensitive	Allocation jitter	Lock convoying	mimalloc	Zeer laag aantal atomische operaties en voorspelbare fast paths	snmalloc	jemalloc, tcmalloc
NUMA / Multi-Socket Servers	Cross-node memory access	Remote cache ownership	snmalloc	Expliciete NUMA awareness en controle over lokaliteit	jemalloc (NUMA tuned)	libumem, glibc malloc
Small Object Heavy (RPC / Web)	Allocator throughput	Central freelist contention	tcmalloc	Per-CPU caches geoptimaliseerd voor kleine allocaties	jemalloc	mimalloc, ptmalloc
Large Object / Mixed Sizes	Fragmentatie	TLB pressure	jemalloc	Uitstekende fragmentatiecontrole en extent management	mimalloc	glibc malloc
False-Sharing Sensitive	Cacheline ping-pong	Metadata sharing	Hoard	Ontworpen om false sharing te vermijden	jemalloc	mimalloc, dlmalloc
Security-Hardened	Use-after-free exploits	Heap corruption	snmalloc	Isolatie + security invarianten	mimalloc (secure)	ptmalloc
Debugging / Leak Detection	Memory misuse visibility	Silent corruption	libumem	Sterke runtime diagnostics	jemalloc (profiling)	tcmalloc
Embedded / Low Memory	Footprint size	Overhead	dlmalloc	Klein en simpel bij single-threaded gebruik	nedmalloc	jemalloc
Real-Time / Deterministic	Unbounded latency	OS interference	mimalloc	Lage variantie in fast paths	snmalloc	jemalloc, tcmalloc
HPC / Scientific NUMA	Memory bandwidth	Remote NUMA hits	snmalloc	NUMA-first design en lage CAS traffic	jemalloc + mbind	glibc malloc
Legacy / Compatibility	ABI stability	Toolchain issues	glibc malloc	Systeemstandaard en veiligste fallback	ptmalloc	-

Referenties

• R. J. Maher, Problems of storage allocation in a multiprocessor multiprogrammed system, Communications of the ACM, 4(10):421-422, Oktober 1961
• Kenneth C. Knowlton, A fast storage allocator, Communications of the ACM, 8(10):623-625, Oktober 1965
• P.W. Purdom and S. M. Stigler, Statistical properties of the buddy system, Journal of the ACM, 17(4):683-697, Oktober 1970
• P. W. Purdom, S. M. Stigler, and Tat-Ong Cheam, Statistical investigation of three storage allocation algorithms, BIT, 11:187-195, 1971
• J. A. Campbell, A note on an optimal-fit method for dynamic allocation of storage, Computer Journal, 14(1):7-9, Februari 1971
• M. R. Garey, R. L. Graham, and J. D. Ullman, Worst-case analysis of memory allocation algorithms, In Fourth Annual ACM Symposium on the Theory of Computing, 1972
• D. S. Hirschberg, A class of dynamic memory allocation algorithms, Communications of the ACM, 16(10):615-618, Oktober 1973
• J. S. Fenton and D. W. Payne, Dynamic storage allocations of arbitrary sized segments, In Proc. IFIPS, pagina's 344-348, 1974
• Garey, Worst-case of Memory Allocation Algorithms, 1972
• B. Cranston and R. Thomas, A simplified recombination scheme for the Fibonacci buddy system, Communications of the ACM, 18(6):331-332, Juli 1975
• J. L. Peterson and T. A. Norman, Buddy systems, Communications of the ACM, 20(6):421-431, Juni 1977
• J. M. Robson, Worst case fragmentation of first fit and best fit storage allocation strategies, Computer Journal, 20(3):242-244, Augustus 1977
• M. Tadman, Fast-fit: A new hierarchical dynamic storage allocation technique, Master’s thesis, UC Irvine, Computer Science Dept., 1978
• David S. Wise, The double buddy-system, Technical Report 79, Computer Science Department, Indiana University, Bloomington, Indiana, December 1978
• A. G. Bromley, Memory fragmentation in buddy methods for dynamic storage allocation, Acta Informatica, 14(2):107-117, Augustus 1980
• Ivor P. Page, Optimal fit of arbitrary sized segments, Computer Journal, 25(1), Januari 1982
• A. Gottlieb and J. Wilson, Parallelizing the usual buddy algorithm, Technical Report System Software Note 37, Courant Institute, New York University, 1982
• C. J. Stephenson, Fast fits: New methods for dynamic storage allocation, In Proceedings of the Ninth Symposium on Operating Systems Principles, pagina's 30-32, Bretton Woods, New Hampshire, Oktober 1983. ACM Press. Gepubliceerd als Operating Systems Review 17(5), Oktober 1983
• E. G. Coffman, Jr., T. T. Kadota, and L. A. Shepp, On the asymptotic optimality of first-fit storage allocation, IEEE Transactions on Software Engineering, SE-11(2):235-239, Februari 1985
• R. Brent, Efficient implementation of the first-fit strategy for dynamic storage allocation, ACM Transactions on Programming Languages and Systems, Juli 1989
• David R. Hanson, Fast allocation and deallocation of memory based on object lifetimes, Software Practice and Experience, 20(1), Januari 1990
• Dynamic Storage Allocation: A Survey and Critical Review (chronologisch overzicht van malloc()), 1995
• Johnstone, The Memory Fragmentation Problem: Solved?, 1997
• A Memory Allocator, 2000
• Solaris mtmalloc (archived), 2003
• Anatomy of a Program in Memory, 2009
• A History of malloc, 2010
• Heap and allocators, 2015
• Understanding glibc malloc
• The Origins of Malloc, 2017
• GrapheneOS hardened_malloc, 2019
• Risco-Martin, Simulation of High-Performance Memory Allocators, 2024