为什么 `(map digitToInt) . show` 如此快速？

Question

将非负整数转换为数字列表通常像这样完成:

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)

这个灵感来自于Numeric中的showInt函数：

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。

- gawi

---

将上述代码编译而非在GHCi中运行，将得到截然不同的结果。使用 -O3 编译时，digits4 的速度是 digits 的 1.8 倍。 - gawi

使用至少 -O2 编译代码（如gawi所说），然后使用criterion进行基准测试，为了所有的好处，请不要使用 mod，请使用 rem！ - Thomas M. DuBuisson

@tommd 为什么用 rem 而不是 mod？ - Alex M

此外，将Digits.hi/Digits.o放在与Digits.hs相同的目录中似乎会影响GHCi的性能。 GHCi是否在可用时使用编译工件？ - gawi

@amccausl 关于 rem 和 mod 的问题，请看下面我的回答。 - Thomas M. DuBuisson

Answer 1

由于我目前还不能添加评论，所以我会做更多的工作并分析它们。分析放在顶部; 然而，相关数据在下面。（注意：所有这些也都在6.12.3中完成了-没有GHC 7的魔法）

---

分析：

版本1：对于整数来说，show表现得非常好，尤其是我们有的那么短。在 GHC 中使字符串实际上倾向于不错; 但是读取字符串并将大字符串写入文件（或 stdout，尽管您不想这样做）是代码绝对可以爬行的地方。我会怀疑为什么这样快的许多细节都是由于 Ints 内部 clever optimizations 而产生的。

版本2：编译时，这是一堆中最慢的。一些问题：reverse 对其参数严格。这意味着您不会因为能够在计算下一个元素时对列表的第一部分执行计算而从中受益；您必须计算它们全部，然后翻转它们，然后对列表的元素进行计算（即（`mod`10））。虽然这可能看起来很小，但它可能导致更大的内存使用量（请注意，此处分配了 5GB 的堆内存）和更慢的计算。（长话短说：不要使用 reverse。）

版本3：记得我刚才说过不要使用 reverse 吗？事实证明，如果您将其删除，此版本的总执行时间会降至 1.79s-几乎与基线持平。唯一的问题是，随着您深入数字，您正在以错误的方向建立列表的 spine（实质上，您正在用递归 cons“进”列表，而不是 cons “到”列表中）。

版本4：这是一个非常聪明的实现。您从几个不错的东西中受益：首先，quotRem 应该使用欧几里得算法，该算法对其较大的参数是对数级别的。 （也许它更快，但我不相信有任何东西比欧几里得更快超过一个常数因子。）此外，根据上次讨论，您可以 cons 到列表中，因此在解析它时无需解决任何列表 thunk-列表已经完全构造好了。正如您所看到的那样，从中获得了性能优势。

这段代码可能是 GHCi 中最慢的，因为在 GHC 中使用 -O3 标志进行的许多优化都处理使列表更快的问题，而 GHCi 不会执行任何操作。

教训：以正确的方式 cons 到列表中，注意可能会减慢计算速度的中间强制性，且需在查看代码性能的细粒度统计时进行一些实际工作。还要使用 -O3 标志进行编译：每当您不这样做时，那些投入大量时间使 GHC 超级快的人们就会对您产生积极的影响。

---

Data:

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

编译器选项: 使用ghc --make -O3 [filename].hs进行一些优化。 我们将使用digits +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

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

1. 使用的总内存: 只有1MB，这意味着这个版本非常节省空间。
2. 总时间：1.61秒现在还没有任何意义，但我们将看看它与其他实现的差别。
3. 生产力: 这只是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

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

1. 使用相同数量的内存。这意味着这是一个相当不错的实现，尽管这可能意味着我们需要在更高的样本输入上进行测试，以查看是否可以找到差异。
2. 所需时间是两倍。稍后我们会回来探讨一些原因。
3. 实际上它略微更有效率，但考虑到垃圾回收在两个程序中都不占很大比例，这对我们没有任何显著帮助。

版本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

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

1. 我们仍然使用了1MB的总内存。所以我们还没有遇到任何内存效率低下的问题，这是好的。
2. 我们还没有达到digits1，但我们轻松击败了digits2。
3. 很少有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

哇塞！让我们来分析一下：

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

- dvitek

---

“头部分配的字节”指标似乎很相关。随着分配更多内存，程序运行速度会变慢。 - gawi

gawi：这确实会影响性能，但 OP 也应该关注使用的总内存。如果总内存太大，那就意味着程序要么不够严格，要么不够懒惰。如果总内存超过了 GHC 的堆栈限制，OP 就会遇到很多麻烦... - dvitek

Answer 2

在评论中回答“为什么使用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)
        ]

运行结果显示，rem比mod（使用-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

- Thomas M. DuBuisson