浅谈STL中的分配器

た入场券 2024-02-17 10:18 40阅读 0赞

分配器是STL中的六大部件之一，是各大容器能正常运作的关键，但是对于用户而言确是透明的，它似乎更像是一个幕后英雄，永远也不会走到舞台上来，观众几乎看不到它的身影，但是它又如此的重要。作为用户，你几乎不用关心它的底层是怎么实现的，甚至也很少有能使用到它的机会。这里简单聊一下我对它的认识。

#### 正常情况下我们如何取得一块内存？ ####

*  malloc能够帮你获取一块内存并返回这块内存的首地址；
 *  new operator的底层也是用malloc实现，只是相较于malloc，它不光会给你一块内存，还会帮你自动初始化这块内存，即调用对应对象的构造函数
 *  operator new是C++获取内存的方式，注意：new operator和operator new是两种不同的东西，它也是调用了malloc来实现获取内存，只是封装了一些东西，增加了一些异常机制。
 *  而VC，BC,GNU C等等编译器厂商最初提供的allocate的底层也是通过调用operator new实现的。

所以，你发现没有？殊途同归，大家几乎都是通过调用malloc来实现获取内存这一操作的。而malloc根据机器的不同，去调用操作系统底层提供的api接口去获得真正的内存。

![在这里插入图片描述][8b9fd99966c3431b8b5715cb2afad9f4.png]

但是，如果你申请一块10个字节的内存，malloc给你的内存的大小却并不真的是10个字节。这里面你能用的内存有10个字节没错，但是还会有一些额外的开销在里面，它们会在这块内存的两头加上所谓的“cookie”来处理一些其他事情，就比如你买东西收到的其实并不是东西本身，还会有快递盒，快递袋，快递单等额外的东西帮助你自己买的东西到达你的手上。这些东西对你来说可能没用，但确确实实是不可避免的开销。

从这个角度而言，如果一个容器里放的东西很小，但是元素的数量又很多，假如容器里你想放一个2个字节的short类型的元素，而这样的容器的数量有100w个，这样轮到这个容器底层的分配器去帮你开辟内存的时候，由于cookie的存在，申请一个这样的容器你可能会得到10个字节，其中2个字节是你想要的内存，其余8个字节是额外的开销，这样下来100w个容器本来只需要200w个字节，现在你却不得不得到1000w个字节，性能实在是不这么高。

这里并不是说cookie很消耗内存才造成的你的性能不理想，而是存在一个比例问题。如果你的容器里放的元素的内存很大，那么这额外的开销就显得很渺小，完全可以接受；但是更多的情况下，容器里放的元素其实并没有那么大，这也就显得性能不理想。

#### 如何解决这种问题？ ####

SGI STL中给出的一个思路是先放很多的分配器，但是每个分配器只负责某种固定大小的内存的申请，等到容器真的申请内存的时候，对应大小的分配器会去申请一块很大的内存，然而自己将这些内存切割成固定大小的内存，再返回给使用者某一块固定大小的内存的首地址。

使用这种策略，便不再会对额外开销产生困扰，因为真正的申请内存只有刚开始的那次，所以只会得到一次cookie，得到的这块大的内存被切割成固定大小时，每块内存上并不会带cookie，也就不会有额外开销。  
![在这里插入图片描述][9fd178b3fb3444e8a6ae9fbebf94058a.png]

**STL提供了两层内存分配器**：

*  当分配大于128KB时，直接采用new operator，也就是一级内存分配器；
 *  当分配小于128KB时，采用二级内存分配器，也就是内存池，具体是通过自由链表实现的。参考[文章][Link 1]。

为什么要分两级呢？**主要是为了减少内存碎片，减少malloc的次数**。所以内存池就相当于应用代码和系统调用申请内存的中间件。

#### 第一层内存分配器 ####

##### operator new #####

`operator new`可以被重载：

1.  重载时，返回类型必须声明为void\*；
2.  重载时，第一个参数类型必须为分配空间的大小（字节），类型为size\_t，当然也可以带其它参数；

如：

class Foo
       {
        
       public:
         static void *operator new (size_t size)
         {
        
             Foo *p = (Foo*)malloc(size);
             return p;
         }
       
        static void operator delete(void *p, size_t size)
         {
        
             free(p);
         }
       };

这里只是简单的用`malloc`和`free`来实现，后续可以用内存池。

C++还提供了全局的`operator new`和`operator delete`，可以通过`::operator new`和`::operator delete`来访问全局操作符。

##### placement new #####

`operator new`实现了new表达式的第一步即分配内存，那么谁来调用构造函数呢？就是`placement new`，它的语法是：

Object * p = new (address) ClassConstruct(...)

这里要求`address`是`void*`，并且`placement new`被定义在`#include<new>`头文件中。同样的也可以重载它，也提供了全局下的`placement new`，通过`::`访问。

举个例子

int* ptr = ::operator new(sizeof(int));
     ::new ((void*)ptr) int();

其实本质上`placement new`也是`operator new`**的一个重载版本**！只不过，这个重载版本我们常用来调用构造函数。如：

class Foo
     {
        
     public:
         //一般的 operator new 重载
         void* operator new(size_t size)
         {
         return malloc(size); }
     
         //标准库已经提供的 placement new() 的重载形式
         void* operator new(size_t size, void* start)
         {
         
           dosomething;
           return start; 
         }
     };

那对`new operator`和`delete operator`拆分为两部分功能有什么好处呢？使用`new`表达式在分配内存时，需要在堆中查找足够大的剩余空间，显然这个操作速度是很慢的，而且有可能出现无法分配内存的异常（空间不够）。

`placement new`就可以解决这个问题。**在一个预先准备好了的内存缓冲区上进行构造函数，不需要查找内存，内存分配的时间是常数**。而且不会出现在程序运行中途出现内存不足的异常。所以，placement new非常适合那些对时间要求比较高，长时间运行不希望被打断的应用程序。

总之，new造成的反复分配内存很浪费，所以placement new直接固定内存，在这个固定内存上反复构造和析构，但不再反复分配内存和释放内存。

**note**：如果采用`placement new`，可别忘记在`operator delete`前调用析构函数！除非元素的析构函数是无关紧要的。

##### allocator #####

STL的`allocator`负责对容器的分配内存、释放内存、调用元素的构造函数、调用元素的析构函数。

其实理解了上面的内容，STL的allocator也就很简单。

对外提供四大方法：

*  allocator方法：即调用`operator new`
 *  construct方法：即调用`placement new`
 *  deallocator方法：即调用`operator delete`
 *  destroy方法：即调用`~T()`

**note**：不是所有类都需要调用destroy，当类的析构函数是无关紧要的时候，我们可以不进行析构，那么什么样的是无关紧要的?可以用`std::is_trivially_destructible`类模板判断。具体来说：

1.  使用隐式定义的析构函数，即没有定义自己析构函数
2.  析构函数不是虚函数
3.  其基类与非静态成员也是可trivially析构

其实会发现basic\_string在释放内存前没有调用析构函数，正是因为basic\_string严格要求元素类的析构函数是无关紧要的。而vector等则需要在释放内存前调用析构函数。

#### 第二层内存分配器 ####

先申请一大块内存，然后切割成小块，由单向链表串起来，内存池包括十六条链表，分别负责不同大小的内存大小，比如第7个负责256字节的区块，以8的倍速增长。

至于STL内存池设计的好坏也颇有争议：C++ 标准库中的allocator是多余的，allocator作为模板参数这就导致不同allocator是不同的type。

[8b9fd99966c3431b8b5715cb2afad9f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/ccd23723e01e4dc087bbaf8f1dd8e997.png
[9fd178b3fb3444e8a6ae9fbebf94058a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/426c6ddc3a7c4a4084d98d2afeaf5d36.png
[Link 1]: https://link.zhihu.com/?target=https%3A//github.com/rongweihe/CPPNotes/blob/master/STL-source-code-notes/5%20%E5%8D%83%E5%AD%97%E9%95%BF%E6%96%87%2B%2030%20%E5%BC%A0%E5%9B%BE%E8%A7%A3-%E9%99%AA%E4%BD%A0%E6%89%8B%E6%92%95%20STL%20%E7%A9%BA%E9%97%B4%E9%85%8D%E7%BD%AE%E5%99%A8%E6%BA%90%E7%A0%81.md