haskell列表理解表现

Question

以下是蛮力毕达哥拉斯三胞胎问题的三个版本,附加约束为a + b + c = 1000.所有这些都符合-O3与GHC 7.0.3.下面列出了样本运行时间.

问题:

1. 为什么第二个版本比第一个版本运行得更快？
2. 为什么第三个版本比第二个版本运行得更快？

我意识到差异很小,但排序平均一致.

main=print . product . head $ [[a,b,c] | a<-[1..1000],b<-[a..1000], let c=1000-a-b, a^2+b^2==c^2]
real    0m0.046s
user    0m0.039s
sys     0m0.005s

main=print . product . head $ [[a,b,c] | a<-[1..1000],b<-[1..1000], let c=1000-a-b, a^2+b^2==c^2]
real    0m0.045s
user    0m0.036s
sys     0m0.006s

main=print . product . head $ [[a,b,c] | a<-[1..1000],b<-[1..1000], b>=a, let c=1000-a-b, a^2+b^2==c^2]
real    0m0.040s
user    0m0.033s
sys     0m0.005s

Answer 1

让我们命名的三个方案一,乙和Ç分别.

C vs B.

我们将从最简单的开始:C有一个b >= a相对于B的额外约束().直观地,这意味着在C中遍历的搜索空间小于B的搜索空间.我们可以通过注意,而不是对每一个可能被置换的对a, b(我们知道有1000^2=1000000可能的对)进行测距,而不是考虑所有b小于的情况a.据推测,检查是否b >= a产生一些额外的代码(比较),通过运行比较避免了计算,因此我们注意到(轻微)加速.很公平.

B vs A.

接下来有点棘手:似乎A与C(b >= a)具有相同的约束,但编码方式不同(即在这里我们将其编码为值的范围b可以在其中获得List Monad).我们可能会认为A应该比B运行得更快(事实上​​,它应该与C类似地运行).显然,我们的直觉是缺乏的.

正中核心

现在,既然我们不能总是相信我们的直觉,那么我们应该调查生成的GHC Core中真正发生的事情.让我们为我们的3个程序(无优化)转储核心:

for p in A B C
do
  ghc -ddump-simpl $p.hs >> $p.core
done

如果我们比较B.core和C.core,我们会注意到,这两个文件有大致相同的结构:

首先调用几个熟悉的函数(System.IO.print ...),(Data.List.product ...)然后(GHC.List.head ...)

接下来,我们使用签名定义一对嵌套的递归函数:

ds_dxd [Occ=LoopBreaker]
    :: [GHC.Integer.Type.Integer] -> [[GHC.Integer.Type.Integer]]

我们在表单的枚举中调用每个定义的函数:

    (GHC.Enum.enumFromTo                
    @ GHC.Integer.Type.Integer       
    GHC.Num.$fEnumInteger            
    (GHC.Integer.smallInteger 1)     
    (GHC.Integer.smallInteger 1000)))

并在最内部定义的函数中执行我们的逻辑.值得注意的是,我们可以B.core看到

                     case GHC.Classes.==
                            @ GHC.Integer.Type.Integer
                            ...
                            (GHC.Num.+
                               ...
                               (GHC.Real.^
                                  ...
                                  ds3_dxc
                                  (GHC.Integer.smallInteger 2))
                               (GHC.Real.^
                                  ...
                                  ds8_dxg
                                  (GHC.Integer.smallInteger 2)))
                            (GHC.Real.^
                               ...
                               c_abw
                               (GHC.Integer.smallInteger 2))

对应于符合我们约束的所有可能值的天真过滤器,而在C.core,我们改为:

case GHC.Classes.>=
    @ GHC.Integer.Type.Integer GHC.Classes.$fOrdInteger ds8_dxj ds3_dxf
    of _ {
        GHC.Bool.False -> ds5_dxh ds9_dxk;
        GHC.Bool.True ->
        let {
        ...
                case GHC.Classes.==
                ...

对应于>=在我们的三元组约束之前添加额外约束,因此正如我们的直觉所期望的那样,通过较少的整数搜索较短的运行时间.

在比较A.core和B.core,我们立即看到一个熟悉的结构(一对嵌套递归函数每次叫过一个枚举)和在事实上,它似乎是核心输出A和B几乎是一样的!似乎差异在于最里面的枚举:

            ds5_dxd
             (GHC.Enum.enumFromTo
                @ GHC.Integer.Type.Integer
                GHC.Num.$fEnumInteger
                ds3_dxb
                (GHC.Integer.smallInteger 1000))

我们看到从给定的归纳变量ds3_dxb到枚举范围1000,而不是作为静态范围([1..1000]).

那给了什么？这不是表明A应该跑得比B快吗？(我们天真地期望A与C类似地执行,因为它们实现了相同的约束).好吧,事实证明,各种编译器优化会产生非常复杂的行为,并且各种组合通常会产生非直观(并且坦率地说奇怪)的结果,在这种情况下,我们有两个编译器相互交互:ghc和gcc.为了有机会理解这些结果,我们必须依赖生成的优化核心(尽管如此,它是真正重要的生成汇编程序,但我们暂时忽略它).

优化核心,超越

让我们生成优化的核心:

for p in A B C
do
  ghc -O3 -ddump-simpl $p.hs >> $p.core
done

并将我们的问题儿童(A)与速度较快的儿童进行比较.相比较而言,B和C都执行了一类优化,A单独不能:浮动和lambda-lifting.我们可以看到这一点,注意到我们在B和C中的递归函数中包含40较少的代码行,从而导致更紧密的内循环.要理解为什么A没有从这个优化中受益,我们应该看一下没有浮出的代码:

let {
  c1_s10T
    :: GHC.Integer.Type.Integer
       -> [[GHC.Integer.Type.Integer]]
       -> [[GHC.Integer.Type.Integer]]
  [LclId, Arity=2, Str=DmdType LL]
  c1_s10T =
    \ (ds2_dxg :: GHC.Integer.Type.Integer)
      (ds3_dxf :: [[GHC.Integer.Type.Integer]]) ->
      let {
        c2_s10Q [Dmd=Just L] :: GHC.Integer.Type.Integer
        [LclId, Str=DmdType]
        c2_s10Q = GHC.Integer.minusInteger lvl2_s10O ds2_dxg } in -- subtract
      case GHC.Integer.eqInteger
             (GHC.Integer.plusInteger lvl3_s10M (GHC.Real.^_^ ds2_dxg lvl_r11p))
             -- add two squares (lve3_s10M has been floated out)
             (GHC.Real.^_^ c2_s10Q lvl_r11p)
             -- ^ compared to this square
      of _ {
        GHC.Bool.False -> ds3_dxf;
        GHC.Bool.True ->
          GHC.Types.:
            @ [GHC.Integer.Type.Integer]
            (GHC.Types.:
               @ GHC.Integer.Type.Integer
               ds_dxe
               (GHC.Types.:
                  @ GHC.Integer.Type.Integer
                  ds2_dxg
                  (GHC.Types.:
                     @ GHC.Integer.Type.Integer
                     c2_s10Q
                     (GHC.Types.[] @ GHC.Integer.Type.Integer))))
            ds3_dxf
      } } in

也就是说,在我们的循环的临界区(由辅助函数的主体表示)内执行减法(minusInteger)和相等(eqInteger)以及两个正方形(^_^),而相同的辅助函数C.core包含较少的计算(如果我们进一步挖掘,我们会发现这是因为GHC无法确定在优化过程中将这些计算浮出来是否安全.这符合我们先前的分析硬碰硬,因为我们可以看到,约束(b >= a)是确实存在,只是不像Ç,我们已经无法飘起了大多数外循环冗余计算.

为了确认,让我们增加任意涉及的循环的界限(为了演示),比如说[1..10000].我们应该期望看到A的运行时行为应该渐近地接近C的运行时行为,就像我们期望B留在尘埃中一样.

?  time ./A                                 
./A  0.37s user 0.01s system 74% cpu 0.502 total  
?  time ./B                                 
./B  3.21s user 0.02s system 99% cpu 3.246 total  
?  time ./C                                 
./C  0.33s user 0.01s system 99% cpu 0.343 total  

你知道什么,就像我们期望的那样!你的初始界限太小,无法发挥任何有趣的性能特征(无论理论如何,不​​断的开销在实践中都很重要).另一种看待这个结果的方法是,我们对A匹配C的性能的初步直觉实际上比它首次出现时更准确.

当然,所有这些对于手头的代码示例来说可能都是过度的,但是这种分析在资源受限的环境中非常有用.