haskell - 使用 GHC 的分析统计数据/图表来识别问题区域/提高 Haskell 代码的性能

Question

TL；DR: 基于 Haskell 代码及其下面的相关分析数据，我们可以得出哪些结论，让我们修改/改进它，以便我们可以缩小与用命令式语言(即 C++/Python/C# 但具体的语言并不重要)？
背景
我编写了以下代码作为对一个流行网站上的问题的回答，该网站包含许多编程和/或数学性质的问题。 (你可能听说过这个网站，它的名字被一些人发音为“oiler”，另一些人发音为“yoolurr”。)由于下面的代码是一个问题的解决方案，我有意避免提及该网站的任何名称或问题中的任何特定术语。也就是说，我说的是问题一百零三。
(事实上​​，我在该站点的论坛中看到了许多来自 Haskell 常驻向导的解决方案:P)
为什么我选择分析此代码？
这是第一个问题(在上述站点上)，我遇到了 Haskell 代码与 C++/Python/C# 代码(当两者都使用类似算法时)之间的性能差异(以执行时间衡量)。事实上，对于所有问题(到目前为止；我已经完成了大约 100 个问题，但不是按顺序)，优化的 Haskell 代码几乎与最快的 C++ 解决方案并驾齐驱，其他条件不变算法，当然。
但是，论坛中针对此特定问题的帖子表明，这些其他语言中的相同算法通常最多需要一两秒，最长需要 10-15 秒(假设启动参数相同；我忽略了非常幼稚的算法，需要 2-3 分钟+)。相比之下，下面的 Haskell 代码在我的(体面的)计算机上需要大约 50 秒(禁用分析；启用分析，需要大约 2 分钟，如下所示；注意:使用 -fllvm 编译时执行时间相同) .规范:i5 2.4GHz 笔记本电脑，8GB RAM。
为了以一种可以成为命令式语言的可行替代品的方式学习 Haskell，我解决这些问题的目标之一是学习编写代码，在可能的情况下，其性能与那些命令式语言相当.在这种情况下，我仍然认为我还没有解决这个问题(因为性能相差近 25 倍!)
到目前为止我做了什么？
除了简化代码本身的明显步骤(尽我所能)之外，我还执行了“Real World Haskell”中推荐的标准分析练习。
但是我很难得出结论来告诉我哪些部分需要修改。这就是我希望人们能够帮助提供一些指导的地方。
问题描述:
我会向您推荐上述网站上问题 103 的网站，但这里有一个简短的总结:目标是找到一个由七个数字组成的组，使得(该组的)任何两个不相交的子组满足以下两个性质(由于上述原因，我试图避免使用“设置”一词......):

没有两个子组的总和相同

元素越多的子群总和越大(换句话说，最小的四个元素的总和必须大于最大的三个元素的总和)。

特别是，我们试图找到总和最小的七个数字组。
我的(公认的弱)观察
警告:其中一些评论可能完全错误，但我想至少尝试根据我在 Real World Haskell 和 SO 上其他与分析相关的帖子中阅读的内容来解释分析数据。

似乎确实存在效率问题，因为有三分之一的时间用于垃圾收集 (37.1%)。第一个图表显示堆中分配了~172gb，这看起来很可怕......(也许有更好的结构/函数用于实现动态编程解决方案？)

毫不奇怪，绝大多数 (83.1%) 的时间都花在检查规则 1 上:(i) value 子函数中的 41.6%，它确定要填充动态规划 (“DP”) 表的值，(ii) 29.1% 在 table 函数中，它生成 DP 表和 (iii) 12.4% 在 rule1 函数中，它检查生成的 DP 表以确保给定的总和只能以一种方式计算(即，从一个子组) .

但是，我确实发现令人惊讶的是，相对于 value 和 table 函数，在 rule1 函数上花费了更多时间，因为它是三个中唯一一个不构造数组或过滤大量元素的函数(它是实际上只执行 O(1) 查找并在 Int 类型之间进行比较，您认为这会相对较快)。所以这是一个潜在的问题领域。也就是说，value 函数不太可能驱动高堆分配

坦率地说，我不确定这三个图表是什么。
堆配置文件图表(即下面的第一个字符):

老实说，我不确定标记为 Pinned 的红色区域代表什么。 dynamic 函数具有“尖峰”内存分配是有道理的，因为每次 construct 函数生成满足前三个条件的元组时都会调用它，并且每次调用它都会创建一个相当大的 DP 数组。此外，我认为存储元组(由构造生成)的内存分配在程序过程中不会平坦。

待澄清“固定”红色区域，我不确定这个区域是否告诉我们任何有用的信息。

按类型分配和按构造函数分配:

我怀疑 ARR_WORDS(根据 GHC 文档表示 ByteString 或未装箱的数组)表示 DP 数组构造的低级执行(在 table 函数中)。坚果我不是100％肯定。

我不确定 FROZEN 和 STATIC 指针类别对应的是什么。

就像我说的，我真的不知道如何解释图表，因为没有任何东西(对我来说)出乎意料。

代码和分析结果
事不宜迟，这里是 代码 以及解释我的算法的注释。我试图确保代码不会超出代码框的右侧 - 但有些注释确实需要滚动(抱歉)。

{-# LANGUAGE NoImplicitPrelude #-}
{-# OPTIONS_GHC -Wall #-}

import CorePrelude
import Data.Array
import Data.List
import Data.Bool.HT ((?:))
import Control.Monad (guard)

main = print (minimum construct)

cap = 55 :: Int
flr = 20 :: Int
step = 1 :: Int

--we enumerate tuples that are potentially valid and then
--filter for valid ones; we perform the most computationally
--expensive step (i.e., rule 1) at the very end
construct :: [[Int]]
construct = {-# SCC "construct" #-} do
  a <- [flr..cap]                         --1st: we construct potentially valid tuples while applying a
  b <- [a+step..cap]                      --constraint on the upper bound of any element as implied by rule 2
  c <- [b+step..a+b-1]
  d <- [c+step..a+b-1]
  e <- [d+step..a+b-1]
  f <- [e+step..a+b-1]
  g <- [f+step..a+b-1]
  guard (a + b + c + d - e - f - g > 0)   --2nd: we screen for tuples that completely conform to rule 2
  let nn = [g,f,e,d,c,b,a]
  guard (sum nn < 285)                    --3rd: we screen for tuples of a certain size (a guess to speed things up)
  guard (rule1 nn)                        --4th: we screen for tuples that conform to rule 1
  return nn

rule1 :: [Int] -> Bool
rule1 nn = {-# SCC "rule1" #-} 
    null . filter ((>1) . snd)           --confirm that there's only one subgroup that sums to any given sum
  . filter ((length nn==) . snd . fst)   --the last column us how many subgroups sum to a given sum
  . assocs                               --run the dynamic programming algorithm and generate a table
  $ dynamic nn

dynamic :: [Int] -> Array (Int,Int) Int
dynamic ns = {-# SCC "dynamic" #-} table
  where
    (len, maxSum) = (length &&& sum) ns
    table = array ((0,0),(maxSum,len)) 
      [ ((s,i),x) | s <- [0..maxSum], i <- [0..len], let x = value (s,i) ]
    elements = listArray (0,len) (0:ns)
    value (s,i)
      | i == 0 || s == 0 = 0
      | s ==  m = table ! (s,i-1) + 1
      | s > m = s <= sum (take i ns) ?: 
          (table ! (s,i-1) + table ! ((s-m),i-1), 0)
      | otherwise = 0
      where
        m = elements ! i

堆分配、垃圾收集和耗时的统计信息:

% ghc -O2 --make 103_specialsubset2.hs -rtsopts -prof -auto-all -caf-all -fforce-recomp
[1 of 1] Compiling Main             ( 103_specialsubset2.hs, 103_specialsubset2.o )
Linking 103_specialsubset2 ...
% time ./103_specialsubset2.hs +RTS -p -sstderr
zsh: permission denied: ./103_specialsubset2.hs
./103_specialsubset2.hs +RTS -p -sstderr  0.00s user 0.00s system 86% cpu 0.002 total
% time ./103_specialsubset2 +RTS -p -sstderr
SOLUTION REDACTED
 172,449,596,840 bytes allocated in the heap
  21,738,677,624 bytes copied during GC
         261,128 bytes maximum residency (74 sample(s))
          55,464 bytes maximum slop
               2 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0     327548 colls,     0 par   27.34s   41.64s     0.0001s    0.0092s
  Gen  1        74 colls,     0 par    0.02s    0.02s     0.0003s    0.0013s

  INIT    time    0.00s  (  0.01s elapsed)
  MUT     time   53.91s  ( 70.60s elapsed)
  GC      time   27.35s  ( 41.66s elapsed)
  RP      time    0.00s  (  0.00s elapsed)
  PROF    time    0.00s  (  0.00s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time   81.26s  (112.27s elapsed)

  %GC     time      33.7%  (37.1% elapsed)

  Alloc rate    3,199,123,974 bytes per MUT second

  Productivity  66.3% of total user, 48.0% of total elapsed

./103_specialsubset2 +RTS -p -sstderr  81.26s user 30.90s system 99% cpu 1:52.29 total

每个成本中心花费的时间统计:

    Wed Dec 17 23:21 2014 Time and Allocation Profiling Report  (Final)

       103_specialsubset2 +RTS -p -sstderr -RTS

    total time  =       15.56 secs   (15565 ticks @ 1000 us, 1 processor)
    total alloc = 118,221,354,488 bytes  (excludes profiling overheads)

COST CENTRE     MODULE  %time %alloc

dynamic.value   Main     41.6   17.7
dynamic.table   Main     29.1   37.8
construct       Main     12.9   37.4
rule1           Main     12.4    7.0
dynamic.table.x Main      1.9    0.0


                                                                    individual     inherited
COST CENTRE               MODULE                  no.     entries  %time %alloc   %time %alloc

MAIN                      MAIN                     55           0    0.0    0.0   100.0  100.0
 main                     Main                    111           0    0.0    0.0     0.0    0.0
 CAF:main1                Main                    108           0    0.0    0.0     0.0    0.0
  main                    Main                    110           1    0.0    0.0     0.0    0.0
 CAF:main2                Main                    107           0    0.0    0.0     0.0    0.0
  main                    Main                    112           0    0.0    0.0     0.0    0.0
 CAF:main3                Main                    106           0    0.0    0.0     0.0    0.0
  main                    Main                    113           0    0.0    0.0     0.0    0.0
 CAF:construct            Main                    105           0    0.0    0.0   100.0  100.0
  construct               Main                    114           1    0.6    0.0   100.0  100.0
   construct              Main                    115           1   12.9   37.4    99.4  100.0
    rule1                 Main                    123      282235    0.6    0.0    86.5   62.6
     rule1                Main                    124      282235   12.4    7.0    85.9   62.6
      dynamic             Main                    125      282235    0.2    0.0    73.5   55.6
       dynamic.elements   Main                    133      282235    0.3    0.1     0.3    0.1
       dynamic.len        Main                    129      282235    0.0    0.0     0.0    0.0
       dynamic.table      Main                    128      282235   29.1   37.8    72.9   55.5
        dynamic.table.x   Main                    130   133204473    1.9    0.0    43.8   17.7
         dynamic.value    Main                    131   133204473   41.6   17.7    41.9   17.7
          dynamic.value.m Main                    132   132640003    0.3    0.0     0.3    0.0
       dynamic.maxSum     Main                    127      282235    0.0    0.0     0.0    0.0
       dynamic.(...)      Main                    126      282235    0.1    0.0     0.1    0.0
    dynamic               Main                    122      282235    0.0    0.0     0.0    0.0
    construct.nn          Main                    121    12683926    0.0    0.0     0.0    0.0
 CAF:main4                Main                    102           0    0.0    0.0     0.0    0.0
  construct               Main                    116           0    0.0    0.0     0.0    0.0
   construct              Main                    117           0    0.0    0.0     0.0    0.0
 CAF:cap                  Main                    101           0    0.0    0.0     0.0    0.0
  cap                     Main                    119           1    0.0    0.0     0.0    0.0
 CAF:flr                  Main                    100           0    0.0    0.0     0.0    0.0
  flr                     Main                    118           1    0.0    0.0     0.0    0.0
 CAF:step_r1dD            Main                     99           0    0.0    0.0     0.0    0.0
  step                    Main                    120           1    0.0    0.0     0.0    0.0
 CAF                      GHC.IO.Handle.FD         96           0    0.0    0.0     0.0    0.0
 CAF                      GHC.Conc.Signal          93           0    0.0    0.0     0.0    0.0
 CAF                      GHC.IO.Encoding          91           0    0.0    0.0     0.0    0.0
 CAF                      GHC.IO.Encoding.Iconv    82           0    0.0    0.0     0.0    0.0

堆配置文件:

按类型分配:

构造函数分配:

Answer 1

有很多可以说的。在这个答案中，我将仅评论 construct 中的嵌套列表推导式功能。

了解 construct 中发生的事情我们将隔离它并将其与您用命令式语言编写的嵌套循环版本进行比较。我们删除了 rule1守卫只测试列表的生成。

-- List.hs -- using list comprehensions

import Control.Monad

cap = 55 :: Int
flr = 20 :: Int
step = 1 :: Int

construct :: [[Int]]
construct =  do
  a <- [flr..cap]                         
  b <- [a+step..cap]                      
  c <- [b+step..a+b-1]
  d <- [c+step..a+b-1]
  e <- [d+step..a+b-1]
  f <- [e+step..a+b-1]
  g <- [f+step..a+b-1]
  guard (a + b + c + d - e - f - g > 0)
  guard (a + b + c + d + e + f + g < 285)
  return  [g,f,e,d,c,b,a]
  -- guard (rule1 nn)

main = do
  forM_ construct print


-- Loops.hs -- using imperative looping

import Control.Monad

loop a b f = go a
  where go i | i > b     = return ()
             | otherwise = do f i; go (i+1)

cap = 55 :: Int
flr = 20 :: Int
step = 1 :: Int

main =
  loop flr cap $ \a ->
  loop (a+step) cap $ \b ->
  loop (b+step) (a+b-1) $ \c ->
  loop (c+step) (a+b-1) $ \d ->
  loop (d+step) (a+b-1) $ \e ->
  loop (e+step) (a+b-1) $ \f ->
  loop (f+step) (a+b-1) $ \g ->
    if (a+b+c+d-e-f-g > 0) && (a+b+c+d+e+f+g < 285)
      then print [g,f,e,d,c,b,a]
      else return ()

这两个程序都是用 ghc -O2 -rtsopts 编译的并使用 prog +RTS -s > out 运行.

以下是结果摘要:

                          Lists.hs    Loops.hs
  Heap allocation        44,913 MB    2,740 MB
  Max. Residency            44,312      44,312
  %GC                        5.8 %       1.7 %
  Total Time             9.48 secs   1.43 secs

正如你所看到的，循环版本，这是你在像 C 这样的语言中编写它的方式，
在每个类别中获胜。

列表推导式版本更清晰、更可组合，但性能也低于直接迭代。