Pharo是否提供尾调优化？

Question

Integer>>#factorialPharo 的实施是:

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的执行模型毫无疑问.递归片段

^ 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选择器是其他任何代码,代码就会以相同的方式发送.特别是我们可以看到这里没有对堆栈的特殊操作.

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

UPDATE

有趣的是,非递归版本

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

递归的一个(Pharo)有点慢.原因必须是与增加相关的开销i比递归发送机制稍微大一些.

这是我试过的表达式:

[25000 factorial] timeToRun
[25000 factorial2] timeToRun

Answer 2

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

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

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