编程语言与软件工程2014cs.virginia.edu编辑精选
垃圾回收的统一理论（2004）
A Unified Theory of Garbage Collection (2004)
进阶 · 约 50 分钟读完前置知识：垃圾回收基础、引用计数与追踪式GC、编译器/运行时系统
导读
这篇2004年论文提出垃圾回收的统一理论，把纯追踪式GC与纯引用计数视为同一连续谱的两端，并说明分代等优化往往是在两端之间移动。结论是实际高性能GC（如HotSpot、.NET、现代JS引擎）多为追踪与引用计数的混合体。
HN 关注点：如何统一GC算法、解释实际运行时的混合设计，并延伸到RAII、数据库视图维护等话题。
后来怎么样
该论文成为垃圾回收领域的经典理论框架，被广泛用于教学与解释追踪式、引用计数式及混合式收集器的设计。
HN 评论精选
这几条评论里：支持 1 补充 3
支持统一理论把GC视为追踪与引用计数的连续谱，实际GC多为混合体。
这是一篇经典论文，任何对GC感兴趣的人都必读。基本思想是：引用计数不仅是垃圾回收的一种形式，而且纯追踪和纯引用计数之间存在一个连续谱。每种算法都有取舍，关键在于多数优化——例如分代GC——实际上只是把方案推向相反的一极，从而获得另一算法的部分优缺点。以此视角看，Java HotSpot、.NET、现代JS引擎等实际部署的优化GC，最好被视为追踪与引用计数的混合体，平衡两者的优缺点。
pcwalton查看英文原文
This is a classic paper that's a must-read for anyone interested in GC. The basic idea is that not only is reference counting a form of garbage collection, there's actually a continuum of GC approaches between pure tracing and pure reference counting. Each algorithm has its tradeoffs, and, crucially, most optimizations—for example, generational garbage collection—actually just move the scheme toward the opposite pole, acquiring some of the upsides and downsides of the other algorithm. Viewed through this lens, most of what we would consider well-optimized GCs deployed in the wild (Java HotSpot, .NET, modern JS engines, etc.) are really best viewed as hybrids of tracing and reference counting, balancing the upsides and downsides of each approach.
补充提问RAII是否属于统一GC理论中的引用计数一端。
我很好奇RAII方法与这个理论如何关联？它会被视为一种二元引用计数（引用计数并未显式使用，即C++中非shared_ptr代码），还是完全独立、不属于双重GC理论？
tybit查看英文原文
I'm curious how RAII approaches relate to this? Would it be considered a form of binary reference counting(where reference counting isn't explicitly used, i.e non shared_ptr code in C++) or it's just completely separate and not part of the dual GC theory?
补充把GC与数据库视图/理由维护、不动点计算及前向/后向链联系起来。
垃圾回收与数据库中的视图维护（更具体地说是理由维护/真值维护）很相似。尤其是论文找到最小不动点表述，暗示它与演绎数据库中计算和维护不动点——即从基础事实和规则计算并维护物化视图——有强相似性；基础事实也可视为特殊规则。视图维护中已有约30年的计数算法，例如PF（Propagate and Filter）和DRed（derive-rederive）。一个区别是GC总拥有完整图（边和顶点），而视图维护通常只有顶点，这催生了proof traces方法：构建完整图并保留边，尽管边只用于维护或解释。追踪式GC与引用计数GC也可类比Datalog或规则系统中前向链与后向链的区别。这似乎是另一个案例：提高对相关领域成果的认识可能更快结出果实。
jkbyc查看英文原文
Garbage collection is quite similar to view maintenance in databases (or more specifically reason maintenance / truth maintenance). Especially the fact that they found a least fix-point formulation of the problem hints at strong similarity with computing and maintaining fixpoints in deductive databases - that is computing and maintaining materialized views from some base facts and rules (a distinction that does not need to be made; base facts can be seen as special kinds of rules). In view maintenance, there are various counting algorithms known since around 30 years - for example the PF (Propagate and Filter) algorithm, or DRed (derive-rederive) algorithm. One difference is that in garbage collection you always have the whole graph: edges and vertices, while in view maintenance you typically have only the vertices. That gives rise to the "proof traces" method of view/reason maintenance where you build up the whole graph and keep the edges even though they are useful only for maintenance (or for explanation). The distinction of tracing garbage collection vs. reference counting garbage collection could be also seen as sort of analogous to the difference between forward chaining and backward chaining in datalog or rule systems in general. It seems like another case where bigger awareness of results from different but related fields could help to bear fruit much faster. This paper in particular seems like something that could have been inspired by the old view maintenance research. Maybe there still are some opportunities left for transferring results from one of the fields to the other.
补充GC和RC都涉及追踪，分代混合可让老年代回收成本与分配率而非堆大小成正比。
GC和RC也有一些巧妙的混合方案，这可能是该领域最先进的工作。概念上的关键洞见是GC和RC都涉及追踪：GC从存活根追踪以找到幸存者；RC从新死对象追踪以找到其他也应死亡的对象。结合分代收集器时这有有趣含义。设想稳态：分配率为X MB/秒，年轻代存活率为0.1X，因此进入老年代的分配率也是0.1X；稳态下老年代死亡率同样是0.1X。若年轻代用GC、老年代用RC，每秒追踪0.2X MB。即使老年代存活集极大也成立：老年代收集不必追踪整个堆，只需追踪该区间内死亡的对象，且成本与分配率而非堆大小成正比。理想情况下追踪式GC的工作量可降到与分配率成正比，但这需要堆大小为最大存活量的2倍；用RC老年代则可以……
rayiner查看英文原文
There are some neat hybrids of GC and RC as well. This is probably state of the art in this area: https://www.google.com/url?sa=t&source=web&rct=j&ei=xkTDU-GUCtOkyAT-4oKIDQ&url=http://www.cs.utexas.edu/users/mckinley/papers/rcix-oopsla-2013.pdf&cd=5&ved=0CC8QFjAE&usg=AFQjCNF44hAyxlBLnQO2xh527_TGA7_vDQ Conceptually, the key insight is that both GC and RC involve tracing. In GC you trace from live roots to find survivors. In RC, you trace from newly dead objects to find others that should also become dead. This has interesting implications when you combine the algorithms in a generational collector. Imagine the following steady state situation. You're allocating at X MB/sec, with a young-generation survival rate of 0.1X. Consequently, this is the allocation rate into the old generation. Since we're in a steady state, this is also the death rate in the old generation. If you use GC in the young generation and RC in the old generation, you'll trace 0.2X MB per second. This holds true even for an extremely large old generation live size. You'll never have to trace the whole heap during an old-generation collection, just the objects that die during that interval. And if you're in a steady-state, this will be proportional to your allocation rate, not your heap size. Now, ideally, in a tracing GC you can get your work down to being proportional to your allocation rate, but this requires, even ideally, a heap sized at 2x the maximum live size. With an RC old generation, you can get away with a heap not much bigger than your live size. There are also certain advantages in terms of concurrent collection. The nice thing about tracing dead objects is that they are never mutated. So you do it concurrently with the application without worrying about mutations of the object graph, like a concurrent mark-sweep collector has to. The downside is that the write barrier is more complicated. See: https://www.google.com/url?sa=t&source=web&rct=j&ei=wEnDU_23BZGwyATqpoGwDQ&url=http://dl.acm.org/citation.cfm%3Fid%3D504309&cd=3&ved=0CCMQFjAC&usg=AFQjCNEhxDpi-_L4vd9bjlSEpBv_XIXc-Q
历次讨论
- 2014Hacker News 讨论帖135 分 · 15 评
- 2017Hacker News 讨论帖151 分 · 22 评
同领域还值得读
Google 的软件工程（2017）
Software Engineering at Google (2017)
介绍了 Google 的软件工程实践，包括其单一代码库（monorepo）、几乎全部开发在主干进行而非分支、代码审查、构建系统 Blaze、协议缓冲区等工具与流程，并讨论了频繁重…
编程语言与软件工程2017 · 1,127 分 · 465 评 · 引用 15入门 · 约 45 分钟编辑精选Peter Naur：编程作为理论构建 (1985)
Peter Naur – Programming as Theory Building (1985)
Peter Naur 1985 年的经典论文《Programming as Theory Building》提出：编程的本质不是写代码或文档，而是在程序员头脑中构建对程序及其运行…
编程语言与软件工程2016 · 629 分 · 74 评入门 · 约 45 分钟编辑精选SciPy 1.0：Python 科学计算的基础算法
SciPy 1.0: fundamental algorithms for scientific computing in Python
这篇发表于 Nature Methods 的论文介绍了 SciPy 1.0——Python 科学计算生态的基石库，涵盖其核心算法模块（优化、积分、插值、线性代数等）、软件架构与社…
编程语言与软件工程2020 · 387 分 · 98 评入门 · 约 45 分钟编辑精选Lisp 的历史（1979）
History of Lisp (1979)
这是 Lisp 发明者 John McCarthy 于 1979 年为 HOPL（编程语言史）会议撰写的回顾文章，讲述 Lisp 的起源、设计动机与早期演进，文中也涉及 if 表…
编程语言与软件工程2018 · 352 分 · 44 评入门 · 约 45 分钟编辑精选使用 NumPy 进行数组编程
Array Programming with NumPy
这篇 Nature 文章介绍 NumPy 的数组编程模型及其在科学计算中的核心作用：以 ndarray 为中心，通过向量化操作让 Python 高效处理多维数组。
编程语言与软件工程2020 · 318 分 · 134 评入门 · 约 40 分钟编辑精选