返回题库

placement new 缓冲区管理

Placement New Buffer

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

题目详情

Placement new 允许在预分配的内存上构造对象，避免额外的堆分配。在量化交易中，可以将相关对象紧密放置在连续缓冲区中，极大提升 CPU 缓存局部性。

任务：实现一个基于 placement new 的固定容量对象缓冲区。

英文原题

In high-frequency trading systems, dynamically allocating memory on the heap can introduce unpredictable latency spikes that degrade execution speed. To ensure deterministic performance, quantitative developers often pre-allocate a continuous block of memory at startup and manually construct objects within this buffer using placement new.
Task
Implement a TradeBuffer class that manages a pre-allocated byte buffer capable of holding up to 100 Trade objects. You must implement the following metho

解析

问题分析

Placement new 允许在已分配的内存上构造对象，避免额外的堆分配。在量化交易中，可以将相关对象（如订单、成交记录）紧密放置在连续缓冲区中，提升缓存局部性。必须手动管理构造和析构的顺序。

实现

template<typename T, size_t Capacity>
class PlacementBuffer {
    alignas(T) char buffer_[Capacity * sizeof(T)];
    bool occupied_[Capacity]{};
public:
    template<typename... Args>
    T* create(size_t index, Args&&... args) {
        if (index >= Capacity || occupied_[index]) return nullptr;
        T* ptr = new (buffer_ + index * sizeof(T)) T(std::forward<Args>(args)...);
        occupied_[index] = true;
        return ptr;
    }
    void destroy(size_t index) {
        if (index < Capacity && occupied_[index]) {
            reinterpret_cast<T*>(buffer_ + index * sizeof(T))->~T();
            occupied_[index] = false;
        }
    }
    T* get(size_t index) {
        return (index < Capacity && occupied_[index]) 
            ? reinterpret_cast<T*>(buffer_ + index * sizeof(T)) : nullptr;
    }
};

复杂度与边界

  • 时间复杂度：所有操作 O(1)
  • 空间复杂度：O(Capacity * sizeof(T))
  • 边界条件：(1) 重复构造同一槽位返回 nullptr (2) 析构未构造槽位无操作 (3) 对齐要求通过 alignas 满足 (4) 适用于平凡和非平凡析构类型

英文解析

Analysis

Placement new allows constructing objects in pre-allocated memory, avoiding additional heap allocation. In quantitative trading, related objects (orders, trade records) can be tightly placed in contiguous buffers for improved cache locality. Construction and destruction order must be managed manually.

Solution

template<typename T, size_t Capacity>
class PlacementBuffer {
    alignas(T) char buffer_[Capacity * sizeof(T)];
    bool occupied_[Capacity]{};
public:
    template<typename... Args>
    T* create(size_t index, Args&&... args) {
        if (index >= Capacity || occupied_[index]) return nullptr;
        T* ptr = new (buffer_ + index * sizeof(T)) T(std::forward<Args>(args)...);
        occupied_[index] = true;
        return ptr;
    }
    void destroy(size_t index) {
        if (index < Capacity && occupied_[index]) {
            reinterpret_cast<T*>(buffer_ + index * sizeof(T))->~T();
            occupied_[index] = false;
        }
    }
    T* get(size_t index) {
        return (index < Capacity && occupied_[index]) 
            ? reinterpret_cast<T*>(buffer_ + index * sizeof(T)) : nullptr;
    }
};

Complexity & Edge Cases

  • Time complexity: All operations O(1)
  • Space complexity: O(Capacity * sizeof(T))
  • Edge cases: (1) Duplicate construction at same slot returns nullptr (2) Destroying unconstructed slot is no-op (3) Alignment requirements satisfied via alignas (4) Works for both trivial and non-trivial destructible types

Key Considerations

  1. Alignment requirements: Placement new does not guarantee alignment beyond what the buffer provides; use alignas or std::aligned_storage for type-specific alignment
  2. Lifetime management: Objects constructed via placement new must be explicitly destroyed via destructor call before buffer reuse — no automatic RAII
  3. Buffer ownership: The underlying buffer and the placed object have independent lifetimes; destroying the buffer without destroying placed objects causes undefined behavior
  4. Debug instrumentation: In production, track allocation offsets within buffer to detect overlap, leaks, and double-destroy bugs