ghci编译器优化:两次调用具有相同参数的函数

Question

在下面的简单代码中,从二叉搜索树中删除元素的函数定义的一部分:

 deleteB x (Node n l r) | x == n = Node (leastB r) l (deleteB (leastB r) r)

编译器是否优化了代码,以便它只调用(至少B r)一次,就好像它是:

 deleteB x (Node n l r) | x == n = Node k l (deleteB k r)
                          where k = leastB r

？

换句话说,编译器是否能够理解由于参数r在函数deleteB的主体内没有改变,因此调用相同函数(leastB)的结果不能给出不同的结果,因此它是没用它来计算两次？

更一般地说,如果编译器执行此优化,我将如何理解是否存在令人惊讶的stackoverflow？谢谢

Answer 1

如果你想知道GHC"真正做了什么",你想看看"核心"输出.

GHC采用非常高级的Haskell源代码,并将其转换为低级和低级语言的序列:

Haskell⇒核心⇒STG⇒C--⇒汇编语言⇒机器代码

几乎所有的高级优化都发生在Core中.你要问的那个基本上是"常见的子表达消除"(CSE).如果你考虑一下,这是一个时间/空间权衡; 通过保存以前的结果,您使用的CPU时间更少,但也使用更多的RAM.如果您尝试存储的结果很小(即整数),那么这是值得的.如果结果很大(即刚刚加载的17GB文本文件的全部内容),这可能是一个非常糟糕的主意.

据我了解(⇒不太好!),GHC往往不做CSE.但是,如果您想确切地知道,在您的特定情况下,您希望查看您的程序实际编译到的Core.我相信你想要的开关是--ddump-prep.

http://www.haskell.org/ghc/docs/7.0.2/html/users_guide/options-debugging.html

Answer 2

GHC不执行此优化，因为它并不总是在空间方面进行优化。

例如，考虑

n = 1000000
x = (length $ map succ [1..n], length $ map pred [1..n])

在像Haskell这样的惰性语言上，人们会希望它在恒定的空间中运行。确实，生成列表的表达式[1..n]应该一次懒惰地生成一个元素，由于s 会受到succ/ 影响，然后由计数。（甚至更好，并且因为不强制使用list元素而根本不计算）。之后，可以对产生的元素进行垃圾回收，并且列表生成器可以产生下一个元素，依此类推。在实际的实现中，人们不会期望立即对每个元素进行垃圾收集，但是如果垃圾收集器良好，则随时都应该在内存中保留一定数量的元素。predmaplengthsuccpredlength

相比之下，“优化”代码

n = 1000000
l = [1..n]
x = (length $ map succ l, length $ map pred l)

在对的l两个组成部分x都进行评估之前，不允许对的元素进行垃圾收集。因此，虽然它仅产生一次列表，但它使用O（n）内存字来存储完整列表。与未优化的代码相比，这可能导致性能降低。