为什么在 Racket 中的 gvector 中保留容量会使性能变差？

Question

在 Racket 6.6 中使用以下简单基准测试：

#lang racket
(require data/gvector)
(define (run)
  ;; this should have to periodically resize in order to incorporate new data
  ;; and thus should be slower
  (time (define v (make-gvector)) (for ((i (range 1000000))) (gvector-add! v i)) )
  (collect-garbage 'major)
  ;; this should never have to resize and thus should be faster
  ;; ... but consistently benchmarks slower?!
  (time (define v (make-gvector #:capacity 1000000)) (for ((i (range 1000000))) (gvector-add! v i)) )
  )

(run)

正确预留容量的版本表现始终较差。为什么？这当然不是我期望的结果，并且与您在 C++ (std::vector) 或 Java (ArrayList) 中看到的结果不一致。我是不是基准测试不正确？

示例输出：

cpu time: 232 real time: 230 gc time: 104
cpu time: 228 real time: 230 gc time: 120

Answer 1

将向量大小增加 10 倍，我在 DrRacket 中得到以下结果（关闭所有调试）：

cpu time: 5245 real time: 5605 gc time: 3607
cpu time: 4851 real time: 5136 gc time: 3231

注意：如果第一个基准测试留下垃圾，它会影响下一个基准测试。因此在再次使用 time 之前使用 collect-garbage（三次）。

此外...不要像我一样在 DrRacket 中进行基准测试 - 使用命令行。

Answer 2

一个基准测试评论：在您的微基准测试中使用 in-range 而不是 range；否则，您将在测量中包括构建百万元素列表的成本。

我在你的微基准测试中添加了一些额外的循环，让它做更多的工作（我修复了 range 问题）。以下是部分结果：

对于大容量使用#:capacity速度较慢。

== 5 iterations of 1e7 sized gvector, measured 3 times each way
with #:capacity
cpu time: 9174 real time: 9169 gc time: 4769
cpu time: 9109 real time: 9108 gc time: 4683
cpu time: 9094 real time: 9091 gc time: 4670
without
cpu time: 7917 real time: 7912 gc time: 3243
cpu time: 7703 real time: 7697 gc time: 3107
cpu time: 7732 real time: 7727 gc time: 3115

小容量使用#:capacity速度更快。

== 20 iterations of 1e6 sized gvector, measured three times each way
with #:capacity
cpu time: 2167 real time: 2168 gc time: 408
cpu time: 2152 real time: 2152 gc time: 385
cpu time: 2112 real time: 2111 gc time: 373
without
cpu time: 2310 real time: 2308 gc time: 473
cpu time: 2316 real time: 2315 gc time: 480
cpu time: 2335 real time: 2334 gc time: 488

我的假设：这是 GC 开销。当支持向量发生变化时，Racket 的分代 GC 会记住该向量，以便它可以在下一个小集合中扫描它。当支持向量非常大时，在每个次要 GC 上扫描整个向量超过重新分配和复制的成本。具有更精细的记忆集粒度的 GC 不会发生开销（但是......权衡）。

顺便说一句，查看 gvector 代码我发现了几个改进的机会。不过，他们并没有改变大局。

为什么在 Racket 中的 gvector 中保留容量会使性能变差？

Why does reserving capacity in a gvector in Racket make performance worse?

performance

profiling

vector

racket