11

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

假设我有以下功能：

foobar x y = expensive x + cheap y

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

我可以保留代码原样，也可以将其更改为

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

这让我想知道...

  • GHC 是否足够聪明，可以自行消除重复工作？（即，第一个版本是否已经完成了我想要的操作？）

  • 如果不是，第二个版本是否真的解决了这个问题？（即，优化器是否会将其转换回与第一个版本相同的代码？）

4

3 回答 3

8 
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-expand/reduce（以及何时巧妙地改变严格行为/语义）对于编译器来说真的很棘手，所以 GHC 很大程度上依赖于你如何在语法上定义你的函数.

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

于 2013-07-27T17:43:04.297 回答
7

直觉上我的回答是否定的，是的。但是，让我通过尝试来回答您的问题。考虑这段代码：

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。如果我们禁用foobarand的内联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)。

于 2013-07-27T18:27:59.590 回答
0

看了一篇STG的各种论文，看来这就是所谓的full laziness transformation。似乎 [在撰写本文时] GHC确实应用了这种转换，但并非一直如此，因为它可能导致空间泄漏。

典型例子：

foo x = map f [1..1000000]

如果我们将其转换为

foo x = map f big

big = [1..1000000]

我们现在有一个巨大的 CAF 永远挂着 - 这可能不是程序员想要的！（我个人也被这种方式咬过，实际上......）

于 2014-01-31T15:42:43.840 回答