GHC的优化程度是多少？

Question

我对Haskell/GHC优化代码的程度不是很熟悉。下面是一个相当“暴力”（在声明性方面）的n皇后问题实现。我知道它可以更有效地编写，但这不是我的问题。我的问题是这让我开始思考GHC优化能力和限制。

我以我认为相当直接的声明方式表达了它。过滤满足谓词对于所有索引i,j s.t j<i, abs(vi - vj) != j-i的[1..n]的排列。我希望这是一种可以优化的东西，但它也感觉像是要求编译器做很多事情。

validQueens x = and [abs (x!!i - x!!j) /= j-i | i<-[0..length x - 2], j<-[i+1..length x - 1]] 

queens n = filter validQueens (permutations [1..n])

oneThru x = [1..x]    
pointlessQueens = filter validQueens . permutations . oneThru

main = do
          n <- getLine 
          print $ pointlessQueens $ (read :: String -> Int) n

这段代码运行缓慢且增长迅速。当n=10时需要大约一秒钟，而n=12则需要很长时间。没有优化的情况下，我可以确定增长是阶乘（排列数）乘以二次方程式（要检查的谓词中的差异数）。是否有任何方法可以通过智能编译使此代码更快？我尝试了基本的ghc选项，如-O2，但没有注意到显着的差异，但我不知道细节（只添加了标志）。

我的印象是，我调用的函数queens不能被优化，并且必须在过滤之前生成所有排列。点无版本有更好的机会吗？一方面，我觉得一个聪明的函数理解可能会在完全生成之前从筛选器和谓词之间削减一些明显不需要的元素，但另一方面，这似乎有点困难。

如果这看起来有点混乱，请原谅，我想问的问题是：

1. 以上函数的点无版本是否更有优化能力？
2. 我可以采取哪些步骤，在编译/链接时鼓励优化？
3. 您能简要描述一些可能的（并与不可能进行对比！）上述代码的优化方法吗？这些过程在哪个阶段发生？
4. 我应该关注ghc --make queensN -O2 -v输出的哪个特定部分？对我来说没有什么特别突出的地方。甚至由于优化标志而看不到太多输出差异。

我不过分关注此代码示例，但我认为编写它让我思考，并且对于讨论优化似乎是一个不错的工具。

PS- permutations来自Data.List，看起来像这样：

permutations            :: [a] -> [[a]]
permutations xs0        =  xs0 : perms xs0 []
  where
    perms []     _  = []
    perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
      where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
            interleave' _ []     r = (ts, r)
            interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
                                     in  (y:us, f (t:y:us) : zs)

- jon_darkstar

---

无意义或有意义并不重要。一般而言，糟糕的算法是编译器无法修复的少数问题之一（对于相对简单的事情，如将递归阶乘转换为循环，尤其是对于聪明的编译器例外）。 - user395760

你选择了一个糟糕的算法，ghc 无法为你解决这个问题。 - augustss

可能只是我个人的感觉，但我认为这个问题的前提可能过于宽泛，无法以任何直接的方式回答：我目前理解这个问题背后的驱动力是：“可以在纯粹的声明式函数代码上进行哪些通用的、节省成本的整体程序转换”，这似乎是一个完整的研究领域，而且在很大程度上依赖于给定的问题域。@delnan的观点非常尖锐；即使使用现代“智能”编译器，计算复杂度仍然占主导地位。 - Raeez

我认为这个问题的前提很好，但是在我看来，最好限制问题只涉及编译器实际进行了哪些优化，并提供一个算法的代码示例，该算法具有可接受的效率。再次强调，这只是我的个人意见。 - HaskellElephant

顺便提一句，oneThru = enumFromTo 1。（翻译：BTW是“顺便提一句”的意思；oneThru = enumFromTo 1表示将从1开始的整数序列生成为一个枚举类型） - augustss

谢谢大家的回答 - 我知道这个问题有点宽泛，但仍然有一些非常有信息量的答案/评论。我想知道的是，(.)函数组合是否会在幕后发生任何聪明的事情，看起来答案是否定的。 - jon_darkstar

Answer 1

在更一般的层面上，关于"GHC 能够进行哪种优化"，可以将"优化"这个概念分解一下。存在一些概念性的区别可以用来划分可以被优化的程序方面。例如：

• 算法的内在逻辑结构：几乎每种情况下都可以安全地假设这部分永远不会被优化。除了实验性研究外，你不太可能找到一个编译器来用归并排序或插入排序替代冒泡排序，甚至很难找到一个能用合理的方法替代bogosort。

• 算法的非必要逻辑结构：例如，在表达式g (f x) (f x)中，f x会被计算多少次？在表达式g (f x 2) (f x 5)中呢？这些都不是算法本身固有的，而且不同的变体可以交换而不会影响任何东西，除了效率。在这里进行优化的难点基本上是识别何时可以进行替换，而不改变含义，以及预测哪个版本会有最好的结果。许多手动优化都属于这个范畴，连同 GHC 的大量巧妙之处。

  这也是很多人被绊倒的部分，因为他们看到 GHC 有多聪明，期望它能做更多事情。由于合理的期望是 GHC 不应该让事情变得更糟，因此很常见有潜在的优化看起来显而易见（对程序员来说是这样），但 GHC 不能应用，因为区分同一转换会显著降低性能的情况并非易事。例如，这就是为什么记忆化和共同表达式消除不总是自动完成的原因。

这也是 GHC 有巨大优势的一部分，因为惰性和纯度使得很多事情变得更容易。我猜这也是人们会开玩笑说"优化编译器都是神话（除了 Haskell 可能之外）"的原因，但也让人们对 GHC 的能力过于乐观。

底层细节：比如内存布局以及代码最终形态的其他方面。这些通常是相当深奥的，并且高度依赖运行时、操作系统和处理器的实现细节。这种类型的优化基本上就是编译器的存在原因，通常不需要担心，除非你正在编写非常计算密集型的代码（或者自己在编写编译器）。

至于您特定的例子：GHC 不会显著改变您算法的固有时间复杂度。它可能能够消除一些常数因子。它无法应用不确定是否正确的常数因子改进，尤其是那些从技术上改变程序意义的方式，而您并不关心这些的改变。@sclv 的答案就是一个例子，他解释了您使用 print 会创建不必要的开销；GHC 无能为力，事实上当前形式可能会抑制其他优化。

- C. A. McCann

---

只是一种想法：据我所知，可以从Haskell生成C源代码，我想——也许这样做有意义，然后再使用GCC进行编译？GCC正在不断改进，而且它最近相对较新地获得了所谓的“链接时优化”。 - Hi-Angel

Answer 2

这里存在一个概念问题。Permutations正在生成流式排列，而filter也在进行流式处理。导致过早强制执行的是“显示”在“打印”中的隐含操作。将最后一行改为以下内容：

mapM print $ pointlessQueens $ (read :: String -> Int) n

您会发现结果以流式方式生成得更快。对于大型结果集，这修复了潜在的空间泄漏问题，除此之外，它只是按计算出的内容逐个打印，而不是一次性打印所有内容。

然而，您不应该期望从ghc优化中获得数量级的改进（有一些明显的优化，主要与严格性和折叠有关，但依赖它们很烦人）。通常，您将获得常数因子。

编辑：正如luqui在下面指出的那样，show也是流式的（或者至少[Int]的show是），但行缓冲使真正的计算速度更难看到...

- sclv

---

你是说只是行缓冲强制太多了吗？！show也在流式传输。 - luqui

很好的观点。这完全不是我所期望的，我很高兴你提出来了。 - jon_darkstar

Answer 3

需要翻译的内容如下：

需要注意的是，虽然您表达了这不是您问题的一部分，但您的代码存在一个严重问题，即没有进行任何修剪。

在您的问题中，当我们面对一个算法改进时，谈论可能/不可能的优化、编译器标志以及如何最佳构造等感觉很愚蠢。

首先尝试的是以第一个皇后在位置1，第二个皇后在位置2（[1,2...]）开始的排列。当然，这不是一个解决方案，我们必须移动其中一个皇后。然而，在您的实现中，将测试涉及这两个第一位皇后组合的所有排列！搜索应该在那里停止并立即转移到涉及 [1,3,...] 的排列。

这里是一个执行此类修剪的版本：

import Data.List
import Control.Monad

main = getLine >>= mapM print . queens . read

queens :: Int -> [[Int]]
queens n = queens' [] n

queens' xs n 
 | length xs == n = return xs 
 | otherwise = do 
  x <- [1..n] \\ xs
  guard (validQueens (x:xs))
  queens' (x:xs) n

validQueens x = 
  and [abs (x!!i - x!!j) /= j-i | i<-[0..length x - 2], j<-[i+1..length x - 1]]

- HaskellElephant

---

我主要想知道编译器优化函数组合与filter是否可以自动实现一些修剪。而且我肯定避免任何命令式逻辑，认为这会危及任何这样的机会。我的想法是部分构造排列的短路逻辑组合可能会在构造完成之前拒绝那些明显的坏情况（尽管可能无法学会避免所有这样的情况）。然而，看起来很明显我有点过于乐观了。 - jon_darkstar

我真的很喜欢你如何实现修剪并完全消除了“排列”的需要。如果问题是“重写这段代码”，我可能会接受另一个，因为你没有告诉我太多关于编译器优化，但你做得很好。 - jon_darkstar

有趣的是，你的 queens 在每一步都使用守卫条件作为过滤器来生成所有这些整数排列。看起来这是一个值得记住的模式。 - jon_darkstar

@jon_darkstar，我知道我没有说太多关于编译器优化，这是一个缺点，但我仍然觉得这个答案有所贡献。至于为什么过滤器不会为您执行此修剪操作，是因为，正如您已经意识到的那样，尽管惰性评估避免了很多检查，但仍必须进行n！次检查。编译器无法缩短您的排列列表，因为不能保证每个lambda表达式内部只评估一次函数调用的原则。 - HaskellElephant

Answer 4

我了解到你的问题是关于编译器优化的，但是讨论表明修剪是必要的。

我所知道的第一篇关于如何在惰性函数语言中解决N皇后问题的修剪的论文是Turner的“递归方程作为编程语言”。你可以在Google Books 这里 阅读它。

关于您提到的值得记住的模式，这个问题引入了一个非常强大的模式。关于这个想法的一篇很好的论文是Philip Wadler的论文，“如何用成功列表替换失败”，可以在Google Books 这里 阅读。

以下是基于Turner's Miranda实现的纯粹的、非单子的实现。在n = 12的情况下（queens 12 12），它会在0.01秒内返回第一个解决方案，并在不到6秒的时间内计算出所有14,200个解决方案。当然，打印这些需要更长的时间。

queens :: Int -> Int -> [[Int]]
queens n boardsize = 
    queensi n 
        where
          -- given a safe arrangement  of queens in the first n - 1 rows,
          -- "queensi n" returns a list of all the safe arrangements of queens
          -- in the first n rows
          queensi :: Int -> [[Int]]
          queensi 0  = [[]]
          queensi n  = [ x : y | y <- queensi (n-1) , x <- [1..boardsize], safe x y 1]

-- "safe x y n" tests whether a queen at column x would be safe from previous
-- queens in y where the first element of y is n rows away from x, the second
-- element is (n+1) rows away from x, etc.
safe :: Int -> [Int] -> Int -> Bool
safe _ [] _ = True
safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]
-- we only need to check for queens in the same column, and the same diagonals;
-- queens in the same row are not possible by the fact that we only pick one
-- queen per row

- George Co