Emacs GC 一直是卡顿 Emacs 的主要元凶。
今天花了一点时间研究了 Emacs GC 的源代码 emacs/src/alloc.c, 关键代码在 garbage_collect 这个函数, 其代码实现的核心流程如下：
阻止用户输入: GC 操作之前先调用 block_input 函数阻止用户输入, 并把 GC 标志位 gc_in_progress 设置为 1
标记可达对象： 用 visit_static_gc_roots 和各种 mark_xx 函数， 扫描 Emacs 的一些根对象（比如全局函数定义、 变量定义、 Buffer 列表等）， 最后通过函数 mark_object 把这些对象标记为‘可达’
清理垃圾对象： 通过 gc_sweep 函数按照对象的类型（string, cons, float, interval, symbol, buffer, vector 等）进行扫描， 查看没有被第二步标记的对象， 释放其内存
允许用户输入： 通过unblock_input函数解除输入阻止， 把 GC 标志位gc_in_progress设置为 0， 完成垃圾回收
Emacs 这种全局扫描的垃圾对象的算法策略， 主要的问题是， 随着 Emacs 对象增多（主要是 LSP 或 overlay 场景下短时间生成大量对象）时， 第二步标记和第三步清理的耗时会随着对象数量急剧增加， 一旦这两个过程的耗时超过 30~100 毫秒， 就会产生 Emacser 遇到的卡手现象， 如果这个过程超过 2 秒以上， 就会导致用户极度烦躁甚至强制 kill。
因为 Emacs 本身是单线程程序， 所以我们没办法把 GC 过程放到后台线程去跑。
所以， 针对 GC 性能优化， 我自己想了几个研究方向：
随时中断 GC： 在 garbage_collect 过程中插入大量 detect_input_pending 判断， 如果 GC 过程中检测到用户有输入事件发生， 立即中断 GC 过程, 避免 GC 导致 Emacs 无法响应用户操作
双进程模型： 需要进行 GC 时， 通过类似 pdumper 的技术， 把当前 Emacs 的内存保存到磁盘中（为了性能可以用内存文件）， 然后再根据 dump 文件开一个后台 Emacs 进程， 通过后台 Emacs 进程慢慢分析需要清理的对象， 分析完成发送清理列表给第一个 Emacs 进程进行清理
分代回收： 根据对象的创建时间进行分代分析， 那些创建时间非常短的对象（一般是临时变量）优先分析， 那些创建时间比较长的对象延迟分析（一般是插件引入的全局函数或者变量）， 降低每次全局垃圾对象分析的规模
这三种方式的优缺点分析：
第一种， 就是比较简单粗暴， 随时中断 GC 以保持用户操作响应， 用户频繁输入的时候 GC 基本没有机会运行， 用户暂停的时候 GC 可以尽情的运行， 为了避免标记和清除的过程也卡住用户， 可以在 mark_xx 和 gc_sweep 函数里面继续插入大量 detect_input_pending 判断， 只要 detect_input_pending 插入细粒度越细， 理论上可以做到 GC 不卡用户； 缺点是随时中断 GC 需要做很多状态恢复和代码保护， 避免 Emacs 崩溃（今天晚上已经尝试了第一种方法， 因为时间不够， 各种崩溃， 哈哈哈哈）
第二种， 就是第一个 Emacs 完全不做 GC 分析， 让第二个进程做 GC 分析， 要卡也卡第二个 Emacs， 这种方案的优点是 Emacs 开发者不用关心 GC 兼容性问题， 正常写代码逻辑就好了， 缺点是比较占用内存资源， 或者让一部分 Emacser 洁癖用户心理不舒服
第三种， 通过时间戳或者 let 表达式进行创建时间标注， 避免让 Emacs 对一些常驻对象（比如插件引入的函数定义和全局变量等）进行检查, 多分析临时对象， 提高 GC 效率， 缺点是， 要大量改造 Emacs GC 代码， 难度到没啥， 主要是测试工作量比较大
以上是一些关于 Emacs GC 的研究， 因为时间关系， 很难在短时间内有进展， 前期只能先理理思路， 把思路分享出来抛砖引玉, 欢迎大家一起讨论贡献智慧。
30 个赞
第一种，就是比较接近现在所谓软实时 GC 的思路。有个相对温和折衷的方法在 GitHub - emacsmirror/gcmh: The Garbage Collector Magic Hack
第二种，我不相信在短期大量创建 short lived objects 的情况下还能保证健壮性
3 个赞
另外，我估计当前 emacs gc 收到碎片化的问题影响比较严重。
根据 info page 里的各种描述，似乎实现的 gc 和这个比较接近
Boehm-Demers-Weise garbage collector which uses a list of free memory blocks, partitioned by size
所以可以研究一下，有没有可能把 gc 实现成精确的，如果不能的话，再考虑能不能用现成的成熟实现
emacs gc原理的是，它检测垃圾对象的原理是全局扫描一次正在用的对象标记一下，然后再全局扫描所有内存对象去清除没有标记对象的内存占用。
它这个方式比较蠢得是，不管有没有垃圾对象，每次都挺耗费时间的，我的emacs配置还是根据按键触发动态加载的，那些一股脑加载所有插件的配置，估计扫描耗时更长。
gcmh应该是控制gc加载时机，但是没有处理用户输入时停止gc，要达到这个效果，必须把gc c代码改了才行。
我想到第四个方法就是，大量改set，let，还有函数作用域退出时的代码，对作用域内临时变量做标记。
gc运行时，直接回收这些被标记的临时变量，不用了去扫描所有对象2遍。
但这个方法要大量改emacs代码，不是短时间之功。
实际上这个原理本身没啥问题，你用的语言不够准讲的不够明白，别人可能会误解。Go 用的和上面所说同样方法，没有实现分代，甚至没有实现去碎片化，并没有啥不适合高强度使用的问题。（当然 Go 的实现方法利用了并发能力）
真正的问题在实现细节上，Go，Ruby 等用的三色标记法是比 emacs 用的成熟很多的算法。注意这个三色标记是精确 gc，就算是全局扫一次，也只会扫引用（指针），这个需要专门用一个树保存引用。
而 emacs 居然用的是保守 gc，实现虽然简单，内存空间里的任何东西哪怕不是指针也会扫到，怪不得比谁都慢。
这个可以参考 Common Lisp 和 Lisp Machine 就有的，𣏾上分配版本的 let。问题在于，在现在的内存和编译模型下还是隔靴挠痒，可能还不如少用 list 多用 vector 提升显著。
好像你还没考虑到特殊版本 let 运行到一半 GC 启动了咋办，try catch 没运行完就退出了咋办，这要做对的话，要加很多额外检查，不见的性能会好。只有在有比较好的编译器才会有赚头
9 个赞
你可能感兴趣 scratch/alloc 分支上的改变。意思就是 GC 处理到一定的程度后，退出 GC，利用虚拟内存保护保证已经受到扫描的 Object 再修改后重新扫描，以免丢失 Lisp_Object。原则和 bdw 的比较相似。
可惜最近没时间继续折腾，现在不适合使用。
（另外，detect_input_pending 不能安全的从 GC 调用，在 Solaris 等不支持 interrupt input 的平台上精准度不高，最好是检测耗时，不是检测输入。）
7 个赞
以前的 GC 是精准的，C stack 上的 Lisp_Object 要手动 GCPRO。后面因为维护成本太高，GCPRO 代码被删除了。我们大概不会重新往这条路上走，因为调试 GCPRO 一直是 Emacs 维护中最困难的任务只一。
GCPRO 过程可以参考：https://git.savannah.gnu.org/cgit/emacs.git/tree/src/editfns.c?h=emacs-19.34#n273
7 个赞
其他语言好做的是有多线程支持，线程fork一下后，慢慢分析，不影响主线程，分析完再让主线程清理一下。
如果线程分析得同时主线程产生了新的对象，先不管，下次再分析。
emacs这种单线程的集中策略：
增量回收，每次垃圾回收继续上次进度，不要每次都全局扫描一遍
分摊式标记，针对作用域退出后得临时变量，平常用一个hashtab存储一下引用，回收的时候先把这些临时变量干掉，大头垃圾对象就没有了，插件引入全局变量和函数不用管
双进程监控，这种不影响emacs，但是没有实测过双进程代价
至于你说的细节，我先不思考，最好能从根本解决性能问题，不管那种策略，各种细节处理都要花很长时间，首先方向不能错，大家可以讨论下。
感谢方案分享，我最近也没时间，大家可以讨论下，只要解决问题，谁实现都无所谓。
cireu
2023 年4 月 17 日 03:48
13
我看了一下原理和代码实现不难， 就是牵扯地方太多了， 测试强度很大。
我看了一下Git日志， GC这一块的修改几个时间 1994, 2000, 2014年， 其他年份没有动过了。
这个不是一日之功， 就当每天可以当智力题，研究一下， 前期要做大量的性能日志分析工作， 才知道哪些瓶颈比较大。
9 个赞
LdBeth
2023 年4 月 17 日 05:46
18
直接说结论：
Functions live_string_p etc
call mem_find to lookup information about a given pointer in the
tree, and use that to determine if the pointer points into a Lisp
object or not.
引入了 conservative 导致了每次调用 live_XX_p 都要在 heap 里扫一遍（RB tree lookup）看有没有 lisp object 对应是这个指针的，而每 cons 一次也意味着做一次树的插入，显然是一很大额外开销
完全精确了的 tri-color 就不该有这个 RB tree lookup，然后现在的 emacs gc 也没有 compact (除了部分 string)
Bitnut
2023 年4 月 17 日 05:59
19
第三个方法看着有点眼熟，是不是 Chrome 的思路
感觉如果可以的话，1 + 3 效果会最好。
显然不是每次 cons 插入，是每次添加 cons block 才插入，一个 cons block 的大小大概在 1000-4000 cons 左右。
三色 GC 和 mem tree 无关，如果你要利用硬件 write barrier，就必须有把内存地址转换成 object 的记录，如果你用软件实现 write barrier，那就不需要，但是会给 GC 外写入 object 带来性能影响。
另外，只有 mark_maybe_object 才会参考 mem_tree，只有 mark_memory 会调用 mark_maybe_object。
4 个赞
LdBeth
2023 年4 月 17 日 13:17
22
那好像 mark 阶段其实并没有特别耗时间的操作，尤其是 c stack 其实不会很深的话。
那感觉好像通过减少 full gc 次数才是比较有效的方法，不管是分代还是提前结束 gc。
！
