Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1375018
  • 博文数量: 317
  • 博客积分: 1557
  • 博客等级: 上尉
  • 技术积分: 1208
  • 用 户 组: 普通用户
  • 注册时间: 2008-02-26 23:38
个人简介

如果想出发,就不要等到明天!

文章分类

全部博文(317)

文章存档

2016年(1)

2015年(41)

2014年(152)

2013年(114)

2012年(4)

2011年(1)

2009年(4)

分类: C/C++

2014-09-23 20:52:26

对于C/C++开发者,想要开发一款高性能、高稳定性的程序,最重要的问题之一就是内存管理

通常我们会使用malloc(什么,你说newnew是封装malloc的了)来分配内存,并把内存管理交给系统去做。

但是malloc的性能真的够用吗?为什么很多著名开源服务器都会自己写一套内存管理器?如果老板要我优化架构,要不要考虑把malloc给废了?


一 malloc寻根

linux下的malloc实现又叫ptmallocptmallocdlmalloc的一种变形,所以有些地方也会直接说成dlmalloc

当我们调用malloc时,根据申请的大小会分成截然不同的几种处理流程。小内存会进入“定长内存”系统;大内存则进入“变长内存”系统(备注1)。


“定长内存”系统会事先准备好(备注2)一系列空闲内存链表。链表中的空闲内存块都是一样大的。

  

分配内存时只需找到相应的链表,从链表头部取出一个空闲内存块即可。释放时也是直接插入即可。分配和释放的复杂度都是O(1)

虽然定长内存系统的分配和释放极快。但是在分配大块内存时,定长内存分配会导致大量内存碎片(内碎片),关于内存碎片分类和优化我们会在后续章节再讨论。


“变长内存”系统也会组织一系列空闲内存链表。链表中的空闲块通常是不一样大的:

 

在很早以前,变长内存只有1条链表,每次分配时需要遍历这个长长长长的链表以找到大小合适的内存块。

后来ptmalloc做了很多的优化,在分配速度上已经提升了很多。

变长内存会按照大小范围组织成很多个不同的链表,例如:

10K-15K属于链表1

16K-23K属于链表2

24K-39K属于链表3

.........

(数值是随手写的,真实数值请google largebin_index_64

通过分链表(或者叫分箱),每个链表的大小都会缩小很多。这样就能更快的查找到我们需要的size

总体来说,变长内存的性能比定长内存要差。分配时需要遍历会导致耗时增加,而且变长内存通常需要分裂内存块,会导致外碎片增加。


二 细节决定成败

从整体设计上来看,malloc做的相当好。

但是当我们深入一些关键的细节时,会发现malloc针对一些特殊场景,会出现很严重的问题

管理小内存块时浪费了大量的空间

每个内存块需要一个size_t的空间来存放本内存块的大小,供释放时使用。以64位机器为例,size_t8字节长的。而且内存块必须在2*size_t的长度上对齐。所以当我们malloc(26)时,实际消耗的内存是48字节,浪费了45%的内存。

另外内存块有一个最小大小4*size_t。在64位机器上,最小的分配单位就是32字节。当我们需要分配大量小结构体时,malloc会导致极大的内存浪费。

验证代码请参考附件中的mem_little.cpp


定长小内存和变长大内存容易交错混在一起

所有内存块都是从top内存区分出来的,并没有专门给不同尺寸的内存划分专属内存池,所以定长小内存有很大几率会和变长大内存交错混在一起。

这将使得小内存块随时可能和大内存块合并(合并后就走变长内存系统了),使得定长内存的优势大打折扣,malloc时的局部性也很不好


释放内存时可能因为brk而被卡住

malloc的主分配区是通过brk向内核申请内存的,非主分配区通过mmap模拟brk。而brk是一个线性的分配器,类似栈。

简单来说,如果我先malloc5G内存;再malloc 16字节,抓住这16字节不释放;然后释放前面的5G内存,这5G内存是无法还给系统的。

验证代码请参考附件中的mem_brk.cpp

malloc的这个特性对于需要长期持有而不释放的内存是极其不友好的。而且一旦出现内存泄漏,哪怕只漏了几个字节,也可能把几个G的内存释放卡住。


锁的性能消耗

ptmalloc的内存分配区不是和线程绑定的,所以必须在进入mallocfree时加一把大锁(针对单个分配区的锁)。虽然可以通过建立多个分配区和try_lock来降低等待锁的几率,但是锁本身也是很消耗性能的


低效的realloc

当需要扩大已分配的内存块时,ptmalloc将尝试从尾部扩展内存块。但是当系统内存压力较大时,这个尝试的成功率是不高的,这时就需要分配一个全新的内存块并把旧数据拷贝过去,而这将引入极其巨大的性能消耗(备注3)。


三 我们的目标

技术是为需求服务的。我之所以追求性能优化,是因为当时公司的硬件成本占总销售收入的30-40%,而公司的净利润只有10-15%

对于某些土豪行业来说(别躲了,手游,说的就是你),硬件成本只有不到5%的,就不要花太多精力去优化性能了。


我们做的是一款http正向缓存代理服务器,约等于带强大缓存功能的nginx

具体目标是在一台816G内存的机器上承载每秒4Gbhttp流量,100万并发连接。

我们需要缓存整个互联网,所以需要上亿个10字节的结构体来存储url信息;另外还需要处理每秒4Gbhttp socket数据,并尝试进行缓存写入和读出。

在连接建立时我们是不知道每个连接需要多大缓冲区的,这就需要大量的realloc来扩大已有缓冲区。

当用户下载1GB的文件时,原始服务器先将1GB文件发给我们,我们再转发给用户,这将持续相当长的一段时间。在这个过程中,我们可以把已转发给用户的部分内存先释放掉,但是可惜malloc不支持部分free


总结成一句话就是:我们需要一个内存利用率极高的定长小内存系统和一个支持“高效realloc”和“一次malloc可分为多次free”的变长大内存系统


四 内存系统设计的一般原则 

在设计内存管理系统时,我们主要关心三个方面:

内存利用率

分配和释放效率

局部性


内存利用率方面主要是三个问题:

内碎片:分配内存时,分配出的内存大于需要的内存叫内碎片。

例如ptmalloc中,需要8字节对齐,再加上8字节管理信息,这一部分就是内碎片(很多论文中不把管理信息算到内碎片中,而是单独计算,个人喜欢合在一起计算,方便)

如果对大内存块采用定长内存系统,前后两个定长内存块之间的大小会差的较大,从而产生较大的内碎片。这也是为什么绝大多数内存管理系统,仅对小内存块使用定长内存。


外碎片:因为空闲内存块太小导致有内存又无法分配叫外碎片

如下图,经过长时间malloc-free后,空闲内存(绿色)被分隔到成很多小碎片,就无法再malloc出大块内存了

外碎片主要是由于把变长的大内存块分裂成两个内存块而导致的。例如空闲内存块为900K,我们需要分配875K,剩下的25K被分裂出来后,就会形成外碎片


无法还给系统:在上一节中已经举例说明过这个问题,free将内存还给内存管理器后可能无法归还给系统,导致其它进程分配内存失败

分配释放效率:

定长分配和释放往往都是O(1)的效率

变长内存分配则通常需要遍历链表来找到大小合适的内存块。通常会通过按大小范围分箱来提高分配速度。

如果定长内存和变长内存交错在一起,定长内存会经常和变长内存合并,使得定长内存的优势体现不出来。

另外我们还可以为每个线程分配一个专属的线程池,可以避免加锁解锁的消耗。

局部化:

最近20年来,CPU速度提升了上万倍,内存提升了上百倍,硬盘速度提升仅有几倍,所以优化性能的关键,很多时候都不在于减少CPU的运算压力,而在于减少内存总线读写

通过提升内存的局部化,可以大幅优化CPUcache效果,提高运行效率

验证代码请参考附件中的mem_cache.cpp


五 slab定长内存池 

linux内核采用的slab算法是一个极好的定长内存管理算法

通过将若干个小定长内存集中在一个桶里,我们就不必为每个内存块维护独立的管理信息了。当我们需要读取管理信息时,对内存块取模取到桶的头部,就可以读到相关管理信息了。

同时,这还将极大的减少定长内存和变长内存交错的情况,提升分配和释放效率。

要让slab达到最高效率,我们需要事先对slab系统进行初始化,声明我们需要用到定长内存块大小(通常是某个频繁使用的struct/class),最好还能手动设定一下桶的大小。这也是为什么malloc不采用slab算法的原因。


六 大内存支持非连续化 

非连续化,即我们不再要求指针指向一段连续内存。例如在传统情况下,一个10MB的缓冲区必须是连续10MB的虚拟地址。而非连续化之后,一个10MB的缓冲区可以由若干个4K的虚拟页拼接而成。

通过支持非连续内存,我们将变长内存池的问题转化成了定长内存的问题,大内存使用过程中碰到的几个最主要问题,都已经解决了。

因为所有内存块都是定长的,我们不再会有任何外碎片的问题,跑上100年也不会有外碎片。

内碎片有可能会较多,这取决于我们对内存块大小的控制。

通过实际测试,对http代理来说,采用4K512两级内存块就可以达到90%以上的内存利用率。


realloc重分配问题上有着极高的性能。我们随时可以从已分配内存的头部释放内存(代理服务器已转发数据的释放),也随时可以在已分配内存的尾部追加内存。


非连续内存有一个极大的缺陷:无法用常规的strcmpmemcpy系列函数处理;也无法转换成string;使用时一不小心就会踩内存。必须提供一系列函数对非连续内存池进行处理,例如jump_get_next来获取下一个字符并自动判断是否需要跳到下一个内存块。

08年阅读nginx代码时,发现nginx就已经实现了一套非连续内存池的代码,但是并没有发现任何代码在使用这个非连续内存池。对于开源这样人员多变的开发环境,确实不太适合使用非连续内存池;但是对于人员稳定性和素质有保障的商业公司,完全可以尝试用非连续内存来提升性能。   

备注1

实际上ptmalloc会按大小维护5个级别的分配算法:

fastbinsmallbinlargebintopmmap

fastbin:最小的内存空闲块,属于定长内存。

smallbin:大于等于fastbin,也属于定长内存。

有一些最小的内存块,即可以属于fastbin也可以属于smallbin(优先从fastbin分配,当fastbin为空时走smallbin逻辑)

fastbinsmallbin最大的区别在于fastbin的合并更lazy一些,系统中更容易留下未被合并的fastbin;而smallbin更容易被合并掉(合并指当两个相邻内存块都是空闲时,合并成一个大的空闲内存块)

largebin大于smallbin,属于变长内存,包含大量的内存块链表,每个链表覆盖一个长度范围

top内存:top内存只有一个块,所有从内核brk上来的内存(非主分配区会通过mmap模拟brk)都会先放在这里,再分配给前面的3种内存块。当从上述3种内存块释放内存时,也必须先合并到top之后才能还给内核

mmap内存:大于一定大小的内存会直接通过mmap从内核获取,释放时直接unmmap还给内存。


备注2

实际上这里有一个lazy的机制。

第一次malloc时并没有事先准备好的定长内存,此时需要从更高层的内存块中(例如largebintop),速度较慢。

free时,如果大小属于fastbin会直接放入定长内存池中。如果属于smallbin,在尝试和相邻内存块合并失败时,也会放入定长内存池。

在经过一段时间的mallocfree之后,如果没有触发大量的合并,我们就可以幸运的拥有一个快速的定长内存池了


备注3

在不同的系统中,性能的瓶颈是不一样的。在我们的http代理服务器中,CPU消耗比例大概是:

应用层消耗        5%

    Tcp协议栈 20%

    copy_to_user 20%

    网卡驱动 15%

    其它内核函数 40%

可以看到copy_to_usercopy_from_user加起来占了20%CPU。这两个内核函数属于recvsend的内核实现,负责在内核和应用层间拷贝socket数据。

换句话说,如果我们通过realloc将所有socket缓冲区拷贝了一遍,就会增加约20%性能消耗

验证代码压缩包:

 mem_test.zip

阅读(638) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册