gc-viz核心实现逐行精读：mark_live、sweep、compact、move四大GC函数的工作原理

gc-viz核心实现逐行精读mark_live、sweep、compact、move四大GC函数的工作原理【免费下载链接】gc-vizAnimated visualizations of several garbage collection algorithms项目地址: https://gitcode.com/gh_mirrors/gc/gc-viz本文带你逐行精读 gc-viz 垃圾回收GC动画可视化项目的核心代码深入讲解 mark_live、sweep_garbage、compact_live、move_live 四大 GC 函数的工作原理配合项目自带的 mark-sweep、mark-compact、copy 等 GC 算法动画帮助新手从源码层面看懂内存如何被回收是一份难得的 GC 算法源码阅读教程。项目一览让垃圾回收算法“活”起来gc-viz 是一个 GCgarbage collection垃圾回收动画可视化项目作者用 C 手写了一个玩具内存管理器内置了 NO_GC、引用计数、标记-清除、标记-压缩、复制收集共 5 种垃圾回收算法把每一次分配、标记、释放都输出成帧序列最终合成 GIF让你能逐帧看内存的变化 项目结构速览dkp.cc — 全部 GC 实现都在这里本文主角Makefile — 通过ALGO变量一键切换算法data/dkp.log-big — 驱动 GC 工作的示例数据docs/ — 5 个 GC 动画 GIF 与网页播放器 step-by-step.htmlreference/dkp.rb、dkp.scala — Ruby / Scala 参考实现总览gc() 如何调度四种算法所有算法的入口 gc() 只是一个调度器由编译期宏决定调用哪几个函数static void gc() { #if MARK_SWEEP_GC mark_live(); sweep_garbage(); #else #if COPY_GC move_live(); fixup_references(); // 整个旧半区一次性释放 ... #if MARK_COMPACT_GC Loc old_top top; compact_live(); if (old_top top) { fixup_references(); log_free_mem(top, old_top - top); } #endif开始精读四大函数前先记住 Mem 里的 4 个核心道具变量作用heap[2000]整个堆共 2000 个字top分配水位线bump 分配器reserve()只做top sizelive集合标记阶段得到的存活对象集合forwarding表被移动对象的旧址 → 新址转发表每个对象的对象头 dkp.cc 用位域紧凑地存了ref_count(8 位)、mark(1 位)、type(4 位)——这套类型标签系统正是可视化得以实现的基础。mark_live如何找出所有存活对象标记阶段标记阶段是三种 GC 算法共有的第一步也是最核心的函数 mark_livestatic void mark_live() { ObjRef *p ObjRef::root; live.clear(); while (p) { Loc loc p-loc; mark_live_loc(loc); Obj::at(loc)-traverse(mark_live_loc); p p-next; } }逐行拆解ObjRef::root是根集合root set——所有活着的引用变量组成的双向链表对应 README.md 中的术语 root set: active variables (and stack, registers)。live.clear()先清空存活集再标记保证结果不被上一次回收污染。对每个根对象调用 mark_live_loc 插入live集合顺带打出一个ref_count事件所以动画里被标记会表现为对象变色。traverse(mark_live_loc)做递归深度优先遍历Tup遍历每个元素Vec遍历内部元组每发现一个对象就继续递归——从根可达的即为存活其余全是垃圾。sweep_garbage如何回收垃圾清除阶段mark-sweep标记-清除1960的第二半 sweep_garbage 简单得让人惊讶static void sweep_garbage() { Loc loc 1; while (loc top) { Obj *obj Obj::at(loc); int size obj-size(); if (live.count(loc) 0) { free(loc, size); } loc size; } }从loc 1开始loc 0 是永不清理的nil。逐个对象走查堆每步前进obj-size()天然跳过当前对象。不在live集合中的对象就调 free——注意它并不真正擦除内存而是把对象头改写为TFree类型并记录长度形成一块可见的空闲块标记。mark-sweep 的代价对象不用搬家引用不会失效但空闲块散落各处堆里留下大量碎片。下面的动画里你能清楚看到白色空闲块像挖洞一样散布在已用区域中move_live复制收集与半区翻转COPY_GC复制收集1962的 move_live 只有十来行static void move_live() { mark_live(); // nil is located at heap loc 0 and doesnt move top (top HeapSemiSize) ? 1 : HeapSemiSize; for (it live.begin(); it ! live.end(); it) { Loc from *it; if (from) { move(from); } } }关键在第 2 行堆被对半切成两个半区各HeapSemiSize1000字top (top HeapSemiSize) ? 1 : HeapSemiSize就是经典的翻转半区——上次用了上半区水位线就重置回 1否则切到上半区。然后按顺序把live集合里的存活对象逐个拷贝move()会把原地改写为TForward转发对象。拷贝完成后整个旧半区可以一次性全部释放无需逐块扫描。这就是复制收集工作量只与存活数据成正比的原因垃圾连被看一眼的机会都没有 ⚡compact_live原地压缩与转发表mark-compact标记-压缩1964是四大函数中最精巧的compact_live 在一次扫描中同时完成移动 压缩 记录转发static void compact_live() { forwarding.clear(); mark_live(); Loc old_top top; Loc from 1; while (from old_top) { Obj *obj Obj::at(from); int size obj-size(); if (live.count(from) 0) { if (old_top ! top) { Loc to move_without_forwarding(from, size); forwarding[from] to; } } else if (old_top top) { top from; } from size; } }old_top ! top表示已遇到第一个空隙此后top只随存活对象前移——等于把所有存活对象紧挨着压实到堆底部空隙随之消失。forwarding[from] to记下旧址 → 新址映射稍后由 loc_after_move 和 fixup_references 依据这张表修复全部旧引用。精妙之处若堆里压根没有空隙全程old_top top则一个对象都不用搬转发表也省了。收益是 README.md 所描述的内存无任何碎片、总占用最小分配器只需几条指令的 bump 分配代价是需要 3 趟处理、并发控制极其复杂。配套函数 fixup_references移动收集器的必经之路凡会搬家的算法COPY / MARK_COMPACT都必须在 GC 后调用 fixup_references先遍历根集合把每个根的旧地址换成新地址再逐个堆对象调用其自身的fixup_references()如Tup改写val[i]、Vec改写tup把整个引用网全部修好。这也是移动式收集器难以移植进现有系统的根本原因。动手运行如何切换算法并生成 GC 动画git clone https://gitcode.com/gh_mirrors/gc/gc-viz cd gc-viz make # 需要安装 ImageMagick修改 Makefile 顶部的ALGO即可切换算法NO_GC/REF_COUNT_GC/MARK_SWEEP_GC/MARK_COMPACT_GC/COPY_GCmake会用不同-D宏重新编译 dkp.cc并合成对应 GIF默认编译的是MARK_SWEEP_GC。想在浏览器里逐步播放直接打开 docs/step-by-step.html它由 frames.js 与 engine.js 驱动。作为对照REF_COUNT_GC引用计数不做批量 GC而是在dec_ref_count()减到 0 时立即就地释放回收是随用随销的总结四大 GC 函数速查表函数所属算法一句话原理主要权衡mark_live三算法共用从根集合 DFS 标记可达对象需要遍历整个对象图sweep_garbagemark-sweep释放未标记对象形成空闲块内存碎片化move_livecopy存活对象复制到另一半区后翻转浪费一半空间compact_livemark-compact存活对象压到底部并记录转发表需修复引用、并发复杂作者在 dkp.cc 里留下的建议值得新手记住先读懂一本好的入门书等理解算法后再来对照这些动画——这里的代码是故意砍掉很多细节的玩具实现而正因如此它才最适合逐行精读 【免费下载链接】gc-vizAnimated visualizations of several garbage collection algorithms项目地址: https://gitcode.com/gh_mirrors/gc/gc-viz创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考