performance - 为什么 `(map digitToInt) 。show`这么快？

Question

将非负数Integer转换为其数字列表通常是这样完成的：

import Data.Char

digits :: Integer -> [Int]
digits = (map digitToInt) . show

我试图找到一种更直接的方法来执行任务，而不涉及字符串转换，但我无法想出更快的方法。

到目前为止我一直在尝试的事情：

基线：

digits :: Int -> [Int]
digits = (map digitToInt) . show

从 StackOverflow 上的另一个问题得到这个：

digits2 :: Int -> [Int]
digits2 = map (`mod` 10) . reverse . takeWhile (> 0) . iterate (`div` 10)

试图推出我自己的：

digits3 :: Int -> [Int]
digits3 = reverse . revDigits3

revDigits3 :: Int -> [Int]
revDigits3 n = case divMod n 10 of
               (0, digit) -> [digit]
               (rest, digit) -> digit:(revDigits3 rest)

这个灵感来自showInt于Numeric：

digits4 n0 = go n0 [] where
    go n cs
        | n < 10    =  n:cs
        | otherwise =  go q (r:cs)
        where
        (q,r) = n `quotRem` 10

现在是基准。注意：我强制使用filter.

λ>:set +s
λ>length $ filter (>5) $ concat $ map (digits) [1..1000000]
2400000
(1.58 secs, 771212628 bytes)

这是参考。现在为digits2：

λ>length $ filter (>5) $ concat $ map (digits2) [1..1000000]
2400000
(5.47 secs, 1256170448 bytes)

那是3.46倍。

λ>length $ filter (>5) $ concat $ map (digits3) [1..1000000]
2400000
(7.74 secs, 1365486528 bytes)

digits3慢4.89倍。只是为了好玩，我尝试只使用 revDigits3 并避免使用reverse.

λ>length $ filter (>5) $ concat $ map (revDigits3) [1..1000000]
2400000
(8.28 secs, 1277538760 bytes)

奇怪的是，这甚至更慢，慢了5.24倍。

最后一个：

λ>length $ filter (>5) $ concat $ map (digits4) [1..1000000]
2400000
(16.48 secs, 1779445968 bytes)

这慢了10.43倍。

我的印象是，仅使用算术和 cons 会胜过任何涉及字符串转换的操作。显然，有些东西我无法掌握。

那么诀窍是什么？为什么digits这么快？

我正在使用 GHC 6.12.3。

score 30 · Accepted Answer

鉴于我还不能添加评论，我会做更多的工作，并分析所有这些。我将分析放在首位；但是，相关数据如下。（注意：所有这些都在 6.12.3 中完成 - 还没有 GHC 7 魔法。）

分析：

版本 1： show 非常适合整数，尤其是像我们这样短的整数。在 GHC 中制作字符串实际上往往是不错的；但是读取字符串并将大字符串写入文件（或标准输出，尽管您不想这样做）是您的代码绝对可以抓取的地方。我怀疑为什么这么快背后的许多细节是由于 Ints 的 show 中的巧妙优化。

版本 2：这是编译时最慢的版本。一些问题： reverse 的论点很严格。这意味着您在计算下一个元素时无法从列表的第一部分执行计算中受益；你必须计算它们，翻转它们，然后对列表的元素进行计算（即 (`mod` 10) ）。虽然这看起来很小，但它会导致更大的内存使用（注意这里也分配了 5GB 的堆内存）和更慢的计算。（长话短说：不要使用反向。）

版本 3：还记得我刚才说的不要使用反向吗？事实证明，如果你把它拿出来，这个总执行时间会下降到 1.79 秒——几乎不比基线慢。这里唯一的问题是，当你更深入地研究数字时，你会在错误的方向上建立列表的脊椎（本质上，你是在使用递归“进入”列表，而不是“进入”名单）。

版本 4：这是一个非常聪明的实现。您可以从几件好事中受益：其中之一，quotRem 应该使用欧几里得算法，该算法在其更大的参数中是对数的。（也许它更快，但我不相信有什么比欧几里德更快的常数因子。）此外，您可以使用上次讨论的列表，因此您不必像您一样解决任何列表重击go - 当你回来解析它时，列表已经完全构建好了。如您所见，性能从中受益。

这段代码可能是 GHCi 中最慢的，因为在 GHC 中使用 -O3 标志执行的许多优化都是为了使列表更快，而 GHCi 不会做任何事情。

经验教训：将正确的方法放到列表中，注意可能会减慢计算速度的中间严格性，并在查看代码性能的细粒度统计数据方面做一些工作。还可以使用 -O3 标志进行编译：只要您不这样做，所有那些花费大量时间使 GHC 超快的人都会对您大发雷霆。

数据：

我只是将所有四个函数都放入一个 .hs 文件中，然后根据需要进行更改以反映正在使用的函数。另外，我将您的限制提高到 5e6，因为在某些情况下，编译后的代码在 1e6 上会在不到半秒的时间内运行，这可能会导致我们正在进行的测量出现粒度问题。

编译器选项：使用ghc --make -O3 [filename].hs让 GHC 进行一些优化。我们将使用数字 +RTS -sstderr将统计信息转储到标准错误。

转储到 -sstderr 给我们的输出看起来像这样，在 digits1 的情况下：

digits1 +RTS -sstderr
12000000
   2,885,827,628 bytes allocated in the heap
         446,080 bytes copied during GC
           3,224 bytes maximum residency (1 sample(s))
          12,100 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  5504 collections,     0 parallel,  0.06s,  0.03s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    1.61s  (  1.66s elapsed)
  GC    time    0.06s  (  0.03s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    1.67s  (  1.69s elapsed)

  %GC time       3.7%  (1.5% elapsed)

  Alloc rate    1,795,998,050 bytes per MUT second

  Productivity  96.3% of total user, 95.2% of total elapsed

这里有三个关键统计数据：

使用中的总内存：只有 1MB 意味着这个版本非常节省空间。
总时间：1.61s 现在没有任何意义，但我们将看看它与其他实现的对比。
生产力：这只是 100% 减去垃圾收集；因为我们是 96.3% 这意味着我们没有创建很多我们留在内存中的对象..

好吧，让我们继续第 2 版。

digits2 +RTS -sstderr
12000000
   5,512,869,824 bytes allocated in the heap
       1,312,416 bytes copied during GC
           3,336 bytes maximum residency (1 sample(s))
          13,048 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0: 10515 collections,     0 parallel,  0.06s,  0.04s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    3.20s  (  3.25s elapsed)
  GC    time    0.06s  (  0.04s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    3.26s  (  3.29s elapsed)

  %GC time       1.9%  (1.2% elapsed)

  Alloc rate    1,723,838,984 bytes per MUT second

  Productivity  98.1% of total user, 97.1% of total elapsed

好的，所以我们看到了一个有趣的模式。

使用的内存量相同。这意味着这是一个非常好的实现，尽管这可能意味着我们需要在更高的样本输入上进行测试，看看我们是否能找到差异。
它需要两倍的时间。我们将回到一些关于为什么会这样的猜测。
它实际上稍微更有效率，但鉴于 GC 不是这两个程序的很大一部分，这对我们没有任何重要的帮助。

版本 3：

digits3 +RTS -sstderr
12000000
   3,231,154,752 bytes allocated in the heap
         832,724 bytes copied during GC
           3,292 bytes maximum residency (1 sample(s))
          12,100 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  6163 collections,     0 parallel,  0.02s,  0.02s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    2.09s  (  2.08s elapsed)
  GC    time    0.02s  (  0.02s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    2.11s  (  2.10s elapsed)

  %GC time       0.7%  (1.0% elapsed)

  Alloc rate    1,545,701,615 bytes per MUT second

  Productivity  99.3% of total user, 99.3% of total elapsed

好的，所以我们看到了一些奇怪的模式。

我们仍在使用 1MB 的总内存。所以我们没有遇到任何内存效率低的问题，这很好。
我们还没有完全达到digits1，但我们很容易击败digits2。
很少有GC。（请记住，任何超过 95% 的生产力都是非常好的，所以我们在这里并没有真正处理任何太重要的事情。）

最后，版本 4：

digits4 +RTS -sstderr
12000000
   1,347,856,636 bytes allocated in the heap
         270,692 bytes copied during GC
           3,180 bytes maximum residency (1 sample(s))
          12,100 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  2570 collections,     0 parallel,  0.00s,  0.01s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    1.09s  (  1.08s elapsed)
  GC    time    0.00s  (  0.01s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    1.09s  (  1.09s elapsed)

  %GC time       0.0%  (0.8% elapsed)

  Alloc rate    1,234,293,036 bytes per MUT second

  Productivity 100.0% of total user, 100.5% of total elapsed

哇扎！让我们分解一下：

我们仍然是 1MB。这几乎可以肯定是这些实现的一个特性，因为它们在 5e5 和 5e7 的输入上保持在 1MB。懒惰的证明，如果你愿意的话。
我们削减了大约 32% 的原始时间，这非常令人印象深刻。
我怀疑这里的百分比反映了 -sstderr 监控的粒度，而不是对超光速粒子的任何计算。

score 12 · Accepted Answer

回答“为什么用 rem 而不是 mod？”这个问题。在评论中。在处理正值时rem x y === mod x y，唯一需要注意的是性能：

> import Test.QuickCheck
> quickCheck (\x y -> x > 0 && y > 0 ==> x `rem` y == x `mod` y)

那么表现如何呢？除非你有充分的理由不这样做（懒惰不是一个很好的理由，也不知道 Criterion）然后使用一个好的基准测试工具，我使用 Criterion：

$ cat useRem.hs 
import Criterion
import Criterion.Main

list :: [Integer]
list = [1..10000]

main = defaultMain
        [ bench "mod" (nf (map (`mod` 7)) list)
        , bench "rem" (nf (map (`rem` 7)) list)
        ]

Running this shows rem is measurably better than mod (compiled with -O2):

$ ./useRem 
...
benchmarking mod
...
mean: 590.4692 us, lb 589.2473 us, ub 592.1766 us, ci 0.950

benchmarking rem
...
mean: 394.1580 us, lb 393.2415 us, ub 395.4184 us, ci 0.950

performance - 为什么 `(map digitToInt) 。show`这么快？

2 回答 2

Related

Reference