Archive for gc

Evil of Memory Leak

本篇含技术内容,不喜者勿入。

这是一个关于内存泄漏的凄惨故事。内存泄漏,乃是C/C++ Programmer最恐惧的Bug之一;来不知其来,去往往也不知其去,潜伏在层层花括号深处,当你发现它的时候,往往已经是程序崩溃之时。我几天前还被一个诡异的memory bug困扰了一晚,此bug举止异于常bug,在调试时单步执行没有任何问题,但一运行就出一些稀奇古怪的结果。以至于我都无法定位bug的位置,最后不得不借助于石器时代的printf调试大法,在可能出错的位置加上一摞一摞的printf才找到bug的可能位置。就算我已经定位到某一行代码,在我盯着屏幕看了半天,看得眼前快要出现幻觉,还是想不通bug从何而来。果然,从哪里来,到哪里去,是个终极关怀级别的问题。这一块代码和内存分配有关,无奈之下只好重写一遍,用了个稍微不同的逻辑。然后bug消失,程序再次和谐。

我个人喜欢用C写东西,尽管已经有无数与memory leak搏斗的经验,每次仍然免不了犯这类错误,经验虽然不停增长,错误好像未见减少。所以有时候觉得Java, C#这样的带Garbage Collection的语言也不错,但昨天看了一篇文章,讲述了一个C#中的内存泄漏怎样导致200万美金旁落的悲惨故事。涉及到这么大的支票,我们的兴趣总会提高一些。

文章作者是Princeton大学电子工程系的学生,他(当然还有一堆牛人)参加了一项汽车自动驾驶比赛,奖金是2个million。他们控制汽车的程序是用C#写的,有1万行代码。在比赛的最后关头,汽车老是开一会就失去响应,然后要么一头撞到障碍物(例如灌木丛),或者就茫然地在大地上行走直到没油。分析起来,问题出在代码的障碍物探测模块,它负责寻找汽车前进道路上的障碍。当然,如果车已经开过去了,那么刚才路上的障碍信息就没用了,所以会被垃圾回收器处理掉。最后的Bug是,这些对象,理应被丢弃掉的废物,根本没有被回收。一开始只见内存占用像滚雪球一样越来越大,开了一会汽车就歇了。可想而知,2百万肯定是黄了,最郁闷的是都这样了还不知道为什么垃圾回收器就是不干活,正宗的死不瞑目。

比赛完了,牛人们坐下来开会总结经验教训。其中某牛从网上下了个ANTS Profier,分析了他们代码的内存使用,终于看到了问题所在。前面说过这是一个C#式的内存泄漏,并不是说垃圾回收器出了问题,没有处理该回收的内存。虽然微软很不招人喜欢,但要相信它还不至于犯这种错误。垃圾回收器判断一个对象是否该被回收,是根据它能否被当前代码所引用。如果代码里已经不能访问到这个对象,那么它自然是垃圾。出问题的程序里,虽然程序员已经清除了到这些废物对象的引用,但这些对象作为事件的订阅者(subscriber,基本上是C#程序员的黑话),还在被其他活跃对象默默地引用。最后的结果自然是内存耗尽。所以那篇回顾文章的作者在标题里就痛心疾首地喊:”If Only We’d Used ANTS Profiler Earlier…”,言下之意,还在为那几乎到手的200万美金心疼。

这个故事告诉我们一个道理:垃圾回收机制虽然很方便,但它实际上是把一个问题变成了另外一个问题(手动释放内存到去掉所有引用)。相对来说,发生错误的可能性减少了,“去掉所有引用”这句话是我在这里说说的,听起来有些别扭,实际上在代码中是一件比较自然的事,不需要特别操心。但是一旦出错,也更加难以察觉——因为我们几乎不可能跟踪垃圾收集器的动作。所谓一饮一啄,天下没有免费的午餐。

阅读(641 次)

Comments (2)

Garbage Collection Algorithm

Quick Taxonomy:

  • Reference Counting
  • Tracing Collector - traverse live objects
    • Mark-and-Sweep Collectors
    • Copying Collectors
    • Hybrids

Other collector characteristics:

  • Conservative Tracing
  • Generational Tracing
  • Real or Incremental

上面这个大纲基本上概括了目前的主流垃圾收集算法。一般来说,工业产品级的实现,通常是在标记-清扫算法和复制算法的基础上,引入分代式或渐进式(也叫增量式)策略。对像我这样单枪匹马实现语言的人来说,暂时可以把分代式和渐进式仍在一边,先把标记-清扫算法和复制算法弄清楚再说。至于古老的,最通俗易懂容易实现的引用计数,我想已经成为边缘算法了。据说Python用的还是RC,反正Python这么慢,也不差这一点了……

说到垃圾收集,最重要的莫过于性能问题。垃圾收集和人肉回收哪个比较快?标记-清扫算法和复制算法哪个比较好?就算是标记-清扫算法,在这个名下也有许多变种,哪个最好?在下结论之前,不妨先问一问:好的标准是什么?衡量垃圾收集算法的指标在哪里?垃圾收集界老大之一,Hans-J.Bohem做过一个lecture,题为Memory Allocation Myths and Half-Truths,前半部分集中谈内存分配算法,后半部分讲垃圾收集,很值得一读,作为进一步研究前扫除知识垃圾之用,充分凸显了内存管理这一问题的复杂性,让我们养成一种小心谨慎的态度。Bohem的演讲可以概括成一句话:具体问题具体分析,实事求是(这是我党的重要思想,可以应用于世上一切已解决与未解决的问题……)

下面简单的列举一下gc算法需要考虑的几个方面:

  • 时间,包括垃圾收集本身的时间,以及内存分配的时间
  • 空间,主要是内存的使用量
  • 局部性,碎片问题以及缓存性能

上面三点,每一点展开都洋洋洒洒,并且三者相互影响,错综复杂。特别是最后一点,很容易被人忽视但实际上非常重要——也非常难搞。把这些内容全部弄清楚不是像我这样的门外汉力所能及;就算是专家,面对这样复杂的问题也不敢妄言自己都明白了,并且本身这里面还有许多未解决的问题。我的目标,就是学习一下基本的Mark-Sweep Algorithm和Copying Algorithm,并实现一个Garbage Collector来用在我自己的语言上。

阅读(832 次)

Comments (2)