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

• 下载 stl_allocator.zip

引言

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

标准模板库 (STL) 是一个强大的 C++ 软件库，包含容器和迭代器支持。在对任务关键型或时间关键型项目使用该库时存在的问题并非 STL 本身——该库非常健壮。而是全局堆的无限制使用。标准的 STL 分配器在运行过程中会大量使用堆。这在资源受限的嵌入式系统上是个问题。嵌入式设备可能需要运行数月或数年，必须防止由堆碎片引起的故障。幸运的是，STL 提供了一种用我们自己设计的 std::allocator 的方法。

固定块内存分配器是一种常见的技术，可以提供动态分配的类似操作，但内存来自内存池，并且分配的块大小固定。与通用堆不同，通用堆可以处理任意大小的块，固定块分配器可以针对狭窄定义的用途进行定制。固定块分配器还可以提供一致的执行时间，而全局堆无法提供这种保证。

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

使用 CMake 创建构建文件。CMake 是免费开源软件。支持 Windows、Linux 和其他工具链。有关更多信息，请参阅 **CMakeLists.txt** 文件。

查看 GitHub 以获取最新源代码

• 自定义 STL std::allocator 替换提升性能 - 作者：David Lafreniere

std::allocator

STL std::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 分配器必须遵循特定的接口要求。这不是一篇关于 std::allocator API 的“如何”和“为什么”的文章——网上有很多参考资料比我解释得更好。相反，我将重点介绍在现有 STL 分配器类接口中放置内存分配/释放调用的位置，并提供所有常用容器的新“x”版本以简化使用。

xallocator    

新的固定块 STL 分配器的绝大部分繁重工作来自底层 xallocator，正如我在文章《**用快速固定块内存分配器替换 malloc/free**》中所述。正如标题所示，该模块用新的固定块 xmalloc/xfree 版本替换了 malloc/free。

对用户而言，这些替换函数的操作方式与标准 CRT 版本相同，只是增加了固定块功能。简而言之，xallocator 有两种操作模式：静态池，其中所有内存都来自预先声明的静态内存；或堆块，其中块来自全局堆，但在释放后可用于后续使用。有关实现细节，请参阅上述文章。

stl_allocator

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 容器的每个“x”版本都像 std 版本一样使用，只是所有分配都由 stl_allocator 处理。例如

#include  "xlist.h"

xlist<xstring> myList;
myList.push_back("hello world");

以下容器类型使用动态大小的堆内存块，这些块在运行过程中会扩展或收缩。

• std::string
• std::vector

之所以没有实现对应的 xvector，是因为 vector 需要连续的内存区域，而其他容器类型是基于节点的。固定块分配器可以很好地处理等大小的块，但对于不断扩展到越来越大的单个块的 vector 来说效果不佳。虽然 stl_allocator 可以与 vector 一起使用，但可能会被误用并导致固定块内存管理器出现运行时问题。

std::string 在执行过程中也会改变其请求的内存大小，但通常情况下，字符串的使用不是无限制的。也就是说，在大多数情况下，您不会尝试存储一个 100KB 的字符串，而对于 vector，您可能确实会这样做。因此，提供了 xstring，如下所述。

"x" 字符串

为标准版和宽版 string 类创建了新的 x 版本。

• xstring
• xwstring

这里，我们只是 typedef 一个新的 x 版本，使用 stl_allocator 作为 char 和 wchar_t 类型的默认分配器。

#ifndef _XSTRING_H
#define _XSTRING_H

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

typedef std::basic_string<char, std::char_traits<char>, stl_allocator<char> > xstring;
typedef std::basic_string<wchar_t, std::char_traits<wchar_t>, stl_allocator<wchar_t> > xwstring;

#endif 

xstring 的用法与其他任何 std::string 都一样。

#include "xstring.h"

xwstring s = L"This is ";
s += L"my string.";

"x" 流

C++ 标准库的 iostreams 通过 stream 类提供了强大易用的字符串格式化功能。

• std::stringstream
• std::ostringstream
• std::wstringstream
• std::wostringstream

与容器类一样，iostreams 使用自定义 STL 分配器而不是全局堆，如这些新定义所示。

• xstringstream
• xostringstream
• xwstringstream
• xwostringstream

同样，通过 typedef 新的 x 版本并使用默认的 stl_allocator 模板参数即可轻松实现。

#ifndef _XSSTREAM_H
#define _XSSTREAM_H

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

typedef std::basic_stringstream<char, std::char_traits<char>, 
stl_allocator<char> > xstringstream;
typedef std::basic_ostringstream<char, std::char_traits<char>, 
stl_allocator<char> > xostringstream;

typedef std::basic_stringstream<wchar_t, std::char_traits<wchar_t>, 
stl_allocator<wchar_t> > xwstringstream;
typedef std::basic_ostringstream<wchar_t, std::char_traits<wchar_t>, 
stl_allocator<wchar_t> > xwostringstream;

#endif

现在，使用 xstringstream 非常简单。

xstringstream myStringStream;
myStringStream << "hello world " << 2016 << ends;

基准测试

在我之前的分配器文章中，简单的测试表明固定块分配器比全局堆更快。现在，让我们检查启用了 stl_allocator 的容器，看看它们在 Windows PC 上与 std::allocator 的比较情况。

所有测试均使用 Visual Studio 2008 和最大速度编译器优化级别构建。xallocator 以堆块模式运行，其中块最初从堆中获取，但在释放时进行回收。通过设置 **Debugging > Environment _NO_DEBUG_HEAP=1** 来禁用调试堆。调试堆由于额外的安全检查而明显较慢。

基准测试非常简单，侧重于插入/删除 10000 个元素。每个测试运行三次。插入/删除是 STL 库依赖于动态存储的地方，这也是这些测试的重点，而不是底层算法的性能。

下面的代码片段是 std::list 的测试。其他容器的测试也类似。

list<int> myList;
for (int i=0; i<MAX_BENCHMARK; i++)
    myList.push_back(123);
myList.clear();

下面显示了以堆块模式运行的 std::allocator 和 stl_allocator 之间的性能差异：
 

容器	模式	Run	基准测试时间（毫秒）
std::list	全局堆	1	60
std::list	全局堆	2	32
std::list	全局堆	3	23
xlist	堆块	1	19
xlist	堆块	2	11
xlist	堆块	3	11
std::map	全局堆	1	37
std::map	全局堆	2	34
std::map	全局堆	3	41
xmap	堆块	1	38
xmap	堆块	2	25
xmap	堆块	3	25
std::string	全局堆	1	171
std::string	全局堆	2	146
std::string	全局堆	3	95
xstring	堆块	1	57
xstring	堆块	2	36
xstring	堆块	3	40

测试结果表明，对于此基准测试，启用了 stl_allocator 的版本比 std::allocator 快约 2 到 3 倍。这并不意味着 STL 现在整体上神奇地快了两倍。同样，此基准测试仅关注插入和删除性能。底层容器算法的性能没有改变。因此，看到的总体改进将取决于您的应用程序从容器中插入/删除的频率。

如果 xallocator 以静态池模式使用，stl_allocator 将以固定时间运行。如果使用 xallocator 堆块模式，一旦空闲列表被从堆中获取的块填充，执行时间就是恒定的。请注意，上面的 xlist 基准测试的初始执行时间为 19ms，而后续执行时间均为 11ms。首次运行时，xallocator 不得不通过 operator new 从全局堆中获取新块。在运行 2 和 3 中，块已存在于 xallocator 的空闲列表中，因此不依赖于堆，从而使后续运行更快。

全局堆在堆碎片化时具有不可预测的执行时间性能。由于 xallocator 只分配块并回收它们以供以后使用，因此执行时间更加可预测和一致。

游戏开发者不遗余力地解决堆碎片化及其各种相关问题。Electronic Arts 标准模板库 (EASTL) 白皮书详细介绍了 STL 和特别是 std::allocator 的问题。Paul 在《EASTL -- Electronic Arts Standard Template Library》文档中指出：

引用

在游戏开发者中，最根本的弱点是 std 分配器的设计，而正是这个弱点是 EASTL 诞生的最大促成因素。

虽然我不为游戏编写代码，但我可以看到与碎片化相关的延迟以及不稳定的分配/释放时间会如何影响游戏玩法。

参考文章

• 用快速固定块内存分配器替换 malloc/free 作者：David Lafreniere
• 高效的 C++ 固定块内存分配器 作者：David Lafreniere
• EASTL -- Electronic Arts 标准模板库 作者：Paul Pedriana

优点

STL 是一个非常有用的 C++ 库。然而，在医疗设备项目中，我常常因为堆碎片化内存故障的可能性而无法使用它。这导致每个项目都要自己编写自定义容器类，而不是使用现有、经过充分测试的库。

我使用 stl_allocator 的目标是消除内存故障；然而，固定块分配器确实提供了更快、更一致的执行时间，而堆则不然。堆的实现和碎片化程度会导致执行时间不可预测。取决于您的应用程序，这可能是一个问题，也可能不是。

正如本文所示，仅仅采用一个 STL 兼容的固定块分配器就使得在以往可能无法使用的项目中使用 C++ 标准模板库成为可能。

修订

• 2016年4月3日
  • 首次发布
• 2016 年 4 月 11 日
  • 修复了代码中的错误。新源代码已附在文章中
• 2017 年 4 月 14 日
  • 修复了 Linux 系统上轻微的编译器包含错误
  • 更新了附带的源代码
• 2024 年 1 月 21 日
  • 简化了 xallocator 以使用 std::mutex