鉴于我还无法添加评论,我将做更多工作并分析所有评论。我把分析放在最上面;不过,相关数据如下。 (注意:所有这些都是在 6.12.3 中完成的 - 还没有 GHC 7 魔法。)
分析:
版本1:show 对于整数来说非常好,尤其是像我们这样短的整数。实际上,在 GHC 中制作字符串往往是不错的;然而,读取字符串并将大字符串写入文件(或标准输出,尽管您不想这样做)是您的代码绝对可以抓取的地方。我怀疑为什么这么快背后的很多细节都是由于 Ints 显示中的巧妙优化。
版本2:编译时,这是其中最慢的一个。一些问题:反向论证的严格性。这意味着在计算下一个元素时,您无法从对列表的第一部分执行计算中受益;您必须计算所有它们,翻转它们,然后对列表的元素进行计算(即 (`mod` 10) )。虽然这看起来很小,但它可能会导致更大的内存使用量(请注意此处分配的 5GB 堆内存)和更慢的计算速度。 (长话短说:不要使用反向。)
版本3:还记得我刚才说过不要使用反向吗?事实证明,如果你把它拿出来,总执行时间会下降到 1.79 秒——仅比基线慢一点。这里唯一的问题是,当你深入了解数字时,你会以错误的方向构建列表的主干(本质上,你是通过递归“进入”列表,而不是“进入”列表)列表)。
版本 4:这是一个非常巧妙的实现。您可以从几件好事中受益:首先,quotRem 应该使用欧几里得算法,该算法的较大参数是对数的。 (也许它更快,但我不相信有什么比欧几里得更快的常数因子。)此外,您可以像上次讨论的那样对列表进行操作,这样您就不必在处理时解决任何列表重击问题。 go - 当您返回解析列表时,列表已经完全构建完毕。如您所见,性能由此受益。
这段代码可能是 GHCi 中最慢的,因为 GHC 中使用 -O3 标志执行的许多优化都是为了使列表更快,而 GHCi 不会这样做。
Lessons:以正确的方式将 cons 放入列表中,注意可能减慢计算速度的中间严格性,并做一些跑腿工作来查看代码性能的细粒度统计数据。还要使用 -O3 标志进行编译:只要你不这样做,所有那些花费大量时间使 GHC 超快的人都会对你大眼瞪小眼。
Data:
我只是将所有四个函数粘贴到一个 .hs 文件中,然后根据需要进行更改以反映正在使用的函数。另外,我将限制提高到 5e6,因为在某些情况下,编译的代码在 1e6 上运行时间不到半秒,这可能会导致我们正在进行的测量出现粒度问题。
编译器选项:使用ghc --make -O3 [文件名].hs让 GHC 做一些优化。我们将使用以下命令将统计数据转储到标准错误数字+RTS -sstderr.
在数字 1 的情况下,转储到 -stderr 会得到如下所示的输出:
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.61 秒现在没有任何意义,但我们将看看它与其他实现相比如何。
- 生产力:这只是 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 监控的粒度,而不是对超光速粒子的任何计算。