设计线程腌制或“无栈 Python 的精髓”¶
2007-07-22 的说明：本文档略微过时，应改为腌制的描述。需要进行一些研究才能摆脱显式恢复点等……
线程腌制是无栈 Python 中的独特功能，应该尽快为 PyPy 实现。
腌制是什么意思？¶
我想将线程腌制定义为正在运行程序的可重启子集。可重新运行的部分应基于 Python 帧链，由协程、任务或任何其他应用程序级可切换子上下文表示。当然可以支持任意层级间状态的腌制，但只要我们将无栈视为参考实现，这似乎就不是强制性的。完成基本任务后，可以考虑对此进行扩展。
腌制应该创建一个可重新启动的类似协程的东西，它可以在不同的机器上运行，使用相同的 Python 版本，但不一定使用相同的 PyPy 翻译。这属于更难的部分。
腌制不包括什么？¶
保存整个内存状态并编写一个加载器来重建整个二进制文件及其内存状态，这不是我认为的真正解决方案。从某种意义上说，如果我们在其他所有情况下都失败，这可以作为一种后备方案，但我认为对于 C 后端来说，这真的很糟糕。
如果我们有一个支持直接创建程序及其状态的动态后端（例如：Forth 后端），我会将其视为一个有效的解决方案，因为它可以重新定位。当然，如果我们失败了，编写这样一个后端作为后备方案也是可能的。
有一些简单的步骤，也有一些更困难的步骤。让我们从简单的开始。
基本需求¶
正在运行的线程的腌制涉及比普通对象腌制更多的东西，因为存在许多没有腌制接口的对象，人们根本不会关心腌制它们。但是对于线程腌制，这些对象只是作为局部变量存在，并且需要恢复当前运行时环境，用户不应该知道腌制中包含了什么。
例如
- 生成器
- 帧
- 单元格
- 迭代器
- 跟踪
仅举几例。幸运的是，这些对象中的大多数已经在无栈 Python 中有了腌制实现，即 prickelpit.c 文件。
重新实现这些功能应该简单直接。然而，存在一个复杂问题。支持 pickling 的最自然方式是提供一个 __getstate__/__setstate__ 方法对。这对于我们可以控制的扩展类型（如协程/任务）来说是可以的，但应该避免用于现有类型。
例如，考虑框架。我们必须添加一个 __getstate__ 和一个 __setstate__ 方法，这是一个接口变更。此外，我们需要支持通过调用框架类型来创建框架，这并不是真正想要的。
对于其他已经可调用的类型，事情变得更加复杂，因为我们需要确保创建新实例不会干扰现有调用类型的途径。
直接向现有类型添加 pickling 接口很可能会在调用接口中产生重叠。例如，当模块类型变得可调用时，签名与 Stackless 之前添加的签名不同。
对于 Stackless，我使用了 copyreg 模块，并创建了特殊的代理对象作为占位符，这些占位符在解封后用正确的类型指针替换对象的类型。有关详细信息，请参阅 Stackless 发行版中的 prickelpit.c 文件。
总之，任务的 pickling 是 Stackless 的一个补充，但并非旨在成为 Python 的扩展。支持某些对象 pickling 的需求不应该改变接口。最好将此解耦，并使用代理类型进行 pickling，这些类型不会与 Python 的未来添加内容发生冲突。
真正的问题¶
目前，Stackless Python（简称 SLP）和 PyPy Stackless 支持（简称 PyPy）在发展方面存在一些关键差异。当 CPython 调用 Python 函数时，会涉及几个辅助函数来调整参数、解包方法等等。SLP 在启动函数的 Python 解释器之前，需要花费很长时间才能从 C 栈中移除所有这些 C 函数。这种行为的改变是通过手动完成的，方法是找出调用后哪些变量仍然需要。事实证明，在大多数情况下，可以先让所有辅助函数完成工作并从函数调用中返回，然后再启动解释器。
这是 PyPy 需要解决的主要差异。每当我们运行 Python 函数时，相当数量的函数会在 C 栈上实例化，并且它们在运行新框架之前不会完成。在协程切换的情况下，我们只是保存了整个激活记录链 - 带有保存的块变量的 C 函数入口点。这对于协程切换来说是可以的，但在 SLP 的意义上，它相当不完整，根本不是无栈的。栈仍然存在，我们可以展开和重建它，但这是一个问题。
为什么是问题？¶
在理想情况下，线程 pickling 只需要构建封存的框架链，而不需要其他任何操作。对于上面提到的每个不同的额外激活记录，我们都有如何保存这些信息的问题。我们需要一个不依赖于机器或编译器的表示。目前，PyPy 在它将产生的块、内联的内容等方面非常不稳定。最好的解决方案是尝试完全摆脱这些额外的结构。
不幸的是，即使是 SLP 也无法做到这一点，因为存在不同类型的状态，这使得在没有额外信息的情况下很难进行操作。
SLP 切换策略¶
SLP 经历了多次重写。第一个实现的目标是完全协作。新框架的执行被推迟，直到所有准备性的 C 函数调用都离开了 C 栈。没有额外的状态需要保存。
嗯，这只是部分正确 - 有几种情况，递归调用是不可避免的，因为必要的支持需要对实现进行大量重写。
例如
- map 是对一系列操作进行迭代的状态化实现。如果 map 操作创建自己的框架来保存状态，则可以使其非递归。
- __init__ 看起来很简单，但语义是 __init__ 的返回值应该为 None，CPy 在调用后会对此进行特殊检查。这可能被简单地忽略，但它是一个无法自动处理的简单示例。
- 诸如 operator.__add__ 之类的东西理论上可以生成一个递归调用的疯狂模式，而 CPy 试图弄清楚它是数字加法还是序列加法，并且当 __coerce__ 等方法参与时，可能会发生其他回调。这对于 SLP 永远无法解决，但可以通过下面概述的策略得到解决。
第二个实现采用了截然不同的方法。上下文切换通过劫持 C 栈的部分内容来完成，将它们存储起来，并用目标需要的栈片段替换它们。这非常强大，允许即使在外部代码的上下文中进行切换。有一点风险，我甚至能够为外部 Fortran 代码添加并发性。
上述概念称为硬（切换），协作的软（切换）。请注意，硬的改进版本仍然是 greenlet 的构建块，这使得它们并不真正绿色 - 我会称之为黄色。
最新的 SLP 重写结合了这两种想法，尽可能使用 Soft，但在嵌套解释器存在的情况下使用 Hard。
值得注意的是，当涉及 Hard 时，从未尝试过对 tasklet 进行序列化。在 SLP 中，序列化与 Soft 一起使用。为了收集更多可序列化的情况，你需要发明新的帧类型或编写替换的 Python 代码并使用 Soft 切换它。
SLP 和 PyPy 之间的类比¶
现在，PyPy 在微小的激活记录中保存函数的 C 状态：块的活动变量，以及离开的函数的入口点。这比存储原始栈切片有所改进，但模式类似：当我们切换时，C 栈状态会被恢复。
从这个意义上说，上周我和 Richard 讨论这件事时，令人惊讶的是：PyPy 本质上做的是 Hard 切换的一种变体！至少它做了一个折衷方案，并没有真正帮助序列化。
另一方面，这种方法只走了一半。事实证明，与 SLP 相比，不必首先避免递归是一个改进。相反，似乎更优雅、更有效的是在切换的上下文中，而不是更早地消除不必要的状态！
以最小化方式处理问题的方法¶
比较 SLP 和 PyPy 的不同方法，似乎没有必要首先改变解释器。PyPy 不需要改变其调用行为才能协作。关键是要找出哪些激活记录需要存储。这应该可以在无栈转换的一部分中识别出来。
考虑调用普通 Python 函数的最简单、最常见的情况。涉及到对函数的多次调用，这些调用执行准备步骤。不试图精确（这是要做的工作的一部分），涉及的步骤是
- 解码函数的参数
- 准备一个新的帧
- 将参数存储在帧中
- 执行帧
- 返回结果
现在假设我们不执行帧，而是进行上下文切换，那么现在一堆激活记录序列被存储在堆上。如果我们想重新激活这个激活记录链，在进行函数调用之前，我们真正需要恢复什么？
- 参数解码已经完成，并且我们可以进行函数调用这一事实表明，没有发生异常。我们可以忽略这个激活记录的其余部分并进行清理。
- 帧已准备就绪，参数已存储在其中。操作成功，我们拥有了帧。我们可以忽略异常处理，只需通过消除引用来进行清理。
- 为了执行帧，我们需要一个执行帧的特殊函数。我们可能需要不同的风格，因为上下文不同。SLP 通过使用不同的注册函数来做到这一点，这些函数根据帧的状态（第一次进入、调用后重新进入、返回、生成等）对帧进行操作。
- 执行帧后，需要以通常的方式处理异常，我们应该返回到调用者。
需要更深入的分析才能使这些事情正确。但应该已经很清楚，在所有准备步骤完成后，除了 Python 帧中拥有的状态之外，没有其他必要的状态：绑定参数、指令指针，仅此而已。
我的建议是现在手动进行这样的分析，识别要处理的不同情况，然后尝试找到一种算法，该算法可以自动识别整个程序中可以避免恢复 C 栈的块，并且我们可以直接跳回之前的调用者。
必要分析的粗略草图
对于 RPython 函数中可以到达 unwind 的每个块：分析控制流。它应该立即导致返回块，只有一个输出变量。所有其他活动变量都应该在这个块中结束其生命周期。
我认为这在一开始不会起作用。例如，对于绑定的帧参数，我认为我们需要一些表示法，这些表示法表明它们由帧持有，并且我们可以在进行调用之前丢弃它们的生命周期，因此我们不需要在激活记录中保存这些变量，因此可以删除整个激活记录。
作为这个不完整的第一次分析的结论，似乎有必要识别无用的激活记录以支持序列化。然后，剩下的不可约的激活记录应该是那些持有对 Python 帧的引用的记录。如果其根指向协程的 interp 级实现的上下文切换代码，则这样的链是可序列化的。
观察发现，这种转换不仅支持序列化，而且是一种优化，如果我们可以避免保存许多激活记录。
另一个我希望能够证明的观察结果是：剩下的不可约激活记录，它们不仅仅包含一个 Python 框架，这些记录应该被视为特殊的。它们应该被转换为类似特殊框架的东西，它们将是使 PyPy 完全无栈的关键，而这对于 SLP 来说几乎是不可能的！这些激活记录需要成为官方接口的一部分，并且需要为其必要的函数提供命名支持。
我希望能在这里结束这篇论文。我相信其他所有内容都需要在实现中尝试，而到目前为止，我只能通过想象来做到这一点。
最好的 - chris
在进一步思考后，我补充一点¶
实际上，在我检查完之后，我突然意识到，确定哪些块需要保存状态，哪些块不需要保存状态的问题，并不是一个无栈问题。这是一个系统固有的问题，缺少一种我们还没有尝试解决的优化。
从 GC 转换的角度来说，特别是引用计数，可能很容易理解我的意思。我们当前的引用计数实现是天真的，因为我们没有尝试进行每个扩展编写者手动进行的优化：我们没有尝试保存引用。
这也是我一直争论引用计数可以并且实际上是有效的，因为 CPython 做得很好。
我们的引用计数没有意识到变量的生命周期，它没有跟踪已知由其他对象持有的引用。优化这一点将做两件事：引用计数将变得非常有效，因为我们将节省大约 80% 的引用计数。第二部分与序列化问题相关：通过进行适当的分析，我们已经丢失了对所有不再需要保存的变量的引用，因为我们知道它们被保存在例如框架中。
我希望你明白：如果我们改进变量的生命周期分析，上面提到的关于哪些块需要保存状态，哪些块不需要保存状态的问题，应该变得微不足道，并且应该消失。正确地做到这一点将几乎自动地解决序列化问题，同时带来更有效的实现。
我希望我说的是实话，并会努力证明这一点。
再见 - chris