自定义页分配器
Custom Page Allocator
题目详情
低延迟交易系统常绕过操作系统内核直接管理内存，减少 TLB 失效和避免非确定性页错误。常见技术是预分配 2MB "大页" 池并自定义分配器从池中分配，消除内核介入。
任务：实现 HugePageAllocator 类，预分配 2MB 大页池。allocate() 从池中返回对齐内存块，deallocate() 释放回池。支持配置池大小和对齐要求。
英文原题
Low-latency trading systems often bypass the operating system kernel to manage memory directly, reducing translation lookaside buffer (TLB) misses and avoiding non-deterministic page faults. A common technique is to pre-allocate a pool of 2MB "huge pages" and manage them in userspace using a buddy memory allocation algorithm. This ensures deterministic, microsecond-level latency for high-frequency trading applications.
Task
Implement a BuddyAllocator class that manages a contiguous virtual memo
解析
问题分析
mmap 可以绕过 glibc malloc，直接从内核获取页对齐的内存块。自定义页分配器对大对象（如订单簿快照缓存）更高效，避免 malloc 的元数据开销和碎片化。
实现
class PageAllocator {
public:
static void* alloc(size_t bytes) {
size_t pages = (bytes + 4095) / 4096;
void* p = ::mmap(nullptr, pages * 4096, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
if (p == MAP_FAILED) throw std::bad_alloc();
return p;
}
static void free(void* p, size_t bytes) {
::munmap(p, ((bytes + 4095) / 4096) * 4096);
}
};复杂度与边界
- 时间复杂度：alloc/free O(1) 系统调用
- 空间复杂度：O(请求大小按页对齐)
- 边界条件：(1) 频繁分配小对象浪费页空间 (2) munmap 后访问触发 SIGSEGV (3) 不适合频繁分配/释放的 < 4KB 对象
英文解析
Analysis
mmap can bypass glibc malloc, directly obtaining page-aligned memory blocks from the kernel. A custom page allocator is more efficient for large objects (such as order book snapshot caches), avoiding malloc metadata overhead and fragmentation.
Solution
class PageAllocator {
public:
static void* alloc(size_t bytes) {
size_t pages = (bytes + 4095) / 4096;
void* p = ::mmap(nullptr, pages * 4096, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
if (p == MAP_FAILED) throw std::bad_alloc();
return p;
}
static void free(void* p, size_t bytes) {
::munmap(p, ((bytes + 4095) / 4096) * 4096);
}
};Complexity & Edge Cases
- Time complexity: alloc/free O(1) system call
- Space complexity: O(requested size, page-aligned)
- Edge cases: (1) Frequent allocation of small objects wastes page space (2) Access after munmap triggers SIGSEGV (3) Not suitable for frequent alloc/free of objects smaller than 4KB
Verification
Allocate and free large blocks, verify no fragmentation. Benchmark allocation speed against malloc for >4KB objects. Confirm munmap properly releases pages.
Key Considerations
Page-level allocation eliminates malloc fragmentation for large, long-lived objects. In order book systems, snapshot caches are allocated once and reused throughout the session - page allocator provides zero-fragmentation guarantees and direct kernel memory mapping.