返回题库

压缩内存分配器

Compacting Allocator

专题
Systems & Architecture / 系统与架构
难度
L4
来源
MyntBit

题目详情

长期运行的服务中，频繁的内存分配和释放会导致碎片化。压缩分配器通过定期移动已分配对象来消除碎片，类似于 JVM 的 GC 压缩阶段，但在 C++ 中需要额外的指针追踪机制。

任务：实现一个支持碎片整理（compact）的自定义内存分配器。

英文原题

High-frequency trading systems require deterministic, ultra-low latency memory management to avoid unpredictable latency spikes caused by memory fragmentation. A compacting allocator addresses this by maintaining objects in contiguous memory blocks and relocating them to eliminate gaps, ensuring optimal cache locality. This technique uses handle indirection so references remain valid after relocation, a critical pattern in performance-sensitive quantitative finance applications.
Task
Implement

解析

问题分析

长期运行的服务中，频繁分配和释放不同大小的对象会导致内存碎片化。压缩分配器通过定期移动已分配对象来消除碎片，类似于 JVM 的 GC 压缩阶段。但由于 C++ 对象可能被指针引用，需要额外机制追踪所有指针。

实现

class CompactingAllocator {
    struct Block { size_t size; bool free; size_t prev_size; };
    char* pool_; size_t capacity_; size_t used_ = 0;
public:
    CompactingAllocator(size_t cap) : pool_(new char[cap]), capacity_(cap) {}
    void* allocate(size_t size) {
        if (used_ + size + sizeof(Block) > capacity_) compact();
        auto* blk = reinterpret_cast<Block*>(pool_ + used_);
        blk->size = size; blk->free = false; blk->prev_size = 0;
        void* ptr = reinterpret_cast<char*>(blk) + sizeof(Block);
        used_ += sizeof(Block) + size;
        return ptr;
    }
    void compact() {
        size_t write_pos = 0;
        for (size_t pos = 0; pos < used_; ) {
            auto* blk = reinterpret_cast<Block*>(pool_ + pos);
            if (!blk->free) {
                if (pos != write_pos) std::memmove(pool_ + write_pos, blk, sizeof(Block) + blk->size);
                write_pos += sizeof(Block) + blk->size;
            }
            pos += sizeof(Block) + blk->size;
        }
        used_ = write_pos;
    }
};

复杂度与边界

  • 时间复杂度：allocate O(1)（不含 compact），compact O(已分配对象数)
  • 空间复杂度：O(capacity)
  • 边界条件：(1) 单个对象超过 capacity 时拒绝 (2) compact 后外部指针失效(需使用句柄) (3) 对齐要求需满足

英文解析

Analysis

In long-running services, frequent allocation and deallocation of varying-sized objects causes memory fragmentation. A compacting allocator periodically moves allocated objects to eliminate fragmentation, similar to JVM GC compaction. However, since C++ objects may be referenced by pointers, additional mechanisms are needed to track all pointers.

Solution

class CompactingAllocator {
    struct Block { size_t size; bool free; size_t prev_size; };
    char* pool_; size_t capacity_; size_t used_ = 0;
public:
    CompactingAllocator(size_t cap) : pool_(new char[cap]), capacity_(cap) {}
    void* allocate(size_t size) {
        if (used_ + size + sizeof(Block) > capacity_) compact();
        auto* blk = reinterpret_cast<Block*>(pool_ + used_);
        blk->size = size; blk->free = false; blk->prev_size = 0;
        void* ptr = reinterpret_cast<char*>(blk) + sizeof(Block);
        used_ += sizeof(Block) + size;
        return ptr;
    }
    void compact() {
        size_t write_pos = 0;
        for (size_t pos = 0; pos < used_; ) {
            auto* blk = reinterpret_cast<Block*>(pool_ + pos);
            if (!blk->free) {
                if (pos != write_pos) std::memmove(pool_ + write_pos, blk, sizeof(Block) + blk->size);
                write_pos += sizeof(Block) + blk->size;
            }
            pos += sizeof(Block) + blk->size;
        }
        used_ = write_pos;
    }
};

Complexity & Edge Cases

  • Time complexity: allocate O(1), compact O(used) — moves all live objects
  • Space complexity: O(capacity)
  • Edge cases: (1) All pointers to moved objects must be updated (2) Compaction pauses all allocations (3) Free blocks are reclaimed, reducing fragmentation

Key Considerations

  1. Compaction pause cost: Compaction scans all live objects and relocates them — pause duration scales with live object count, not total allocation count
  2. Pointer stability: Compaction invalidates all pointers to moved objects; must update references or use handle-based indirection
  3. Fragmentation threshold: Trigger compaction only when fragmentation exceeds configurable threshold (e.g., 30% wasted space) to avoid unnecessary pauses
  4. Thread safety: Compaction must run exclusively; all allocation/free operations block during compaction phase