您的位置 首页 golang

内存优化-比glibc更快的tcmalloc

TCMalloc 是 Google 开发的内存分配器,在不少项目中都有使用,例如在 Golang 中就使用了类似的算法进行内存分配。它具有现代化内存分配器的基本特征:对抗内存碎片、在 多核处理器 能够 scale。据称,它的内存分配速度是 glibc2.3 中实现的 malloc的数倍。

之前在学习 Golang 内存管理的时候,发现 Golang 竟然就用了鼎鼎大名的 TCMalloc。我之前也喜欢写一些源码分析之类的文章,但渐渐发觉从源码出发虽然能够探究实现的细节,但这些东西更适合作为自己的学习笔记,如果要讲给别人,还是用一些更加可读的方式比较好。因此,这篇文章主要以看图说话为主,是为图解。

什么是TCmalloc

tcmalloc就是一个内存分配器,管理堆内存,主要影响malloc和free,用于降低频繁分配、释放内存造成的性能损耗,并且有效地控制内存碎片。 glibc 中的内存分配器是ptmalloc2,tcmalloc号称要比它快。一次malloc和free操作,ptmalloc需要300ns,而tcmalloc只要50ns。同时tcmalloc也优化了小对象的存储,需要更少的空间。tcmalloc特别对多线程做了优化,对于小对象的分配基本上是不存在锁竞争,而大对象使用了细粒度、高效的 自旋锁 (spinlock)。分配给 线程 的本地缓存,在长时间空闲的情况下会被回收,供其他线程使用,这样提高了在多线程情况下的内存利用率,不会浪费内存,而这一点ptmalloc2是做不到的。

tcmalloc区别的对待大、小对象。

tcmalloc将内存请求分为两类,大对象请求和小对象请求,大对象为>=32K的对象。

tcmalloc会为每个线程分配本地缓存,小对象请求可以直接从本地缓存获取,如果没有空闲内存,则从central heap中一次性获取一连串小对象。

tcmalloc对于小内存,按8的整数次倍分配,对于大内存,按4K的整数次倍分配。

当某个线程缓存中所有对象的总大小超过2MB的时候,会进行垃圾收集。垃圾收集阈值会自动根据线程数量的增加而减少,这样就不会因为程序有大量线程而过度浪费内存。

实际上tcmalloc为每个线程分配了一个线程局部的 cache ,线程需要的小对象都是在其cache中分配的,由于是 thread local 的,所以基本上是无锁操作(在cache不够,需要增加内存时,会加锁)。同时,tcmalloc维护了进程级别的cache,所有的大对象都在这个cache中分配,由于多个线程的大对象的分配都从这个cache进行,所以必须加锁访问。在实际的程序中,小对象分配的频率要远远高于大对象,通过这种方式(小对象无锁分配,大对象加锁分配)可以提升整体性能。

线程级别cache和进程级别cache实际上就是一个多级的空闲块列表(Free List)。一个Free List以大小为k bytes倍数的空闲块进行分配,包含n个 链表 ,每个链表存放大小为nk bytes的空闲块。在tcmalloc中,<=32KB的对象被称作是小对象,>32KB的是大对象。在小对象中,<=1024bytes的对象以8n bytes分配,1025<size<=32KB的对象以128n bytes大小分配,比如:要分配20bytes则返回的空闲块大小是24bytes的,这样在<=1024的情况下最多浪费7bytes,>1025则浪费127bytes。而大对象是以页大小4KB进行对齐的,最多会浪费4KB – 1 bytes。

如何分配定长记录

首先是基本问题,如何分配定长记录?例如,我们有一个 Page 的内存,大小为 4KB,现在要以 N 字节为单位进行分配。为了简化问题,就以 16 字节为单位进行分配。

解法有很多,比如,bitmap。4KB / 16 / 8 = 32, 用 32 字节做 bitmap即可,实现也相当简单。

出于最大化内存利用率的目的,我们使用另一种经典的方式,freelist。将 4KB 的内存划分为 16 字节的单元,每个单元的前8个字节作为节点指针,指向下一个单元。初始化的时候把所有指针指向下一个单元;分配时,从链表头分配一个对象出去;释放时,插入到链表。

由于链表指针直接分配在待分配内存中,因此不需要额外的内存开销,而且分配速度也是相当快。

相关视频推荐

学习地址:

需要C/C++ Linux服务器架构师学习资料加qun 812855908 获取(资料包括 C/C++,Linux,golang技术, Nginx ,ZeroMQ,MySQL, Redis ,fastdfs, MongoDB ZK ,流媒体, CDN ,P2P,K8S, Docker ,TCP/IP,协程,DPDK, ffmpeg 等),免费分享

如何分配变长记录

定长记录的问题很简单,但如何分配变长记录的。对此,我们把问题化归成对多种定长记录的分配问题。

我们把所有的变长记录进行“取整”,例如分配7字节,就分配8字节,31字节分配32字节,得到多种规格的定长记录。这里带来了内部内存碎片的问题,即分配出去的空间不会被完全利用,有一定浪费。为了减少内部碎片,分配规则按照 8, 16, 32, 48, 64, 80这样子来。注意到,这里并不是简单地使用2的 幂级数 ,因为按照2的幂级数,内存碎片会相当严重,分配65字节,实际会分配128字节,接近50%的内存碎片。而按照这里的分配规格,只会分配80字节,一定程度上减轻了问题。

大对象如何分配

上面讲的是基于 Page,分配小于Page的对象,但是如果分配的对象大于一个 Page,我们就需要用多个 Page 来分配了:

这里提出了 Span 的概念,也就是多个连续的 Page 会组成一个 Span,在 Span 中记录起始 Page 的编号,以及 Page 数量。

分配对象时,大的对象直接分配 Span,小的对象从 Span 中分配。

Span如何分配

对于 Span的管理,我们可以如法炮制:

还是用多种定长 Page 来实现变长 Page 的分配,初始时只有 128 Page 的 Span,如果要分配 1 个 Page 的 Span,就把这个 Span 分裂成两个,1 + 127,把127再记录下来。对于 Span 的回收,需要考虑Span的合并问题,否则在分配回收多次之后,就只剩下很小的 Span 了,也就是带来了外部碎片 问题。

为此,释放 Span 时,需要将前后的空闲 Span 进行合并,当然,前提是它们的 Page 要连续。

问题来了,如何知道前后的 Span 在哪里?

从Page到Span

由于 Span 中记录了起始 Page,也就是知道了从 Span 到 Page 的映射,那么我们只要知道从 Page 到 Span 的映射,就可以知道前后的Span 是什么了。

最简单的一种方式,用一个数组记录每个Page所属的 Span,而数组索引就是 Page ID。这种方式虽然简洁明了,但是在 Page 比较少的时候会有很大的空间浪费。

为此,我们可以使用 RadixTree 这种数据结构,用较少的空间开销,和不错的速度来完成这件事:

乍一看可能有点懵,这个跟 RadixTree 能扯上关系吗?可以把 RadixTree 理解成压缩过的 前缀树 (trie),所谓压缩,就是在一条路径上的节点都只有一个子节点,就把这条路径合并到父节点去,因此内部节点最少会有 Radix 个字节点。具体的分析可以参考一下 wikipedia 。

实现时,可以通过一定的空间换来时间,也就是减少层数,比如说3层。每层都是一个数组,用一个地址的前 1/3 的bit 索引数组,剩下的 bit 对下一层进行寻址。实际的寻址也可以非常快。

PageHeap

到这里,我们已经实现了 PageHeap,对所有 Page进行管理:

全局对象如何分配

既然有了基于 Page 的对象分配,和Page本身的管理,我们把它们串起来就可以得到一个简单的内存分配器了:

按照我们之前设计的,每种规格的对象,都从不同的 Span 进行分配;每种规则的对象都有一个独立的内存分配单元:CentralCache。在一个CentralCache 内存,我们用链表把所有 Span 组织起来,每次需要分配时就找一个 Span 从中分配一个 Object;当没有空闲的 Span 时,就从 PageHeap 申请 Span。

看起来基本满足功能,但是这里有一个严重的问题,在 多线程 的场景下,所有线程都从CentralCache 分配的话,竞争可能相当激烈。

ThreadCache如何分配

到这里 ThreadCache 便呼之欲出了:

每个线程都一个线程局部的 ThreadCache,按照不同的规格,维护了对象的链表;如果ThreadCache 的对象不够了,就从 CentralCache 进行批量分配;如果 CentralCache 依然没有,就从PageHeap申请Span;如果 PageHeap没有合适的 Page,就只能从操作系统申请了。

在释放内存的时候,ThreadCache依然遵循批量释放的策略,对象积累到一定程度就释放给 CentralCache;CentralCache发现一个 Span的内存完全释放了,就可以把这个 Span 归还给 PageHeap;PageHeap发现一批连续的Page都释放了,就可以归还给操作系统。

至此,TCMalloc 的大体结构便呈现在我们眼前了。

Tcmalloc总结

这里用图解的方式简单讲述了 TCMalloc 的基本结构,如何减少内部碎片,如何减少外部碎片,如何使用伙伴算法进行内存合并,如何使用 单链表 进行内存分配,如何通过线程局部的方式提高扩展性。

不过实现一个高性能的内存分配器绝非如此简单,TCMalloc 中有许多策略,许多参数,许多细节的考量,都值得我们深究。一篇文章难以覆盖,之后的文章再做详解: 如何在项目中使用tcmalloc, 如何使用tcmalloc查 内存泄漏

文章来源:智云一二三科技

文章标题:内存优化-比glibc更快的tcmalloc

文章地址:https://www.zhihuclub.com/100225.shtml

关于作者: 智云科技

热门文章

网站地图