侯捷 | C++ | 内存管理 | 学习笔记（二）:第二章节 std::allocator

侯捷 | C++ | 内存管理 | 学习笔记（二）:第二章节 std::allocator

第二章节 std::allocator（为小区块服务）

西北有高楼，上与浮云齐。

在工业级别，可能会用malloc上百万次，即使是有内存池的存在，cookie占用的额外内存还是不容小觑，同时malloc也挺慢的，所以这部分的目标就是去掉malloc，使得效率提高，空间率精简。

去除cookie的先决条件是申请的块是一样的大小，如果块有大有小那就不能去掉，因为要标识块的大小，如果是一样的大小，那就可以去掉。而一个类的对象实例大小肯定是一样的。

1.占用内存的计算方式

0xC是block size,是咱们申请分配的内存大小，实际给咱的是计算后的结果即0x40

2.不同版本的allocator设计

1. VC6、BC5、G2.9和G4.9的allocator

VC6的标准分配器

这个编译器的allocator没有任何特殊设计，单纯是调用malloc和free，分配是以对象元素为单位。

BC5的标准分配器

和VC6相同，没有任何特殊设计。

GNU4.9的标准分配器

同样，没有任何特殊设计，和VC6，BC5一样。这个文件中已经说明，这个分配器没有用，容器的分配器不使用它！

GUN 2.9d的标准分配器

同样，没有任何特殊设计

这些版本下的allocator()本质上都是malloc()

在这些版本下，所有的容器都是直接调用allocator(),即第二个模板参数都是allocator。

2. G2.9的alloc流程解析

这个和G4.9 pool allocator就消除了大部分cookie的额外空间，因为只要用malloc就会有cookie，所以不可能完全没有，只是尽可能去回收已经分配过得内存来减少malloc从而减少cookie。两者实现方式差不多所以看2.9版的

1.内存池配置器：

1. 一级配置器：直接对malloc和free（或new和delete）进行封装，提供预申请内存接口，减少内存分配的上下文切换。当申请的内存区块大于一定阈值（如128bytes）时，一级配置器会处理这些大块内存的分配和释放。
2. 二级配置器：是真正的内存池实现，主要针对小块内存的频繁申请和释放。它采用内存块分级管理策略，将内存划分为多个不同大小的区块（如8, 16, 24, …, 120, 128 bytes等），并使用自由链表（free-lists）来管理这些区块。当需要小块内存时，二级配置器会尝试从自由链表中找到合适大小的区块进行分配；当释放小块内存时，也会将其回收到对应的自由链表中。

2.具体流程

  原始的allocator()只维护一个内存链表，链表中每个节点的内存块大小根据创建allocator的对象来决定。现在的alloc通过free-list维护16条链表,节点的内存块大小从8byte到128byte共16种。

内存申请过程：程序申请一块32bytes大小的空间，alloc会先通过malloc申请一块32*40bytes的空间，分一块给程序，32*19挂到free-list上维护为一条大小为32bytes，个数为19的链表.剩下32*20交给备用空间，暂时不进行处理。若程序继续要申请一块64bytes大小的空间，则直接将刚刚剩余的32*20的空间挂到free-list变为64*10的链表，并把第一个节点内的内存分配给程序。

下一次申请就没有备用空间了，就得重新和malloc申请

PS：加入追加量概念和每次除以16都是经验所得，不用太纠结

注意点：
  1.每一个区块采用union结构，前四个字节表示为指向下一个区块的指针，好处是减少了额外的指针开销。有元素的时候就放元素了，用完了归还的时候又变成了指针。
  2.每条链表的长度为1-20，即使空间足够，长度也不会超过20。
  3.申请的空间如果很大，那还是会到一级配置器调用malloc。若当前需要申请一块104bytes的空间，而备用空间只剩下80bytes，则先将备用空间的80bytes挂到#9号链表下，再进行内存申请，若空间剩余不为8的倍数，则向上补齐为8的倍数再放入链表。
  4.若当前要申请一块72bytes的空间，备用空间不够，系统内存也不够无法通过malloc()额外申请。则将80bytes的链表（即最靠近72bytes，且比72bytes大的链表）中切下一块放入备用空间，再从备用空间中切下72bytes，交给程序。若80bytes的链表也没有空间，则依次向后继续找，若找到128bytes仍然没有足够的空间，则报错内存分配失败。
  5.备用空间是通过一头一尾两个指针来界定。

  6.当程序将空间返回时，若大于128bytes，直接通过一级配置器返还给系统，还是会调用free来回收，若小于128bytes，则直接安插到free-list对应链表的头部。

  7.若程序申请80bytes的内存空间，链表上为空，则先调用备用空间。若备用空间能分配一块以上但不足20块的内存大小，比如备用空间还有248，那就分成3块，给程序一块，然后两块空余，这三块都挂在9号，备用空间只剩8这样子。若备用空间内存足够，则将一块内存分配给程序，剩余19块内存挂载到链表上，并通过指针相连。

  8.若程序申请80bytes的内存空间，链表上为空且备用空间不足，则free-list会调用refill()函数来填充链表，进行malloc()操作。若系统空间只能分配一块80bytes，则直接将内存分配给程序，不挂到链表上；若系统空间内存足够，则将一块内存分配给程序，剩余19块内存挂载到链表上，并通过指针相连。

  9.为什么当备用空间不足，且系统空间不足以申请20块内存时，要从更大的内存块链表切下一块放入备用空间，而不是向系统申请一块内存？
  因为链表上挂着的内存，本质上都是由alloc维护，只要是申请过并且分配过的（很大的一块空间但是内存池不知道这个到底有多大，因为链表很长，所以就都拿在手中)就不还给操作系统，如果这样做就相当于不使用alloc现有的内存而去向系统继续申请额外内存，后果是当前程序占有的内存越来越大，对于多任务系统是一种灾难。尽可能使用已经拥有的内存！！！

3.缺陷以及消除cookie后的测试结果

缺陷：

比如3号一开始的指针，这个是一开始用malloc分配的有cookie，在后面分配的时候，没有变量去保存这个指针，所以也导致归还不了内存，在第四讲中会有更好的东西来弥补它

测试结果：

都是一百万个对象

左边用了内存池，分配内存的行为malloc只调用了122次，而右边没有用的调用了一百万次malloc，一个cookie是8字节，相当于多用了8百万字节的额外空间，前面只是122*8个字节而已。

而上面的1675283是new的调用的次数，其实这个没有影响，因为内存池多了一层管理，而右边没人管理，所以左边会比右边多一些new和delete的操作，而这里面的delete其实没办法计数的。