Real-World Allocators

Different code, same skeleton. Every one of them uses: per-thread caching for a lock-free fast path, size classes with tight spacing, coalescing at some granularity, page/slab-level grouping for cache locality, and background reclaim that returns idle memory to the OS.

The specialized families

General-purpose malloc is the DEFAULT, not the optimum. When the allocation PATTERN is known, a specialized allocator wins by an order of magnitude:

• Bump: one pointer, no individual free. For truly one-shot lifetimes — parse, use, exit.
• Arena / region: bump-style chunks with an explicit group lifetime — allocate freely, then free EVERYTHING in one reset. Parsers, per-request server state, per-frame game scratch. Apache's pools and protobuf arenas are this pattern industrialized.
• Slab / object pool: fixed-size slots for ONE type. The Linux kernel allocates every dentry and inode from a slab cache; real-time systems use pools for their worst-case guarantees.
• Thread-cached malloc (tcmalloc-style): when the workload is general but heavily multi-threaded.

One correction to widespread folklore: alloca allocates on the STACK — automatic, gone on function return. The heap-based structure with stack discipline is the obstack. Arena allocators give you the same lifetime shape with explicit control.

Rule of thumb: profile first. If malloc is not hot, the default allocator is fine. If it is, match the LIFETIME pattern before reaching for a faster general-purpose malloc.

A classifier with priorities

Your exercise reads one scenario per line and prints one of bump | slab | arena | tcmalloc | default. The rules form a PRIORITY CASCADE — test top to bottom, first match wins:

1. "never free" / "one-shot" / "bump" -> bump
2. "kernel" / "dentry" / "inode" / "fixed-type" -> slab
3. thread-related / "web server" / "tcmalloc" -> tcmalloc
4. "per-frame" / "request handler" / "parser" -> arena
5. anything else -> default

Priority is the point. "One-shot config parser that never frees" matches rule 1 AND rule 4 ("parser") — the correct answer is bump, because lifetime beats workload shape: if nothing is ever freed individually, the cheapest allocator that can possibly work is a bump pointer, parser or not.

Your exercise

Two hidden tests catch the two real bugs. First, cascade order: One-shot config parser that never frees must print exactly bump — checking "parser" before "one-shot" prints arena and fails. Second, keyword spelling: Multithread JIT compiler must print exactly tcmalloc, but the word has NO hyphen — a literal substring check for "multi-thread" misses it and falls through to default. Match threads loosely: lowercasing the line and checking for the substring thread covers "Multithread", "multi-threaded", and "thread-per-request" in one stroke, and no scenario in the other buckets contains that substring.