Pharo是否提供尾部调用优化

Question

Pharo 中 Integer>>#factorial 的实现是：

factorial
        "Answer the factorial of the receiver."
        self = 0 ifTrue: [^ 1].
        self > 0 ifTrue: [^ self * (self - 1) factorial].
        self error: 'Not valid for negative integers'

这是一个尾递归定义。但是，我可以在工作区中评估10000 factorial而不会出错。

Pharo是否在任何情况下都执行尾部调用优化，是进行其他优化，还是只是使用非常深的堆栈？

Answer 1

这是一个非常深的堆栈。或者更确切地说，根本没有堆栈。

Pharo是Squeak的后代，Squeak直接从Smalltalk-80继承了它的执行语义。没有线性固定大小的堆栈，而是每个方法调用都会创建一个新的MethodContext对象，该对象为每个递归调用中的参数和临时变量提供空间。它还指向发送上下文(供以后返回(创建上下文链表(就像调试器中的堆栈一样显示(。上下文对象在堆上分配，就像任何其他对象一样。这意味着调用链可能非常深，因为可以使用所有可用内存。您可以检查thisContext以查看当前活动的方法上下文。

分配所有这些上下文对象是昂贵的。为了速度，现代虚拟机(例如Pharo中使用的Cog VM(实际上在内部使用堆栈，该堆栈由链接页面组成，因此它也可以任意大。上下文对象仅按需创建(例如在调试时(，并引用隐藏的堆栈帧，反之亦然。幕后的这个机制相当复杂，但幸运的是，Smalltalk程序员隐藏了它。

Answer 2

Pharo的执行模式并不神秘。递归片段

^ self * (self - 1) factorial

这发生在编译为以下字节码序列的第二个ifTrue:中：

39 <70> self                  ; receiver of outer message *
40 <70> self                  ; receiver of inner message -
41 <76> pushConstant: 1       ; argument of self - 1
42 <B1> send: -               ; subtract
43 <D0> send: factorial       ; send factorial (nothing special here!) 
44 <B8> send: *               ; multiply
45 <7C> returnTop             ; return

请注意，在第 43 行中没有发生任何异常情况。代码只是以与选择器相同的方式发送factorial，如果选择器是任何其他选择器。特别是我们可以看到，这里没有对堆栈进行特殊操作。

这并不意味着基础本机代码中不能进行优化。但这是一个不同的讨论。执行模型对程序员来说很重要，因为字节码下的任何优化都是为了在概念级别支持这个模型。

更新

有趣的是，非递归版本

factorial2
  | f |
  f := 1.
  2 to: self do: [:i | f := f * i].
  ^f

比递归的(Pharo(慢一点。原因一定是与增加i相关的开销比递归发送机制大一点。

以下是我尝试过的表达式：

[25000 factorial] timeToRun
[25000 factorial2] timeToRun

Answer 3

恕

我直言，假定具有尾部递归调用的初始代码factorial

factorial
        "Answer the factorial of the receiver."
        self = 0 ifTrue: [^ 1].
        self > 0 ifTrue: [^ self * (self - 1) factorial].
        self error: 'Not valid for negative integers'

其实不然。Leandro的回复报告的字节码证明：

39 <70> self                  ; receiver of outer message *
40 <70> self                  ; receiver of inner message -
41 <76> pushConstant: 1       ; argument of self - 1
42 <B1> send: -               ; subtract
43 <D0> send: factorial       ; send factorial (nothing special here!) 
44 <B8> send: *               ; multiply
45 <7C> returnTop             ; return

在returnTop之前，发送*而不是factorial.我会使用累加器写一条消息作为

factorial: acc
    ^ self = 0
        ifTrue: [ acc ]
        ifFalse: [ self - 1 factorial: acc * self ]

这将生成此图中报告的字节码。

顺便说一句，

n := 10000.
[n slowFactorial] timeToRun .
[n factorial] timeToRun.
[n factorial: 1] timeToRun.

第一个和第二个都需要 29 毫秒，最后一个在新鲜的 Pharo 9 图像上需要 595 毫秒。为什么这么慢？

Answer 4

不，Pharo 及其 VM 不会优化递归尾调用。

从对Pharo 9图像的运行测试中可以明显看出，这篇关于该主题的硕士论文证实了这一点。

截至今天，Pharo 提供了两种阶乘方法，一种(整数>>阶乘(使用 2 分区算法并且是最有效的，另一种如下所示：

Integer >> slowFactorial [
    self > 0
        ifTrue: [ ^ self * (self - 1) factorial ].
    self = 0
        ifTrue: [ ^ 1 ].
    self error: 'Not valid for negative integers'
]

它有一个外部递归结构，但实际上仍然调用非递归阶乘方法。这可能解释了为什么马西莫·诺森蒂尼(Massimo Nocentini(在计时时会得到几乎相同的结果。

如果我们尝试这个修改版本：

Integer >> recursiveFactorial [
    self > 0
        ifTrue: [ ^ self * (self - 1) recursiveFactorial ].
    self = 0
        ifTrue: [ ^ 1 ].
    self error: 'Not valid for negative integers'
]

我们现在有一个真正的递归方法，但是，正如Massimo指出的那样，它仍然不是尾递归。

这是尾递归：

tailRecursiveFactorial: acc
^ self = 0
    ifTrue: [ acc ]
    ifFalse: [ self - 1 tailRecursiveFactorial: acc * self ]

如果没有尾部调用优化，即使与递归阶乘相比，此版本也显示出迄今为止最差的性能。我认为这是因为它给堆栈带来了所有冗余的中间结果。