Pharo 是否提供尾调用优化?
Does Pharo provide tail-call optimisation?
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 是否在任何情况下都执行尾部调用优化,它是否在进行其他一些优化,还是只是使用了一个非常深的堆栈?
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
。特别是我们可以看到这里并没有对栈进行特殊的操作。
这并不意味着底层本机代码不能进行优化。但这是一个不同的讨论。执行 model 对程序员来说很重要,因为字节码下的任何优化都是为了在概念层面支持这个模型。
更新
有趣的是,非递归版本
factorial2
| f |
f := 1.
2 to: self do: [:i | f := f * i].
^f
比递归的(Pharo)慢一点。原因一定是与增加 i
相关的开销比递归发送机制稍微大一点。
以下是我试过的表达方式:
[25000 factorial] timeToRun
[25000 factorial2] timeToRun
这是一个非常深的筹码。或者更确切地说,根本没有堆栈。
Pharo 是 Squeak 的后代,它直接从 Smalltalk-80 继承了它的执行语义。没有线性固定大小的堆栈,而是每个方法调用都会创建一个新的 MethodContext
对象,该对象在每个递归调用中为参数和临时变量提供 space。它还指向发送上下文(稍后 return)创建上下文链接列表(在调试器中显示就像堆栈一样)。上下文对象就像任何其他对象一样在堆上分配。这意味着调用链可以非常深,因为可以使用所有可用内存。您可以检查 thisContext
以查看当前活动的方法上下文。
分配所有这些上下文对象非常昂贵。为了速度,现代 VM(例如 Pharo 中使用的 Cog VM)实际上在内部使用了一个堆栈,它由链接页面组成,因此它也可以是任意大的。上下文对象仅按需创建(例如,在调试时)并引用隐藏的堆栈帧,反之亦然。这个幕后机制相当复杂,幸好对 Smalltalk 程序员隐藏了。
恕我直言,假定对 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'
实际上并非如此。 报告的字节码证明:
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 ]
生成 this picture 中报告的字节码。
顺便说一句,
n := 10000.
[n slowFactorial] timeToRun .
[n factorial] timeToRun.
[n factorial: 1] timeToRun.
在新的 Pharo 9 图像上,第一个和第二个都需要 29 毫秒,最后一个需要 595 毫秒。为什么这么慢?
不,Pharo 及其 VM 不优化递归尾调用。
从 运行 对 Pharo 9 图像的测试可以明显看出,master thesis on the subject 证实了这一点。
截至今天,Pharo 附带两种阶乘方法,一种 (Integer >> factorial) 使用 2-partition 算法并且效率最高,另一种如下所示:
Integer >> slowFactorial [
self > 0
ifTrue: [ ^ self * (self - 1) factorial ].
self = 0
ifTrue: [ ^ 1 ].
self error: 'Not valid for negative integers'
]
虽然有外层递归结构,但实际上还是调用了非递归的factorial方法。这可能解释了为什么 Massimo Nocentini 在为它们计时时得到几乎相同的结果。
如果我们尝试这个修改后的版本:
Integer >> recursiveFactorial [
self > 0
ifTrue: [ ^ self * (self - 1) recursiveFactorial ].
self = 0
ifTrue: [ ^ 1 ].
self error: 'Not valid for negative integers'
]
我们现在有了一个真正的递归方法,但是,正如 Massimo 指出的那样,它仍然不是 tail 递归的。
这是尾递归:
tailRecursiveFactorial: acc
^ self = 0
ifTrue: [ acc ]
ifFalse: [ self - 1 tailRecursiveFactorial: acc * self ]
如果没有尾部调用优化,这个版本显示出迄今为止最差的性能,甚至与 recursiveFactorial 相比也是如此。我认为那是因为它给堆栈增加了所有冗余中间结果的负担。
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 是否在任何情况下都执行尾部调用优化,它是否在进行其他一些优化,还是只是使用了一个非常深的堆栈?
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
。特别是我们可以看到这里并没有对栈进行特殊的操作。
这并不意味着底层本机代码不能进行优化。但这是一个不同的讨论。执行 model 对程序员来说很重要,因为字节码下的任何优化都是为了在概念层面支持这个模型。
更新
有趣的是,非递归版本
factorial2
| f |
f := 1.
2 to: self do: [:i | f := f * i].
^f
比递归的(Pharo)慢一点。原因一定是与增加 i
相关的开销比递归发送机制稍微大一点。
以下是我试过的表达方式:
[25000 factorial] timeToRun
[25000 factorial2] timeToRun
这是一个非常深的筹码。或者更确切地说,根本没有堆栈。
Pharo 是 Squeak 的后代,它直接从 Smalltalk-80 继承了它的执行语义。没有线性固定大小的堆栈,而是每个方法调用都会创建一个新的 MethodContext
对象,该对象在每个递归调用中为参数和临时变量提供 space。它还指向发送上下文(稍后 return)创建上下文链接列表(在调试器中显示就像堆栈一样)。上下文对象就像任何其他对象一样在堆上分配。这意味着调用链可以非常深,因为可以使用所有可用内存。您可以检查 thisContext
以查看当前活动的方法上下文。
分配所有这些上下文对象非常昂贵。为了速度,现代 VM(例如 Pharo 中使用的 Cog VM)实际上在内部使用了一个堆栈,它由链接页面组成,因此它也可以是任意大的。上下文对象仅按需创建(例如,在调试时)并引用隐藏的堆栈帧,反之亦然。这个幕后机制相当复杂,幸好对 Smalltalk 程序员隐藏了。
恕我直言,假定对 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'
实际上并非如此。
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 ]
生成 this picture 中报告的字节码。
顺便说一句,
n := 10000.
[n slowFactorial] timeToRun .
[n factorial] timeToRun.
[n factorial: 1] timeToRun.
在新的 Pharo 9 图像上,第一个和第二个都需要 29 毫秒,最后一个需要 595 毫秒。为什么这么慢?
不,Pharo 及其 VM 不优化递归尾调用。
从 运行 对 Pharo 9 图像的测试可以明显看出,master thesis on the subject 证实了这一点。
截至今天,Pharo 附带两种阶乘方法,一种 (Integer >> factorial) 使用 2-partition 算法并且效率最高,另一种如下所示:
Integer >> slowFactorial [
self > 0
ifTrue: [ ^ self * (self - 1) factorial ].
self = 0
ifTrue: [ ^ 1 ].
self error: 'Not valid for negative integers'
]
虽然有外层递归结构,但实际上还是调用了非递归的factorial方法。这可能解释了为什么 Massimo Nocentini 在为它们计时时得到几乎相同的结果。
如果我们尝试这个修改后的版本:
Integer >> recursiveFactorial [
self > 0
ifTrue: [ ^ self * (self - 1) recursiveFactorial ].
self = 0
ifTrue: [ ^ 1 ].
self error: 'Not valid for negative integers'
]
我们现在有了一个真正的递归方法,但是,正如 Massimo 指出的那样,它仍然不是 tail 递归的。
这是尾递归:
tailRecursiveFactorial: acc
^ self = 0
ifTrue: [ acc ]
ifFalse: [ self - 1 tailRecursiveFactorial: acc * self ]
如果没有尾部调用优化,这个版本显示出迄今为止最差的性能,甚至与 recursiveFactorial 相比也是如此。我认为那是因为它给堆栈增加了所有冗余中间结果的负担。