自定义 STL std::allocator 替换可提高性能

• 下载 stl_allocator.zip - 20.6 KB

介绍

这是我在代码项目上关于固定块内存分配器的第三篇也是最后一篇文章。这次，我们将std::allocator使用前两篇文章奠定的基础来创建一个替代的 C++ 标准库内存管理器。 

标准模板库 (STL) 是功能强大的 C++ 软件库，包括容器和迭代器支持。使用该库进行任务关键型或时间关键型项目的问题不在于 STL 本身 - 该库非常强大。相反，它是不受限制地使用全局堆。标准STL分配器在操作过程中大量使用堆。这是资源受限的嵌入式系统上的一个问题。嵌入式设备预计可以运行数月或数年，其中必须防止碎片堆引起的故障。幸运的是，STL提供了一种手段来替换std::allocator我们自己的设计。 

固定块内存分配器是提供类似动态操作的常用技术，但内存是从内存池提供的，其中分配的块具有固定大小。与预期可在任何大小的块上普遍操作的全局堆不同，固定块分配器可以针对狭窄定义的目的进行定制。固定块分配器还可以提供一致的执行时间，而全局堆无法提供此类保证。 

本文介绍了一个与 STL 兼容的分配器实现，它依赖于固定块分配器来分配和回收内存。新的分配器可以防止碎片堆引起的错误，并提供一致的分配/释放执行时间。 

std::分配器

STLstd::allocator类提供了默认的内存分配和释放策略。如果您检查容器类（例如 ）的代码，std::list您将看到默认std::allocator模板参数。在本例中，allocator<_Ty>模板类处理_Ty对象的分配职责。

template<class _Ty, class _Ax = allocator<_Ty> >
class list : public _List_val<_Ty, _Ax>
{
    // ...
}

由于模板参数_Ax默认为allocator<_Ty>，因此您可以创建列表对象，而无需手动指定分配器。myList 如下所示的声明创建一个用于分配/解除分配int 值的分配器类。 

std::list<int> myList;

STL 容器依赖于元素和节点的动态内存。元素是插入对象的大小。在本例中，sizeof(int)是存储一个列表元素所需的内存。节点是将元素绑定在一起所需的内部结构。对于std::list，它是一个双向链表，至少存储指向下一个和上一个节点的指针。 

当然，元素大小根据存储的对象而变化。但是，节点大小也会根据所使用的容器而变化。节点std::list的大小可以与std::map节点的大小不同。因此，STL 分配器必须能够处理不同大小的内存块请求。 

STL 分配器必须遵守特定的接口要求。这不是一篇关于 API 的使用方式和原因的文章std::allocator– 有许多在线参考资料比我更好地解释了这一点。相反，我将重点讨论在现有 STL 分配器类中的何处放置内存分配/释放调用接口并提供所有常见容器的新“x”版本以简化使用。 

x分配器    

新的固定块 STL 分配器的大部分繁重工作都来自底层，如我的文章“用快速固定块内存分配器替换 malloc/freexallocator ”中所述。正如标题所述，该模块用新的固定块/版本替换/ 。 mallocfree xmallocxfree

对于用户来说，除了固定块功能之外，这些替换功能的操作方式与标准 CRT 版本相同。简而言之，xallocator有两种操作模式：静态池，其中所有内存都从预先声明的静态内存中获取，或堆块，其中块从全局堆中获取，但在释放时回收以供以后使用。有关实现细节，请参阅上述文章。 

stl_分配器

该类stl_allocator 是固定块 STL 兼容实现。此类用作 的替代品std::allocator。 

template <typename T>
class stl_allocator
{
public:
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;

    stl_allocator(){}
    ~stl_allocator(){}

    template <class U> struct rebind { typedef stl_allocator<U> other; };
    template <class U> stl_allocator(const stl_allocator<U>&){}

    pointer address(reference x) const {return &x;}
    const_pointer address(const_reference x) const {return &x;}
    size_type max_size() const throw() {return size_t(-1) / sizeof(value_type);}

    pointer allocate(size_type n, stl_allocator<void>::const_pointer hint = 0)
    {
        return static_cast<pointer>(xmalloc(n*sizeof(T)));
    }

    void deallocate(pointer p, size_type n)
    {
        xfree(p);
    }

    void construct(pointer p, const T& val)
    {
        new(static_cast<void*>(p)) T(val);
    }

    void construct(pointer p)
    {
        new(static_cast<void*>(p)) T();
    }

    void destroy(pointer p)
    {
        p->~T();
    }
};

代码实际上只是一个标准std::allocator接口。网上有很多例子。本文所附的源代码已在许多不同的编译器（GCC、Keil、VisualStudio）上使用。我们感兴趣的是从哪里进入我们自己的内存管理器的界面。感兴趣的方法是：

• allocate()
• deallocate()

allocate()分配n对象类型的实例数T。xmalloc()用于从固定块内存池而不是全局堆获取内存。

pointer allocate(size_type n, stl_allocator<void>::const_pointer hint = 0)
{
    return static_cast<pointer>(xmalloc(n*sizeof(T)));
}

deallocate()释放之前使用 分配的内存块allocate()。一个简单的调用将xfree()请求路由到我们的内存管理器。 

void deallocate(pointer p, size_type n)
{
    xfree(p);
}

事实上，一旦你有了一个固定的块内存管理器，这就是全部了。xallocator旨在处理任何大小的内存请求。因此，无论 C++ 标准库、元素或节点要求的存储大小，xmalloc/xfree都会处理内存请求。

当然stl_allocator是模板类了。请注意，固定块分配职责被委托给非模板函数xmalloc()和xfree()。这使得每个实例的实例化代码尽可能小。 

“x”个容器

以下 STL 容器类使用固定大小的内存块，在使用容器时这些内存块的大小不会改变。堆元素/节点块的数量会上下变化，但对于给定的容器实例化，块大小是恒定的。

• std::list
• std::map
• std::multipmap
• std::set
• std::multiset
• std::queue

为了使使用stl_allocator更容易一些，为许多标准容器类型创建了新的类。每个新容器都继承自标准库对应项，并以“”开头x。 

• xlist
• xmap
• xmultimap
• xset
• xmultiset
• xqueue

以下代码显示了完整的xlist实现。请注意，xlist只是继承自std::list，但关键区别是_Ax模板参数默认为stl_allocator，而不是std::allocator。 

#ifndef _XLIST_H
#define _XLIST_H

#include "stl_allocator.h"
#include <list>

template<class _Ty, class _Ax = stl_allocator<_Ty> >
class xlist : public std::list<_Ty, _Ax>
{
};

#endif

STL 容器的每个“