Memory Allocator Design — Ideas Behind jemalloc and mimalloc TODO
Concept
A general-purpose memory allocator has to handle arbitrary-sized requests quickly while keeping fragmentation under control, so it rounds sizes into a few dozen size classes and manages same-class blocks together using a segregated free list structure. jemalloc assigns each thread an arena and adds a thread-local cache called tcache, so most allocations and frees complete without taking a lock, and it pulls memory from the OS in large units (chunks or extents) that it then carves up. mimalloc gives each thread its own heap and each page its own free list, and it separates local frees from remote frees (frees issued by a different thread) into distinct lists — the free list sharding idea — to cut down on atomic operations. What the two designs share is thread-local caching to eliminate contention, using size classes to turn external fragmentation into internal fragmentation so it stays manageable, and treating the moment memory is returned to the OS (purge/decay) as a policy decision.
In multithreaded servers, when throughput fails to scale with core count the culprit is often allocator contention, and RSS staying far above actual usage is likewise explained by the allocator's fragmentation and memory-return policy.
Code & Formula
# 메모리 할당자 설계 — jemalloc/mimalloc 아이디어: size class segregated free list + 스레드 로컬 캐시(tcache).
# 요청 크기를 몇 개의 size class 로 반올림해 같은 클래스끼리 free list 로 묶으면, 할당/해제가 O(1) 에 가까워진다.
SIZE_CLASSES = [8, 16, 32, 64, 128, 256]
def size_class_for(n):
for c in SIZE_CLASSES:
if n <= c:
return c
raise ValueError("too large for this toy allocator")
class TinyAllocator:
def __init__(self):
# 클래스별 free list (한 번 반환된 블록은 재사용) — jemalloc 의 segregated free list 흉내.
self.free_lists = {c: [] for c in SIZE_CLASSES}
self.next_addr = 0
self.live = {} # addr -> size_class (누가 뭘 들고 있는지 추적)
def alloc(self, n):
c = size_class_for(n)
if self.free_lists[c]:
addr = self.free_lists[c].pop() # 스레드 로컬 캐시 hit 에 해당 — 락 없이 즉시 재사용
else:
addr = self.next_addr
self.next_addr += c # 새 청크는 size class 단위로만 늘어남(내부 단편화로 흡수)
self.live[addr] = c
return addr
def free(self, addr):
c = self.live.pop(addr)
self.free_lists[c].append(addr) # OS 에 즉시 반환하지 않고 재사용 대기열에 둔다(decay 정책 흉내)
alloc = TinyAllocator()
a = alloc.alloc(10) # 10 -> class 16
b = alloc.alloc(60) # 60 -> class 64
alloc.free(a)
c = alloc.alloc(15) # 같은 class 16 free list 를 즉시 재사용 → 새 청크를 늘리지 않음
print("a addr:", a, "class:", alloc.live.get(a))
print("b addr:", b, "class:", alloc.live[b])
print("c addr:", c, "reused a's slot:", c == a)
print("free list state:", {k: v for k, v in alloc.free_lists.items() if v or k in (16, 64)})
print("total bytes carved from OS:", alloc.next_addr)
docs/code/algorithms/algorithms-31.py
Exercise
Run the same multithreaded allocation benchmark while swapping in the default malloc versus jemalloc (or mimalloc) via LD_PRELOAD, and compare throughput and peak RSS.
Practical Connection
In services like a Go-based indexer or matching engine that create tens of thousands of small objects per second, the allocation pattern directly becomes GC pressure — the same principle explains why object reuse (sync.Pool) or pre-allocating slices pays off so much.
Where it lands in Jayverse
- Verex: profile allocator contention before assuming a logic bottleneck. If the CLOB matching engine's throughput doesn't scale with cores under load, check allocator contention first, the same signal the PoC's benchmark surfaces.
- Devnet: watch RSS on the hosted Anvil node as a fragmentation signal. RSS sitting far above actual chain-state size points to the allocator's purge/decay policy, not a leak, before digging further.
- gitboard: add peak RSS next to throughput and latency for any hot-path service. A throughput number alone hides what allocator behavior is doing to memory, so track both together.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| keep ~ under control | ~을 통제 가능한 상태로 유지하다 · 단편화를 관리 가능한 수준으로 억제한다는 뜻 · "keeping fragmentation under control" |
| pull ~ from | ~로부터 (자원을) 끌어오다 · OS로부터 큰 단위로 메모리를 받아옴 · "it pulls memory from the OS in large units" |
| carve up | (큰 덩어리를) 잘게 나누다 · 받아온 큰 메모리 청크를 잘라서 쓰는 것 · "chunks or extents) that it then carves up" |
| cut down on | ~을 줄이다 · 원자적 연산 횟수를 줄이기 위한 free list sharding · "to cut down on atomic operations" |
| fail to scale with | ~에 비례해 늘지 않다, ~만큼 확장되지 않다 · 코어 수를 늘려도 처리량이 안 느는 문제 · "throughput fails to scale with core count" |
| far above | ~보다 훨씬 위로, 크게 웃도는 · 실제 사용량보다 RSS가 과도하게 높은 상태 · "RSS staying far above actual usage" |
| treat ~ as | ~을 ~으로 취급하다, 간주하다 · 메모리 반납 시점을 정책적 결정으로 다룸 · "treating the moment memory is returned to the OS" |
| jemalloc | 제이말록(jemalloc) · 스레드별 아레나와 tcache를 쓰는 범용 메모리 할당자. "jemalloc assigns each thread an arena and adds a thread-local cache" |
| mimalloc | 미말록(mimalloc) · 스레드별 힙과 페이지별 프리리스트를 쓰는 메모리 할당자, free list sharding 기법의 예. "mimalloc gives each thread its own heap and each page its own free list" |
| RSS | 상주 집합 크기(Resident Set Size, RSS) · 프로세스가 실제 점유한 물리 메모리량, 할당자 정책과 괴리될 수 있음. "RSS staying far above actual usage" |
| LD_PRELOAD | LD_PRELOAD · 실행 전 공유 라이브러리를 끼워넣어 기본 malloc을 jemalloc 등으로 바꿔치기하는 리눅스 메커니즘. "swapping in the default malloc versus jemalloc (or mimalloc) via LD_PRELOAD" |
| tcache | 스레드 로컬 캐시(tcache) · jemalloc이 락 없이 할당·해제를 처리하도록 스레드마다 두는 캐시. "adds a thread-local cache called tcache" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.