Улучшение реализации трэпа - PullRequest
Новая
       20

Улучшение реализации трэпа

17 голосов
/ 07 января 2011

Вот моя реализация своего рода трепа (с неявными ключами и некоторой дополнительной информацией, хранящейся в узлах): http://hpaste.org/42839/treap_with_implicit_keys

Согласно данным профилирования GC отнимает 80% времени для этой программы.Насколько я понимаю, это связано с тем, что каждый раз, когда узел «модифицируется», каждый узел на пути к корню воссоздается.

Есть ли что-то, что я могу сделать здесь, чтобы улучшить производительность, или мне нужно погрузиться в царство монады ST?

1 Ответ

26 голосов
/ 17 апреля 2011

Используя GHC 7.0.3, я могу воспроизвести ваше тяжелое поведение GC: * ​​1001 * 

  $ time ./A +RTS -s
  %GC time      92.9%  (92.9% elapsed)
  ./A +RTS -s  7.24s user 0.04s system 99% cpu 7.301 total

Я потратил 10 минут на просмотр программы.Вот что я сделал по порядку:

  • Установить флаг -H GHC, увеличить пределы в GC
  • Проверить распаковку
  • Улучшить встраивание
  • Отрегулируйте область выделения первого поколения

Получив 10-кратное ускорение, и GC примерно в 45% времени.

По порядку, используя магический флаг GHC -H,мы можем немного сократить время выполнения: 

  $ time ./A +RTS -s -H
  %GC time      74.3%  (75.3% elapsed)
  ./A +RTS -s -H  2.34s user 0.04s system 99% cpu 2.392 total

Неплохо!

Прагмы UNPACK на узлах Tree ничего не сделают, поэтому удалите их.

Inlining update сокращает время выполнения: 

 ./A +RTS -s -H  1.84s user 0.04s system 99% cpu 1.883 total

, как и Inline height

 ./A +RTS -s -H  1.74s user 0.03s system 99% cpu 1.777 total

Таким образом, пока GC все еще доминирует -- поскольку мы проверяем распределение, в конце концов.Одна вещь, которую мы можем сделать, это увеличить размер первого поколения: 

 $ time ./A +RTS -s -A200M
 %GC time      45.1%  (40.5% elapsed)
 ./A +RTS -s -A200M  0.71s user 0.16s system 99% cpu 0.872 total

И увеличение порога развертывания, как предположил ДжонЛ, немного помогает, 

 ./A +RTS -s -A100M  0.74s user 0.09s system 99% cpu 0.826 total

, что в 10 раз быстреечем мы начали?Неплохо.

Используя ghc-gc-tune , вы можете видеть время выполнения как функцию -A и -H,

Time and GC

Интересно, что для лучшего времени работы используются очень большие значения -A, например 

$ time ./A +RTS -A500M   
./A +RTS -A500M  0.49s user 0.28s system 99% cpu 0.776s
...