THE FOLD / RESPAWN / GARBAGE COLLECTION / THE SLAB ALLOCATOR
THE SLAB ALLOCATOR
excellent at one question, useless at the rest
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A general allocator rounds your request up to something convenient for itself. A slab allocator refuses to: it dedicates whole pages to one object size, packs them end to end, and hands back a pointer with no header and no search.
LIT verified live. A 4,096-byte page holding 48-byte objects fits 85 of them and wastes 16 bytes — 0.39%. The same object under power-of-two rounding becomes a 64-byte slot and wastes 25% — sixty-four times as much, for the same object. Swept across all 505 sizes from 8 to 512 bytes: mean waste 2.98% for slabs against 24.65% for rounding, and the worst case is 10.94% against 49.8%, the latter at size 257 — one byte over a power of two.
LIT verified live. A 4,096-byte page holding 48-byte objects fits 85 of them and wastes 16 bytes — 0.39%. The same object under power-of-two rounding becomes a 64-byte slot and wastes 25% — sixty-four times as much, for the same object. Swept across all 505 sizes from 8 to 512 bytes: mean waste 2.98% for slabs against 24.65% for rounding, and the worst case is 10.94% against 49.8%, the latter at size 257 — one byte over a power of two.
2 HOW IT WAS WEAVED · AI + HUMAN
Jeff Bonwick introduced the slab allocator in SunOS 5.4 (1994); Linux’s SLUB is its descendant and the idea is now in every serious kernel.
AVAN (AI) swept the whole size range rather than picking a flattering example. The interesting structure is not the average — it is that the power-of-two curve is a sawtooth: waste collapses to zero exactly at 8, 16, 32, 64 and climbs to nearly half just past each one. An allocator that is excellent at 256 bytes and catastrophic at 257 is not "roughly 25% overhead"; it has a cliff, and the mean hides it.
AVAN (AI) swept the whole size range rather than picking a flattering example. The interesting structure is not the average — it is that the power-of-two curve is a sawtooth: waste collapses to zero exactly at 8, 16, 32, 64 and climbs to nearly half just past each one. An allocator that is excellent at 256 bytes and catastrophic at 257 is not "roughly 25% overhead"; it has a cliff, and the mean hides it.
3 ONE DIMENSION
Waste against object size. The sawtooth is the rounding.
4 TWO DIMENSIONS · INTERACTIVE
Pick an object size and fill a page with it.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a page packed to the edge.
AVAN’s addition (the inverse-companion): the forward reading is that slabs eliminate the waste. The inverse is that they eliminate it by refusing to be general. A slab is fast and tight because it already knows what it will be asked for; it has traded the ability to answer any question for excellence at one. Read backwards, the 24.65% that power-of-two rounding burns is not incompetence — it is the price of not knowing in advance, paid in memory instead of in time. Every allocator is a bet about the future, and the slab wins only where the future was announced.
LIT a 4,096-byte page of 48-byte objects fits 85 of them and wastes 16 bytes, 0.39%, while the same object under power-of-two rounding becomes a 64-byte slot and wastes 25% - sixty-four times as much; swept across all 505 sizes from 8 to 512 the mean waste is 2.98% for slabs against 24.65% for rounding, worst case 10.94% against 49.8%, the latter at size 257, one byte over a power of two
FIG Jeff Bonwick introduced the slab allocator in SunOS 5.4 (1994); Linux's SLUB is its descendant. AVAN swept the whole size range rather than picking a flattering example. The interesting structure is not the average but that the power-of-two curve is a sawtooth: waste collapses to zero exactly at 8, 16, 32, 64 and climbs to nearly half just past each one. An allocator excellent at 256 bytes and catastrophic at 257 does not have roughly 25% overhead; it has a cliff, and the mean hides it.
FIG Jeff Bonwick introduced the slab allocator in SunOS 5.4 (1994); Linux's SLUB is its descendant. AVAN swept the whole size range rather than picking a flattering example. The interesting structure is not the average but that the power-of-two curve is a sawtooth: waste collapses to zero exactly at 8, 16, 32, 64 and climbs to nearly half just past each one. An allocator excellent at 256 bytes and catastrophic at 257 does not have roughly 25% overhead; it has a cliff, and the mean hides it.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GARBAGE COLLECTION · David Lee Wise (ROOT0), with AVAN