问题 运行一次子表达式


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

假设我有以下功能:

foobar x y = expensive x + cheap y

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

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

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

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

  • GHC足够智能,可以自行消除重复的工作吗? (即,第一个版本的确做了我想要的吗?)

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


1433
2017-07-27 17:19


起源

这不会改变语义, map (foo 5) []; foo a b = undefined a + b如果强制进行评估 foo 5 对于地图,你会不必要地爆炸 - jozefg
@jozefg let 不会强制进行评估。它是在第一次需要时进行评估(然后希望分享用于所有进一步的用途)。 - Daniel Fischer


答案:


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 在计算之间共享

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

我认为简短的回答是GHC 威力 将您的第一个函数转换为第二个函数,但唯一可以确定的方法是编写函数,以便语法为编译器提供有关如何内联以获得所需共享的提示,然后提供 INLINE 编译指示。这是另一个 有趣的讨论这个问题


8
2017-07-27 17:43



所以,基本上,主要的答案是“如果你关心它是哪一个,你应该明确地写第二个版本”(?) - MathematicalOrchid
@MathematicalOrchid我认为这可能是正确的。 - jberryman
对,那是正确的。 - augustss
如果有人有兴趣,我只是发布了一个旧的想法,用于替代内联语法 GHC功能请求。会对任何人是否有意义或似乎是一个好主意感兴趣。 - jberryman


直觉我的回答是 没有,和 。但是,让我通过尝试来回答你的问题。考虑以下代码:

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

所以编译器足够聪明,也可以优化原始版本。但为什么?因为他列出了定义 foobar 在 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)。


7
2017-07-27 18:27





阅读各种STG论文之一,似乎这就是所谓的 完全懒惰的转变。似乎[在撰写论文时] GHC  应用此转换,但不是所有时间,因为它可能导致空间泄漏。

典型例子:

foo x = map f [1..1000000]

如果我们将其转化为

foo x = map f big

big = [1..1000000]

我们现在有一个巨大的CAF永远徘徊 - 这可能不是程序员想要的! (我个人被这种方式咬了,实际上......)


0
2018-01-31 15:42