performance - 为什么在 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

一个基准测试评论:在您的微基准测试中使用 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 上扫描整个向量超过重新分配和复制的成本。具有更精细的 memset 粒度的 GC 不会发生开销(但是……权衡)。

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