Word foldl'没有像Int foldl'一样被优化

Question

Word foldl'没有像Int foldl'一样被优化

14

import Data.List

test :: Int -> Int
test n = foldl' (+) 0 [1..n]

main :: IO ()
main = do
  print $ test $ 10^8

GHC优化了上述代码，使得垃圾回收器甚至不必做任何工作：

$ ghc -rtsopts -O2 testInt && ./testInt +RTS -s
[1 of 1] Compiling Main             ( testInt.hs, testInt.o )
Linking testInt ...
5000000050000000
          51,752 bytes allocated in the heap
           3,480 bytes copied during GC
          44,384 bytes maximum residency (1 sample(s))
          17,056 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0         0 colls,     0 par    0.000s   0.000s     0.0000s    0.0000s
  Gen  1         1 colls,     0 par    0.000s   0.000s     0.0001s    0.0001s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.101s  (  0.101s elapsed)
  GC      time    0.000s  (  0.000s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.103s  (  0.102s elapsed)

  %GC     time       0.1%  (0.1% elapsed)

  Alloc rate    511,162 bytes per MUT second

  Productivity  99.8% of total user, 100.9% of total elapsed

然而，如果我将test的类型更改为test :: Word -> Word，则会产生大量垃圾，并且代码运行速度变慢40倍。

ghc -rtsopts -O2 testWord && ./testWord +RTS -s
[1 of 1] Compiling Main             ( testWord.hs, testWord.o )
Linking testWord ...
5000000050000000
  11,200,051,784 bytes allocated in the heap
       1,055,520 bytes copied during GC
          44,384 bytes maximum residency (2 sample(s))
          21,152 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0     21700 colls,     0 par    0.077s   0.073s     0.0000s    0.0000s
  Gen  1         2 colls,     0 par    0.000s   0.000s     0.0001s    0.0001s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    4.551s  (  4.556s elapsed)
  GC      time    0.077s  (  0.073s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    4.630s  (  4.630s elapsed)

  %GC     time       1.7%  (1.6% elapsed)

  Alloc rate    2,460,957,186 bytes per MUT second

  Productivity  98.3% of total user, 98.3% of total elapsed

为什么会出现这种情况？我本以为它们的性能几乎相同？（我正在使用x86_64 GNU/Linux上的 GHC 版本 8.0.1）编辑：我提交了一个错误报告：https://ghc.haskell.org/trac/ghc/ticket/12354#ticket

- Kevin Slagle

1

在这两种情况下，核心生成是什么？ - Cactus

2

你应该在 GHC 问题跟踪器（https://ghc.haskell.org/trac/ghc/newticket）上提交一个错误报告。 - Reid Barton

我提交了一个错误报告：https://ghc.haskell.org/trac/ghc/ticket/12354#ticket - Kevin Slagle

这是Int核心 http://pastebin.com/ixBhgMqc 和Word核心http://pastebin.com/gtVeKjgX。 - Kevin Slagle

2个回答

2

正如dfeuer在这里的评论中指出的那样，对于Int，Enum实例比Word更好： Int:

instance  Enum Int  where
    {-# INLINE enumFromTo #-}
    enumFromTo (I# x) (I# y) = eftInt x y

{-# RULES
"eftInt"        [~1] forall x y. eftInt x y = build (\ c n -> eftIntFB c n x y)
"eftIntList"    [1] eftIntFB  (:) [] = eftInt
 #-}
{- Note [How the Enum rules work]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Phase 2: eftInt ---> build . eftIntFB
* Phase 1: inline build; eftIntFB (:) --> eftInt
* Phase 0: optionally inline eftInt
-}

{-# NOINLINE [1] eftInt #-}
eftInt :: Int# -> Int# -> [Int]
-- [x1..x2]
eftInt x0 y | isTrue# (x0 ># y) = []
            | otherwise         = go x0
               where
                 go x = I# x : if isTrue# (x ==# y)
                               then []
                               else go (x +# 1#)

{-# INLINE [0] eftIntFB #-}
eftIntFB :: (Int -> r -> r) -> r -> Int# -> Int# -> r
eftIntFB c n x0 y | isTrue# (x0 ># y) = n
                  | otherwise         = go x0
                 where
                   go x = I# x `c` if isTrue# (x ==# y)
                                   then n
                                   else go (x +# 1#)
                        -- Watch out for y=maxBound; hence ==, not >
        -- Be very careful not to have more than one "c"
        -- so that when eftInfFB is inlined we can inline
        -- whatever is bound to "c"

现在，Word 实际上使用了 Integer 的实现。

enumFromTo n1 n2       = map integerToWordX [wordToIntegerX n1 .. wordToIntegerX n2]

使用的是

instance  Enum Integer  where
    enumFromTo x lim       = enumDeltaToInteger x 1     lim

现在，enumDeltaToInteger已经设定了重写规则，但事实证明，Word的enumFromTo从未被内联，因此这种设置在这里没有融合的机会。

将此函数复制到我的测试代码中会导致GHC内联它，使fold/build规则触发，并且大大减少了分配，但是转换Integer（会分配）仍然存在。

- Joachim Breitner

以上是使用7.10版本的结果。在8.0版本中应该稍微好一些，因为remInteger已经变得更加严格了（请参见#10691）。 - Joachim Breitner

你已经提交了一个bug报告来添加一个更高效的Word实例，还是我应该提交呢？ - Thomas M. DuBuisson

已经完成：#12354 - Joachim Breitner

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

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

- Thomas M. DuBuisson · Accepted Answer

这可能主要是由于存在于Int而非Word的重写规则所致，尽管不是唯一原因。我之所以这么说是因为，如果我们在Int情况下使用-fno-enable-rewrite-rules，我们得到的时间接近，但不如Word情况那么糟糕。

% ghc -O2 so.hs -fforce-recomp -fno-enable-rewrite-rules && time ./so
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
5000000050000000
./so  1.45s user 0.03s system 99% cpu 1.489 total

如果我们使用-ddump-rule-rewrites选项来卸载重写规则，并对这些规则进行差异比较，那么我们可以看到一个在Int情况下触发而不是Word情况下触发的规则：

 Rule: fold/build
 Before: GHC.Base.foldr
 ...

那个特定规则位于 Base 4.9 GHC.Base 的第823行（注意，我实际上正在使用的是 GHC 7.10），并且未明确提到 Int。我很好奇它为什么没有对Word触发，但现在没有时间进一步调查。