Здесь моя реализация рода treap (с неявными ключами и некоторой дополнительной информацией, хранящейся в узлах): http://hpaste.org/42839/treap_with_implicit_keys
В соответствии с данными профилирования GC занимает 80% времени для этой программы. Насколько я понимаю, это связано с тем, что каждый раз, когда a node "изменен", каждый node на пути к корню воссоздается.
Есть ли что-то, что я могу сделать здесь, чтобы улучшить производительность, или мне нужно спуститься в царство монады ST?
Используя GHC 7.0.3, я могу воспроизвести ваше тяжелое поведение GC:
$ 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 минут, проходя через программу. Вот что я сделал, в порядке:
Результат в 10-кратном ускорении и GC около 45% времени.
Для того, чтобы использовать флаг magic -H GHC magic, мы можем немного сократить время выполнения:
$ 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 ничего не сделают, поэтому удалите их.
Вложение update сокращает время выполнения:
./A +RTS -s -H 1.84s user 0.04s system 99% cpu 1.883 total
как и вставка 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,
Интересно, что лучшие времена работы используют очень большие значения -A, например.
$ time ./A +RTS -A500M
./A +RTS -A500M 0.49s user 0.28s system 99% cpu 0.776s