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。

Answer 1

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

分析:

版本 1: show 非常适合整数，尤其是像我们这样短的整数。在 GHC 中制作琴弦实际上往往是体面的；然而，读取字符串并将大字符串写入文件(或标准输出，尽管您不想这样做)是您的代码绝对可以爬行的地方。我怀疑为什么这么快背后的很多细节都是由于对 Ints 的 show 进行了巧妙的优化。

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

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

版本 4:这是一个非常聪明的实现。您可以从几个好处中受益:首先，quotRem 应该使用欧几里得算法，该算法在其较大的参数中是对数的。 (也许它更快，但我认为没有什么比 Euclid 更快的常数因子了。)此外，正如上次讨论的那样，您将缺点列在列表中，这样您就不必像您一样解决任何列表问题go - 当你回来解析它时，列表已经完全构建好了。如您所见，性能由此而受益。

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

类(class): cons 以正确的方式列在列表中，注意可能会减慢计算速度的中间严格性，并在查看代码性能的细粒度统计数据方面做一些工作。还要使用 -O3 标志进行编译:每当您不这样做时，所有那些花费大量时间使 GHC 超快的人都会瞪大眼睛看着您。

数据:

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

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

在digits1的情况下，转储到-sstderr为我们提供了如下所示的输出:

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，但我们已经很容易击败了digital2。

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% 的原始时间，这令人印象深刻。

我怀疑这里的百分比反射(reflect)了 -sstderr 监控中的粒度，而不是对超光速粒子的任何计算。