go语言内存分配之TCMalloc

tcmalloc

tcmalloc 优点

• 速度更快，比glicbc 2.3 快
• 占用更少的内存空间，8倍8-byte的对象内存分配中占用大约8N*1.01byte的头空间，而ptmalloc则会占用16N*byte的头空间

使用

• 在程序中只需使用“-ltmalloc”连接标识将其链接到程序中

综述

• TCMalloc为每一个线程分配本地缓存，以满足小对象分配的需求，当需要时候，对象从中央数据结构移动到本地缓存，周期性的垃圾回收则将内存从各个线程的本地缓存收回中央数据结构。
  

小对象分配

• 每个小对象映射到170个不同的大小空间。每个空间间隔8byte，0-8byte（8），8-24byte（16），24-48byte（24），最大间隔为256byte。大对象和小对象的界限为32kb。每个线程的缓存包括一系列大小不同的空闲对象连接到一起的链表。
  
• 分配一个小对象时
  
  1. 先由其大小映射到对应的空间集合
  2. 查找当前线程线程缓存空闲的链表
  3. 若果空闲的链表非空，则取出第一个对象返回给调用者，通过这样获取空间时，TCMalloc不需要加锁。加锁和解锁这一对操作在2.8 GHz Xeon处理器上会占用100纳秒的时间，因此这样的机制可以很有效的加速内存分配的效率。
  4. 若链表为空，则从中央空闲链中取出一些对象填充到对应的集合中（中央空闲链对所有线程共享）。
  5. 将其放到线程本地的空闲链
  6. 返回这些新对象给调用程序。
  7. 如果中央缓存区空闲链也为空；
  8. 向中央页分配器申请连续的页
  9. 把页分割为一系列大小不同的对象
  10. 把这些对象放入中央空闲链表
  11. 把其中而一些对象放入线程本地缓存。
      

大对象分配

• 一个大对象的大小（大于32K）要向上按照页大小（4K）对齐，并且是由中央的页面堆来处理。中央页面堆同样也是由一些不同大小的元素的链表组成的数组。对于i小于256，数组中第k的入口，是由k个页组成的元素所链接在一起的空闲链表。第256个入口是由长度大于256个页链接在一起的空闲链表。
  
• 一个需要k个页面大小的分配请求，可以通过访问第k个空闲链表来满足。如果该空闲链表为空，我们就访问下一个空闲链表（页面大一些的），以此类推。最终，如果需要的话我们会访问最后一个空闲链。如果这一系列的查找都失败的话，我们将从系统中得到内存（使用sbrk,mmap或者通过映射一部分/dev/mem）。如果一个k页面大小的分配请求分配到的内存空间大于k个页面，当该空间释放的时候需要放回到页面堆中相应大小的空闲链表中。

Spans

• TCMalloc的堆管理机制是将一些页面集合，一组连续的页面的结合称为一个span对象。span既可以被分配也可以被释放。如果被释放，span将会被放到对应的页面堆链表。如果被分配，span可以是一个交给应用程序的大对象，或者是一组被分割成连续小对象的页面。如果是被分割成为小对象，那么在span中会记录对象的大小级别。中央数组的页号索引，能够用于实现找到一个Span由哪些页面组成。举例来说，下图的span a占有2个页面，spanb占有1个页面，span c占有5个页面，而span d占有3个页面。
  
• 一个32位的地址空间能够分配2^20个4K的页面，因此中央数组占据4MB的内存空间是可以令人接受的。在64位的机器上，我们使用3级的基树来代替数组，用于映射页号与对应的span指针。

对象释放

• 对象释放时，计算器页好并在中央数组查找其对应的span。span中包含对象的信息，可以得知对象是否为小对象。如果是小对象，则放回线程缓存的空闲链表中。如果线程的缓存超出预定大小（默认2MB），则运行垃圾收集器把当前线程不用的对象放回central的freelist。
• 如果释放对象是大对象，通过span可以获取对象包含页范围。通过页范围查找范围的上下限，如果上下限的页也为空闲的，则将其一起放到heap的页管理器中。

小对象中央空闲链

• 每一个中央空闲链包含二级数据结构：一系列的span以及span中的空闲对象组成的空闲链表。
• 中央空闲链表分配对象时，通过移动某个span的链表到第一个对象实现的，如果所有spa都有空闲的链表，则选择大小合适的span进行分配。
• 一个对象返回到中央空闲链，是通过将其挂到span所属的链表中实现的。若链表的长度与span中所有的小对象的个数完全相等，该span是完全空闲的，并且需要返回到页堆中。

线程缓存垃圾回收

• 当线程缓存中所有空闲对象的带下超过2MB的时候，垃圾回收期会自动进行回收，线程数增加时候，垃圾回收的阈值会减少以避免内存的浪费。
• 我们遍历缓存中的所有空闲链表，从中移动一定数量的对象到对应的中央链表中。每个链的低水位标记L决定了从空闲链中移出对象的数量。L记录了自从上一次垃圾收集操作之后本链的最小长度。注意我们可以缩短链的长度，通过在前一次垃圾收集时移走L个对象，并且没有从中央链中获取其他对象。我们使用这个过去的记录来预测未来的情况，从线程缓存中移走L/2个对象到中央链中。这个算法性能良好，如果一个线程停止使用某个特定大小的对象，该大小的所有对象将会很快的从线程缓存中迁移到中央空闲链中，以便被其他线程来使用。

参考内容