有趣的CS - 垃圾回收两三事
周末看LOL比赛去了，忘了做正事了（？？？ 不过DRX真鸡儿逆天，震 撼 我 妈 一 整 年 想了想，就带逛三篇比较有意思的垃圾回收的paper凑凑数（？ 自我吐槽：喂，你就是这样对待你主方向的吗？？？ The Transactional Memory / Garbage Collection Analogy：这篇paper就如同名字上所说，把两个不太接近的概念联系起来了，大体思路就是两个东东都能提高编写体验，然后对比lock ordering，或者对比rc，都不怕cycle，但是会损失点性能。 续上，有一个更逆天的联系在How OCaml type checker works – or what polymorphism and garbage collection have in common里面。大体说，当你进行let generalization的时候，你只能generalize由你‘独占’的类型变量，而如果你独占了会‘逃逸’，或者是‘外面传来‘的类型变量，就会type unsound，而这跟你free了不该free的东东会引发dangling ptr是一样的。然后blog把解决方法联系上了region based memory management。 A theory of garbage collection：这把reference counting跟tracing based garbage collection对立起来了。更具体的说，reference counting是在求一个least fixed point of garbage，所以会从已有垃圾开始推更多垃圾，而tracing是在求greatest fixed point，于是会从live memory里面iterate。相比前两篇这个联系更’明显‘。 Improving flow analyses viaΓCFA: Abstract garbage collection and counting.：当你跑abstracting abstract machine的时候，你的allocated cell会越用越小，最后一个cell要被迫重复放值，从而需要merge，污染精度。这paper是在说，你这时候跑一跑垃圾回收就好辣！比起前面几篇，这篇的逆天之处在于提出了一个很离谱的connection，但是真的能行，还给一群人指了路，在这以后来回搬运什么Abstract Reference Counting之类的工作 Garbage collection can be faster than stack allocation - 这paper核心idea很简单：mark copy gc只动live memory不动dead memory，那我一个垃圾回收器，只要很久才回收一些内存，不就比手动内存管理（这时候需要时间去回收单独的dead memory cell）快吗？当然，现实里面没这么多内存，也就佩恩入侵木叶 - 图一乐 Ulterior Reference Counting: Fast Garbage Collection without a Long Wait：ref counting的主要问题是（不是cycle！）频繁refcount会严重降低性能，而tracing based GC的主要问题是需要不停重复遍历live set。这篇paper把两个合二为一，从而试图去掉两个的主要问题：old generation用rc，这样由于old generation动得小refcount不频繁，而young generation用gc，这时候live set只需要遍历一次（就promote了） 本来想好三篇的，但是写着写着记起来更多paper了（？