Ruby Tail call optimization In Ruby1.9

hooopo · 2012年09月04日 · 最后由 fsword 回复于 2012年09月05日 · 2704 次阅读

def fib(n) return 1 if n == 0 || n == 1 return fib(n - 1) + fib(n - 2) end fib(40)

开启TCO版本:

RubyVM::InstructionSequence.compile_option = { :tailcall_optimization => true, :trace_instruction => false }

RubyVM::InstructionSequence.new(<<-EOF).eval def fib(n) return 1 if n == 0 || n == 1 return fib(n - 1) + fib(n - 2) end EOF

fib(40)

在我机器上第一个跑了40s,第二个35s。还是有一点儿效果的:-) ps: Ruby1.9默认TOC是关闭的,只有通过RubyVM::InstructionSequence.new.eval的方法才能开启优化。

refs:

  1. http://blog.grayproductions.net/articles/the_ruby_vm_episode_v
  2. http://jabberwocky.eu/2010/11/23/tail-call-optimization/
  3. http://timelessrepo.com/tailin-ruby
共收到 20 条回复

good。。有没什么副作用?要不为何默认关闭

#1楼 @jjym 因为貌似只有MRI有。

因为开了不一定会快而且某些情况下是不对的...

这个东西的主要功效不是加速,是让递归调用不会栈溢出吧…

InstructionSequence.compile_option 是全局选项,后面的所有代码不需要 InstructionSequence.new 了。

只用特定参数编译一段代码,可以用 InstructionSequence.new src, file, path, line, opts (new 和 compile 是同一个方法)

opts = {
  tailcall_optimization: false,
  trace_instruction: false
}
iseq = RubyVM::InstructionSequence.compile <<-RUBY, nil, nil, nil, opts
  def fib(n)
    return 1 if n == 0 || n == 1 
    return fib(n - 1) + fib(n - 2)
  end
RUBY
puts iseq.disasm

输出如下

== disasm: <RubyVM::InstructionSequence:<compiled>@<compiled>>==========
0000 putspecialobject 1
0002 putspecialobject 2
0004 putobject        :fib
0006 putiseq          fib
0008 send             :"core#define_method", 3, nil, 0, <ic:0>
0014 leave            
== disasm: <RubyVM::InstructionSequence:fib@<compiled>>=================
local table (size: 2, argc: 1 [opts: 0, rest: -1, post: 0, block: -1] s1)
[ 2] n<Arg>     
0000 getlocal         n                                               (   1)
0002 putobject        0
0004 opt_eq           <ic:7>
0006 branchif         16
0008 getlocal         n
0010 putobject        1
0012 opt_eq           <ic:8>
0014 branchunless     21
0016 jump             18
0018 putobject        1
0020 leave            
0021 putself                                                          (   2)
0022 getlocal         n
0024 putobject        1
0026 opt_minus        <ic:9>
0028 send             :fib, 1, nil, 8, <ic:3>
0034 putself          
0035 getlocal         n
0037 putobject        2
0039 opt_minus        <ic:10>
0041 send             :fib, 1, nil, 8, <ic:5>
0047 opt_plus         <ic:11>
0049 leave 

@hooopo 你那个例子速度变快的原因应该是 :trace_instruction => false 去掉了编译后的 trace 指令 (默认 trace 是打开的)

这个例子不是尾递归,最后一个指令是 opt_plus,不是递归调用 send :fib (所有 opt_ 开头的指令都是为了优化特定 code pattern 的,opt_plus 相当于 send :+ 但为整数优化了)

不过尾调用优化和尾递归优化不同,尾递归优化把字节码里的某些递归变成循环,尾调用优化不改写字节码,但在运行的时候碰到 return method call 时就改写栈帧(或者说只把 send 指令改成 tail_send 指令),改写耗的时间往往比增长栈多,所以除了避免暴栈以外作用很微...

#5楼 @luikore 看来是我理解错了。我以为会像Erlang那样把非尾递归的写法转换成尾递归写法。

MRI 没把尾调用放到指令集中而是直接替换 send 的实现,@hooopo 的例子尾调用优化其实是发生在 fib(40) 中 ...

刚刚也是觉得fib这个例子不大好,记得就是haskell也是没办法直接将fib优化成循环的样子...

于是写了个fact的例子:

require 'date'

def prof 
  t0 = DateTime.now
  yield
  p (DateTime.now - t0).to_f
end

def fact(n)
  r = 1
  i = 1
  while i <= n
    r*=i
    i+=1
  end
  return r
end

def fact0(n)
  return 1 if n == 0 || n == 1 
  return n * fact0(n-1)
end

prof { fact(4000) } 
prof { fact0(4000) }

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

def fact1(n)
  return 1 if n == 0 || n == 1 
  return n * fact1(n-1)
end

def _fact2(r, n)
  return r if n <= 1 
  return _fact2(r*n, n-1)
end

def fact2(n)
  _fact2(1, n)
end


prof { fact1(4000) }
prof { fact2(4000)}

结果fact2最慢 = =

update: 调大数据fact2是最后一个报stack overflow的倒是...

#8楼 @fleuria 看来只能避免stack level too deep

更确切的说是能避免尾递归写法的stack level too deep?

#6楼 @hooopo erlang也不能把非尾递归转换成尾递归啊

#10楼 @fsword 那传说的Erlang尾递归优化是指的什么?

#11楼 @hooopo 尾递归是一种特殊结构的递归,如果程序员写的递归属于这类结构,编译器可以做针对性的优化(比如因为没有对递归返回值的处理,所以可以直接丢掉栈帧信息),仅此而已

#12楼 @fsword 不是吧

这是《Erlang编程指南》里的一段话:

关于Erlang性能的主要传说之一:Erlang中尾递归要比直接递归有效的多。在该语言初期也许是真的。但在对发行版7到12进行了优化之后,如果还继续认为尾递归让你的程序更有效率那就不再正确了。

难到不是说Erlang里非尾递归也会很有效率?

不是你说的只有程序员写成尾递归寒数编译器才能优化吧

#13楼 @hooopo 这一段我就不理解了,去请教一下

#13楼 @hooopo Erlang里已经没尾递归优化一说了吧。现在看上去像是,只要调用另外一个函数是这个函数最后一个求值就不会额外占用栈。

早期会占用是因为那个JAM完全就是照着Prolog那个WAM来的,这其实是因为第一代的Erlang其实就是一个Prolog的库。

#15楼 @bhuztez 我也是这么理解的,不过这句话继续认为尾递归让你的程序更有效率那就不再正确了感觉莫名其妙,不用尾递归erlang应该还是会爆栈的啊

我一直觉得尾递归被神话了,感觉这个概念是因为不可变性被引入后没法做循环而导致的

#16楼 @fsword 你可以把JAM的代码去挖出来和现在的BEAM对比一下,说不定能看出来

#18楼 @bhuztez 这你可高估我了,语言实现我是彻底的门外汉

问了一下yufeng,回复——

实际上是这样的,递归用的堆内存,尾递归用的是栈的内存
所以总体现在性能差不多
除非递归的深度非常深

看起来erlang没有改造普通递归(我觉得也改不了),但是尾递归只能避免爆栈,对于性能没优势

jasl 最近的一点小感悟 中提及了此贴 10月31日 14:43
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册