Jeremy W. Sherman

stay a while, and listen

Memory Allocation in sam

Bad news, bucko. Malloc is merely “adequate.” And it’s only adequate if you’re writing simple programs. Real programmers write their own memory manager. It’s the first thing they do after they ditch their shaving kit and start growing their Samson neckbeard.

Don’t believe me? Listen up:

The C language has no memory allocation primitives, although a standard library routine, malloc, provides adequate service for simple programs. For specific uses, however, it can be better to write a custom allocator.

Sam was just some text editor from the 80s, and its memory management was way more rocking than your Twitter client’s will ever be.

Sam memory management was so rocking that it filled two arenas. That’s right: two arenas. Your memory management needs are insignificant, puny, and plebeian, serviced adequately by the C standard library. Sam got true rockstar treatment: two arenas; two custom allocators; high maintenance, premium memory management.

The first arena holds staid structs of fixed length. It’s filled first-fit. Nothing magic there.

The second arena holds variably sized objects like strings. In an editor, strings are always changing, growing, splitting, combining. A regular bunch of problem children. So it’s managed by a garbage-compacting allocator.

These arenas are erected side-by-side in memory, with the second arena getting the higher addresses. When the first-fit arena needs more space, it just bumps the compacting arena up in memory.

The real magic is how these two arenas are used together. Take for example a variable-length array. Sam handles this by creating a struct with a length and a pointer. The struct is allocated in the struct arena of course, but its pointer points into the compacting arena. The allocator knew to go back and rewrite the struct pointer whenever it moved its memory during compaction, and the programmer knew (or learned really fast the hard way) to always use the struct’s pointer field directly each time rather than caching it away somewhere.

Now that’s some pretty boss hacking: elegant, but at what many today might consider an advanced, “don’t go there without a friend” low level.


P.S.: I would encourage you to check out sam’s source to see how it’s done, but yesterday’s arenas are no more. The current source just calls malloc once for each allocation.