编程与软件工程blog.reverberate.org
以 2+GB/s 解析 Protobuf：我如何爱上 C 语言中的尾调用
Parsing Protobuf at 2+GB/S: How I Learned to Love Tail Calls in C
2021 — 2024，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
文章讲解作者如何利用 C 语言的尾调用（尤其是 musttail）来构建高性能解释器式代码，把 Protobuf 解析速度做到 2GB/s 以上。文中还讨论了这种写法如何影响寄存器分配、字节码分发以及不同架构上的性能。
为什么经久不衰：它把经典语言特性与底层 ABI/编译器行为结合成可复用的高性能技巧，并清楚揭示其收益与架构权衡，因此多年后仍值得读。
HN 评论精选
尾调用风格可借 ABI 控制寄存器分配，但高度依赖架构，32 位系统上可能不利。
非常有趣的技巧！在我看来，最大的收获是：如果你愿意用尾调用风格写 C 代码，就能对哪些变量放进机器寄存器有很大控制权。在 x86-64 ABI 中，前 6 个函数参数保证通过寄存器传递。显然这依赖架构；其他架构可能使用不同的调用约定，破坏这种手工寄存器分配。我想在 32 位系统上性能会很差，因为函数参数通过栈传递。我还知道至少 Lua 和 Python 在内部循环里用了 computed goto，这也能帮助编译器生成更好的代码，但尾调用技巧的架构依赖性可能是个问题，而且这些解释器还需要在 32 位系统上表现良好。
ufo查看英文原文
A very interesting trick! In my opinion, the big takeaway here is that if you are willing to write your C code in tail call style, you can get a lot of control over which variables are stored in machine registers. In the x86-64 ABI, the first 6 function parameters are guaranteed to be passed via registers. Obviously, this is architecture-specific. Other architectures may use a different calling convention that ruins this kind of manual register allocation. I'd imagine that it would be bad for performance in 32-bit systems, where function arguments are passed via the stack. -------- > I think it’s likely that all of the major language interpreters written in C (Python, Ruby, PHP, Lua, etc.) could get significant performance benefits by adopting this technique. I know that at least Lua and Python use "computed gotos" in their inner loops, which also helps the compiler generate better code. The architecture-dependent nature of the tail-call trick could be a problem here. Some of these interpreters also need to work well on 32-bit systems.
Zig 提案认为尾调用分发可行，但存在架构支持、调试和热路径额外函数跳转问题。
这里有一个相关的 Zig 提案。其中提到：尾调用能解决分发问题——每个 switch 分支会 return foo()（尾调用），foo() 完成业务后调用一个做 switch 的函数，然后尾调用下一个分支。这在可立即实现的意义上合理，但有一些问题：据我理解，尾调用在某些架构上不工作（有哪些？有人知道吗？）；我还担心用尾调用做分发时调试困难；它迫使你把逻辑组织成函数，这可能是热路径中你不想要的额外跳转。另见 Dino 语言文档第 3.1 节“Byte Code Dispatch”。
AndyKelley查看英文原文
Here's a related Zig proposal: https://github.com/ziglang/zig/issues/8220 Relevant section pasted here: > Other Possible Solution: Tail Calls > Tail calls solve this problem. Each switch prong would return foo() (tail call) and foo() at the end of its business would inline call a function which would do the switch and then tail call the next prong. > This is reasonable in the sense that it is doable right now; however there are some problems: * As far as I understand, tail calls don't work on some architectures. * (what are these? does anybody know?) * I'm also concerned about trying to debug when doing dispatch with tail calls. * It forces you to organize your logic into functions. That's another jump that maybe you did not want in your hot path. See also https://dino-lang.github.io/learn/dino.pdf, section 3.1 "Byte Code Dispatch".
Scheme 长期以尾位置/尾调用作为状态机等实现的优雅基础。
Scheme 一直把尾调用当作基本惯用法（有人称其为 Proper Implementation of Tail Calls，有人称其为 Tail Call Optimization），我在 Scheme 中实现任何非平凡东西时都会记着它们。没有特殊语法——只有尾位置的概念，从尾位置可以发生尾调用。例如，如果 if 本身在尾位置，那么它的两个分支都是尾位置；如果在某个分支里引入顺序块，块的最后位置就是尾位置。实现状态机时，状态转换就是对新状态的一次函数应用（调用），被调用的函数表示状态。当你意识到原本凌乱的东西可以如此优雅时，会感到很满足，也能想象它会非常快。
neilv查看英文原文
Scheme has had tail calls as a basic idiom (some call it Proper Implementation of Tail Calls; others call it Tail Call Optimization) forever, and I keep them in mind any time I'm implementing anything nontrivial in Scheme. There's no special syntax -- there's just the notion of tail positions, from which tail calls can occur. For example, both arms of an `if` form are tail position, if the `if` itself is. And if you introduce a sequencing block in one of those arms, the last position in the block is tail position. (A specialized IDE like DrRacket can indicate tail positions, and DrRacket will even hover arrows, tracing the tail positions back to the top of the code.) When implementing a state machine, for example, a state transition is simply a function application (call) to the new state (optionally with arguments), where the the called function represents a state. It's satisfying when you realize how elegant something that used to be messy is, and you can imagine it being very fast (even if your Scheme implementation isn't quite up to getting as fast as a C or Rust compiler that can recognize and special-case tail calls.) (For the state machine example, compare to more conventional approaches in C ,of "state ID" variables, `switch` statements on those, and record-keeping for additional state. Or doing it in data, with state ID being index into arrays, again with any additional recordkeeping. Or lots of function calls when you didn't really need the time overhead and stack usage of function calls with full returns.)
Protobuf 解析在 Google 消耗大量算力，评论者惊讶未使用手写汇编。
Protobuf 对 Google 非常重要。很大比例的计算周期都花在解析 protobuf 上。如果性能还能提升这么多，我惊讶解析没有用手写汇编。
ma2rten查看英文原文
Protobufs are very important for Google. A significant percentage of all compute cycles is used on parsing protobufs. I am surprised that the parsing is not doing using handwritten assembly if it's possible to improve performance so much.
历次讨论
同类还值得读
开源应用架构
The Architecture of Open Source Applications
《开源软件架构》（AOSA）是一本在线免费书，邀请知名开源项目的作者亲自剖析其内部设计，涵盖 SQLAlchemy、LLVM、Audacity、Apache、Bash 等系统。
编程与软件工程上首页 9 次 · 2011–2024aosabook.org编辑精选编程语言简史：简短、不完整且多半错误
A Brief, Incomplete, and Mostly Wrong History of Programming Languages
一篇以戏谑、故意不准确的方式回顾编程语言史的博客文章，用夸张轶事和讽刺定义串起 Lisp、C、C++、Java、JavaScript、PHP 等语言。
编程与软件工程上首页 8 次 · 2009–2021james-iry.blogspot.comSQLite 是如何测试的
How SQLite is tested
SQLite 官方文档页，系统介绍 SQLite 的测试体系：多种测试方法（TCL 测试、模糊测试、回归测试、静态分析等）和海量测试用例，展示了这个小型开源项目如何靠极致测试获得…
编程与软件工程上首页 8 次 · 2009–2025sqlite.org编辑精选高级编程语言（2009）
Advanced programming languages (2009)
Matt Might 的经典文章，按用途推荐“高级编程语言”：如果追求就业就选主流语言，如果追求表达力、学术研究或创业，则推荐 Haskell、OCaml、Scala 等函数式语…
编程与软件工程上首页 8 次 · 2009–2022matt.might.net我的 Forth 与栈机器经历
Yosefk - My history with Forth & stack machines
作者以亲身经历回顾了使用 Forth 语言和栈式机器的历程：既赞叹其简洁优雅、代码量小、可自举的优点，也坦率指出栈操作在实际编程中的痛苦，以及 Forth 社区文化中的问题。
编程与软件工程上首页 8 次 · 2010–2024yosefk.com编辑精选