Haskell；where子句的性能

Question

Haskell；where子句的性能

performancehaskelltime-complexityspace-complexity

5

我正在分析where子句对Haskell程序性能的影响。

在Haskell函数式编程艺术, Thomspson的第20.4章中，我找到了以下示例：

exam1 :: Int -> [Int]
exam1 n = [1 .. n] ++ [1 .. n]

exam2 :: Int -> [Int]
exam2 n = list ++ list
  where list = [1 .. n]

引用一下：

计算[exam1]所需的时间将为O(n)，所需的空间将为O(1)，但我们将不得不计算表达式[1 .. n] 两次。

...

[exam2]的效果是计算列表[1 .. n]一次，以便在计算后保存其值，以便能够再次使用它。

...

如果我们通过引用where子句中的内容来节省空间，则必须支付其占用的空间的代价。

因此，我疯狂地认为-O2标志必须处理这个并为我选择最佳行为。我使用Criterion分析这两个示例的时间复杂度。

import Criterion.Main

exam1 :: Int -> [Int]
exam1 n = [1 .. n] ++ [1 .. n]

exam2 :: Int -> [Int]
exam2 n = list ++ list
  where list = [1 .. n]

m :: Int
m = 1000000

main :: IO ()
main = defaultMain [ bench "exam1" $ nf exam1 m
                   , bench "exam2" $ nf exam2 m
                   ]

我使用-O2编译，并发现：

benchmarking exam1
time                 15.11 ms   (15.03 ms .. 15.16 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 15.11 ms   (15.08 ms .. 15.14 ms)
std dev              83.20 μs   (53.18 μs .. 122.6 μs)

benchmarking exam2
time                 76.27 ms   (72.84 ms .. 82.75 ms)
                     0.987 R²   (0.963 R² .. 0.997 R²)
mean                 74.79 ms   (70.20 ms .. 77.70 ms)
std dev              6.204 ms   (3.871 ms .. 9.233 ms)
variance introduced by outliers: 26% (moderately inflated)

多大的差异啊！为什么会这样呢？根据上面的引文，我以为exam2应该更快但内存效率低。但是事实上，它实际上要慢得多（可能更加内存效率低，但需要进行测试）。

也许它之所以慢是因为[1..1e6]必须存储在内存中，这需要很长时间。你怎么看？

附注：我找到了一个可能相关的问题，但不完全相关。

- Dominik Schrempf

在第二个例子中，编译器似乎无法内联“list”，因此它实际上计算它，存储在内存中，并从内存中读取。 - talex

@talex 对于常见情况，内联let x = expensiveComputation in f x x可能会有害，因为它会导致x被计算两次。使用where也会出现类似的问题。我认为GHC在这种情况下非常保守地进行内联，因为它可能会导致性能灾难（例如，执行两个递归调用而不是一个可能会导致指数级的爆炸增长）。 - chi

@chi 是的，但在这种情况下，内联导致根本没有计算。它将实时计算。 - talex

@talex 我同意，但我不指望 GHC 能够理解在这种情况下它可以安全地进行内联。检测何时可以内联和何时不能内联看起来并不容易。 - chi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- chi · Accepted Answer

您可以使用-ddump-simpl来检查 GHC 核心，并观察 GHC 生成的优化代码。核心不像 Haskell 那样易读，但通常仍然能够理解正在发生的事情。

对于exam2，我们得到了简单枯燥的代码：

exam2
  = \ (n_aX5 :: Int) ->
      case n_aX5 of { GHC.Types.I# y_a1lJ ->
      let {
        list_s1nF [Dmd=<S,U>] :: [Int]
        [LclId]
        list_s1nF = GHC.Enum.eftInt 1# y_a1lJ } in
      ++ @ Int list_s1nF list_s1nF
      }

大致来说，这将list_s1nF定义为[1..n](eftInt=从...到的枚举)并调用++。这里没有进行内联。 GHC 不敢内联list_s1nF，因为它被使用了两次，并且在这种情况下内联定义可能会有害。的确，如果let x = expensive in x+x被内联，就会重复计算expensive，这是不好的。在这里，GHC信任程序员，认为如果他们使用let / where，则希望只计算一次。未能内联list_s1nF会阻止进一步的优化。

所以，这段代码分配了list=[1..n]，然后复制结果为1:2:...:n:list，其中尾指针被设置为指向原始列表。复制任意列表需要遵循指针链并为新列表分配单元格，这从直觉上来看比[1..n]更昂贵，后者只需为新列表分配单元格并保留一个计数器即可。

相反，exam1被进一步优化：经过一些小的取消箱操作。

exam1
  = \ (w_s1os :: Int) ->
      case w_s1os of { GHC.Types.I# ww1_s1ov ->
      PerfList.$wexam1 ww1_s1ov
      }

我们进入实际的工作函数。

PerfList.$wexam1
  = \ (ww_s1ov :: GHC.Prim.Int#) ->
      let {
        n_a1lT :: [Int]
        [LclId]
        n_a1lT = GHC.Enum.eftInt 1# ww_s1ov } in
      case GHC.Prim.># 1# ww_s1ov of {
        __DEFAULT ->
          letrec {
            go_a1lX [Occ=LoopBreaker] :: GHC.Prim.Int# -> [Int]
            [LclId, Arity=1, Str=<L,U>, Unf=OtherCon []]
            go_a1lX
              = \ (x_a1lY :: GHC.Prim.Int#) ->
                  GHC.Types.:
                    @ Int
                    (GHC.Types.I# x_a1lY)
                    (case GHC.Prim.==# x_a1lY ww_s1ov of {
                       __DEFAULT -> go_a1lX (GHC.Prim.+# x_a1lY 1#);
                       1# -> n_a1lT
                     }); } in
          go_a1lX 1#;
        1# -> n_a1lT
      }

在这里，第一个“enum from to”[1..n]被内联，这也触发了++的内联。最终递归函数go_a1lX只依赖于:和基本算术运算。当递归结束时，返回n_a1lT，它是第二个“enum from to”[1..n]。由于不会触发任何更多的优化，因此这不是内联的。

在这里，没有生成并复制任何列表，因此我们获得更好的性能。

请注意，这也会产生优化后的代码：

exam3 :: Int -> [Int]
exam3 n = list1 ++ list2
  where list1 = [1 .. n]
        list2 = [1 .. n]

此外，由于GHC不会自动缓存函数的结果，因此这些函数可以被内联。

exam4 :: Int -> [Int]
exam4 n = list () ++ list ()
  where list () = [1 .. n]