内存池介绍
该项目所使用的内存池原型是 Google 的开源项目 tcmalloc，其全称为 Thread-Caching Malloc，即线程缓存的 malloc，实现了高效的多线程内存管理，用于替换系统的内存分配相关函数，即 malloc 和 free。
内存池主要解决的就是效率问题，它能够避免让程序频繁的向系统申请和释放内存。其次，内存池作为系统的内存分配器，还需要尝试解决内存碎片的问题，内存碎片分为如下两种：
- 外部碎片：指的是空闲的小块内存区域，由于这些内存空间不连续，以至于合计的内存足够，但是不能满足一些内存分配的需求。
- 内部碎片：指的是由于一些对齐的需求，导致分配出去的空间中一些内存无法被充分利用。
内存池尝试解决的是外部碎片的问题，同时也尽可能的减少内部碎片的产生。
该内存池的整体架构如下图所示：
其主要由以下三个部分组成：
Thread Cache: 线程缓存是每个线程独有的，用于小于等于 256KB 的内存分配，每个线程独享一个 ThreaCache了。Central Cache: 中心缓存是所有线程共享的，当 ThreadCache 需要内存时会按需从 CentralCache 中获取内存，而当 ThreadCache 中的内存满足一定条件时，CentralCache 也会在合适的时机对其进行回收。Page Cache: 页缓存中存储的内存是以页为单位进行存储及分配的，当 CentralCache 需要内存时，PageCache 会分配出一定数量的页给 CentralCache，而当 CentralCache 中的内存满足一定条件时，PageCache 也会在合适的时机对其进行回收，并将回收的内存尽可能的进行合并，组成更大的连续内存块，缓解内存碎片的问题。
上述三个部分的主要作用如下：
- Thread Cache: 主要解决锁竞争的问题；
- Central Cache: 主要负责居中调度的问题；
- Page Cache: 主要负责提供以页为单位的大块内存；
1.ThreadCache
Thread Cache 的结构如下图所示：
通过使用字节对齐的方法来减少哈希桶的数目，并且进一步增加内存利用率，在设计时，让不同的范围的字节数按照不同的对齐数进行对齐，具体的对齐方式如下：
| 字节数 | 对齐数 | 哈希桶下标 | 自由链表数目 |
|---|---|---|---|
| [1, 128] | 8 | [0, 16) | 16 |
| [129, 1024] | 16 | [16, 72) | 56 |
| [1025, 8*1024] | 128 | [72, 128) | 56 |
| [81024+1, 641024] | 1024 | [128, 184) | 56 |
| [641024+1, 2561024] | 8*1024 | [184, 208) | 24 |
为了实现每个线程无锁访问属于自己的 Thread Cache，就需要用到线程局部存储(Thread Local Storage, TLS)，使用该存储方法的变量在它所在的线程是全局可访问的，但是不能被其它线程访问到，这样就保证了数据的线程独立性。
当某个线程申请的对象不用了，可以将其释放给 Thread Cache，然后 Thread Cache 将该对象插入到哈希桶的自由链表当中即可。
但是随着线程不断地释放，对应自由链表中的长度也会越来越长，这些内存堆积在一个 Thread Cache 中就是一种浪费，此时应该将这些内存还给 Central Cache，这样一来，这些内存对于其它线程来说就是可申请的，因此当 Thread Cache 中某个桶当中的自由链表太长时，可以将其释放给 Central Cache。
2. CentralCache
当线程申请某一大小的内存时，如果 Thread Cache 中对应的自由链表不为空，那么直接取出一个内存块返回即可，但如果此时该自由链表为空，那么这时 Thread Cache 就需要向 Central Cache 申请内存了。
Central Cache 的结构与 Thread Cache 是一样的，都是哈希桶结构，并且所遵循的对齐规则也一致。这样做的好处是当 Thread Cache 的某个桶中没有内存时，就可以直接到 Central Cache 中相对应的哈希桶中取内存。
Central Cache 与 Thread Cache 不同之处有两点：
- Central Cache 是所有线程共享的，而 Thread Cache 是线程独享的；
- Central Cache 的哈希桶中挂载的是 Span，而 Thread Cache 的哈希桶中挂载的是切好的内存块；
其结构如下所示：
由于 Central Cache 是所有线程共享的，多个 Thread Cache 可能在同一时刻向 Central Cache 申请内存块，因此为了保证线程安全，需要加锁控制。此外，由于只有多个线程同时访问 Central Cache 的同一个桶时才会存在锁竞争，因此无需用锁来锁住所有哈希桶，只需锁住当前所访问的哈希桶即可。
当 Thread Cache 向 Central Cache 申请内存时，如果给的太少，那么 Thread Cache 在短时间用完了又会再来申请；但是如果给的太多，那么 Thread Cache 可能用不完而浪费大量的空间。为此，此处采用慢反馈调节算法，当 Thread Cache 向 Central Cache 申请内存时，如果申请的是较小的对象，那么可以多给一点，但如果申请的是较大的对象，就可以少给一点。
当 Thread Cache 中的某个自由链表太长时，会将自由链表中的对象归还给 Central Cache 中的 Span。但是需要注意的是，归还给 Central Cache 的这些对象不一定都属于同一个 Span 的，且 Central Cache 中的每个哈希桶中都可能不止一个 Span，因此归还时不仅需要知道该对象属于哪一个桶，还需要知道它属于这个桶中的哪一个 Span。为了建立页号和 Span 之间的映射，需要使用一种哈希表结构进行管理，一种方式是采用 C++ 中的 unordered_map，另一种方式是采用基数树数据结构。
3. PageCache
Page Cache 的结构与 Central Cache 一样，都是哈希桶的结构，并且 Page Cache 的每个哈希桶中都挂的是一个个的 Span，这些 Span 也是按照双向链表的结构连接起来的。
但是，Page Cache 的映射规则与 Central Cache 和 Thread Cache 不同，其采用的是直接定址法，比如 1 号桶挂的都是 1 页的 Span，2 号桶挂的都是 2 页的 Span，以此类推。
其次，Central Cache 每个桶中的 Span 都被切为了一个个对应大小的对象，以供 Thread Cache 申请。而 Page Cache 服务的是 Central Cache，当 Central Cache 中没有 Span 时，向 Page Cache 申请的是某一固定页数的 Span。而如果切分这个申请到的 Span 就应该由 Central Cache 自己来决定。
其结构如下图所示：
当每个线程的 Thread Cache 没有内存时都会向 Central Cache 申请，此时多个线程的 Thread Cache 如果访问的不是 Central Cache 的同一个桶，那么这些线程是可以同时进行访问的。这时 Central Cache 的多个桶就可能同时向 Page Cache 申请内存，所以 Page Cache 也是存在线程安全问题的，因此在访问 Page Cache 时也必须要加锁。
但是此处的 Page Cache 不能使用桶锁，因为当 Central Cache 向 Page Cache 申请内存时，Page Cache 可能会将其他桶中大页的 Span 切小后再给 Central Cache。此外，当 Central Cache 将某个 Span 归还给 Page Cache 时，Page Cache 也会尝试将该 Span 与其它桶当中的 Span 进行合并。
也就是说，在访问 Page Cache 时，可能同时需要访问多个哈希桶，如果使用桶锁则可能造成大量频繁的加锁和解锁，导致程序的效率底下。因此在访问 Page Cache 时没有使用桶锁，而是用一个大锁将整个 Page Cache 锁住。
如果 Central Cache 中有某个 Span 的 useCnt_ 减到 0 了，那么 Central Cache 就需要将这个 Span 归还给 Page Cache 了。为了缓解内存碎片问题，Page Cache 还需要尝试将还回来的 Span 与其它空闲的 Span 进行合并。
4. 基数树
由于在 PageCache 中最初建立页号与 Span 之间的映射关系时，采用的是 unordered_map 数据结构，但是通过性能测试发现，内存池的性能并未优于原生的 malloc/free 接口，因此通过 Visual Studio 的性能分析工具发现性能瓶颈位于 unordered_map 处。
这主要是因为 unordered_map 不是线程安全的，在多线程环境下需要加锁，而大量的加锁则会导致资源的消耗和性能的下降，因此在映射页号与 Span 之间的关系时，采用基数树（Radix Tree）数据结构来进行优化。
当采用如下图所示的单层基数树时，在 32 位平台下，以一页大小为 8K(213) 为例，此时页的数目就是 232÷213=219，因此存储页号最多需要 19 个比特位，同时由于 32 位平台下的指针大小为 4 字节，因此该数组的大小就是 219×4=221=2�，内存消耗不大，是可行的。但是如果是在 64 位平台下，此时该数组的大小就是 251×8=254=224�，这显然是不可行的：
如下图所示，为二层基数树，同样在 32 位平台下，以一页的大小为 8K 为例来说明，此时存储页号最多需要 19 个比特位。而二层基数树实际上就是把这 19 个比特位分为两次进行映射。例如，前 5 个比特位在基数树的第一层进行映射，映射后得到对应的第二层，然后用剩下的比特位在基数树的第二层进行映射，映射后最终得到该页号所对应的 Span 指针。
在二层基数树中，第一层的数组占用 25×4=27 Bytes 空间，第二层的数组最多占用 25×214×4=221=2�。二层基数树相比与一层基数树的好处就是，一层基数树必须一开始就把 2M 的数组开辟出来，而二层基数树一开始只需要将第一层的数组开辟出来，当需要进行某一页号映射时再开辟对应的第二层的数组就行了。
在 32 位平台下，一层基数树和二层基数树都是适用的，但是在 64 位平台下，就需要使用下图所示的三层基数树了。三层基数树类似于二层基数树，实际上就是把存储页号的若干比特分为三次进行映射，而且只有当需要建立某一页号的映射关系时，才会开辟对应的数组空间，在一定程度上节约了内存空间：
5. 性能测试
单线程下内存池性能测试结果如下表所示，其中 alloc/dealloc 表示使用内存池来进行内存的申请和分配，而 malloc/free 表示使用系统原生的 API 来进行内存的申请和分配，表格中的单位为秒：
| 申请次数 | malloc | free | malloc&free | alloc | dealloc | alloc&dealloc |
|---|---|---|---|---|---|---|
| 100 | 0.000108 | 2.2e-05 | 0.00013 | 0.000366 | 6e-05 | 0.000426 |
| 500 | 0.000344 | 0.000111 | 0.000455 | 0.002713 | 0.000235 | 0.002948 |
| 1000 | 0.000935 | 0.000409 | 0.001344 | 0.007691 | 0.000355 | 0.008046 |
| 5000 | 0.021884 | 0.004798 | 0.026682 | 0.007954 | 0.00218 | 0.010134 |
| 10000 | 0.06108 | 0.011623 | 0.071731 | 0.020134 | 0.003578 | 0.023712 |
| 20000 | 0.120307 | 0.028152 | 0.148459 | 0.024508 | 0.006907 | 0.031415 |
| 30000 | 0.199733 | 0.043747 | 0.24348 | 0.03611 | 0.011694 | 0.047804 |
单线程性能测试结果的折线图如下所示：
多线程下的性能测试结果如下表所示，每个线程都需申请/释放内存 10000 次：
| 线程数目 | malloc | free | malloc&free | alloc | dealloc | alloc&dealloc |
|---|---|---|---|---|---|---|
| 1 | 0.06108 | 0.011623 | 0.071731 | 0.06108 | 0.011623 | 0.071731 |
| 2 | 0.2204 | 0.076146 | 0.296546 | 0.059878 | 0.015874 | 0.075752 |
| 3 | 0.613199 | 0.194174 | 0.807373 | 0.156596 | 0.03168 | 0.188276 |
| 4 | 0.492761 | 0.060352 | 0.553113 | 0.492761 | 0.060352 | 0.553113 |
| 5 | 2.65943 | 0.416495 | 3.07592 | 0.680774 | 0.092576 | 0.77335 |
| 6 | 4.16152 | 0.528937 | 4.69046 | 0.815121 | 0.123539 | 0.93866 |
| 7 | 5.43473 | 0.805814 | 6.24054 | 1.18223 | 0.166473 | 1.34871 |
多线程性能测试结果的折线图如下所示：
综合对比上面的测试数据，可以看出，当申请的内存次数较小时，使用系统原生的 API 更为合适，而如果申请次数过多时，内存池的优势就逐渐体现出来了。