ghci的編譯器優化：調用具有相同參數的函數兩次

在下面的簡單的代碼，即從二叉查找樹中刪除的元素的函數的定義的一部分：ghci的編譯器優化：調用具有相同參數的函數兩次

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）的結果不能給出不同的結果，因此計算兩次是沒有用的？

更一般地說，如果編譯器做了這種優化或者沒有驚人的計算器不存在，我該如何理解該編譯器？謝謝

來源

2014-05-01 sowdust

GHC將不會這樣做：http://www.haskell.org/haskellwiki/GHC/FAQ#Does_GHC_do_common_subexpression_elimination.3F – user2407038

GHC不執行該優化。

例如，考慮

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

在一個慵懶的語言如Haskell中，一個希望它可以在不變空間運行。事實上，產生表達式[1..n]的列表應當一次延遲地產生一個元素，由於maps的原因，這將受到succ/pred的影響，然後由length進行計數。（更好的是，succ和pred根本不計算，因爲length不強制列表元素）。在此之後，生成的元素可以被垃圾收集，列表生成器可以生成下一個元素，依此類推。在實際的實現中，人們不會期望每個單元都立即被垃圾收集，但是如果垃圾收集器是好的，那麼隨時都只有內存中的數量不變。

通過比較，「優化的」代碼

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

不允許垃圾收集的l元件直到x兩種組分進行評估。所以，雖然它只產生一次列表，但它使用內存的O（n）字來存儲完整列表。這可能會導致比未優化的代碼更低的性能。

來源

2014-05-01 14:31:24 chi

其實最近有關於Haskell-Cafe的討論，其中GHC特別列出文字... hmm – jozefg

@jozefg有趣。我承認我沒有及時更新GHC優化。然而，浮動和CSE是不同的。雖然浮動在某些情況下似乎很危險。 – chi

如果你想知道什麼GHC「真的」，你想看看「核心」輸出。

GHC需要你的Haskell源代碼，這是非常高級的，並將其轉換爲低和較低級別的語言的序列：

的Haskell ⇒核心⇒ STG ⇒Ç− − ⇒彙編語言⇒機代碼

幾乎所有的高級優化都發生在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

來源

2014-05-01 12:25:34 MathematicalOrchid

我認爲GHC會真正走出去的方式不這樣做 - 因爲你有工具讓它你明確地說出你想要的（'where'，'let'）。 +1核心檢查建議tho – ScarletAmaranth

ghci的編譯器優化：調用具有相同參數的函數兩次

回答

相關問題