jp_alloc

jp_alloc is a compact C11 allocator built around per-thread freelists, on-demand buddy splitting, and optional intermediate size classes. Its hot allocation and free paths use no locks or atomic operations.

It is optimized for workloads with short-lived, repeatedly reused objects, especially when allocation and deallocation happen on the same thread. It is not intended to match the fragmentation control of a mature general-purpose allocator on every workload.

Design

Per-thread pools

Each thread has one singly linked freelist per size class:

allocate: pop tls.freelist[pool]
free:     push tls.freelist[pool]

Both operations are plain thread-local pointer accesses. A block freed by a different thread moves to the freeing thread's pool. This keeps the hot path simple, but sustained cross-thread memory flow can strand reusable blocks in one thread while another thread maps new memory.

When a thread exits, its freelist pointers are dropped. The mapped regions remain owned by the process and are reclaimed by the operating system at process exit.

Size classes

The base classes are powers of two from 1 byte through 8 MiB. Restricted K=4 intermediate classes are enabled by default:

..., 64, 128, 160, 256, 320, 512, 640, 1024, 1280, 2048, 4096, 8192, ...

Power-of-two classes use binary buddy splitting. Intermediate classes use an asymmetric split:

1 * small + 3 * intermediate = power-of-two parent

For example:

4096 = 256 + 3 * 1280

Intermediate splits are limited to parents no larger than 4 KiB, so every asymmetric split remains within one page. Define JP_ALLOC_INTERMEDIATE_K=0 to use only power-of-two classes. K=6 is also available experimentally.

Pool selection is constant time: one count-leading-zeros operation, one intermediate threshold comparison where needed, and fixed index arithmetic.

Memory acquisition

An empty pool recursively splits a larger block. The largest class obtains a new 8 MiB anonymous mapping. Demand paging means untouched parts of that mapping do not consume physical memory.

There is no buddy coalescing. Once split, blocks remain in their current size classes.

Sized allocations

Normal malloc-style allocation reserves a hidden header containing the pool ID. When the size is known again at deallocation, the sized API exposes the complete raw block:

void *p = jp_alloc_sized(128);
jp_free_sized(p, 128);

Fixed-type users can avoid repeating numeric sizes:

static const struct jp_pool_config node_pool =
    JP_POOL_CONFIG(struct node);

struct node *node = jp_pool_alloc(&node_pool);
jp_pool_free(&node_pool, node);

Sized and unsized allocations share the same underlying freelists. Once a block is free, either API can reuse it. The allocation and deallocation APIs must not be mixed for a live pointer:

void *a = jp_alloc_sized(80);
jp_free(a);                    /* invalid */

void *b = jp_alloc(80);
jp_free_sized(b, 80);          /* invalid */

Release builds trust the size supplied to jp_free_sized. Debug builds store an address/next/pool-derived cookie while a block is free and validate it before following the freelist link. This detects corrupted free metadata, many writes after free, and immediate duplicate frees. The first wrong-size free cannot be detected without retaining metadata while the block is live.

Large-block page advice

Optional page advice applies only to complete payload pages of pooled blocks at least 64 KiB. The metadata page remains resident, and advice completes before the block is published on a freelist. This avoids races with reuse and preserves in-band freelist links.

Three modes are available:

JP_ALLOC_MADVISE_NONE
JP_ALLOC_MADVISE_DONTNEED
JP_ALLOC_MADVISE_FREE

No advice is the default. Calling madvise on every free adds enough syscall overhead to hurt the tested applications. MADV_DONTNEED also forces payload pages to fault back in on reuse. Linux MADV_FREE avoids repeated faults when memory is plentiful, but still pays one syscall per free and does not lower RSS until the kernel reclaims the lazy-free pages.

A future hot/cold freelist could apply MADV_FREE only to blocks that survive an aging generation, amortizing advice over cold blocks.

API

#include "jp_alloc.h"

void *jp_alloc(size_t size);
void  jp_free(void *ptr);
void *jp_calloc(size_t count, size_t size);
void *jp_realloc(void *ptr, size_t new_size);
void *jp_alloc_aligned(size_t alignment, size_t size);
size_t jp_good_size(size_t size);

void *jp_alloc_sized(size_t size);
void  jp_free_sized(void *ptr, size_t size);
void *jp_realloc_sized(void *ptr, size_t old_size, size_t new_size);

void *jp_pool_alloc(const struct jp_pool_config *pool);
void  jp_pool_free(const struct jp_pool_config *pool, void *ptr);

Linking jp_alloc.c also overrides the process malloc, free, calloc, and realloc symbols. jp_alloc_cpp.cpp provides C++ global new/delete overrides.

Build And Test

make                    # jp_alloc.so and debug jp_allocd.so
make test               # K=0, debug K=0, K=4, and MADV_FREE variants
make bench               # synthetic workload binaries
make madvise-bench       # NONE/DONTNEED/FREE focused binaries

Preload example:

LD_PRELOAD=./jp_alloc.so your_program

Focused advice examples:

./jp_madvise_none reuse 262144 512 30
./jp_madvise_dontneed idle 262144 512
./jp_madvise_free pressure 262144 512

Current Benchmarks

Measurements below were collected on an AMD Ryzen Threadripper PRO 7955WX (16 cores, 32 hardware threads), Linux 6.17, using -O2. Synthetic results are one 5-second timed run per allocator. Real-application results are medians of three runs unless noted.

Synthetic Balanced Workload

This repeatedly allocates and frees tup-shaped fixed-size objects. It strongly favors thread-local LIFO reuse.

Threads	Allocator	Throughput	Approx. p99	Peak RSS
1	jp_alloc	14.8 Mops/s	96 ns	2.6 MiB
1	tcmalloc	14.7 Mops/s	96 ns	8.4 MiB
1	jemalloc	11.8 Mops/s	96 ns	5.0 MiB
1	mimalloc	11.5 Mops/s	192 ns	2.9 MiB
1	glibc	8.7 Mops/s	192 ns	2.4 MiB
8	jp_alloc	112.1 Mops/s	96 ns	4.3 MiB
8	mimalloc	89.2 Mops/s	192 ns	6.4 MiB
8	jemalloc	87.6 Mops/s	192 ns	10.4 MiB
8	tcmalloc	68.7 Mops/s	192 ns	12.5 MiB
8	glibc	63.1 Mops/s	192 ns	3.4 MiB
300	jp_alloc	272.1 Mops/s	96 ns	77.8 MiB
300	mimalloc	242.8 Mops/s	192 ns	153.4 MiB
300	jemalloc	227.5 Mops/s	192 ns	215.0 MiB
300	glibc	145.4 Mops/s	192 ns	49.6 MiB
300	tcmalloc	38.8 Mops/s	98 us	162.5 MiB

Synthetic Alloc-Heavy Workload

This keeps 4096 objects outstanding per thread before draining them.

Threads	Allocator	Throughput	Approx. p99	Peak RSS
1	jp_alloc	34.9 Mops/s	24 ns	3.1 MiB
1	tcmalloc	34.2 Mops/s	24 ns	8.8 MiB
1	mimalloc	31.4 Mops/s	48 ns	3.4 MiB
1	jemalloc	22.9 Mops/s	48 ns	5.3 MiB
1	glibc	18.7 Mops/s	48 ns	2.8 MiB
8	jp_alloc	257.7 Mops/s	24 ns	8.3 MiB
8	mimalloc	231.7 Mops/s	48 ns	9.9 MiB
8	tcmalloc	202.7 Mops/s	96 ns	15.1 MiB
8	jemalloc	168.7 Mops/s	96 ns	13.2 MiB
8	glibc	136.5 Mops/s	96 ns	5.6 MiB
300	jp_alloc	803.1 Mops/s	48 ns	227.1 MiB
300	mimalloc	733.1 Mops/s	96 ns	279.4 MiB
300	jemalloc	502.8 Mops/s	96 ns	308.1 MiB
300	glibc	378.9 Mops/s	192 ns	152.1 MiB
300	tcmalloc	22.6 Mops/s	197 us	213.2 MiB

These results demonstrate the intended fast path, not universal allocator superiority. The benchmark has predictable same-thread reuse and does not model arbitrary object-size distributions or long-running fragmentation.

Real Applications

The same current K=4 allocator was compared through LD_PRELOAD:

Workload	jp_alloc	glibc	Best measured
GCC compiling SQLite	13.14s / 371MiB	12.59s / 362MiB	tcmalloc: 12.45s
ffmpeg 1080p transcode	1.30s / 2162MiB	1.25s / 2033MiB	jemalloc: 1.24s
OpenSCAD 8K spheres	0.36s / 149MiB	0.31s / 124MiB	jemalloc: 0.30s
Inkscape 10K paths	0.60s / 230MiB	0.54s / 184MiB	mimalloc: 0.52s
SQLite 2M rows	4.91s / 2764MiB	4.37s / 1733MiB	glibc
Blender 1000 spheres	42.49s / 24.2GiB	14.03s / 464MiB	mimalloc: 13.16s

The Blender result is pathological: Python-heavy 20-60-byte allocations are not helped by the current intermediate classes, and the lack of coalescing greatly amplifies retained memory. General-purpose allocators remain the right choice for heterogeneous applications.

Tup Integration

In the tup-jp integration, known fixed-size parser objects use the sized descriptor API. A clean parse of bes_devel with three variants measured:

Build	Time	Peak RSS
Unsized fixed objects	61.08s	497,080 KiB
Sized descriptors	60.90s	437,132 KiB

The sized API reduced peak RSS by about 60 MiB (12%) with no material runtime change in alternating runs.

Page Advice Comparison

At 256 KiB, 512 blocks, and 30 immediate-reuse cycles:

Mode	Time	Final RSS	LazyFree	Minor faults
NONE	0.049s	130MiB	0	32,771
MADV_FREE	0.139s	130MiB	126MiB	32,771
MADV_DONTNEED	1.530s	3.7MiB	0	968,195

Clean tup parse medians were 57.78s for NONE, 58.49s for MADV_DONTNEED, and 58.67s for MADV_FREE, with equivalent peak RSS. Consequently, no advice is the default.

Limitations

• No coalescing after blocks are split.
• No global or owner-directed return path for cross-thread frees.
• Exiting threads abandon their freelist reachability until process exit.
• Sparse classes below 128 bytes can waste substantial memory.
• Sized free trusts the caller-provided size in release builds.
• MADV_FREE is Linux-specific; unsupported platforms compile that mode as no advice.

Configuration

Flag	Default	Description
JP_ALLOC_DEBUG	off	Freelist cookie and double-free checks
JP_ALLOC_INTERMEDIATE_K	4	Intermediate classes; valid values are 0, 4, and 6
JP_ALLOC_MADVISE_SIZE	65536	Minimum pooled block size eligible for payload advice
JP_ALLOC_MADVISE_MODE	JP_ALLOC_MADVISE_NONE	NONE, DONTNEED, or Linux FREE
JP_ALLOC_STATS	off	Print per-pool statistics at exit
JP_CACHELINE	64	Alignment override for target platforms

Platform Notes

• Linux x86-64 is the primary tested platform.
• POSIX builds require pthreads and anonymous mmap.
• Windows uses VirtualAlloc; madvise modes are unavailable.
• The source includes GCC/Clang and MSVC compatibility fallbacks, but not all combinations are continuously tested.

License

GPL-3.0-or-later. See LICENSE.