posts - 14,  comments - 57,  trackbacks - 0
  昨天一个同事一大早在群里推荐了一个google project上的开源内存分配器(http://code.google.com/p/google-perftools/),据说google的很多产品都用到了这个内存分配库,而且经他测试,我们的游戏客户端集成了这个最新内存分配器后,FPS足足提高了将近10帧左右,这可是个了不起的提升,要知道3D组的兄弟忙了几周也没见这么大的性能提升。

如果我们自己本身用的crt提供的内存分配器,这个提升也算不得什么。问题是我们内部系统是有一个小内存管理器的,一般来说小内存分配的算法都大同小异,现成的实现也很多,比如linux内核的slab、SGI STL的分配器、ogre自带的内存分配器,我们自己的内存分配器也和前面列举的实现差不多。让我们来看看这个项目有什么特别的吧。

一、使用方法

打开主页,由于公司网络禁止SVN从外部更新,所以只能下载了打包的源代码。解压后,看到有个doc目录,进去,打开使用文档,发现使用方法极为简单:
To use TCMalloc, just link TCMalloc into your application via the "-ltcmalloc" linker flag.再看算法,也没什么特别的,还是和slab以及SGI STL分配器类似的算法。
unix环境居然只要链接这个tcmalloc库就可以了!,太方便了,不过我手头没有linux环境,文档上也没提到windows环境怎么使用,
打开源代码包,有个vs2003解决方案,打开,随便挑选一个测试项目,查看项目属性,发现仅仅有2点不同:
1、链接器命令行里多了
  "..\..\release\libtcmalloc_minimal.lib",就是链接的时候依赖了这个内存优化库。
2、链接器->输入->强制符号引用 多了 __tcmalloc。
这样就可以正确的使用tcmalloc库了,测试了下,测试项目运行OK!

二、如何替换CRT的malloc

从前面的描述可知,项目强制引用了__tcmalloc, 搜索了测试代码,没发现用到_tcmalloc相关的函数和变量,这个选项应该是为了防止dll被优化掉(因为代码里没有什么地方用到这个dll的符号)。
初看起来,链接这个库后,不会影响任何现有代码:我们没有引用这个Lib库的头文件,也没有使用过这个dll的导出函数。那么这个dll是怎么优化应用程序性能的呢?
实际调试,果然发现问题了,看看如下代码
    void* pData = malloc(100);
00401085 6A 64            push        64h 
00401087 FF 15 A4 20 40 00 call        dword ptr [__imp__malloc (4020A4h)]
跟踪 call malloc这句,step进去,发现是
78134D09 E9 D2 37 ED 97   jmp         `anonymous namespace'::LibcInfoWithPatchFunctions<8>::Perftools_malloc (100084E0h)
果然,从这里开始,就跳转到libtcmalloc提供的Perftools_malloc了。
原来是通过API挂钩来实现无缝替换系统自带的malloc等crt函数的,而且还是通过大家公认的不推荐的改写函数入口指令来实现的,一般只有在游戏外挂和金山词霸之类的软件才会用到这样的挂钩技术,
而且金山词霸经常需要更新补丁解决不同系统兼容问题。

三、性能差别原因

如前面所述,tcmalloc确实用了很hacker的办法来实现无缝的替换系统自带的内存分配函数(本人在使用这类技术通常是用来干坏事的。。。),但是这也不足以解释为什么它的效率比我们自己的好那么多。
回到tcmalloc 的手册,tcmalloc除了使用常规的小内存管理外,对多线程环境做了特殊处理,这和我原来见到的内存分配器大有不同,一般的内存分配器作者都会偷懒,把多线程问题扔给使用者,大多是加
个bool型的模板参数来表示是否是多线程环境,还美其名曰:可定制,末了还得吹嘘下模板的优越性。
tcmalloc是怎么做的呢? 答案是每线程一个ThreadCache,大部分操作系统都会支持thread local storage 就是传说中的TLS,这样就可以实现每线程一个分配器了,
这样,不同线程分配都是在各自的threadCache里分配的。我们的项目的分配器由于是多线程环境的,所以不管三七二十一,全都加锁了,性能自然就低了。

仅仅是如此,还是不足以将tcmalloc和ptmalloc2分个高下,后者也是每个线程都有threadCache的。
关于这个问题,doc里有一段说明,原文贴出来:
ptmalloc2 also reduces lock contention by using per-thread arenas but there is a big problem with ptmalloc2's use of per-thread arenas. In ptmalloc2 memory can never move from one arena to another. This can lead to huge amounts of wasted space.
大意是这样的:ptmalloc2 也是通过tls来降低线程锁,但是ptmalloc2各个线程的内存是独立的,也就是说,第一个线程申请的内存,释放的时候还是必须放到第一个线程池中(不可移动),这样可能导致大量内存浪费。
 

四、代码细节

1、无缝替换malloc等crt和系统分配函数。

   前面提到tcmalloc会无缝的替换掉原有dll中的malloc,这就意味着使用tcmalloc的项目必须是 MD(多线程dll)或者MDd(多线程dll调试)。tcmalloc的dll定义了一个
static TCMallocGuard module_enter_exit_hook;
的静态变量,这个变量会在dll加载的时候先于DllMain运行,在这个类的构造函数,会运行PatchWindowsFunctions来挂钩所有dll的 malloc、free、new等分配函数,这样就达到了替换功能,除此之外,
为了保证系统兼容性,挂钩API的时候还实现了智能分析指令,否则写入第一条Jmp指令的时候可能会破环后续指令的完整性。

2、LibcInfoWithPatchFunctions 和ThreadCache。

LibcInfoWithPatchFunctions模板类包含tcmalloc实现的优化后的malloc等一系列函数。LibcInfoWithPatchFunctions的模板参数在我看来没什么用处,tcmalloc默认可以挂钩
最多10个带有malloc导出函数的库(我想肯定是够用了)。ThreadCache在每个线程都会有一个TLS对象:
__thread ThreadCache* ThreadCache::threadlocal_heap_。

3、可能的问题


设想下这样一个情景:假如有一个dll 在tcmalloc之前加载,并且在分配了内存(使用crt提供的malloc),那么在加载tcmalloc后,tcmalloc会替换所有的free函数,然后,在某个时刻,
在前面的那个dll代码中释放该内存,这岂不是很危险。实际测试发现没有任何问题,关键在这里:
 span = Static::pageheap()->GetDescriptor(p);
    if (!span) {
      // span can be NULL because the pointer passed in is invalid
      // (not something returned by malloc or friends), or because the
      // pointer was allocated with some other allocator besides
      // tcmalloc.  The latter can happen if tcmalloc is linked in via
      // a dynamic library, but is not listed last on the link line.
      // In that case, libraries after it on the link line will
      // allocate with libc malloc, but free with tcmalloc's free.
      (*invalid_free_fn)(ptr);  // Decide how to handle the bad free request
      return;
    }
tcmalloc会通过span识别这个内存是否自己分配的,如果不是,tcmalloc会调用该dll原始对应函数(这个很重要)释放。这样就解决了这个棘手的问题。

五、其他

其实tcmalloc使用的每个技术点我从前都用过,但是我从来没想过用API挂钩来实现这样一个有趣的内存优化库(即使想过,也是一闪而过就否定了)。
从tcmalloc得到灵感,结合常用的外挂技术,可以很轻松的开发一个独立工具:这个工具可以挂载到指定进程进行内存优化,在我看来,这可能可以作为一个外挂辅助工具来优化那些
内存优化做的很差导致帧速很低的国产游戏。
posted on 2010-07-10 17:32 feixuwu 阅读(9046) 评论(14)  编辑 收藏 引用 所属分类: 游戏开发

FeedBack:
# re: 推荐一个跨平台内存分配器
2010-07-10 19:52 | chaogu
好像内存分配策略没有讲明白.....
  回复  更多评论
  
# re: 推荐一个跨平台内存分配器
2010-07-10 20:39 | feixuwu
@chaogu
恩,这篇主要不是讲常规小内存分配的,那个到处都在讲,没啥新意了,文章资料里提到的很多都是常规小内存实现,也可以直接看代码或者侯捷的STL源码剖析,有详细内容的。  回复  更多评论
  
# re: 推荐一个跨平台内存分配器
2010-08-07 08:27 | maxime
小内存分配器主要作用是“减小内存碎片化趋势,减小薄记内存比例,提高小内存利用率”,从性能上说,系统内存分配器已针对小内存分配进行优化,单纯使用自定义的小内存分配器,对性能帮助不会很大。内置分配器意义还是体现在,实现无锁分配,避免API调用切换开销。
CRT自身new-delete会用到500个时钟周期,而一个CS会消耗50个时钟周期,一个mutex会用到2000个时钟周期,以上是无竞争的情况。所以,如果用mutex做互斥,那还不如用系统的分配器;如果用CS,也不见会好多少,因为CS会随锁竞争加剧大幅增加时间,甚至会超过mutex。
所以结论是,对于单线程,内置分配器有一定的价值;对于多线程,带锁内置分配器基本上可以无视了(至少对于winxp以后是这样,win2k好像要打补丁)呵呵,从你说的情况来看,很有可能你们原来的分配器用mutex帮倒忙了。

tcmalloc中的唯一亮点应该是,如何做到跨线程归还内存,又能保持高性能,猜想可能使用了某种二级分配策略,内存块可以属于任何线程的内存池,归还到那个线程内存池,就由这个内存池管理。由于各个线程的分配和释放多半不平衡,有线程池会撑满,有的会不足。估计撑满的就会归还到公共内存池。第一级分配无锁,如果内存池不足了,就进入第二级带锁批量分配,而且第二级分配会先从公共内存池获取,如果还不够,这才使用系统内存分配,这该算是第三级分配了。


最后,tcmalloc也是可以用于MT版本的哦,详见(要翻墙才能看见)http://groups.google.com/group/google-perftools/browse_thread/thread/41cd3710af85e57b  回复  更多评论
  
# re: 推荐一个跨平台内存分配器
2010-08-07 08:31 | maxime
为避免大家翻墙,将原文贴在下面了。另外,如果下载chrome的源代码,其中就包含了tcmalloc的,它里面已经帮你把这篇文章要做的都做了,用脚本的形式。

Hi,

I wanted to post a little information about some changes that I'm
working on finishing up for the windows version of tcmalloc. If
you've ever had trouble overriding malloc/free on windows, you might
find this useful.


With Chrome, we wanted to override the default C runtime allocators
with TCMalloc. Chrome links the C runtime statically (/MT) in
VS2005. Unfortunately, VS2005 does not have a static mechanism to
override all allocators. This sounds easy, but it is not - VS2005 and
VS2008 both use C runtimes with internal functions that cannot be
overridden. We also didn't like the runtime patching approach which
tcmalloc currently uses. So, to get static linkage to work, we take
the C runtime library from Microsoft and remove all heap allocators
from it using the LIB.EXE tool. We then implement stub functions for
the non-overridable functions in the C runtime and manually link
Chrome to use the new library.


If you want to do this too, here are the steps:


Steps
1) Create a slimmed down version of the C Runtime Library. The C
Runtime Library ships with VS2005 in $VCInstallDir\lib\libcmt.lib. We
use the script below to do this.
2) In TCMalloc's config.h, define WIN32_OVERRIDE_ALLOCATORS
3) Modify your DLL or EXE build with the following:
a) link in tcmalloc.lib by adding a Project Dependency to it.
b) in Properties -> Linker -> Input, set "Ignore Specific Library"
to "libcmt.lib"
c) in Properties -> Linker -> Input, add "mylibcmt.lib" to the
"Additional Dependencies" line.


SLIM_CRT.BAT
REM
REM This script takes libcmt.lib for VS2005 and removes the allocation
related
REM functions from it.
REM
REM Usage: prep_libcmt.bat <VCInstallDir> <OutputFile>
REM
REM VCInstallDir is the path where VC is installed, typically:
REM C:\Program Files\Microsoft Visual Studio 8\VC\
REM
REM OutputFile is the directory where the modified libcmt file should
be stored.
REM


SET LIBCMT=%1lib\libcmt.lib
SET LIBCMTPDB=%1lib\libcmt.pdb
SET OUTDIR=%2
SET OUTCMT=%2\libcmt.lib


MKDIR %OUTDIR%
COPY %LIBCMT% %OUTDIR%
COPY %LIBCMTPDB% %OUTDIR%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\malloc.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\free.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\realloc.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\calloc.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\new.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\delete.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\new2.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\delete2.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\align.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\msize.obj %OUTCMT%


LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\heapinit.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\expand.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\heapchk.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\heapwalk.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\heapmin.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\sbheap.obj %OUTCMT%
LIB /IGNORE:4006,4221 /REMOVE:build\intel\mt_obj\smalheap.obj %OUTCMT%
  回复  更多评论
  
# re: 推荐一个跨平台内存分配器
2010-08-07 09:15 | feixuwu
@maxime
同意加锁的自定义分配器还不如不用的说法(所以说设计讨论在项目中是需要的,除了开发者,我们大家都不知道项目的多线程分配加锁了:))。

对“系统内存分配器已针对小内存分配进行优化”,这个我观点觉得有可能(毕竟没有验证),不过我倒觉得crt分配小内存的至少还是会有个head的,这个浪费免不了了(当然tcmalloc现在也是有头的,一般自己实现的内存分配器是不会有头的),从比例上来说浪费的还是比较多的,这个可以做个实验验证,一次分配50M和多次分配10byte至50M,2者进程的内存差距还是比较明显的。
好在现在PC和服务器内存越来越大,内存分配器的主要焦点都集中在速度上了。

tcmalloc跨线程归还内存,确实是因为所有线程公用了底层的一个分配器,所以跨线程归还是无需加锁的(从手册上看的,不知道博文提了没有)。
关于tcmalloc亮点,我倒觉得算法上的小优化其实倒没那么振奋,给我冲击最大的是产品的可用性,以往一个产品要使用新的内存分配器,一般需要改很多代码,最常见的是将已有类从一个SmallObject之类的类继承,很麻烦,这方面tcmalloc干的不错。

最后感谢maxime提供了MT使用tcmalloc的资料,以我从前的看法,静态编译的版本是无法使用tcmalloc的。  回复  更多评论
  
# re: 推荐一个跨平台内存分配器
2010-08-08 11:19 | kingzt
不知道博主能否做出一个外挂式的内存优化工具分享一下,现在的国产游戏优化确实是让人无语,如果有这个的话情况估计会好很多  回复  更多评论
  
# re: 推荐一个跨平台内存分配器
2010-08-08 11:22 | kingzt
博主能否实现一个这样的外挂式内存优化工具分享给国内的游戏玩家,现在有的游戏优化确实是让人无语,如果有这个的话情况估计会好很多  回复  更多评论
  
# re: 推荐一个跨平台内存分配器
2010-09-15 01:08 | 求助啊
请问如何在MFC程序中使用此tcmalloc?
能说下吗?
多谢了。
  回复  更多评论
  
# re: 推荐一个跨平台内存分配器
2010-09-17 21:03 | Roger
@求助啊
我在我的VS2003工程中用到TCMalloc,此功能有很多其他DLL模块.
出现2个问题:
1。 有些DLL模块在TCMall模块之前加载,并且分配了内存,此时不能被TCMalloc管理
2。 在进程退出时异常崩溃
出现在:(*invalid_free_fn)(ptr)
好像是地址无效了.
我猜想是:hook其他dll模块的函数,而此时的dll模块已经卸载了,因此此指针函数无效.
// This lets you call back to a given function pointer if ptr is invalid.
// It is used primarily by windows code which wants a specialized callback.
inline void do_free_with_callback(void* ptr, void (*invalid_free_fn)(void*)) {
if (ptr == NULL) return;
ASSERT(Static::pageheap() != NULL); // Should not call free() before malloc()
const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift;
Span* span = NULL;
size_t cl = Static::pageheap()->GetSizeClassIfCached(p);

if (cl == 0) {
span = Static::pageheap()->GetDescriptor(p);
if (!span) {
// span can be NULL because the pointer passed in is invalid
// (not something returned by malloc or friends), or because the
// pointer was allocated with some other allocator besides
// tcmalloc. The latter can happen if tcmalloc is linked in via
// a dynamic library, but is not listed last on the link line.
// In that case, libraries after it on the link line will
// allocate with libc malloc, but free with tcmalloc's free.
(*invalid_free_fn)(ptr); // Decide how to handle the bad free request
return;
}  回复  更多评论
  
# re: 推荐一个跨平台内存分配器
2010-09-17 21:03 | Roger
我的QQ:roger201008@qq.com  回复  更多评论
  
# re: 推荐一个跨平台内存分配器[未登录]
2011-08-25 22:12 | Lee
很奇怪,我在MFC工程里面把tcmalloc编译进去,vc居然报内存泄漏。
我的环境是vc2010.
不知道可否有人碰到这个情况啊?  回复  更多评论
  
# re: 推荐一个跨平台内存分配器
2012-11-16 18:06 | gohay
大哥,tcmalloc 不是通过API挂钩来实现无缝替换系统自带的malloc等crt函数的。
tcmalloc是通过静态全局变量的初始化早于main函数这个原理搞的,它定义了一个全局变量(tcmalloc.cc 文件中920行) static TCMallocGuard module_enter_exit_hook;
在TCMallocGuard这个类的构造函数中做了一大堆事情用来替换系统自带的malloc等crt函数  回复  更多评论
  
# re: 推荐一个跨平台内存分配器
2012-11-29 14:21 | feiwu
@gohay
抱歉我没说清楚。
你说的那个是在tcmalooc在linux下的做法。在windows下就是改写指令来处理的。
linux下不能挂钩,但是可以先加载来覆盖系统crtAPI,相比之下,linux下做这个更容易,linux甚至都不同编译进去就可以直接用。  回复  更多评论
  
# re: 推荐一个跨平台内存分配器
2013-05-17 22:02 | leehark
在windows下怎么做堆检测呢?  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2018年11月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

文章转载请注明出处

常用链接

留言簿(11)

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜