Haskell 执行速度怎样

Haskell 执行速度怎样

ghci是一个解释器，而且并没有进行速度方面的优化，速度当然不快。对于递归计算fibonacci而言，你如果使用ghc来编译，提供合适的类型提示（fibonacci :: Int -> Int就足够了）并且加上-O（优化）选项的话，那么速度将会达到C的50%。这速度自然完爆任何解释型语言，除了luajit和v8能勉强追上之外..

那么为什么ghc还是会比C慢一半呢？这就牵扯到现代CPU自身附带的优化了。递归计算fibonacci的时候，将会进行多次函数调用和返回。函数调用很简单，ghc和gcc生成的代码没什么区别。不过在函数返回这一点上，gcc会使用指令集里现有的返回指令（比如x86上就是ret），这样CPU的分支预测就可以准确预测返回地址，从而导致流水线不会出现停滞的情况。相反，ghc的调用协定就不同，它并不适用C的栈，所以在返回的时候并不使用原生的返回指令，而是使用一个indirect jump指令来完成（比如x86上就是jmp *(RXX)），这样就使得CPU无法准确预测返回地址，从而导致流水线经常会出现停滞的情况。流水线停滞会导致什么？会导致IPC（instruction per cycle，每CPU周期能运行的指令数量）下降，从而降低代码的运行速度。Reddit上面的这篇帖子里，Simon Marlow也谈到了他的SandyBridge i7在运行gcc和ghc生成的fibonacci代码时，IPC相差了3倍。

（当然并不是说函数返回时的分支预测的问题ghc就无法解决了——编译的时候也是可以提供一些代码来帮助CPU进行分支预测的，不过也许是因为ghc的开发者们觉得这个并不是那么重要）
^ 过了一年多的编辑：一个例子详见 Branch predication test ，runDirectThreading可以看作是ghc当前使用的方法，而runWithPredictor可以看作是一种提供了额外的预测代码的方法。Ivy Bridge/Haswell上，gcc-4.8 -O2编译，两者速度差别很大。

那么ghc为什么要这么做呢？这是因为，haskell是一种lazy functional的语言，其运行时环境和C相差太大，所以不使用C的栈而转而使用自己的一套调用协定将会更加合适——详见Implementing Lazy Functional Languages on Stock Hardware: The Spineless Tagless G-machine以及后续的Making a fast curry: push/enter vs. eval/apply for higher-order languages这两篇paper。