performance - haskell列表理解能力

Question

以下是蛮力毕达哥拉斯三胞胎问题的三个版本，其附加约束条件为a + b + c = 1000。所有这些均符合GHC 7.0.3的-O3标准。示例运行时在下面列出。

问题:

为什么第二个版本比第一个版本运行更快？

为什么第三个版本比第二个版本运行更快？

我意识到差异很小，但平均而言顺序是一致的。

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

让我们分别命名这三个程序 A ， B 和 C 。

C 与 B

我们将从最简单的开始: C 相对于 B 有一个额外的约束(b >= a)。从直觉上讲，这意味着在 C 中遍历的搜索空间小于 B 的搜索空间。我们可以合理地指出这一点，而不是对所有可能的偶对a, b(我们知道其中有1000^2=1000000个对)进行覆盖，而不是考虑b小于a的所有情况。大概是检查b >= a是否产生一点额外的代码(比较)，而运行该比较避免了计算所产生的额外代码(比较)，因此，我们注意到(略微)的加速。很公平。

B 和 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 都执行了这类优化，仅不能实现: float 和拉姆达提升。我们可以通过注意到 B 和 C 中的递归函数看到少一些40的代码行，从而看到更紧密的内部循环，从而看到这一点。要了解为什么无法从此优化中受益，我们应该看一下没有浮出水面的代码:

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)实际上存在，与 C 不同，我们无法将大部分冗余计算浮到循环外。

为了确认，让我们任意增加涉及的循环的范围(为了演示)，例如[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  

您知道什么，正是我们所期望的!您的初始界限太小，以至于无法通过任何有趣的性能特征(无论理论告诉您什么，恒定的开销在实践中都很重要)。观察此结果的另一种方式是，我们对的最初直觉实际上与最初出现的 C的C的性能匹配。

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