如果构建和销毁了许多 vector<T> ，自定义分配器是否会提高性能？

Question

在下面的代码中，许多每 10 个整数的向量有 60% 的几率被构建，或者现有的向量有 40% 的几率被删除。因此，将有许多调用 new/malloc 和删除。由于所有这些向量都是 vector<int> 类型，自定义分配器是否可以帮助减少对 new 和 delete 的调用，从而提高性能？这个想法是删除向量的 space 可以被新构造的向量重用。这样的分配器会是什么样子？

注意：这个问题是关于分配器的，它减少了对 new 和 delete 的调用。

#include <iostream>
#include <vector>
#include <random>

using namespace std;

int main() 
{
    // Random generator and distribution
    mt19937 gen(123456);
    uniform_real_distribution<> dis01(0., 1.);

    // Make or delete 10E6 vectors.
    vector< vector<int> > v; //the inner vectors will make many calls to new and delete

    v.reserve(10E5); //assume some size.

    for(int i=0; i<10E6; ++i)
    {
        if(dis01(gen)<0.6) // if true: make new sub-vector
        {
            v.emplace_back(); //new sub-vector
            v.back().reserve(10);

            for(int k=0; k<10; ++k)
                v.back().emplace_back(k); //fill it with some numbers
        }
        else // else, delete the last entry if there is one.
            if(!v.empty())
                v.pop_back();
    }

    cout<<"v.size()= "<<v.size();       
    return 0;
}

Answer 1

自定义分配器可能会解决一些问题，但这不是灵丹妙药。该示例不足以了解最佳解决方案。我要提出一些不同的建议，不是因为它更好，而是因为它在某些情况下可能会更好。

v.resize(10E5, std::vector<int>(10));

而不是

v.reserve(10E5);

但是你需要一个迭代器来处理向量上的下一个空闲槽以及所有这些好东西。

Answer 2

您是否尝试过现有的提升池分配器？

http://theboostcpplibraries.com/boost.pool

我想，如果说到复用'std::vector's object itself'的内存，应该和inplacement有点关系creation/pools.

Answer 3

您可以通过编写分配器更有效地重用最近释放的内存来获得一些性能，特别是如果所有向量的大小都为 10。当然，如果是这种情况，您将获得更多通过使用固定大小的对象来提高性能。如果向量的分配大小需要是动态的，那么你的问题就像一般的内存分配一样抽象，你不太可能改进标准分配器。

与 STL 相比，您根本不可能提高性能，除非您能够利用适用于您的特定情况而非更一般情况的信息。

一个更好的解决方案是不删除向量对象，而是将它们留在向量中>，维护一个 iterator/pointer 到向量的 "end" （递减而不是删除），然后不是放置一个元素（构造一个向量），而是推进你的迭代器，测试 .end()，然后在需要时放置，否则重用旧向量。这假设您的程序不依赖构造函数或析构函数的副作用（vector 不依赖，但您没有告诉我们您的实际用例）。

Answer 4

据我了解 https://en.wikipedia.org/wiki/Allocator_(C%2B%2B)，C++ 分配器减少了对特定容器的分配和释放请求。我假设这意味着创建和删除容器仍然需要调用 new 和 delete。

您可能想看看 https://github.com/gperftools/gperftools。它是 malloc 的替代品。它声称改进了小对象分配，尤其是在多线程程序中。

Answer 5

这是针对 C++11 的。旧标准需要额外的东西在分配器 [1] 中实现。

这是概念验证代码。它运行并解决了这个例子问题，但受到一些限制。它仍然演示了如何使用自定义分配器来改进在有很多 std::vector 的情况下的性能创建和销毁。

PoolAlloc.hh:

template<typename T>
struct MemChunk
{
    std::size_t buf_size=0;
    T* buf=nullptr;
    T* top=nullptr;
    std::size_t used=0;
};

template<typename T>
class PoolAllocator
{
    public:
    using value_type=T;

    PoolAllocator();
    explicit PoolAllocator(std::size_t);
    PoolAllocator(PoolAllocator const&) noexcept;
    template<typename U>
        PoolAllocator(PoolAllocator<U> const&) noexcept;
    PoolAllocator(PoolAllocator&&) noexcept;
    PoolAllocator& operator=(PoolAllocator const&)=delete;
    PoolAllocator& operator=(PoolAllocator&&)=delete;
    ~PoolAllocator();

    template <typename U> 
    struct rebind 
    {
        using other=PoolAllocator<U>;
    };

    T* allocate(std::size_t);
    void deallocate(T*, std::size_t) noexcept;

    template<typename U1, typename U2>
        friend bool operator==(PoolAllocator<U1> const&, PoolAllocator<U2> const&) noexcept;

    private:
    std::vector<MemChunk<T>>* memory_=nullptr;
    int* ref_count_=nullptr;
    std::size_t default_buf_size_=0;
};

template<typename T>
PoolAllocator<T>::PoolAllocator():
    PoolAllocator{100000} {}

template<typename T>
PoolAllocator<T>::PoolAllocator(std::size_t buf_size):
    memory_{new std::vector<MemChunk<T>>},
    ref_count_{new int(0)},
    default_buf_size_{buf_size}
{
    memory_->emplace_back();
    memory_->back().buf_size=buf_size;
    memory_->back().buf=new T[buf_size];
    memory_->back().top=memory_->back().buf;
    ++(*ref_count_);
}

template<typename T>
PoolAllocator<T>::PoolAllocator(PoolAllocator const& src) noexcept:
    memory_{src.memory_},
    ref_count_{src.ref_count_},
    default_buf_size_{src.default_buf_size_}
{
    ++(*ref_count_);
}

template<typename T>
PoolAllocator<T>::PoolAllocator(PoolAllocator&& src) noexcept:
    memory_{src.memory_},
    ref_count_{src.ref_count_},
    default_buf_size_{src.default_buf_size_}
{
    src.memory_=nullptr;
    src.ref_count_=nullptr;
}

template<typename T>
template<typename U>
PoolAllocator<T>::PoolAllocator(PoolAllocator<U> const& src) noexcept:
    memory_{src.memory_},
    ref_count_{src.ref_count_},
    default_buf_size_{src.default_buf_size_}
{
    ++(*ref_count_);
}

template<typename T>
PoolAllocator<T>::~PoolAllocator()
{
    if (ref_count_!=nullptr)
    {
        --(*ref_count_);
        if (*ref_count_==0)
        {
            if (memory_!=nullptr)
            {
                for (auto& it : *memory_)
                {
                    delete[] it.buf;
                }
                delete memory_;
            }
            delete ref_count_;
        }
    }
}

template<typename T>
T* 
PoolAllocator<T>::allocate(std::size_t n)
{
    MemChunk<T>* mem_chunk=&memory_->back();
    if ((mem_chunk->used+n)>mem_chunk->buf_size)
    {
        default_buf_size_*=2;
        memory_->emplace_back();
        mem_chunk=&memory_->back();
        std::size_t buf_size=default_buf_size_;
        if (n>default_buf_size_)
        {
            buf_size=n;
        }
        mem_chunk->buf_size=buf_size;
        mem_chunk->buf=new T[mem_chunk->buf_size];
        mem_chunk->top=mem_chunk->buf;
    }
    T* r=mem_chunk->top;
    mem_chunk->top+=n;
    mem_chunk->used+=n;
    return r;
}

template<typename T>
void 
PoolAllocator<T>::deallocate(T* addr, std::size_t n) noexcept
{
    MemChunk<T>* mem_chunk=&memory_->back();
    if (mem_chunk->used>n and (mem_chunk->top-n)==addr)
    {
        mem_chunk->used-=n;
        mem_chunk->top-=n;
    }
}

template<typename U1, typename U2>
bool operator==(PoolAllocator<U1> const& lhs, PoolAllocator<U2> const& rhs) noexcept
{
    return (std::is_same<U1, U2>::value and lhs.memory_==rhs.memory_);
}

使用您的示例按以下方式修改：

#include <iostream>
#include <vector>
#include <random>   
#include "PoolAlloc.hh"

using namespace std;

int main() 
{
    // Random generator and distribution
    mt19937 gen(123456);
    uniform_real_distribution<> dis01(0., 1.);
    PoolAllocator<int> palloc{1000000};

    // Make or delete 10E6 vectors.
    vector< vector<int, PoolAllocator<int>> > v; //the inner vectors will make many calls to new and delete

    v.reserve(10E5); //assume some size.

    for(int i=0; i<10E6; ++i)
    {
        if(dis01(gen)<0.6) // if true: make new sub-vector
        {
            v.emplace_back(palloc); //new sub-vector
            v.back().reserve(10);

            for(int k=0; k<10; ++k)
                v.back().emplace_back(k); //fill it with some numbers
        }
        else // else, delete the last entry if there is one.
            if(!v.empty())
                v.pop_back();
    }

    cout<<"v.size()= "<<v.size();   
    return 0;
}

malloc 的调用次数从 ~6e6 下降到 21。总计指令数从 3.7e9 下降到 2.5e9（使用 -O3，用 valgrind --tool=callgrind) 测量。

有几个实施细节会影响不同使用情况下的表现。

目前使用了多个缓冲区。如果一个满了，另一个被建造。这样就永远不必重新分配会让你陷入痛苦世界的操作（见评论）。

最大的问题是，如何处理释放的内存。目前使用了一种简单的方法，它只使释放当它在结束时可用于以后分配的内存缓冲。对于你的例子就足够了，因为你只在缓冲区末尾释放内存。

对于更复杂的场景，您将需要更复杂的机制。需要一些数据结构来存储地址和可用内存块的大小。多个概念是可能的这里和他们的表现会随着具体情况而变化它们用于。我怀疑是否有一个很好的一刀切解决方案在这里。

[1] http://howardhinnant.github.io/stack_alloc.html

Answer 6

在我看来，自定义分配器实际上仅在您确切知道内存将如何使用时才提供优于标准分配器的优势。通常，您正在做出 size/perf 权衡，自定义分配器允许您控制此决定。

如果在你的例子中你可以为每个列表使用页面大小块，那么你可以只保留一个免费的页面列表并在所有未来的分配中分发它们。如果每个列表中实际上只有 10 个整数，这将产生大量内存开销，但如果列表更大并且可以在不调用每个 int 的 new 或 delete 的情况下完成，这可能是一个巨大的胜利。这实质上是为每个列表创建一个固定大小的内存池。完成列表后，您只需将页面放回空闲列表并将其用于下一个列表。

如果构建和销毁了许多 vector<T> ，自定义分配器是否会提高性能？

Will a custom allocator improve performance if many vector<T> s get constructed and destroyed?

c++

performance

vector

allocator