过滤器 foo [2..n] 的内存使用！ 0

Question

假设我有以下功能

small_div :: Int -> Int
small_div n = filter (\x -> n `rem` x == 0) [2..n] !! 0

这个函数占用的内存是多少？等效的 C 代码将是恒定的内存使用，我相信 Haskell 的惰性评估意味着它不会创建比找到第一个除数所需的更多的 [2..n] 元素，但是 ghc足够聪明，可以跳转到...

int small_div(int n) {
    for (int x = 2; x <= n; x++) {
        if (n % x == 0) {
            return x;
        }
    }
}

Answer 1

GHC 7.10 和 7.8.4（我测试的版本）足够智能，可以跳转到您的优化示例。

我从互联网上查找了两个质数，15485863 和 67867967。当我编译运行 main = print $ small_div 15485863 并带有 +RTS -s 标志时，我的总堆分配是 51 Kb。当我运行与 67867967 相同时，我也获得了 51 Kb 分配。这意味着没有为列表的生成和过滤分配单元格。

它很可能被所谓的foldr/build融合优化（filter和enumFromTo for Int-s都参与了这种融合）。

Answer 2

为了查看 GHC 高级优化的结果，比汇编程序输出更好的选择是 GHC 在简化阶段之后的内部核心语言。学习阅读确实需要一点时间，但应该比汇编短得多。我只是理解核心的初学者，但让我试着展示一下。

哦，因为我使用的是 Haskell 平台，所以这是 GHC 7.8.3。

给定文件

module Test where

small_div :: Int -> Int
small_div n = filter (\x -> n `rem` x == 0) [2..n] !! 0

如果我们使用 no 优化选项编译，并转储所有核心输入 "extra" 信息被抑制（这删除了大量的分析和类型信息，只留下基本结构）：

ghc -dsuppress-all -ddump-simpl Test.hs

我们得到定义为

small_div =
  \ n_apH ->
    !!
      (filter
         (\ x_arI -> == $fEqInt (rem $fIntegralInt n_apH x_arI) (I# 0))
         (enumFromTo $fEnumInt (I# 2) n_apH))
      (I# 0)

这基本上是直接翻译成核心的Haskell，仍然包含所有列表构造。 core的语法比Haskell简单很多，连运算符都用前缀。另一方面，许多内部 GHC 细节现在正在被窥探，例如 Int 的 I# 构造函数和比较 Int 的 $fEqInt 单态函数。

请注意，即使在这种形式下，惰性和垃圾收集应该意味着它将能够运行常量space，可能（意思是我 "educatedly" 在这里猜测）完全停留在 GHC 的高效 GC "nursery" 生成短期数据。

现在，如果我们向 GHC 添加 -O 基本优化选项，输出会变得很多更棘手（使用 -O2 会更糟）。 filter 和 enumFromTo 都消失了，已被列表融合优化删除并且结果被内联。此外，大多数算术现在都适用于未装箱的 Int#s。这是 -O 输出的全部荣耀：

small_div2
small_div2 = I# (-1)

small_div1
small_div1 = !!_sub ([]) 0

$wsmall_div
$wsmall_div =
  \ ww_s1dD ->
    case tagToEnum# (># 2 ww_s1dD) of _ {
      False ->
        letrec {
          a_s1e8
          a_s1e8 =
            case ww_s1dD of _ {
              __DEFAULT -> go_a1ch 0;
              (-1) -> []
            };
          lvl_s1e1
          lvl_s1e1 = : small_div2 a_s1e8;
          go_a1ch
          go_a1ch =
            \ x_a1ci ->
              case x_a1ci of wild1_a1aq {
                __DEFAULT ->
                  case remInt# ww_s1dD wild1_a1aq of _ {
                    __DEFAULT ->
                      case tagToEnum# (==# wild1_a1aq ww_s1dD) of _ {
                        False -> go_a1ch (+# wild1_a1aq 1);
                        True -> []
                      };
                    0 ->
                      : (I# wild1_a1aq)
                        (case tagToEnum# (==# wild1_a1aq ww_s1dD) of _ {
                           False -> go_a1ch (+# wild1_a1aq 1);
                           True -> []
                         })
                  };
                (-1) -> lvl_s1e1;
                0 -> case divZeroError of wild2_00 { }
              }; } in
        !!_sub (go_a1ch 2) 0;
      True -> small_div1
    }

small_div
small_div =
  \ w_s1dA ->
    case w_s1dA of _ { I# ww1_s1dD -> $wsmall_div ww1_s1dD }

然而，即使在所有这些融合和内联之后，它仍然在某些地方包含 : 列表构造函数。并注意其中的单行，给出最大函数的通常最终结果：

        !!_sub (go_a1ch 2) 0;

外部列表的构造，以及它的 !! 0 索引未被优化掉。（虽然我没有包括 -O2 输出，但同样适用。）

然而，中间 [2..n] 列表是消失了，这意味着，如果我的理解是正确的，懒惰将确保这个函数最多分配一个列表细胞.

过滤器 foo [2..n] 的内存使用！ 0

Memory usage of filter foo [2..n] !! 0

haskell

ghc