“用TCMalloc或者jemalloc比自己实现的可能好十到一百倍”

TCMalloc

优点：快、减少了多线程程序中的锁争用情况、小对象的空间最优表现形式

跨度（Span）

TCMalloc管理的堆由一系列页面组成。连续的页面由一个“跨度”（Span）对象来表示。由页面号索引的中央数组可以用于找到某个页面所属的跨度。

(跨度a占据了2个页面，跨度b占据了1个页面，跨度c占据了5个页面最后跨度d占据了3个页面)

在一个32位的地址空间中，中央阵列由一个2层的基数树来表示，其中根包含了32个条目，每个叶包含了 2^15个条目（一个32为地址空间包含了 2^20个 4K 页面，所以这里树的第一层则是用2^5整除2^20个页面）。这就导致了中央阵列的初始内存使用需要128KB空间（2^15*4字节），看上去还是可以接受的。

在64位机器上，我们将使用一个3层的基数树。

其中基数树是什么?

Linux基数树（radix tree）是将指针与long整数键值相关联的机制，它存储有效率，并且可快速查询，用于指针与整数值的映射（如：IDR机制）、内存管理等。

Linux radix树最广泛的用途是用于内存管理，结构address_space通过radix树跟踪绑定到地址映射上的核心页，该radix树允许内存管理代码快速查找标识为dirty或writeback的页。Linux radix树的API函数在lib/radix-tree.c中实现。

radix树是通用的字典类型数据结构，radix树又称为PAT位树（Patricia Trie or crit bit tree）。Linux内核使用了数据类型unsigned long的固定长度输入的版本。每级代表了输入空间固定位数。

radix tree是一种多叉搜索树，树的叶子结点是实际的数据条目。每个结点有一个固定的、2^n指针指向子结点（每个指针称为槽slot），并有一个指针指向父结点。

Linux内核利用radix树在文件内偏移快速定位文件缓存页，图4是一个radix树样例，该radix树的分叉为4(22)，树高为4，树的每个叶子结点用来快速定位8位文件内偏移，可以定位4x4x4x4=256页，如：图中虚线对应的两个叶子结点的路径组成值0x00000010和0x11111010，指向文件内相应偏移所对应的缓存页。

Linux radix树每个结点有64个slot，与数据类型long的位数相同，图1显示了一个有3级结点的radix树，每个数据条目（item）可用3个6位的键值（key）进行索引，键值从左到右分别代表第1~3层结点位置。没有孩子的结点在图中不出现。因此，radix树为稀疏树提供了有效的存储，代替固定尺寸数组提供了键值到指针的快速查找。

大对象的分配

一个大对象的尺寸(> 32K)会被除以一个页面尺寸（4K）并取整（大于结果的最小整数），同时是由中央页面堆来处理的。中央页面堆又是一个自由列表的阵列。对于i < 256而言，第k个条目是一个由k个页面组成的自由列表。第256个条目则是一个包含了长度>= 256个页面的自由列表：

k个页面的一次分配通过在第k个自由列表中查找来完成。如果该自由列表为空，那么我们则在下一个自由列表中查找，如此继续。最终，如果必要的话，我们将在最后一个自由列表中查找。如果这个动作也失败了，我们将向系统获取内存（使用sbrk、mmap或者通过在/dev/mem中进行映射）。

如果k个页面的一次分配行为由连续的长度> k的页面满足了，剩下的连续页面将被重新插回到页面堆的对应的自由列表中。

其中内存共享机制mmap是什么?
共享内存可以说是最有用的进程间通信方式，也是最快的IPC形式, 因为进程可以直接读写内存，而不需要任何数据的拷贝。（unlike管道和消息队列）并且共享内存中的内容往往是在解除映射时才写回文件的。因此，采用共享内存的通信方式效率是非常高的

UNIX访问文件的传统方法是用open打开它们,如下图两个进程同时读一个文件的同一页的情形，每个进程都要再执行一个存储器内的复制操作将已经被从磁盘读到高速缓冲区的数据再读到自己的地址空间

而mmap()系统调用使得进程之间通过映射同一个普通文件实现共享内存。普通文件被映射到进程地址空间后，进程可以向访问普通内存一样对文件进行访问，不必再调用read()，write（）等操作。

mmap()系统调用形式如下：
void mmap ( void addr , size_t len , int prot , int flags , int fd , off_t offset )
mmap的作用是映射文件描述符fd指定文件的 [off,off + len]区域至调用进程的[addr, addr + len]的内存区域, 如下图所示:

参数解释：

(参数fd为即将映射到进程空间的文件描述字，一般由open()返回，同时，fd可以指定为-1，此时须指定flags参数中的MAP_ANON，表明进行的是匿名映射（不涉及具体的文件名，避免了文件的创建及打开，很显然只能用于具有亲缘关系的进程间通信）。
len是映射到调用进程地址空间的字节数，它从被映射文件开头offset个字节开始算起。
prot 参数指定共享内存的访问权限。可取如下几个值的或：PROT_READ（可读） , PROT_WRITE （可写）, PROT_EXEC （可执行）, PROT_NONE（不可访问）。
flags由以下几个常值指定：MAP_SHARED , MAP_PRIVATE , MAP_FIXED，其中,MAP_SHARED , MAP_PRIVATE必选其一，而MAP_FIXED则不推荐使用。
offset参数一般设为0，表示从文件头开始映射。
参数addr指定文件应被映射到进程空间的起始地址，一般被指定一个空指针，此时选择起始地址的任务留给内核来完成。函数的返回值为最后文件映射到进程空间的地址，进程可直接操作起始地址为该值的有效地址。)