From folklore to fact: comparing implementations of stacks and continuations
From folklore to fact: comparing implementations of stacks and continuations
复制标题
从民间传说到事实：比较堆栈和延续的实现
DOI：
10.1145/3385412.3385994
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Reppy, John
中科院分区：
文献类型：
--
作者：
Farvardin, Kavon;Reppy, John
函数调用和非本地控制转移的有效实现是现代语言实现的关键部分，对于实现从递归、高阶函数、并发和协同程序到基于任务的并行性的一切都很重要。在编译器中，这些特性可以由多种机制支持，包括调用栈、分段栈和堆分配的延续闭包。高级语言的高级控制特性的实现者可能会问这样一个问题：“我的实现的最佳选择是什么？不幸的是，目前的文献并没有提供太多的指导，因为以前的研究在方法上存在各种缺陷，并且对于现代硬件来说已经过时。在没有最近的，规范化的测量和全面的概述其实施细节，选择策略时阻力最小的路径是信任民俗，但民俗也suspiction.This本文试图纠正这种情况，提供一个“苹果到苹果”的比较六种不同的方法来实现调用堆栈和延续。这种比较使用相同的源语言，编译器管道，LLVM后端和运行时系统，唯一的差异是实现策略的差异所需的差异。我们比较不同的方法，其顺序的性能，其适用性，以支持先进的控制机制，包括支持重线程代码的实现挑战。除了实现策略的比较之外，本文的贡献还包括我们在沿着发现的一些有用的实现技术。
The efficient implementation of function calls and non-local control transfers is a critical part of modern language implementations and is important in the implementation of everything from recursion, higher-order functions, concurrency and coroutines, to task-based parallelism. In a compiler, these features can be supported by a variety of mechanisms, including call stacks, segmented stacks, and heap-allocated continuation closures.An implementor of a high-level language with advanced control features might ask the question ``what is the best choice for my implementation?'' Unfortunately, the current literature does not provide much guidance, since previous studies suffer from various flaws in methodology and are outdated for modern hardware. In the absence of recent, well-normalized measurements and a holistic overview of their implementation specifics, the path of least resistance when choosing a strategy is to trust folklore, but the folklore is also suspect.This paper attempts to remedy this situation by providing an ``apples-to-apples'' comparison of six different approaches to implementing call stacks and continuations. This comparison uses the same source language, compiler pipeline, LLVM-backend, and runtime system, with the only differences being those required by the differences in implementation strategy. We compare the implementation challenges of the different approaches, their sequential performance, and their suitability to support advanced control mechanisms, including supporting heavily threaded code. In addition to the comparison of implementation strategies, the paper's contributions also include a number of useful implementation techniques that we discovered along the way.
登录
查看更多内容
SML/NJ 编译器的可移植且优化的后端
DOI：
--
发表时间：
1994
期刊：
International Conference on Compiler Construction
影响因子：
--
作者：
Lal George;F. Guillame;John H. Reppy
通讯作者：
John H. Reppy
机器学习中的并发编程
DOI：
--
发表时间：
1999
期刊：
SOEN
影响因子：
--
作者：
John H. Reppy
通讯作者：
John H. Reppy
被调用者以连续传递方式保存寄存器
DOI：
--
发表时间：
1992
期刊：
LISP and Symbolic Computation
影响因子：
--
作者：
A. Appel;Zhong Shao
通讯作者：
Zhong Shao
DOI：
--
发表时间：
1960
期刊：
影响因子：
--
作者：
Edsger W. Dijkstra
通讯作者：
Edsger W. Dijkstra
DOI：
10.1017/cbo9781139174930
发表时间：
1997-01
期刊：
--
影响因子：
--
作者：
A. Appel;Maia Ginsburg
通讯作者：
A. Appel;Maia Ginsburg