为什么`(map digitToInt).秀`这么快？

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倍.

我的印象是只使用算术和缺点会胜过任何涉及字符串转换的内容.显然,有些东西我无法掌握.

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

我正在使用GHC 6.12.3.

Answer 1

看来我还没有添加评论,我会做更多的工作,只是分析所有这些.我把分析放在首位; 但是,相关数据如下.(注意:所有这些都在6.12.3中完成 - 没有GHC 7魔法.)

分析:

版本1:显示对于整数非常有用,特别是那些与我们一样短的东西.在GHC中,制作弦乐实际上往往是不错的; 但是读取字符串并将大字符串写入文件(或stdout,尽管你不想这样做)是你的代码绝对可以爬行的地方.我怀疑为什么这么快的背后的很多细节都归功于Ints展示的巧妙优化.

版本2:这是编译时最慢的一个.一些问题:反向是严格的论点.这意味着当你计算下一个元素时,你不能从列表的第一部分执行计算中受益; 你必须计算它们,翻转它们,然后对列表的元素进行计算(即(`mod`10)).虽然这看起来很小,但它可能导致更大的内存使用量(请注意此处分配的5GB堆内存)和较慢的计算.(长话短说:不要反向使用.)

版本3:还记得我刚才说的不用反向吗？事实证明,如果你把它拿出来,这个总执行时间下降到1.79秒 - 几乎比基线慢.这里唯一的问题是,当你深入研究这个数字时,你正在以错误的方向构建列表的主干(实际上,你正在通过递归进入"列表",而不是"进入"列表).

版本4:这是一个非常聪明的实现.你可以从几个好东西中受益:对于一个,quotRem应该使用欧几里德算法,它在更大的参数中是对数的.(也许它更快,但我不相信有任何东西比Euclid更快的常数因素.)此外,你在上次讨论的列表中占了一席之地,所以你不必像你一样解决任何列表thunks 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

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

1. 使用的总内存:仅1MB意味着此版本非常节省空间.
2. 总时间:1.61s现在没什么意义,但我们会看到它与其他实现的对比.
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. 实际上它的效率稍高,但鉴于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

好吧,所以我们看到了一些奇怪的模式.

1. 我们的总内存仍然是1MB.所以我们没有打出任何内存效率低的东西,这很好.
2. 我们不是数字1,但我们很容易得到数字2.
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

Wowza!让我们分解一下:

1. 我们总共还是1MB.这几乎可以肯定是这些实现的一个特性,因为它们在5e5和5e7的输入上保持1MB.懒惰的证明,如果你愿意的话.
2. 我们切断了原始时间的32%左右,这非常令人印象深刻.
3. 我怀疑这里的百分比反映了-sstderr监测的粒度,而不是对超光速粒子的任何计算.

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