1. tcmalloc项目简介

tcmalloc是google的开源项目,全称是thread-cache malloc,即使用了线程缓存机制的动态内存开辟项目。

tcmalloc在单线程场景下，性能已优于malloc,而在多线程中，二者性能差距则更大，tcmalloc可以说是专为多线程而设计的动态内存开辟解决方案。

本项目希望通过仿照tcmalloc实现,了解内存管理的机制，并与new,malloc做实现与性能上的分析对比。

2. tcmalloc的核心架构

2.1 三层结构设计

tcmalloc的核心结构分为三层：front-end,middle-end和back-end，这三者分别对应于ThreadCache,CentralCache和PageCache。

其中,ThreadCache是直接与线程交互的，ThreadCache与CentralCache间完成内存的申请与释放，CentralCache与PageCache间完成内存的申请与释放。PageCache申请空间，直接使用系统调用进行申请。

2.2 核心概念

freeList:
自由链表，用于将一个个相同大小的内存块串联起来，本质就是一个链表结构，用于ThreadCache中。

Span:
一段连续的内存空间，这段连续的内存空间在centralcache中已被切分成一段段固定大小的内存块，用以与threadcache交互；在pagecache中，是完整连续的内存空间，未被切分。

Page:
无论是物理内存还是虚拟内存，4KB的页都是最小粒度，也就是说在系统层面，申请释放内存的最小单位就是4KB，申请释放内存的起始地址，也必须是4KB对齐的。

SizeClass:
用户实际申请的内存大小是任意的，但tcmalloc中的内存分配并不任意，而是用一套内存对齐方案，对用户给出的内存大小进行向上对齐。

3. 核心架构的内存申请逻辑

3.1 thread_cache

tcmalloc,作为现代高性能，适用于多线程场景的内存分配器，如何提高多线程性能。

多线程中，限制性能最重要的一环就是锁竞争问题。在tcmalloc中，每一个线各自分配一个thread_cache,从而达到对thread_cache的高速无锁访问。

thread_cache的设计思路是什么呢？

首先，我们对用户申请内存进行对齐处理。thread_cache最大可分配的内存范围是1 ~ 256 * 1024字节，在这个范围内，我们进行不同对齐范围和对齐数的划分，具体划分如下：

在一定范围内，如何对齐，是有讲究的。在上述对齐划分中，较小的字节数，对齐数也小；较大的字节数，对齐数也大。这样，小内存小对齐，大内存大对齐，保证了内存空间的内部碎片占比能够保持在10%左右，并且控制了哈希桶个数。

最终，上述划分的区间，每一个对齐的区间，都对应一个FreeList,这样就得到了208个FreeList,而每个FreeList中，所挂的每块内存空间都是不同的。

实际线程申请时，都是直接与thread_cache交互，在thread_cache中实现无锁高效循环申请。

但实际上，thread_cache特定桶中，自由链表中可能会没有内存空间，此时就需要thread_cache去central_cache中申请内存空间。

那么，thread_cache如何向central_cache中申请空间呢？
本质就是将central_cache中切好的相应大小的内存块，从central_cache所维护的链表中，链入thread_cache所维护的链表中。

那么，用户申请内存空间，肯定是一个个申请，thread_cache从central_cache中获取，也是一个个获取吗？显然不是，这样效率太低。

实际中，由于不同大小的内存块，需求量是有差异的，大内存块需求量少，小内存块需求量大，因此我们需要差异化设置，使用一个函数来计算具体的需求量。

那么大小内存块实际申请个数差异化设置就够了吗？如果在某个场景中，确实小内存使用量很小，那么申请过多就导致浪费了——因此我们再引入慢增长申请机制，即在每一个thread_cache的哈希桶中，存储一个变量max_num,用来控制慢增长逻辑,在计算得到的需求量和max_num中取较小值，每次申请后max_num都需要增大——这样就保证刚开始申请时，获得较少；后面申请时，获得较多。

当然，这时理论上的情况，如果central_cache相应桶中并没有相应数量的内存空间，那么此时至少拿取一个。

3.2 central_cache

central_cache并不是线程私有的，而是线程共享的，所以需要加锁进行保护。

在central_cache中维护的重要结构是Span,即一段内存空间，page_cache中维护的也是这个结构，二者都使用Span,但是central_cache中的Span被切分，而page_cache中则没有。

由于central_cache与thread_cache交互，需要给thread_cache特定大小的内存空间，因此它的结构是与thread_cache完全相同的哈希桶结构，直接映射，但成员是Span,而非FreeList。

在每个哈希桶下，不是单挂一个Span,而是挂了一个SpanList结构，以链表形式串联起多个Span。

central_cache中哈希桶结构的设计，使得多线程对central_cache的访问可以使用桶锁这种细粒度的锁，因为访问同一个central_cache中不同哈希桶中的SpanList是不存在线程冲突问题的，因此使用桶锁，而非一把大锁，能极大提升并发效率。

central_cache与page_cache中交互时，就是到相应桶的SpanList中，找一个非空Span，然后将其中所链的多个内存块，从一个链表转移到另一个链表即可。

那么central_cache中如果出现相应桶的SpanList为空，或者无非空Span的情况，此时就需要central_cache与page_cache进行交互，从page_cache中获得一个新的Span,然后完成切分工作，再链入到相应哈希桶下的SpanList中。

3.3 page_cache

page_cache也是所有线程共享的。page_cache中直接维护的是Span，即完整的大块内存，没有经过切分的，以页为单位划分不同大小的Span,在我们的设计中，实现了至多128页的Span——实际的页可以是系统原本的4KB，也可以在用户层面做二次对齐，我们采用一页为8KB，进行了二次对齐。

从上述介绍中，我们可以发现，page_cache是需要直接与系统交互的，即page_cache中会使用到系统调用。

那么central_cache是如何从page_cache中获得Span呢？首先，在central_cache中没有引入页概念，它的哈希桶结构对应的是thread_cache中所设计的至多256 * 1024字节进行对齐后的范围划分。因此，需要一个函数，将central_cache中相应哈希桶的对齐大小，转换成需要申请的页数。

实际申请的页数也是需要因内存空间大小而异的。小字节空间使用多，需要多申请；大字节空间使用少，可以少申请。这里就不使用慢增长机制，尽量减少page_cache的访问，因为page_cache使用一把大锁(这点后面会解释)。

当然，如果计算出的页数为0，那么至少申请1页。

实际central_cache从page_cache中申请，就是把相应页数映射下的SpanList中的一个完整连续的Span取走(取一个即可,不需要多个,在central_cache逻辑中进行切分，可切分为很多特定大小的内存块)，即从一个链表中转移到另一个链表中。

那么，如果page_cache中完全没有Span呢？
此时,page_cache就要进行申请逻辑，调用系统调用mmap。
实际上，page_cache的申请逻辑分为以下三层：

1. 如果相应的页映射中有Span,那么就返回这个Span。
2. 如果相应的页映射中没有Span,那么就到大于这个页的映射下找，看有没有空闲的Span,如果有，则进行切分逻辑，将这个Span切分成两个Span,其中一个Span即为所需要的Span,然后把切剩下的Span放入指定页映射的SpanList中进行管理。
3. 如果上述逻辑都走不通，那么page_cache就重新通过系统调用申请一个128页，实际是128 * 8kb大小的Span，然后重新走逻辑2，即可完成，这个过程可以通过函数的递归实现。

通过上述了解，我们可以发现，page_cache虽然也分为不同的页映射，但是如果相应页映射不存在的话，就需要涉及到其它页映射，如果我们同样采用桶锁，就会出现多锁的频繁申请和释放，相比给page_cache加一把大锁，前者效率可能反倒会更低，因此page_cache中我们使用一把大锁来保护线程安全。

另外，需要注意的是，由于我们设计中，页大小为8KB，因此需要在用户层面做二次对齐。具体的二次对齐逻辑如下所示：

需要说明的是，在windows中，二次对齐的逻辑无法实现，因为windows中的VirtualFree系统调用不支持部分内存释放，因此如果一定要实现二次对齐逻辑，会造成内存的内碎片问题。

不过虽然Linux中，可以进行部分内存的释放，但是同样要遵守系统页4KB是最小粒度的逻辑，即释放内存的起始地址和释放内存的大小必须是4KB对齐的。

4. 核心架构中的内存释放逻辑

4.1 thread_cache

thread_cache作为直接与线程交互的模块,会处理大量释放请求，那么这些释放的内存如何处理，是直接缓存在thread_cache相应桶中，还是归还到central_cache中？

由于tcmalloc的设计理念就是多线程并发场景下的高效率内存申请，因此释放的内存主要缓存在thread_cache相应桶中，但是这并不代表不需要归还到central_cache中，否则无法对内存空间做充分利用。

那么，如何制定一种高效的归还策略，使得thread_cache不必频繁访问central_cache，同时在一定时候，又能进行归还逻辑，提高内存的使用效率。

实际中，我们采用高低水位和延迟归还这两种策略。高低水位本质就是两个数，如果一个桶中的内存数目超过高水位，那么就释放这些内存，使得数目回到低水位；延迟归还，就是说不是内存数目刚超过高水位就执行归还逻辑，而是超过高水位达到一定程度再归还。

上述策略逻辑上是很简单的，但是实际参数的设置确是有所讲究。
高水位不能设置得太高，否则内存几乎不会归还，当然也不能设置得太低，否则频繁触发归还逻辑，释放效率低；低水位和高水位之间的差距不能太大，否则缓存数目太少，同时差距也不能太小，否则也会导致频繁触发归还逻辑。

当然，延迟归还的参数也要合理设置，不能过大或过小。

上述过程，本质是一个调参过程，一般来说，最终能够达到归还逻辑的触发总次数是释放逻辑总次数的千分之一，那么参数设置相对就比较合理。

上述讲的是释放策略，那么thread_cache释放到central_cache中的哪里呢？

首先，thread_cache和central_cache都维护哈希桶结构，哈希桶的映射下标即为通过对齐大小划分出的对齐范围下标，所以，我们能够直到释放到哪个哈希桶中，但是一个central_cache的哈希桶下挂的是SpanList,如何知道是哪个span中的呢？

我们知道，我们最终page_cache中申请的本质都是起始地址和大小均按8KB对齐的连续完整空间，然后再不断切割使用。central_cache从page_cache中拿到的是完整空间，对完整空间做切分，再分配到thread_cache当中。

所以，thread_cache中每块小内存一定属于某一个页中，我们可以通过这块小内存的起始地址，计算出它在哪一个页中。同时，对于每一个Span，我们在其内部维护一个页号,即page_id——这样就可以通过小块内存所在的页号，找到其所对应的Span。

但是，找的过程需要在相应桶下的SpanList中遍历，找对应的Span，效率太低。

我们发现，内存页号本质是唯一的，通过内存页号找相应Span的过程，就是用key去找对应value，所以我们可以引入一个哈希结构，专门用于页号查找Span。
实际中，我们在page_cache中维护这个哈希结构，并对外提供查找的接口函数(为什么在page_cache中维护,以及这个哈希结构具体使用什么算法结构，这些后面会讲)。

有了这个哈希结构后，可以实现通过页号高效查找Span，找到相应Span后，就是将内存块，由一个链表转移到另一个链表。

这里可能会有疑惑，Span下的大内存块，第一次进行切分时，切分出的内存块排列是有序的，但是分配再归还后，由于顺序的不确定问题，最终链表中的内存块逻辑顺序和物理顺序可能是不一致的——这没有任何关系,链表顺序本质是用户层组织内存块的顺序，并不影响底层内存块的完整和连续性，说白了，底层依旧是一大块内存，只不过用户层使用时，进行额外切分罢了。

4.2 central_cache

thread_cache到central_cache需要归还，central_cache到thread_cache也需要归还。

那么central_cache的归还逻辑是什么呢？

首先，有一点需要注意，tcmalloc由于thread_cache缓存模块的设计，导致实际上线程大部分内存的申请和释放都是在thread_cache内部进行循环交互，所以thread_cache中的申请与释放逻辑，需要设计得较为复杂，引入各种算法进行优化。

但是central_cache中，就以释放为例，首先本身在thread_cache中释放算法的优化下，thread_cache自身的缓存命中率相当之高，实际释放时访问central_cache的频次已经很少，因此即便设置一个简单的central_cache释放到page_cache的逻辑，也不太容易满足，因此我们遵循KISS(keep it simple,stupid)原理即可。

实际中，逻辑这样设置：在Span中引入一个引用计数，当其中任意一块内存被拿走时，引用计数就自增，一块内存被释放时，引用计数就自减，引用计数初始值为0，所以0表示Span中没有内存块被使用。

实际执行归还逻辑时，将thread_cache中的内存块归还到central_cache中后，相应Span的引用计数自减，然后进行条件判断，如果此时该Span的引用计数为0，则代表该Span下的内存块已经被全部归还，即有一块完整内存没有被使用，因此进行central_cache到page_cache的归还逻辑。

上述过程可能会有疑问，那么我刚分配好的一个Span,相关引用计数也是0，那么也会被归还吗？

不会，因为是通过归还的小内存块找到相应Span,刚分配好的Span,绝不会存在这样的逻辑。

4.3 page_cache

首先，page_cache是back_end，是最后一层缓存，这个模块是直接通过系统调用申请内存的，最终释放到page_cache中的内存，不需要再通过系统调用进行释放——因为本身内存池的设计，就是用来申请内存，然后在进程运行时做内存管理的，所以整个进程的运行中，最终的内存释放到page_cache即可，不需要释放到系统，进程结束后，自动回收所有资源。

那么实际上，page_cache所要关注的，就是如何处理central_cache中归还内存的问题。

在讲具体的处理逻辑前，我们必须要明确，为什么要存在归还逻辑？

从thread_cache到central_cache,再从central_cache到page_cache,为什么归还的内存不一直缓存在thread_cache中呢？

如果没有释放逻辑，那么归还到thread_cache中的大量小内存缓存在thread_cache中，同时又不被使用，由于这些小内存本身是由大块完整连续的内存切分而来的，如果进行合理归还，那么我们可以完成小内存到大内存的拼接，获得完整连续的以8KB为单位的大内存。试想这种情况，如果一个线程申请向thread_cache申请一块大内存，然后thread_cach到central_cache,central_cache到page_cache,如果没有释放逻辑，那么page_cache中可能就没有这么大的内存，需要重新通过系统调用申请，那么时间空间上的浪费就太大了；而有释放逻辑，那么大量不被使用的小内存最终就可以还原成完整连续的大内存缓存在page_cache中，那么此时就不需要再通过系统调用申请了。

所以，明确了为什么释放后，我们自然也就明白page_cache中该完成什么工作——讲central_cache中释放的完整内存进行前后页的拼接，拼接成更大的内存。

那么，如何完成前后页的拼接逻辑呢？

要拼接前后页，我们首先要找到前后页，怎么找到？通过页号到Span的映射找。

因为，我们已经拿到central_cache归还到page_cache的Span,其中有存储页号和这个Span所对应的存储空间包含的页数，所以我们可以拿到Span前页的页号，也可以拿到Span后页的页号。

这里又产生两个问题：
第一个问题是：Span前页的页号和后页的页号，如果有，是什么时候存储到相应哈希结构中，甚至Span自身的页号又是什么时候存储进去的？
第二个问题是：怎么就能确定前页和后页就能合并，万一前面或后面的页是分配出去的Span呢？

对于第一个问题，实际上页号存储到哈希结构中，是page_cache申请时就完成的逻辑。对于分配出去的Span,它的每一页都要记录映射(这是肯定的，因为分配出去的Span，会涉及到小内存块找Span的问题，而小内存块，可能会分布在这个Span的任意一个页中)。
如果分配出去的Span是切分得到的，那么必然存在切分剩下的，未分配的Span,对于这个Span，我们只需记录首位页号到哈希结构中即可，因为这个Span如果不分配出去，那么往往用来做页合并，如果分配出去，那么会重走映射逻辑，无需担忧。

对于第二个问题，实际上要解决的是，如何判断一个Span可以进行合并。这时，可能会想到use_count,但即便use_count为0，代表未使用，也不一定能合并，因为可能是分配出去，但未使用。所以，使用use_count进行甄别是不行的，我们需要引入在Span中引入一个额外变量，来确定该Span是否被分配出去。

解决了上述两个问题后，就可以开始前后页合并逻辑。

可以先进行前页合并，再进行后页合并，二者的逻辑基本一致，且都需要循环合并。

1. 首先，根据页号找到相应Span,如果有，则继续；没有，则退出。
2. 其次，判断这个Span是否被分配出去；如果没有，则继续合并逻辑；有，则退出。
3. 然后，判断合并后，总共的页大小是否超过page_cache中设定的128页,即128 * 8 KB 的上限，如果超过，则不合并；否则，继续合并逻辑。
4. 最后，进行真正的合并逻辑。将这个页合并到Span中，相应的需要更改Span中的信息，合并都需要更改页大小，但是只有前页合并需要更改Span中的起始页id。然后，需要更改哈希结构中的相应映射，实际前页合并，只需要更改起始页id映射，而后页合并，只需要更改结尾页id映射。 最后，将被合并的Span从相应的SpanList中删除即可，因为其所管理的大块内存已被合并，交由其它Span管理。

最后，完成前后页合并后，需要将最终合并出的Span,需要重新插入到相应的SpanList当中，然后再将这个Span的是否分配情况赋值为false,即未分配。

4.4 释放接口的模块位置及page_cache中的细节问题

4.4.1 释放接口的模块位置分析

首先，我们明确共有两个释放接口：1个是从thread_cache释放到central_cache,1个是从central_cache释放到page_cache。

先说结论，从thread_cache到central_cache的释放，应该作为ReleasetoCentral放在central_cache模块中，因为该接口，不仅仅要完成thread_cache到central_cache的释放，这个释放过程本身需要加上central_cache的桶锁，还可能涉及central_cache是否要释放到page_cache的逻辑判断，因此涉及对central_cache中SpanList的直接操作，因此放在central_cache中是最合理的。

那么，此时自然ReleasetoPage就应放在page_cache模块中,这个释放接口中的所有操作，都需要在加上page_cache的一把大锁的前提下完成，以保证线程安全。

也正因为ReleasetoPage接口放在page_cache模块中,而这个接口中，涉及到大量的使用哈希结构的操作，包括增删查改，因此，我们将哈希结构设计在page_cache模块中，提供查询接口，供外部使用。

4.4.2 page_cache中的细节问题

page_cache中有两个细节问题值得说一说。

第一个细节问题是，在前后页合并中，对于被合并的页，如果是前页合并，我们只修改起始页对应的映射即可，而如果是后页合并，我们则修改末尾页对应的映射即可。
这是为什么呢？被合并的页，其它页映射，如果存在的话，不需要修改吗？
我们要明确的是，进行页合并之后，最终得到的完整页，可能会参与两件事，一件是与其它Span合并，一件是再次被分配出去。对于前者，如果是被前页合并，只需要用到末尾页id映射，被后页合并，只需要用到起始页id映射，即这个Span仅需要管理好首位映射即可。对于后者，无论是直接分配，还是切割再分配，都会对分配出去的页重写页id映射，即便是切分剩下的Span,也会对可能需要用到的首尾页映射进行重写，故无需担心。

page_cache中的第二个细节问题是，可不可以在进入ReleasetoPage逻辑，彻底完成前后页合并前，就将相应Span是否被分配的变量更改为false?

答案是不行。这样会带来严重的并发问题。为什么？因为如果此时有别的Span在进行前后页合并，而更改为false的这个Span刚好又是在进行合并逻辑Span的前后页Span,那么它就会被合并。而此时这个被合并的Span又会进入合并其它Span的逻辑中，那么这整个逻辑就完全出问题了，存在严重的并发问题。

因此，一定要在彻底完成合并逻辑后，将相应的Span放到相应的SpanList中管理起来，然后再将其修改为未分配状态。

5. 项目深入思考

5.1 tcmalloc三重缓存的设计哲学

首先，为什么要有缓存，缓存本质就是为了提高效率而引入的结构。
tcmalloc的三重缓存也就是为了提高在多线程并发场景下效率而引入的：

1. thread_cache缓存：每个线程独享,可以实现无锁高速访问。
2. central_cache缓存：所有线程共享，但使用桶锁，而非一把粗粒度的大锁，也是在多线程并发场景下的优化。
3. page_cache缓存：page_cache缓存使用一把粗粒度的大锁，但在实际场景中，由于多层缓存，因此访问page_cache的频率也是较低的；page_cache也是唯一会使用系统调用申请内存的模块，一次系统调用，就申请大块内存，然后在用户层面进行切分与分配，也能减少系统调用次数。

page_cache是必要的，因为是直接通过系统调用申请内存模块；而central_cache也是必不可少的,否则page_cache需要额外维护central_cache的逻辑，使得一个模块过于臃肿，模块的划分欠佳；而thread_cache在多线程并发场景下更是不可或缺的，每个线程独享的设计，大大提高并发效率。

所以,tcmalloc中三层缓存的设计是非常优秀的，模块化与解耦合的设计非常好，模块内部的逻辑设计以及模块之间的联系设计都是合理且自洽的，最终使得tcmalloc在多线程高并发场景下具有卓越性能。

5.2 内存对齐的原因探究

tcmalloc的设计中，用户申请的内存都经过内存对齐，那么为什么要内存对齐，为什么不申请一大块内存，然后按照用户要求进行任意切分呢？

首先，要肯定，这样的逻辑是可以实现的，但是存在诸多问题：

1. tcmalloc设计不支持。 本身tcmalloc的设计就无法支持任意切分。因为tcmalloc中的thread_cache和central_cache中采用哈希桶结构，如果任意切分，那么将有无数个哈希桶，这显然是不切实际的。
2. 任意切分本身设计与实现的困难。而如果舍弃tcmalloc设计，设计可以进行任意切分的内存池，不谈别的，由于大块内存是被任意切分的，而不是如tcmalloc中根据内存大小合理区分，会导致申请时比较简单，但是归还逻辑就很难设计与实现。
3. 内存碎片问题。由于在任意内存切分的场景下，就不可能在内存的划分与切分上做到tcmalloc中那样的细粒度， 这就会导致更加严重的内存外碎片问题，
   导致某些情况下，一块连续的大内存空间就无法申请出来，就需要重新调用系统调用，造成时间与空间上的双重浪费。而tcmalloc由于自身内存对齐外加哈希桶的设计，内存的使用划分上足够细粒度，能够在释放内存的过程中，执行小页合并大页的逻辑，而有效减少内存的外碎片问题。虽然，内存对齐会产生内碎片问题，但是设计对齐范围和对齐数时，就尽可能使得内碎片占比减少，以较少的内存内碎片代价，去减轻内存外碎片问题，这是可以接收的。

5.3 alloc与free的进一步优化

现在的alloc，由线程向thread_cache申请空间,thread_cache向central_cache中申请空间时，遵循慢增长原则，那么还可以从哪些方面做优化呢？

首先，对于慢增长，如果频繁申请同一大小内存，或对齐后在同一个哈希桶中的内存，那么可以调快慢增长的速率。
而如果申请的内存跨度范围比较大，从小到大，各种大小内存都有，可以调整哈希桶的个数，因为哈希桶过多的话，那么初始化的成本是很高的，第一次申请时，必然带来central_cache和page_cache的访问，所以可以在合理的情况下，采用更加激进的对齐策略，缩小哈希桶的个数，减少初始化成本。
或者也可以采用热加载的方式，程序启动时，thread_cache就进行所有桶，或者一些桶的初始化工作，减少实际申请时的消耗。

那么free可以做哪些优化呢？
我们现在的free策略，释放内存到thread_cache中，采用高低水位和延迟系数进行优化，调节这些参数进一步优化free效果自不必多说，我们来讲一讲关于page_cache中那个使用页号映射到Span的哈希结构。

首先，在我们一开始的设想中，这个结构使用C++的stl中的unordered_map就可以轻松搞定，但是stl容器的设计理念是高效率，在多线程环境下并不安全，需要加锁进行访问。

由于page_cache的相关接口中，基本都会涉及对unordered_map的访问，这是用一把大锁进行保护，而对外提供unordered_map的查询接口，同样需要是用这把大锁进行保护，那么此时，由于在释放逻辑中unordered_map会被频繁访问，那么关于这把大锁的竞争就过于激了，导致释放逻辑效率太低，因此我们不能是用unordered_map作为哈希结构。

tcmalloc的设计中，引入了radix tree，即基数树这种结构作为unordered_map的优化。
基数树，是什么？讲得简单点，基数树首先是一棵多叉树结构，叶子结点的定位是通过其所对应的数的位数层层划分进行定位的——即基数树是通过一个数bit位上的值划分，实现多层索引而快速定位的多叉树结构。

tcmalloc的设计中，设计了三种基数树，分别对应层级1到层级3，层级1，2的基数树是专门用于32-bit操作系统的；而层级3的radix tree则用于64-bit的操作系统。

在32位系统下，虚拟地址空间不过2³²个，表示成页号，就是2¹⁹个，使用下标进行映射，存储数据是一个指针，最终也就是2MB空间，因此32位系统下，这个基数树的所有空间映射，本质是可以直接开好的。

对于,level1的radix tree,就是直接映射，开了2MB空间；而对于level2的radix tree，则是开了两层，第一层使用2¹⁹中的高五位进行划分，一共是32个，对应32片叶子，然后32片叶子中分别再开剩下的2¹⁴个空间用以映射。

level2 radix tree中，就没有采用直接映射，而是两层映射，这种设计允许实际使用时，按需分配使用，即实际需要用到时，再把相应的叶子动态开辟出来。不过，一次性全开出来，也就是2MB左右的空间，完全可以不采用按需分配策略。

在64位系统下，首先，我们得明白一点，此时虚拟地址的空间远超实际物理内存空间，我们是绝不可能一次性把所有的空间都开出来，因为此时页号就已经由2⁵¹个。而由于可能存在的庞大页号个数，我们设计radix tree时，必然要采用按需分配的策略，即不能直接映射，需要采用层状设计。但是，这么多的页号，如果仅采用两层，那么划分过于粗粒度，空间消耗很大，因此采用三层映射，进行相对较细粒度的划分，比如在我们的仿tcmalloc设计中，我们采用了15，15，21的划分设计，然后采用按需分配策略，实际使用时，如果发现相应映射下为空，再动态分配空间。

这样，三层的基数树就能合理完成64-bit系统下的映射工作。
需要说明的时，三层基数树，为什么选择为3，以及三层每层分别对应多少位数，这些参数的设计都是有讲究的，划分不能过于粗粒度，否则空间消耗太大；同时也不能过于细粒度，因为根据空间的局部性原理，实际动态开辟内存范围的虚拟映射，也往往会较为集中，如果过于细粒度，反倒会导致频繁初始化的问题。

引入radix tree作为优化后，由于level-1和level-2的空间都已经完全开辟好，同时由于内存池在多线程中本身逻辑自洽性，一块内存映射，一个线程在查询时，不可能存在另一个线程在修改，因此这两个等级的基数树，增删查改，完全不用加锁，大大提高了并发能力。

而对于level-3的基数树，查询时不需要加锁，增添时需要加锁，因为涉及到按需分配的问题，不能出现多个线程同时检测到某个位置为空，然后申请空间的情况。不过radix tree可以使用自身细粒度的锁，而不用page_cache的一把大锁，因此并不会太影响并发效率，而且由于radix tree本身的使用消耗是很小的，即便直接使用page_cache大锁进行加锁，也没有太大关系，反倒是radix tree引入自身细粒度锁，而导致频繁加锁解锁，反倒带来额外消耗，影响效率。

5.4 tcmalloc的高效与退化

首先，我们要明确一点，这世界上没有任何东西是十全十美的。
tcmalloc似乎是完美的，在各方面性能都超越malloc，但实际上，tcmalloc是有它的高效场景，而在某些场景中,tcmalloc也会退化与malloc效率近似，甚至不如malloc。

下面，我们从三个方面，来讲tcmalloc的高效与退化。

1. 申请内存大小方面。tcmallo对于小内存申请，效率是很高的，因为小内存申请,thread_cache中缓存多，可以不用频繁访问另外两级缓存;而对于大内存申请，tcmalloc会发生退化，首先是大内存本身需求量不多，因此tcmalloc设计时，thread_cache中，对于大内存的缓存很少，如果频繁发生大内存申请，就需要频繁访问central_cache和page_cache效率太低；而如果是更大的内存申请,那么tcmalloc会直接访问page_cache,甚至直接调用系统调用，这些都是tcmalloc很难优化的地方，消耗是非常大的。
2. 多线程方面。tcmalloc是专为多线程设计的，而在单线程，乃至线程数很少的情况下，锁竞争本身就不多，tcmalloc的三层缓存设计，就无法带来太多优化，效率会退化到与malloc近似，或者略优。
3. 频率与生命周期。tcmalloc最期望的场景，便是基本不访问central_cache和page_cache,申请与释放的逻辑几乎完全在thread_cache中循环交互，这是效率最高的情况。如果，使用tcmalloc对于某个范围的内存频繁申请，申请后又快速释放，既保证内存申请高频率，短生命周期，那么tcmalloc优势明显；而如果内存申请，并不高频率，也就无法稀释第一次申请时的高消耗，非短生命周期，也就无法在thread_cache中进行快速循环，效率自然会退化。

所以，总结一下就是，tcmalloc适用于申请小内存，多线程高并发，内存申请高频率，短生命周期的应用场景，在这些场景中,tcmalloc效率将远优于malloc。

5.5 定长内存池的引入

为什么要引入定长内存池？

首先，本身tcmalloc就是一个内存池项目，其中自身会涉及到动态内存的申请，而且多是一些定长，即类对象的开辟。既然本身是内存池项目，就不希望再使用malloc/new,因此引入定长内存池进行这些类对象的内存开辟。

定长内存池，本质也是内存管理的池化技术，即先通过系统调用申请一大块空间，然后在将这块空间，按照定长分配出去使用，内存归还时，插入到定长内存池中的自由链表结构中，申请内存空间时，优先看自由链表中的内存块。如果自由链表为空，则从申请的大块内存中分配空间。而如果大块内存没有剩下空间，或者空间不够(允许一定的内碎片)，则由定长内存池通过系统调用再申请一大块内存空间用以使用。

引入定长内存池后，即可替换掉tcmalloc中，本身需要使用到new/malloc的地方，从而真正替代new/malloc。

6. 源码

gitee仓库源码

在文章最后，附上博主个人的gitee仓库高并发内存池源码链接，有需要的读者可自行查看使用，如果觉得有价值的话，可以star收藏一下。