GHC优化了分配

Question

我正在尝试提高计算机语言基准游戏中这个二进制树基准测试的性能。这个想法是构建大量的二叉树来基准测试内存分配。树数据定义如下所示：

data Tree = Nil | Node !Int !Tree !Tree

根据问题陈述，没有必要在每个节点中存储Int，其他语言也没有。

我使用 GHC 8.2.2 并在运行原始代码时获得以下 RTS 报告：

stack --resolver lts-10.3 --compiler ghc-8.2.2 ghc -- --make -O2 -threaded -rtsopts -funbox-strict-fields -XBangPatterns -fllvm -pgmlo opt-3.9 -pgmlc llc-3.9 binarytrees.hs -o binarytrees.ghc_run
./binarytrees.ghc_run +RTS -N4 -sstderr -K128M -H  -RTS 21
...
      19,551,302,672 bytes allocated in the heap
       7,291,702,272 bytes copied during GC
         255,946,744 bytes maximum residency (18 sample(s))
             233,480 bytes maximum slop
         635 MB total memory in use (0 MB lost due to fragmentation)
...
Total   time   58.620s  ( 39.281s elapsed)

目前为止，一切都好。让我们删除这个 Int，它实际上从未使用过。定义变为

data Tree = Nil | Node !Tree !Tree

理论上，我们将节省大约 25% 的总内存(每个节点中有 3 个整数而不是 4 个(。让我们试试吧：

 ...
 313,388,960 bytes allocated in the heap
     640,488 bytes copied during GC
      90,016 bytes maximum residency (2 sample(s))
      57,872 bytes maximum slop
           5 MB total memory in use (0 MB lost due to fragmentation)
 ...
 Total   time    9.596s  (  9.621s elapsed)

5MB 总内存正在使用中，GC 几乎为零？为什么？所有的拨款都去哪儿了？

Answer 1

我相信由公共子表达式消除优化引起的内存使用量突然下降。原始代码是：

make i d = Node i (make d d2) (make d2 d2)
--                      ^           ^
--                      |           d2 != d
--                      d != d2

由于构造左子树和右子树的表达式不同，因此编译器无法消除任何分配。

如果我删除未使用的整数，代码如下所示

make d = Node (make (d - 1)) (make (d - 1))
--            ^              ^
--            |              |
--            `--------------`----- identical

如果我将 -fno-cse 标志添加到 GHC，内存分配与预期一样高，但代码相当慢。我找不到在本地抑制此优化的方法，因此我决定通过添加额外的未使用参数来"智胜"编译器：

make' :: Int -> Int -> Tree
make' _  0 = Node Nil Nil
make' !n d = Node (make' (n - 1) (d - 1)) (make' (n + 1) (d - 1))

这个技巧奏效了，内存使用量预期下降了 30%。但我希望有一种更好的方法来告诉编译器我想要什么。

感谢@Carl提到 CSE 优化。