您可以通过内存复制堆栈帧而不是创建状态机来实现异步等待吗?
Could you implement async-await by memcopying stack frames rather than creating state machines?
我正在尝试理解编译器/解释器/内核为您做的所有低级工作(因为我是另一个认为他们可以设计出比大多数其他语言更好的语言的人)
Async-Await 是激发我好奇心的众多事物之一。
我检查了几种语言的底层实现,包括 C#(编译器从糖代码生成状态机)和 Rust(必须从 Future 特性手动实现状态机),它们都是使用状态机实现 Async-Await。
我没有通过谷歌搜索(“异步复制堆栈框架”和变体)或“类似问题”部分找到任何有用的信息。
对我来说,这种方法似乎相当复杂且开销很大;
你能不能通过简单地 memcopy 异步调用的堆栈帧来实现 Async-Await to/from 堆?
我知道这对于某些语言在体系结构上是不可能的(感谢 CLR 做不到,所以 C# 也做不到)。
我是否遗漏了一些使这在逻辑上不可能的事情?我希望这样做的代码不那么复杂,性能也会提高,我错了吗?我想当你在异步调用(例如递归异步函数)后有一个深堆栈层次结构时,你必须 memcopy 的数据量相当大,但可能有解决这个问题的方法。
如果这是可能的,那为什么没有在任何地方完成?
首先我想说,这个答案只是作为一个起点,让您朝着实际的探索方向前进。这包括各种指导和其他作者的工作
I've checked the under-the-hood implementation for a couple languages, including C# (the compiler generates the state machine from sugar code) and Rust (where the state machine has to be implemented manually from the Future trait), and they all implement Async-Await using state machines
您正确理解 C#
和 Rust
的 Async/Await 实现使用状态机。现在让我们了解为什么选择这些实现。
用非常简单的术语来表达堆栈帧的一般结构,无论我们放入堆栈帧中的是什么,它们都不会比导致添加该堆栈帧的方法(包括但不包括仅限于局部变量)。它还包含延续的信息,即。在最近调用的方法的上下文中,接下来需要执行的代码的地址(换句话说,控件必须 return 到)。如果这是同步执行的情况,则方法一个接一个地执行。换句话说,调用方方法被挂起,直到被调用方方法完成执行。从堆栈的角度来看,这符合直觉。如果我们完成了一个被调用方法的执行,控制权被 returned 给调用者并且栈帧可以被弹出。从硬件的角度来看,它也是便宜且高效的,运行 这段代码也是如此(硬件针对堆栈编程进行了优化)。
在异步代码的情况下,一个方法的延续可能必须触发其他几个可能从调用者的延续中调用的方法。查看 this answer,其中 Eric Lippert 概述了堆栈如何为异步流工作的全部内容。异步流程的问题在于,方法调用并不完全形成一个堆栈,尝试像处理纯堆栈一样处理它们可能会变得极其复杂。正如埃里克在回答中所说,这就是为什么 C#
使用 代表工作流的 heap-allocated 任务和委托图 .
但是,如果您考虑像 Go
这样的语言,则异步处理的方式完全不同。我们有一个叫做 Goroutines
的东西,这里不需要 Go
中的 await
语句。这些 Goroutines
中的每一个都在它们自己的轻量级线程上启动(它们每个都有自己的堆栈,默认大小为 8KB)并且它们之间的同步是通过 channels
的通信实现的.这些轻量级线程能够异步等待在通道上执行的任何读取操作并自行挂起。 Go
中的早期实现是使用 SplitStacks technique. This implementation had its own problems as listed out here 完成的,并被 Contigious Stacks 取代。文章还讨论了较新的实现。
这里要注意的一件重要事情是,不仅仅是处理任务之间的连续性所涉及的复杂性有助于选择实施方法 Async/Await,还有其他因素,例如 Garbage Collection即发挥作用。 GC 过程应尽可能高效。如果我们四处移动堆栈,GC 就会变得低效,因为访问一个对象需要线程同步。
Could you not implement Async-Await by simply memcopying the stack frames of async calls to/from heap?
总之,可以。作为 Chicken Scheme 的 this answer states here, Chicken Scheme uses a something similar to what you are exploring. It begins by allocating everything on the stack and move the stack values to heap when it becomes too large for the GC activities (Chicken Scheme uses Generational GC). However, there are certain caveats with this kind of implementation. Take a look at this FAQ。这方面也有很多学术研究(链接在段落开头提到的答案中,我将在进一步阅读中总结)你可能想看看。
进一步阅读
call-with-current-continuation
This answer(包含很少指向该领域学术研究的链接)
TLDR
采用哪种方法的决定取决于影响语言的整体可用性和性能的因素。状态机并不是实现 C#
和 Rust
中完成的 Async/Await 功能的唯一方法。很少有像 Go
这样的语言实现 Contigious Stack 通过通道协调异步操作的方法。 Chicken Scheme
分配堆栈上的所有内容并将最近的堆栈值移动到堆中,以防它对其 GC 算法的性能变得沉重。移动堆栈有其自身的一组影响垃圾收集的负面影响。通读本文 space 中所做的研究将帮助您了解每种方法背后的进步和基本原理。同时,您还应该考虑如何规划 designing/implementing 您语言的其他部分,因为它在性能和整体可用性方面都接近可用。
PS:鉴于此答案的篇幅,我们很乐意纠正可能出现的任何不一致之处。
是的,将代码转换为状态机的另一种方法是复制堆栈。这是go语言现在做的方式,也是Java发布后Project Loom的方式。
对于 real-world 种语言来说,这不是一件容易的事。
例如,它不适用于 C 和 C++,因为这些语言允许您指向堆栈上的内容。这些指针可以被其他线程使用,所以你不能把堆栈移走,即使你可以,你也必须把它复制回完全相同的地方。
出于同样的原因,当您的程序调用 OS 或本机代码并在同一线程中被回调时,它不起作用,因为有一部分堆栈您没有控制。在 Java 中,Loom 项目的 'virtual threads' 不会释放线程,只要堆栈上有本机代码。
即使在可以移动堆栈的情况下,也需要运行时环境的专门支持。堆栈不能只是 复制 到字节数组中。它必须以允许垃圾收集器识别其中所有指针的表示形式复制。例如,如果 C# 采用此技术,则需要对公共语言运行时进行重大扩展,而实现状态机可以完全在 C# 编译器中完成。
我一直在研究各种策略来做这件事,因为我自然地认为我可以比任何人都更好地设计一种语言 - 就像你一样。我只想强调,当我说 更好 时,我实际上是指 更好,因为我喜欢的味道更好,而不是客观上更好。
我得出了几种不同的方法,总结一下:这实际上取决于您在该语言中做出的许多其他设计选择。
一切都是为了妥协;每种方法都有优点和缺点。
感觉编译器设计社区仍然非常关注垃圾收集和最小化内存浪费,考虑到现代计算机可用的大量资源,对于更懒惰和不那么纯粹的语言设计者来说,也许还有一些创新的空间?
完全没有调用堆栈怎么样?
可以在不使用调用堆栈的情况下实现一种语言。
通过延续。当前运行 函数负责保持和恢复调用者的状态。 Async/await 和发电机自然而然。
为整个程序中所有声明的函数中的所有局部变量预分配静态内存地址。当然,这种方法会导致其他问题。
如果这是您的设计,那么异步函数似乎微不足道
树形堆栈
使用树形堆栈,您可以保留所有堆栈帧,直到函数完全完成。是否允许在任何祖先堆栈框架上取得进展并不重要,只要让异步框架继续运行直到不再需要它即可。
线性堆栈
如何序列化函数状态?这似乎是延续的变体。
堆上的独立堆栈帧
像对待堆上任何值的其他指针一样对待调用。
以上都是琐碎的方法,但它们有一个共同点与您的问题相关:
只需找到一种方法来存储恢复该功能所需的任何当地人。并且不要忘记将程序计数器也存储在堆栈帧中。
我正在尝试理解编译器/解释器/内核为您做的所有低级工作(因为我是另一个认为他们可以设计出比大多数其他语言更好的语言的人)
Async-Await 是激发我好奇心的众多事物之一。 我检查了几种语言的底层实现,包括 C#(编译器从糖代码生成状态机)和 Rust(必须从 Future 特性手动实现状态机),它们都是使用状态机实现 Async-Await。 我没有通过谷歌搜索(“异步复制堆栈框架”和变体)或“类似问题”部分找到任何有用的信息。
对我来说,这种方法似乎相当复杂且开销很大;
你能不能通过简单地 memcopy 异步调用的堆栈帧来实现 Async-Await to/from 堆?
我知道这对于某些语言在体系结构上是不可能的(感谢 CLR 做不到,所以 C# 也做不到)。
我是否遗漏了一些使这在逻辑上不可能的事情?我希望这样做的代码不那么复杂,性能也会提高,我错了吗?我想当你在异步调用(例如递归异步函数)后有一个深堆栈层次结构时,你必须 memcopy 的数据量相当大,但可能有解决这个问题的方法。
如果这是可能的,那为什么没有在任何地方完成?
首先我想说,这个答案只是作为一个起点,让您朝着实际的探索方向前进。这包括各种指导和其他作者的工作
I've checked the under-the-hood implementation for a couple languages, including C# (the compiler generates the state machine from sugar code) and Rust (where the state machine has to be implemented manually from the Future trait), and they all implement Async-Await using state machines
您正确理解 C#
和 Rust
的 Async/Await 实现使用状态机。现在让我们了解为什么选择这些实现。
用非常简单的术语来表达堆栈帧的一般结构,无论我们放入堆栈帧中的是什么,它们都不会比导致添加该堆栈帧的方法(包括但不包括仅限于局部变量)。它还包含延续的信息,即。在最近调用的方法的上下文中,接下来需要执行的代码的地址(换句话说,控件必须 return 到)。如果这是同步执行的情况,则方法一个接一个地执行。换句话说,调用方方法被挂起,直到被调用方方法完成执行。从堆栈的角度来看,这符合直觉。如果我们完成了一个被调用方法的执行,控制权被 returned 给调用者并且栈帧可以被弹出。从硬件的角度来看,它也是便宜且高效的,运行 这段代码也是如此(硬件针对堆栈编程进行了优化)。
在异步代码的情况下,一个方法的延续可能必须触发其他几个可能从调用者的延续中调用的方法。查看 this answer,其中 Eric Lippert 概述了堆栈如何为异步流工作的全部内容。异步流程的问题在于,方法调用并不完全形成一个堆栈,尝试像处理纯堆栈一样处理它们可能会变得极其复杂。正如埃里克在回答中所说,这就是为什么 C#
使用 代表工作流的 heap-allocated 任务和委托图 .
但是,如果您考虑像 Go
这样的语言,则异步处理的方式完全不同。我们有一个叫做 Goroutines
的东西,这里不需要 Go
中的 await
语句。这些 Goroutines
中的每一个都在它们自己的轻量级线程上启动(它们每个都有自己的堆栈,默认大小为 8KB)并且它们之间的同步是通过 channels
的通信实现的.这些轻量级线程能够异步等待在通道上执行的任何读取操作并自行挂起。 Go
中的早期实现是使用 SplitStacks technique. This implementation had its own problems as listed out here 完成的,并被 Contigious Stacks 取代。文章还讨论了较新的实现。
这里要注意的一件重要事情是,不仅仅是处理任务之间的连续性所涉及的复杂性有助于选择实施方法 Async/Await,还有其他因素,例如 Garbage Collection即发挥作用。 GC 过程应尽可能高效。如果我们四处移动堆栈,GC 就会变得低效,因为访问一个对象需要线程同步。
Could you not implement Async-Await by simply memcopying the stack frames of async calls to/from heap?
总之,可以。作为 Chicken Scheme 的 this answer states here, Chicken Scheme uses a something similar to what you are exploring. It begins by allocating everything on the stack and move the stack values to heap when it becomes too large for the GC activities (Chicken Scheme uses Generational GC). However, there are certain caveats with this kind of implementation. Take a look at this FAQ。这方面也有很多学术研究(链接在段落开头提到的答案中,我将在进一步阅读中总结)你可能想看看。
进一步阅读
call-with-current-continuation
This answer(包含很少指向该领域学术研究的链接)
TLDR
采用哪种方法的决定取决于影响语言的整体可用性和性能的因素。状态机并不是实现 C#
和 Rust
中完成的 Async/Await 功能的唯一方法。很少有像 Go
这样的语言实现 Contigious Stack 通过通道协调异步操作的方法。 Chicken Scheme
分配堆栈上的所有内容并将最近的堆栈值移动到堆中,以防它对其 GC 算法的性能变得沉重。移动堆栈有其自身的一组影响垃圾收集的负面影响。通读本文 space 中所做的研究将帮助您了解每种方法背后的进步和基本原理。同时,您还应该考虑如何规划 designing/implementing 您语言的其他部分,因为它在性能和整体可用性方面都接近可用。
PS:鉴于此答案的篇幅,我们很乐意纠正可能出现的任何不一致之处。
是的,将代码转换为状态机的另一种方法是复制堆栈。这是go语言现在做的方式,也是Java发布后Project Loom的方式。
对于 real-world 种语言来说,这不是一件容易的事。
例如,它不适用于 C 和 C++,因为这些语言允许您指向堆栈上的内容。这些指针可以被其他线程使用,所以你不能把堆栈移走,即使你可以,你也必须把它复制回完全相同的地方。
出于同样的原因,当您的程序调用 OS 或本机代码并在同一线程中被回调时,它不起作用,因为有一部分堆栈您没有控制。在 Java 中,Loom 项目的 'virtual threads' 不会释放线程,只要堆栈上有本机代码。
即使在可以移动堆栈的情况下,也需要运行时环境的专门支持。堆栈不能只是 复制 到字节数组中。它必须以允许垃圾收集器识别其中所有指针的表示形式复制。例如,如果 C# 采用此技术,则需要对公共语言运行时进行重大扩展,而实现状态机可以完全在 C# 编译器中完成。
我一直在研究各种策略来做这件事,因为我自然地认为我可以比任何人都更好地设计一种语言 - 就像你一样。我只想强调,当我说 更好 时,我实际上是指 更好,因为我喜欢的味道更好,而不是客观上更好。
我得出了几种不同的方法,总结一下:这实际上取决于您在该语言中做出的许多其他设计选择。
一切都是为了妥协;每种方法都有优点和缺点。
感觉编译器设计社区仍然非常关注垃圾收集和最小化内存浪费,考虑到现代计算机可用的大量资源,对于更懒惰和不那么纯粹的语言设计者来说,也许还有一些创新的空间?
完全没有调用堆栈怎么样?
可以在不使用调用堆栈的情况下实现一种语言。
通过延续。当前运行 函数负责保持和恢复调用者的状态。 Async/await 和发电机自然而然。
为整个程序中所有声明的函数中的所有局部变量预分配静态内存地址。当然,这种方法会导致其他问题。
如果这是您的设计,那么异步函数似乎微不足道
树形堆栈
使用树形堆栈,您可以保留所有堆栈帧,直到函数完全完成。是否允许在任何祖先堆栈框架上取得进展并不重要,只要让异步框架继续运行直到不再需要它即可。
线性堆栈
如何序列化函数状态?这似乎是延续的变体。
堆上的独立堆栈帧
像对待堆上任何值的其他指针一样对待调用。
以上都是琐碎的方法,但它们有一个共同点与您的问题相关:
只需找到一种方法来存储恢复该功能所需的任何当地人。并且不要忘记将程序计数器也存储在堆栈帧中。