无额外堆分配拆分大向量及优化std::vector堆分配方案问询

Great question! This is a smart optimization to leverage contiguous memory for better cache performance, and I’ll walk you through exactly how to implement it with std::vector—replacing three separate heap allocations with one shared block, no extra overhead, and fixed-size safety.

Core Idea #

Instead of letting each std::vector allocate its own separate heap block, we’ll pre-allocate a single contiguous chunk of size 3*n, then make each vector point to a distinct n-sized segment of this block. The key is ensuring the vectors don’t try to free the shared memory on their own, and that they respect the fixed size constraint.

Implementation Options #

Option 1: Custom Allocator (C++11+) #

This gives you full control over memory management and works across most C++ versions. We’ll create a minimal allocator that returns pre-defined segments of the shared block and skips deallocation (since we’ll manage the block’s lifecycle externally).

First, define the custom allocator:

template <typename T>
struct SharedBlockAllocator {
    T* base_ptr;
    size_t offset;

    using value_type = T;

    // Constructor: point to the shared block and our segment's offset
    SharedBlockAllocator(T* ptr, size_t off) noexcept : base_ptr(ptr), offset(off) {}

    // Conversion constructor for other types (required by vector)
    template <typename U>
    SharedBlockAllocator(const SharedBlockAllocator<U>& other) noexcept 
        : base_ptr(reinterpret_cast<T*>(other.base_ptr)), offset(other.offset) {}

    // Allocate: return our pre-assigned segment (no new heap allocation)
    T* allocate(size_t n) {
        // Since our vectors are fixed-size, n will always match our segment size
        return base_ptr + offset;
    }

    // Deallocate: do nothing—we'll free the shared block externally
    void deallocate(T*, size_t) noexcept {}
};

// Equality checks required for allocator compatibility
template <typename T, typename U>
bool operator==(const SharedBlockAllocator<T>& a, const SharedBlockAllocator<U>& b) noexcept {
    return a.base_ptr == b.base_ptr && a.offset == b.offset;
}

template <typename T, typename U>
bool operator!=(const SharedBlockAllocator<T>& a, const SharedBlockAllocator<U>& b) noexcept {
    return !(a == b);
}

Now use it to create your shared vectors:

#include <vector>
#include <memory>
#include <cassert>

int main() {
    const size_t n = 1000;
    using ElementType = int;

    // Allocate the single shared block (managed by unique_ptr for automatic cleanup)
    auto shared_buffer = std::unique_ptr<ElementType[]>(new ElementType[3 * n]);

    // Create each vector with its own segment of the shared block
    std::vector<ElementType, SharedBlockAllocator<ElementType>> vec1(
        std::allocator_arg,
        SharedBlockAllocator<ElementType>(shared_buffer.get(), 0),
        n
    );
    std::vector<ElementType, SharedBlockAllocator<ElementType>> vec2(
        std::allocator_arg,
        SharedBlockAllocator<ElementType>(shared_buffer.get(), n),
        n
    );
    std::vector<ElementType, SharedBlockAllocator<ElementType>> vec3(
        std::allocator_arg,
        SharedBlockAllocator<ElementType>(shared_buffer.get(), 2 * n),
        n
    );

    // Verify memory continuity (optional, but confirms our setup works)
    assert(&vec1.back() + 1 == &vec2.front());
    assert(&vec2.back() + 1 == &vec3.front());

    // Use the vectors like normal—no extra allocations!
    for (size_t i = 0; i < n; ++i) {
        vec1[i] = i;
        vec2[i] = i * 2;
        vec3[i] = i * 3;
    }

    return 0;
}

Option 2: Polymorphic Memory Resources (C++17+) #

If you’re using C++17 or later, the standard library’s std::pmr utilities make this even cleaner. We’ll use monotonic_buffer_resource to feed our vectors from a single pre-allocated block.

#include <vector>
#include <memory_resource>
#include <cassert>

int main() {
    const size_t n = 1000;
    using ElementType = int;

    // Pre-allocate the shared contiguous block
    std::vector<ElementType> buffer(3 * n);
    // Wrap the buffer in a monotonic memory resource
    std::pmr::monotonic_buffer_resource mbr(buffer.data(), buffer.size() * sizeof(ElementType));

    // Create vectors that use this shared memory resource
    std::pmr::vector<ElementType> vec1(&mbr);
    std::pmr::vector<ElementType> vec2(&mbr);
    std::pmr::vector<ElementType> vec3(&mbr);

    // Resize to fixed size—this will allocate contiguous segments in the shared block
    vec1.resize(n);
    vec2.resize(n);
    vec3.resize(n);

    // Verify continuity
    assert(&vec1.back() + 1 == &vec2.front());
    assert(&vec2.back() + 1 == &vec3.front());

    // Use the vectors as normal
    for (size_t i = 0; i < n; ++i) {
        vec1[i] = i;
        vec2[i] = i * 2;
        vec3[i] = i * 3;
    }

    return 0;
}

Key Notes for Safety #

• Fixed Size Only: Never call push_back(), insert(), or resize() to increase the size of these vectors—this will trigger reallocation, which breaks the shared memory setup (and may cause undefined behavior).
• Memory Lifecycle: Ensure the shared buffer outlives all the vectors using it. In both examples, the buffer is created before the vectors and destroyed after them, which is safe.
• No Double Free: The custom allocator’s deallocate does nothing, and monotonic_buffer_resource doesn’t free the input buffer—so the shared block is only freed once when its owner (the unique_ptr or std::vector buffer) is destroyed.

Why This Boosts Performance #

Your 2X speedup comes down to CPU cache efficiency:

• Three separate heap allocations are likely to be scattered across memory (due to fragmentation), leading to frequent cache misses when accessing elements across vectors.
• A single contiguous block fits better into CPU caches. When you access elements from one vector, the adjacent elements of the next vector are already loaded into cache, reducing the time waiting for memory reads.

内容的提问来源于stack exchange，提问作者Alireza Majidi