custom-allocators

Custom allocators

Contract

Inputs

1. Target language and allocator type (required): C pool/arena, Rust GlobalAlloc, or tuning jemalloc/mimalloc/tcmalloc.
2. Workload pattern (required): allocation size distribution, object lifetime, thread count, and latency or throughput goal.
3. Observed symptom (optional): OOM, RSS growth, fragmentation, allocator contention, or unexpected latency.

Procedure

1. Classify the allocator type. Match the workload to one of the allocator types below. Done when: the type is named.

   Type	Best for	Allocation	Free
   Pool/fixed-size	Fixed-size objects with a known maximum count	Constant time	Constant time
   Slab	Size-class caching, kernel-style caches	Constant time	Constant time
   Arena/bump	Request-scoped or frame-scoped allocations	Fast pointer bump	Bulk reset
   Buddy	Power-of-two blocks, large allocations	Split and merge by power of two	Coalesce
   General	jemalloc, mimalloc, tcmalloc	Variable time	Variable time

2. Build or review a pool allocator. Use the C example below. Align backing memory to a cache line. Track the block size, block count, and a free list. Done when: the init, alloc, and free paths are shown.

   #include <stddef.h>
   #include <stdint.h>
   #include <stdlib.h>
   
   typedef struct pool_block {
       struct pool_block *next;
   } pool_block_t;
   
   typedef struct {
       void   *memory;
       size_t  block_size;
       size_t  num_blocks;
       pool_block_t *free_list;
   } pool_t;
   
   int pool_init(pool_t *p, size_t block_size, size_t num_blocks) {
       p->block_size = block_size < sizeof(pool_block_t)
           ? sizeof(pool_block_t) : block_size;
       p->num_blocks = num_blocks;
       p->memory = aligned_alloc(64, p->block_size * num_blocks);
       if (!p->memory) return -1;
       p->free_list = NULL;
       for (size_t i = 0; i < num_blocks; i++) {
           pool_block_t *blk = (pool_block_t *)((char *)p->memory
               + i * p->block_size);
           blk->next = p->free_list;
           p->free_list = blk;
       }
       return 0;
   }
   
   void *pool_alloc(pool_t *p) {
       if (!p->free_list) return NULL;
       pool_block_t *blk = p->free_list;
       p->free_list = blk->next;
       return blk;
   }
   
   void pool_free(pool_t *p, void *ptr) {
       pool_block_t *blk = (pool_block_t *)ptr;
       blk->next = p->free_list;
       p->free_list = blk;
   }