继续做题 PKU1034

这个题目不难，只是一开始容易被题目信息迷惑，还有那个可恶的" speed that is up to two times greater than his master's speed" (这句英语我到现在还没明白，是3倍还是2倍，幸亏题目的例子俩面经过测试应该2倍。。。题目的内容给人感觉是网格运动模拟+搜索类的题目。其实稍微分析一下，题目中的一个不完美的限制“小狗”每次在主人的一个运动区段中只能走过一个感兴趣的位置。所以这个题目最后抽象为：主人线段 与 （同时2被速度内）可到达顶点集合的2部图最大匹配问题。结果就是，未匹配点就是小狗乖乖的跟着主人走，匹配点是去玩一下到下一个定点。
刚好复习匈牙利算法，32MS AC! （增广路径每次+一条匹配所以条目计数也是很方便的。）其实匈牙利算法的代码是很精炼的，但是精炼的背后还是有很多细节值得重新学习和分析一下。

Diablo III !!

哈哈，终于出现了，就是Diablo III.

貌似这两天blogspot解封了？

Diablo 3要出来了？

这两暴雪的主页上有神秘的冰裂开的图，似乎有新的游戏要破冰而出，而且上面有暗黑的符文标记，难道是传说中等到花开花谢的Diablo 3??

看球的这些年

我第一个认识的球星是马尔蒂尼，因为那时候买了一张贺年卡，上面就是他。不知不觉看他踢球踢到老，真是岁月如刀。第一个非常喜欢的球星是欧文，98世界杯那一个惊世骇俗的天才，比我大两岁的天才少年，像一把极快的尖刀穿到阿根廷的左肋。也是不知不觉，在06世界杯上，看到他因为那陈年的膝伤，软弱的倒在绿茵场上，不能忘记临倒下的那个眼神，早已失去神童的光泽，只有遗憾，悲伤，和对足球的告别。

今天的足球，逐渐的失去早日的华丽，越来越野蛮，功利的的踢法使得足球在观赏上开始走下坡路，无论是哪个天才，除了伤病就是侵犯。在一点上，马拉多纳是幸运的。今日有很多极高天赋的球星，要不就想罗纳尔多，欧文那样成为一个悲剧，要不就是像梅西一样成为玻璃人。看到梅西过人的时候，除了惊叹，更多的是揪心。

高中的时候开始稍微的看球，在大学看得也不多，真正看得多的是刚刚毕业的时候，因为欧文而喜欢利物浦，喜欢英超。那时候同学大部分更喜欢意甲，英超的强队相对不是很多。周末有个重大的活动就是看球，无论多么晚。去年英超被买断了，没得看了。意甲爆了丑闻。德甲没得看，西甲只有好戏除了皇马对巴萨也是寥寥。能看的球越来越少了。。。

至于中国足球，我从三年前就说再也不看了，可是和很多中国球迷一样，一个字：犯贱。一场又一场，一场更比一场丑。上次回家，还笑话我舅舅被舅妈说看完中国队比较手脚竟然冰凉的，结果前天中国主场对伊拉克，看完了，我才发现我的脚是冰的。中国足球是一个奇迹，一个彻头彻尾的奇迹，非物质文化遗产，前无古人，后无来者，惊天地，泣鬼神。

关于C语言中实现的GC

去年年底做了个ANSI-C的GC简单原型, 写完代码就扔在哪里, 也没有关注过，虽然写GC的过程中很有收获（比如学习了一个GC mark的非栈算法（3p算法)）,但是最终结果是还是应用起来相对比想象中的复杂性还是要高了一些。也就没管了，但是最后也没总结个文档出来。前两天看到云风的blog上面有他在这几天也写了一个GC for C的原型，基本上是另一个方向，基于 C 语言的指针而不是Handle, 因此看到他的Blog，颇有共同语言，遂回复并请教之，他也在回复中做了一些比较详尽的讨论。他是很有勇气的，把他的东西开源了，我那个玩意现在最后的设想，关于finalizer线程并没完全实现，（当时考虑到Geohm GC依赖于图的拓扑排序来finalize,所以做了一些思考，包括这个顺序本身的问题和finalize的线程，还有执行批量一次多少对象的finalize）.

既然有人也做了，我也可以把我的那个做法和基本的思考写出来，做个基本的回顾，不管成功失败，结果总是有一丁点的价值吧。

1.首先重点是接口，其实到底该给用户一个什么样界面，什么样的接口，甚至要提出需要的概念，是否够用，是决定了这个GC是否好用和有价值。当时思考这个问题真的非常的扰人。首先，在C语言，处于C的哲学，你必须够简洁，而且够用。一般的，在Java, C#这些已经有了GC的语言中，引用这个概念是显然的，在C里面，就要选一个，是Handle还是指针。这个后面会提到。另外，全局引用，对象之间的引用，栈上引用，还有甚至所谓寄存器引用(在Geohm GC的实现里面，扫描会饱含寄存器，所有架构相关可能存有引用的都会被扫到）。我的想法是把这个问题简单化，透明化：用户来搞，用户只维护两种引用：全局，对象间。全局引用使用引用计数来作为收集标志，并且他们是所谓的GC 根， 扫描总是从这些开始。（如果非要把根单数化，那么可以考虑有个根对象，跟对象和这些全局有着这些引用，但是这样的归纳看上去简洁了，实现确不如后来的有效率）。对象引用就是普通的赋值，不做赋值跟踪（使用C操作符=而不是定义宏，这个有缺陷，后面会说）。这些是否就够用了呢，基本上，差不多。有些细节，比如为了用户方便，实现一个所谓“基本数组”对象，就不提了。但是有个不能不提，那就是栈上引用的模拟，我是用一个对象，叫做Local frame, 每个线程使用线程局部存储来维护一个Local frame stack.可以push和pop. pop就是吧一个frame去掉，这个对象没了，那么栈上的对象引用也就解除。这个有好处就是GC有个很大的用途：一些紧凑的编程，需要产生不少所谓栈上的对象，而这些对象，用户并不想去自己来释放。少了这个，GC就少了很多威力。


2.Handle ,还是 void *?
这个问题是C里面实现GC的根本指导:要高的还是要低的。普通的C指针是比较简洁的，对用户很透明，但是关于在C里面应用Handle, 好处是很多的，虽然会增加用户代码，因为Handle本身有合法检查性方便，这样就不至于再给用户一把自宫刀子了。可以做内存重新整理，这一点很重要，GC在标记之后的垃圾清扫，使用何种策略是GC能不能带来好处的重大因素。一个整理内存的GC有着非常多的好处比如 没有碎片。

我的GC的指导是用户知道自己该让哪些对象，处于GC的内存管理之下，并且用户在提取Handle的指针的时候，可以处于GC关闭的保护，（我叫他做GC barrier，这个名字不太好去，和并行编程的那个barrier不是一个概念，就是防止用户提取指针的时候GC运行导致指针移动 ）。

到底该使用哪个方式，我觉得都是可行的，只是我个人认为Handle的方式在将来的扩展性可能要好些，当然，这是建立在用户多写handle相关的代码上，不过我觉得现在handle相关的代码很多，C程序员早就习惯了Handle了。


Handle方式的实现比较简单，一般就是一个Handle向量表，和一个堆来存储对象。细节就不说了，将来我的那个也开源吧，最近没有时间，还是要整理一下。

3.GC Thread
这是个困扰我的问题，虽然我早就定下使用一个Thread来做GC的方式。我还没有仔细的看过云风的代码，如果没有猜错，是在用户线程环境下做收集的。我的GC 有 Thread，然而Thread，众所周知，是移植性最大的挑战。首先，当GC在收集的时候，用户到底是把自己的所有线程暂停，还是仅仅是：当GC收集的时候，用户进入Barrier会被挡住，或者如果当前有用户在Barrier保护内，GC就不能收集。（这里有潜在分配/barrier死锁，不在这里细微讨论了，是可解的）。我采用的是后者，但是这并不能说这就是安全的，用户要知道这一点。在一些嵌入式系统上，我们可以简单的关闭中断（吓死人）来防止线程调度，来保护GC收集的时候不会到其他线程导致冲突，这在别的系统上是不可行的，在别的系统上，比如linux，可以参考Geohm GC里面挂起所有线程的办法。

另外，就是Finalizer Thread。这个应该不能放到GC Thread里面，因为把客户代码放到GC Thread简直就是自取灭亡。必须通过另外一个Thread, 或者多个-_-~。 这个我的代码没有实现，因为最后没有想好一个比较好的finalizer顺序。。。。在下面finalizer会提。

使用Thread可能是很自然的，然而在GC for C这样的里面使用Thread是有很大风险的，我的GC有一个OS Porting层，然而这层的接口比较潦草，仅仅是Thread mutex semaphore这些基本实现，并不考虑各种系统的区别。也许直接用posix的比较好，谁知道呢，win的支持不好，@#@$MS@#Q@.

4.隔代收集。
内存整理是个很耗费时间的事情，基于标记-清除或者整理都有这个比较郁闷的僵死时间。这也是早年GC老被人嘲笑的原因。现在有很多成熟的基于隔代收集的算法，这些算法的效率已经非常不错了。然而他们需要一个特点：追踪对象引用的赋值操作，或者说就是要知道某个对象在某时候引用了一个别的object,则需要立刻记录并作一些处理。这个在整体上会有一些效率的耗费，但是获得的是比较短的收集时间。

5.finalizer：
现在很多GC都支持一个所谓的finalize, 来实现GC辅助的资源管理。在 Geohm GC 中，使用拓扑序来call这些finalizer function. 这是个很不错的想法，可惜我没有实现。不过在现实中，对象引用有环的图应该是很容易发生的，但是话说回来，如果依赖finalizer来做资源释放，而本身存在环，这就有点不大对劲了，（不过也是有可能的）。这就不太好做了。我当时想就简单点，随便找个顺序，释放得了。另外，finalizer也需要一个线程，并且优先级要比较低，从一个队列去取对象来调用。这时候，我们再需要一个标记，就是一个对象在mark为不可要的时候，还有finalizer没有call之前也是不能被收集的（如果有finalizer function的话）。当call了之后，标记就置位。

6.Marking算法：
研究GC的应该都会看到那个比较彪悍的不要栈的通过节点缓存（不存父亲指针）的方式图遍历算法，（我叫他3P算法,三个人名字，怪长的），其实实际上，栈的简单深度有限遍历算法也是很有用的，因为我的GC并不是整个系统都在用，所以出现GC回首时，内存无法供给一个动态栈并不是很容发生。反而那个3p算法会需要一个每个节点计数器的存储开销，这个计数器可能并不需要，一般的一些书得介绍因为把对象描述几位几位的省出来一个计数器，有时候并不一定，呵呵。

这个东西做的时间有点长了，记得不太清楚，也不知道有些忘了写出来。先写这么多吧，不然以后忘了就比较失败了。

另，比较佩服云风的精神，开源是需要勇气的，面对回复也是需要勇气的。

mp3的错

自从在电脑上存着mp3, 就会发现听歌简直和拉屎吃饭一样容易，没有放入磁带和碟片的操作，连按按钮的一点点的机械运动都没有。于是一些好听的歌，也被听成黄脸婆了。不断的有歌被删除，又有新的歌加入。那些能坚挺很长时间的歌，还真的不是很多啊。