Блог

Используя следующий простой тест в 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
  

Один комментарий для сравнительного анализа: используйте 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. Когда вспомогательный вектор видоизменяется, generational GC Racket запоминает вектор, чтобы он мог сканировать его в следующей второстепенной коллекции. Когда вспомогательный вектор очень большой, сканирование всего вектора при каждом второстепенном GC перевешивает затраты на перераспределение и копирование. Накладные расходы не будут возникать при использовании GC с более точной детализацией с сохранением заданной детализации (но … компромиссы).

Кстати, просматривая код gvector, я нашел пару возможностей для улучшения. Тем не менее, они не меняют общую картину.

Увеличивая размер вектора в 10 раз, я получаю следующее в DrRacket (при отключенной отладке):

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

Примечание: если после первого теста остался мусор, это может повлиять на следующий. Поэтому используйте сбор мусора (три раза), прежде чем снова использовать time.

Также … не создавайте тесты в DrRacket, как я — используйте командную строку.