运行一次子表达式

Question

好吧,所以这困扰了我一段时间,所以我想我会来问一个可能真正知道答案的人.

假设我有以下功能:

foobar x y = expensive x + cheap y

进一步假设该程序的一部分foobar 5作为输入,并在紧密循环中执行该功能数百万次.显然,我希望expensive 5计算一次,而不是一百万次.

我可以保留代码,或者我可以将其更改为

foobar x = let k = expensive x in \ y -> k + cheap y

这让我想知道......

• GHC是否足够智能,可以自行消除重复的工作？(也就是说,第一个版本能做我想要的吗？)

• 如果不是,第二个版本是否确实解决了问题？(即,优化器是否会将其转换回与第一个版本相同的代码？)

Answer 1

Is GHC smart enough to eliminate the duplicated work by itself? (I.e., does the first version do what I want already?)

我觉得问这个的另一种方式是:将GHC内联foobar x y,这样expensive x的计算之间共享？

我问了一个类似的问题,清除了一些东西,但让我有点不满意.据我了解,确定如何以及何时内联或依次扩展/减少事物(以及何时巧妙地改变严格行为/语义)对于编译器来说真的很棘手,所以GHC在很大程度上依赖于你如何在语法上定义你的函数.

我认为简短的回答是GHC 可能会将您的第一个函数转换为第二个函数,但唯一可以确定的方法是编写函数,以便语法为编译器提供有关如何内联以获取共享的提示你想要的,然后提供INLINEpragma.这是关于这个问题的另一个有趣的讨论

Answer 2

直觉上我的回答是否定的,是的.但是,让我通过尝试来回答你的问题.考虑以下代码:

import Debug.Trace

expensive :: Int -> Int
expensive x = trace ("expensive evaluated for " ++ show x) $ x
{-# NOINLINE expensive #-}

cheap :: Int -> Int
cheap x = x
{-# NOINLINE cheap #-}

foobar x y = expensive x + cheap y

foobar' x = let k = expensive x in \ y -> k + cheap y

part f = sum [f i| i<-[0..10]]

main = do
    print $ part (foobar 5)
    print $ part (foobar' 5)

如果我们运行它,结果是

$ ./Test 
expensive evaluated for 5
110
expensive evaluated for 5
110

所以编译器足够聪明,也可以优化原始版本.但为什么？因为他内联了foobarin 的定义main,然后注意到它可以将表达式expensive 5浮出调用part.如果我们禁用内联foobar和foobar'(或者不使用-O),它将不再起作用:

$ ./Test 
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
expensive evaluated for 5
110
expensive evaluated for 5
110

因此,虽然GHC在某些情况下可以做正确的事情,但如果你想依赖它,你应该总是检查是否是这种情况.要么使用类似的工具Debug.Trace,要么通过查看核心(-ddump-simpl).