Use jemalloc or tcmalloc as Drop-in Replacement and Measure

Topic Overview

Alternative Allocators in Production

Facebook's jemalloc and Google's tcmalloc partition thread caches and size classes to cut lock contention and improve locality. Firefox, Redis, and FreeBSD default to jemalloc for server workloads. Swapping allocators is often a one-line LD_PRELOAD experiment.

When Replacements Help

Many small allocations across threads: tcmalloc shines. Fragmentation-heavy long-running daemons: jemalloc's arena tuning helps. Always measure your allocation profile.

bashCopy
Loading…

• Not a substitute for fixing allocation churn in hot loops
• Profile with malloc_stats or jemalloc prof before trusting preload
• Windows uses different entry points; this task focuses on Linux/macOS
• Container images must ship the chosen .so

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will compare default malloc versus jemalloc or tcmalloc on a provided allocation-heavy benchmark. This exercise requires reporting throughput and explaining which size class behavior mattered.

Your Task

Why is jemalloc or tcmalloc often faster than a basic malloc in multi-threaded programs? Two reasons you can count. First, thread caches: most allocations are served from a per-thread stash with no lock at all, and the shared arena is locked only to refill or flush the stash in batches. Second, size classes: requests are rounded up to a small set of sizes, which trades some internal fragmentation for speed and reuse. Model both allocators on the same trace and compare lock traffic and wasted bytes.

Input

cCopy
Loading…

Rules

• Single-lock malloc: every malloc and free takes the one global lock. A handoff is a lock acquisition by a different thread from the previous acquirer.
• Size classes: 8 16 32 48 64 80 96 112 128 160 192 224 256 320 384 448 512 640 768 896 1024 1280 1536 1792 2048 2560 3072 3584. Larger requests are large: rounded up to a multiple of 4096, and they always take the arena lock (malloc and free).
• Thread cache (per thread, per class):
  • malloc: if the thread's cache holds an object, it is a hit. Otherwise lock the arena and refill N/2 objects (one goes to the caller, N/2 − 1 stay cached).
  • free: the object goes into the freeing thread's cache. If that cache already holds N objects, lock the arena and flush N/2 first (the cache ends with N − N/2 + 1).
• Errors: THREAD malloc ID: rejected (size < 1 or duplicate live id), THREAD free ID: invalid free, and tcache: 2..64.

Output

cCopy
Loading…

Fragmentation = (reserved − requested) / reserved, rounded half up to 1 decimal. Threads are listed in order of first appearance.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Map a size to the smallest class that fits, with one lookup over the class table.
2. Count lock acquisitions exactly where each design takes the lock. The comparison comes down to how often the lock is needed, not how long it is held.

Hidden tests cover a cache that overflows and flushes, frees by a different thread than the allocator (the object lands in the freer's cache), several size classes, a small tcache of 2, large allocations, and invalid frees.