Zero Sound

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来用在我自己的语言上。

阅读(946 次)

Using Tabs in Vim

Vim是我最喜欢用的编辑器。Vim v.s Emacs几乎是除开程序语言之争（比如C++ v.s Java)之外持续时间最长、参与人数最多也是最没意义的口水战。Emacs很好，几乎无限的扩展性，但我就不喜欢两点：第一，我不喜欢把指头拐出去按ctrl,alt，而且往往要同时；第二，Emacs慢，拖了那么多五花八门的extension，不慢才怪了。有人说Vim不也经常要伸出手指去够键盘左上角的Esc键？所以我前面说了这是最没意义的口水战；这一类关于个人喜好的争论都是如此，本来个人喜好就是没道理可讲的，偏要去跟人讨论讲出一堆因为所以然来，结果自然是口水飞溅了。

回到正题。Vim 7用了这么久，突然发现一直没有用上Vim 7的最大新特性（之一），就是标签页，tab。在这里把常用的几个命令总结一下：

首先，默认情况下Vim是不显示tab label的。想让Vim在头上显示一栏标签，就要在_vimrc加一句

set showtabline=2

0表示不显示。

打开新标签页

最常用的命令自然是在新标签页中打开文件了。直接:tabnew filename。注意这个命令是支持自动完成的。顺带提一下tabf，后面可以跟通配符进行搜索。

在标签页间切换

有人说直接用鼠标点就行了。我也觉得鼠标很方便，但掌握一些键盘操作命令也是有好处的（这又涉及到另一大著名口水战GUI v.s CLI)。可以用:tabn和:tabp在标签页间移动，或者在normal mode下按gt。此外，还有诸如:tabfirst和:tablast，顾名思义即可。

重新安排标签页

有时需要调整一下标签页的顺序。很遗憾Vim没有提供通过drag调整顺序的功能，只能借助于命令。:tabm n移动当前标签页。Vim将所有标签页从0开始编号，n就是标签页的新位置。

最后提一个十分有用的命令，即:tabdo command，可以一次性对所有标签页执行command命令。比如要对所有标签页进行替换，按照传统是把foo替换为bar，那么

:tabdo %s/foo/bar/g

这篇文章里提到的内容其实只是tab的很小一部分，欲知详情，请查阅vim的帮助。

阅读(837 次)

Restart my Compiler project

考完试了，有几天空闲时间。我想起还有个建设中的编译器被我遗忘在目录深处，决定利用这几天工夫好好来写点代码。

这个玩具编译器（我的计划是未来某一天它不再是一个toy language，我设想了许多美好的特性，但我现在还没有足够的技术和时间来实现他们）的前端已经完工。编译器前端——词法分析、语法分析——在教科书上占一半的篇幅，涉及到不少理论知识，但实际上是个无聊的工作。而code generation则是麻烦而繁琐的。网上可以找到全套的工具——从flex、bison这样的前端生成器，到MLRISC这样完备的后端，但我还是想自己动手写一遍。 我现在去看几个月以前写的code generation，惊奇于这样丑陋而复杂的代码居然（貌似）是对的。

我的目标是生成机器代码，这两天花了不少功夫研究IA32处理器的浮点运算，深刻地认识到FPU是一个多么难看的设计，让我的代码增加了无数的条件分支和switch。想了解一下MIPS在这个问题上是怎么处理的。string，class等已经初步提上日程。至于我幻想中的gc及lambda expression,high-order function,continuation等一干functional特性，现在还遥遥无期。

从书签里翻出一篇老文章，一直没细读，Modern x86 assembly （blogspot….被和谐掉了。同志们上代理。），里面着重谈了alignment(对齐）和caching(缓存）。对现代的计算机架构，这两样东西对性能有极其重要的影响。对齐主要是编译器考虑的问题；而cache的影响则更为微妙。准备好好学习一下。

阅读(714 次)

Safari 3.0.2 Beta

今天背邓论背得头晕眼花，偷空上网就看到Safari 3.0.2 beta已经上线了。不久前听说Safari 3.0.1 beta出世，虽然我很少下beta版来当无名小白鼠，这回还是忍不住下了一个来尝鲜。苹果公司估计是除了微软、Google之外最有名IT公司——世界范围内，如果是中国就另当别论。虽然我并非Mac用户（还好我有一个iPod，总算是苹果的客户），也不是那种狂热得近乎宗教的Apple fans，苹果仍然是一家非常有趣的公司，那种自以为是的可爱作风很能吸引眼球。

3.0.1版一出来就骂声一片：它居然不能正常显示非英语字符！这个bug大的有点丢人，这样的版本连alpha都算不上。除此之外，速度方面,不管是启动速度还是页面渲染，都表现不佳，有人将其评为”the world’s slowest web browser”。苹果执著于自身的UI风格，想要在Microsoft的地盘上占山为王，不管是字体渲染还是窗体都从头做起，于是中文变成了下划线，整个速度也被拖累，归根结底是苹果想在Windows上完全复制Mac的软件外观所致。但是不这么做也就不是苹果了。

这个漏洞无数，问题百出的beta版放出以后，立刻有一堆苹果爱好者们发布了各式各样的补丁教Safari识字。我开过一次Safari之后就不想再用了，等哪一天把中文显示的问题解决再说。结果今天就解决了，终于有了当beta的资格。总的来说，除了UI效果给人印象深刻（苹果最出名的也就是这个。主要是字体，字体……但是习惯了Windows字体渲染引擎的同志可能反而会觉得Safari的字体难看，这是因为Windows和Apple字体渲染的出发点完全不同，所以算法也不一样），别的方面一般。Steve Jobs之前说的，未来的浏览器市场是IE和Safari的天下，我觉得基本上是梦呓。

阅读(706 次)

初试Qt

昨天一腔热血地编译了Qt 4，编译完才想起可以去下一个Open Source Edition的binary直接来用，大概被俄国同志无私奉献的精神感染了……

顺手装上了一个VS2005的Qt插件。一开始老是出错，而且都只出一行错误信息：找不到头文件。如果代码里有Qt类需要moc出场，就会出另一行：找不到moc。检查了环境变量，没有问题。用qmake生成vcproj，表现良好，说明问题出在VS2005上。昨天折腾了一下午，百思不得其解，不得不感叹微软的产品都像谜一般迷人。

今天早上起来继续钻研，终于发现这回错怪微软了，是我设置的不对。因为是自己编译的版本，所以VS的Qt插件找不到Qt在哪儿，需要手动在选项里指定。当时还迷惑了一会，写上了Qt的二进制代码所在的文件夹$(QTDIR)\bin，实际上只要写$(QTDIR)就可以了。

经过了这么多磨难，终于可以顺顺当当的在VS里用Qt了。

阅读(840 次)

Compling Qt 4.3.0 in a rainy afternoon

这个标题分为两段：技术的，冰冷的前半段和容易被误认为略带一点小资气息的后半段。下午的雨下得无法无天，全过程完美的体现了夏季雷阵雨的特征。我坐在桌前，被一种莫名其妙的空虚感侵袭，决定折磨一下我的电脑，于是上网下了Qt4。

下面要开始谈一点技术内容。大家都把Qt定义为一个非常优秀的GUI库，这么说未免有点片面，事实上它是一个Framework，像.NET Framework 2.0,Spring一样的Framework。但是和一身铜臭的.NET,Java不同，Qt略略带有一些开源色彩。首先当然是因为KDE用了Qt，大家也就一厢情愿的把Qt归到开源软件里了。其次是Qt确实有一个OpenSource版本（可以想象功能上会打点折扣）。对于盗版精神深入骨髓的中国人和俄罗斯人来说，虽然OpenSource很好让人心安理得，但是如果能D到一个商业版当然更美好。Qt Underground。这个网站的标题已经揭示了它罪恶的本质。

最后谈谈编后感（注：编，编译也）。 这个玩意是我编译过的最大的软件，编译后源码加各种lib,dll居然有近2GB之多，编译时间也长得吓人，光configure就不下半小时。泡一杯茶，然后看着nmake上气不接下气得调用cl干活，屏幕上漆黑丑陋的cmd窗口不停得滚动，听着外面单调的雨声，我的不知从何而来的空虚感也消失了。所以大家以后无聊的时候，不妨去下一个boost或者linux kernel编译一下。言归正传，编译前要做一些必要的改动，来配合该死的VS2005SP1(如果你用的是gcc，这一块讲的都不适用)，为了不让技术细节充斥这个页面，我决定只放个链接，是一位高手的Qt 4.2.3编后感，对4.3.0版本也适用。

阅读(744 次)