Структуры данных в haskell и как они влияют на garbage collector

Для решения одной из задачек из стэнфордского курса по криптографии понадобилось создать таблицу соответствия Word64 -> Integer и несколько миллионов раз проверить в ней наличие элемента и добавить новый. Решение очевидно: хэш-таблицы. hoogle предложил Data.HashTable, программа была написана, успешно отработала и можно было бы обо всем забыть, но захотелось потренироваться в профайлинге и оптимизации.

Запуск с +RTS -sstderr вызвал легкий шок: почти половина времени уходила на сборку мусора.

13,902,917,208 bytes allocated in the heap
3,275,041,156 bytes copied during GC
MUT time 26.69s ( 40.10s elapsed)
GC time 27.84s ( 32.47s elapsed)
%GC time 51.1% (44.7% elapsed)

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

Для начала Data.HashTable был заменен на тройку из hashtables: Basic, Cuckoo и Linear. Результаты несколько удивили: Basic и Cuckoo общее время работы почти не изменили, но при этом GC стал занимать до 70% времени. Собственный код стал работать быстрее, а GC занял остальное время. Память при этом копировалась значительно меньше.

Basic:
12,781,006,960 bytes allocated in the heap
408,935,780 bytes copied during GC
MUT time 15.00s ( 15.16s elapsed)
GC time 43.29s ( 43.79s elapsed)
%GC time 74.3% (74.3% elapsed)

Cuckoo:
11,611,257,712 bytes allocated in the heap
419,308,168 bytes copied during GC
MUT time 17.31s ( 17.65s elapsed)
GC time 38.08s ( 38.42s elapsed)
%GC time 68.7% (68.5% elapsed)

Linear таблица, как и следовало ожидать, предназначена совсем для других сценариев и из состязаний выбывает сразу же:
12,547,294,380 bytes allocated in the heap
17,997,812,764 bytes copied during GC
MUT time 26.65s ( 27.16s elapsed)
GC time 123.72s (124.30s elapsed)
%GC time 82.3% (82.1% elapsed)

Еще немного оптимизаций считающего кода, указание изначально правильного размера таблицы и в лидеры уверенно вышла CuckooHashTable:
3,835,164,148 bytes allocated in the heap
179,941,588 bytes copied during GC
MUT time 7.84s ( 7.97s elapsed)
GC time 20.05s ( 20.18s elapsed)
%GC time 71.9% (71.7% elapsed)

Общее время работы уменьшилось уже вдвое, но 70% на GC? Надо что-то менять в консерватории.
Data.Judy является оберткой к сишной реализации judy tables, под GC не попадает совсем и решительно меняет правила игры:
5,366,256,252 bytes allocated in the heap
3,725,456 bytes copied during GC
MUT time 8.99s ( 9.12s elapsed)
GC time 1.44s ( 1.45s elapsed)
%GC time 13.4% (13.3% elapsed)

На профиле кучи видно, что объем выделеной памяти не меняется вообще: ровная горизонтальная линия, все данные лежат вне доступа GC.

Недостатков три:

• надо патчить пакет, выкинув -fvia-C, без этого вылезают совершенно невразумительные ошибки линковки;
• отображение строго из Word в Word, поэтому для ключей Word64 приходится делать массив массивов. Пример хранения ByteString есть в исходниках, но всё равно ненужная работа;
• и наконец, на C я всё это могу и напрямую написать! Хаскель у нас или где?

Что осталось? Конечно Data.Map. Никаких IO, никакого C, правоверный haskell код, который и выглядит красивее. Результаты ВНЕЗАПНЫ:
5,569,024,484 bytes allocated in the heap
4,241,345,748 bytes copied during GC
MUT time 18.55s ( 18.77s elapsed)
GC time 12.66s ( 13.07s elapsed)
%GC time 40.6% (41.1% elapsed)

Всего на 10% медленнее, чем CuckooHashTable, и вообще никакого сравнения с Data.HashTable. Готовая иллюстрация к «думать не надо, надо трясти»: зачем все эти пляски, если можно написать совершенно прямолинейный код и потери практически незаметны?

И финальным аккордом unordered-containers с Data.HashMap.Strict, мгновенной заменой для Data.Map: достаточно поменять import и тип структуры, остальное совместимо.
5,688,939,936 bytes allocated in the heap
3,659,088,964 bytes copied during GC
227,864,212 bytes maximum residency (23 sample(s))
MUT time 10.16s ( 10.75s elapsed)
GC time 8.93s ( 9.61s elapsed)
%GC time 46.8% (47.2% elapsed)

Многовато копируется, на профиле четко видно перевыделение таблицы. Попробуем сразу подсунуть побольше памяти, +RTS -A250M.
5,663,421,460 bytes allocated in the heap
887,689,168 bytes copied during GC
MUT time 11.40s ( 11.70s elapsed)
GC time 3.61s ( 3.83s elapsed)
%GC time 24.1% (24.7% elapsed)

Ta-da! До judy не дотягивает, но все остальные варианты оставлены позади. В качестве бесплатных бонусов те же плюшки, что и у Data.Map: не надо писать свое преобразование ключа в хэш, как в hashtables, не надо засовывать всё подряд в монады, код получается раза в два короче.

Ну и традиционный вывод: premature optimization is the root of all evil. Лобовое решение вполне может оказаться быстрее остальных.