GHC优化的范围

Question

我不太熟悉Haskell/GHC可以优化代码的程度.下面我有一个非常"蛮力"(在声明意义上)实施n皇后问题.我知道它可以更有效地编写,但那不是我的问题.这让我想到了GHC优化功能和限制.

我已经在我认为非常简单的陈述性意义中表达了这一点.过滤满足谓词的[1..n]的排列For all indices i,j s.t j<i, abs(vi - vj) != j-i 我希望这是可以优化的东西,但它也有点像要求很多编译器.

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. 我可以在make/compile/link时采取哪些步骤来鼓励优化？
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)

Answer 1

在关于"GHC可以做什么样的优化"的更一般的层面上,可能有助于打破"优化"的想法.可以在可以优化的程序的各个方面之间进行概念上的区分.例如,考虑:

• 算法的内在逻辑结构:几乎在每种情况下都可以安全地假设这种情况永远不会被优化.在实验研究之外,你不太可能找到一个编译器来替换带有合并排序的冒泡排序,甚至是插入排序,并且极不可能找到一个用合理的东西取代bogosort的编译器.

• 算法的非必要逻辑结构:例如,在表达式中g (f x) (f x),将f x计算多少次？表达式怎么样g (f x 2) (f x 5)？这些并非算法固有的,并且可以互换不同的变体而不会影响性能以外的任何其他变化.这里执行优化的困难基本上是认识到何时可以在不改变含义的情况下完成替换,并预测哪个版本将具有最佳结果.很多手动优化都属于这一类,同时还有很多GHC的聪明才智.

  这也是让很多人参与其中的一部分,因为他们看到GHC是多么聪明,并期望它能做得更多.并且由于合理的期望GHC永远不会让事情变得更糟,因此对于GHC无法应用的潜在优化(并且对于程序员而言)并不常见,因为区分相同转换会显着的情况并不是很重要降低性能.例如,这就是为什么memoization和公共子表达式消除并不总是自动的.

  这也是GHC具有巨大优势的部分,因为懒惰和纯度使很多事情变得更加容易,我怀疑是什么导致人们发表言论,如"优化编译器是一个神话(除了可能在哈斯克尔)." 甚至对GHC可以做什么的不切实际的乐观态度.

• 低级细节:内存布局和最终代码的其他方面.这些往往有些神秘,并且高度依赖于运行时,操作系统和处理器的实现细节.这种优化本质上是为什么我们有编译器,除非你编写的计算要求非常高(或者自己编写编译器),否则通常不需要担心.

就您的具体示例而言:GHC不会显着改变算法的固有时间复杂度.它可能能够消除一些不变因素.它不能做的是应用恒定因子改进,它不能确定是否正确,特别是那些技术上以你不关心的方式改变程序含义的改进.这里的例子是@sclv的答案,它解释了你的使用如何print创造不必要的开销; GHC无法做到这一点,事实上目前的形式可能会抑制其他优化.

Answer 2

这里有一个概念问题.排列正在生成流式排列,过滤器也是流式排列.过早强迫一切的是"印刷"中隐含的"表演".将您的最后一行更改为:

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

并且您将看到结果以流式方式生成得更快.对于大型结果集,这可以解决潜在的空间泄漏问题,除此之外,只需让事情按计算打印,而不是一次性打印.

但是,你不应该期望ghc优化有任何数量级的改进(你会得到一些明显的优化,主要是严格和折叠,但它依赖于它们的刺激性).一般来说,你会得到的是不变因素.

编辑:正如luqui在下面指出的那样,show也是流式传输(或者至少是show的显示[Int]),但是线路缓冲使得更难以看到真正的计算速度......

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]]