返回题库

引用计数对象池

Reference Counted Pool

专题
General / 综合
难度
L3
来源
MyntBit

题目详情

高频交易系统常因关键路径上的频繁动态内存分配而遭受延迟毛刺。引用计数对象池通过重用对象来缓解此问题，有效消除 new 和 delete 的开销。通过强制执行已释放对象的 LIFO 排序，对象池保持高缓存局部性并减少缺页中断。

任务：设计一个线程安全的引用计数对象池。

英文原题

High-frequency trading systems often suffer from latency spikes due to frequent dynamic memory allocation during critical paths. A reference-counted object pool mitigates this by reusing objects, effectively eliminating new and delete overhead. By enforcing Last-In, First-Out (LIFO) reuse, the pool also maximizes cache locality for rapidly recycled trade objects.
Task
Build a generic ObjectPool<T> class in C++ that manages a pool of reusable objects. It should provide a std::shared_ptr<T> to an object from the pool.

解析

问题分析

频繁的对象创建和销毁在高频交易中会引入不可预测的延迟。引用计数对象池通过预分配对象并回收重用，消除了运行时分配开销。LIFO（后进先出）回收策略利用缓存热数据，提高访问效率。

解决方案

template<typename T>
class RefCountedPool {
    struct Slot { T obj; std::atomic<int> refs{0}; bool free{true}; };
    std::vector<Slot> slots_;
    std::stack<size_t> free_list_;
    mutable std::mutex mtx_;
public:
    explicit RefCountedPool(size_t cap) : slots_(cap) {
        for (size_t i = 0; i < cap; ++i) free_list_.push(i);
    }
    
    template<typename... Args>
    T* acquire(Args&&... args) {
        std::lock_guard lk(mtx_);
        if (free_list_.empty()) return nullptr;
        size_t idx = free_list_.top(); free_list_.pop();
        auto& slot = slots_[idx];
        new (&slot.obj) T(std::forward<Args>(args)...);
        slot.free = false; slot.refs = 1;
        return &slot.obj;
    }
    
    void incref(T* ptr) { slotOf(ptr)->refs++; }
    void decref(T* ptr) {
        auto* s = slotOf(ptr);
        if (--s->refs == 0) {
            s->obj.~T(); s->free = true;
            std::lock_guard lk(mtx_);
            free_list_.push(s - slots_.data());
        }
    }
};

关键考虑

  1. 无运行时分配：池在构造时一次性分配所有槽位，之后 acquire/release 仅为 O(1) 的栈操作。
  2. LIFO 回收：最近释放的对象最先被重用，其缓存行更可能仍在 CPU 缓存中。
  3. 线程安全：free_list 受互斥锁保护。引用计数使用 `std::atomic` 确保无竞争递增/递减。
  4. 边界条件：池满时 acquire 返回 nullptr；双重释放检测；use-after-free 防范。
  5. 时间复杂度：acquire/release 均为 O(1)；空间复杂度：O(capacity)。

英文解析

Analysis

Frequent object creation and destruction in high-frequency trading introduces unpredictable latency. A reference-counted object pool eliminates runtime allocation overhead by pre-allocating objects and recycling them. The LIFO (last-in-first-out) reclamation strategy leverages cache-warm data for improved access efficiency.

Solution

template<typename T>
class RefCountedPool {
    struct Slot { T obj; std::atomic<int> refs{0}; bool free{true}; };
    std::vector<Slot> slots_;
    std::stack<size_t> free_list_;
    mutable std::mutex mtx_;
public:
    explicit RefCountedPool(size_t cap) : slots_(cap) {
        for (size_t i = 0; i < cap; ++i) free_list_.push(i);
    }
    
    template<typename... Args>
    T* acquire(Args&&... args) {
        std::lock_guard lk(mtx_);
        if (free_list_.empty()) return nullptr;
        size_t idx = free_list_.top(); free_list_.pop();
        auto& slot = slots_[idx];
        new (&slot.obj) T(std::forward<Args>(args)...);
        slot.free = false; slot.refs = 1;
        return &slot.obj;
    }
    
    void incref(T* ptr) { slotOf(ptr)->refs++; }
    void decref(T* ptr) {
        auto* s = slotOf(ptr);
        if (--s->refs == 0) {
            s->obj.~T(); s->free = true;
            std::lock_guard lk(mtx_);
            free_list_.push(s - slots_.data());
        }
    }
};

Complexity & Edge Cases

  • Time complexity: O(1) for acquire/release with atomic counter; O(N) for bulk reset
  • Space complexity: O(PoolSize) for pre-allocated objects
  • Edge cases: (1) Reference count overflow on 32-bit counters. (2) Release when count is already 0 indicates double-free. (3) Pool exhaustion when all objects are acquired simultaneously.

Key Considerations

  1. No runtime allocation: The pool allocates all slots at construction; subsequent acquire/release are O(1) stack operations.
  2. LIFO reclamation: Recently released objects are reused first, as their cache lines are more likely still in CPU cache.
  3. Thread safety: free_list is protected by a mutex. Reference counts use `std::atomic` for race-free increment/decrement.
  4. Edge cases: Pool full → acquire returns nullptr; double-free detection; use-after-free prevention.
  5. Time complexity: acquire/release O(1); Space complexity: O(capacity).