Чтобы решить одну из задач из Стэнфордского курса по криптографии, нужно было создать таблицу соответствия Word64 -> Integer и несколько миллионов раз проверить наличие в ней элемента и добавить новый.
Решение очевидно: хеш-таблицы.
google предложил Data.HashTable, программа была написана, она работала успешно и мы могли обо всем забыть, но мне хотелось попрактиковаться в профилировании и оптимизации.
Запуск с +RTS -sstderr вызвал легкий шок: почти половина времени уходила на сбор мусора.
В куче выделено 13 902 917 208 байт. 3 275 041 156 байт скопировано во время сборки мусора Время MUT 26,69 с (прошло 40,10 с) Время GC 27,84 с (прошло 32,47 с) %GC время 51,1% (прошло 44,7%) Обращение к профилировщику кучи и коллективному разуму объяснило: чередование данных хэш-таблицы в куче с промежуточными результатами вычислений расстраивает GC, а увеличение и копирование внутренних таблиц при их заполнении полностью убивает производительность.
Оптимизация считающего кода с целью уменьшения количества промежуточных данных почти ничего не дала; хеш-таблицу необходимо изменить.
Для начала Data.HashTable был заменен тремя хеш-таблицами: Basic, Cuckoo и Linear. Результаты оказались несколько неожиданными: Basic и Cuckoo почти не изменили общее время работы, но при этом GC стал занимать до 70% времени.
Нативный код стал работать быстрее, а остальное время занял GC. При этом памяти копировалось существенно меньше.
Базовый: В куче выделено 12 781 006 960 байт. 408 935 780 байт скопировано во время сборки мусора Время MUT 15.00с (прошло 15.16с) Время GC 43,29 с (прошло 43,79 с) %GC времени 74,3% (прошло 74,3%) Кукушка: В куче выделено 11 611 257 712 байт. 419 308 168 байт скопировано во время сборки мусора Время MUT 17,31 с (прошло 17,65 с) Время GC 38,08 с (прошло 38,42 с) %GC-время 68,7% (прошло 68,5%) Линейный стол, как и следовало ожидать, предназначен совершенно для других сценариев и сразу выбывает из конкуренции: В куче выделено 12 547 294 380 байт. 17 997 812 764 байт скопировано во время сборки мусора Время MUT 26,65 с (прошло 27,16 с) Время GC 123,72 с (прошло 124,30 с) %GC времени 82,3% (прошло 82,1%) Еще несколько оптимизаций считающего кода, задав изначально правильный размер таблицы, и CuckooHashTable уверенно вырвался вперед: В куче выделено 3 835 164 148 байт. 179 941 588 байт скопировано во время сборки мусора Время MUT 7,84 с (прошло 7,97 с) Время GC 20,05 с (прошло 20,18 с) %GC времени 71,9% (прошло 71,7%) Общее время работы уже сократилось вдвое, но 70% на GC? Надо что-то менять в консерватории.
Data.Judy — это обертка для C-кодовой реализации таблиц judy, вообще не подпадает под GC и решительно меняет правила игры: В куче выделено 5 366 256 252 байта 3 725 456 байт скопировано во время сборки мусора Время MUT 8,99 с (прошло 9,12 с) Время GC 1,44 с (прошло 1,45 с) %GC время 13,4% (прошло 13,3%) Профиль кучи показывает, что объем выделенной памяти вообще не меняется: ровная горизонтальная линия, все данные находятся вне доступа GC. Есть три недостатка:
- патчить пакет нужно скинув -fvia-C, иначе появятся совершенно непонятные ошибки линковки;
- Сопоставление строго из Word в Word, поэтому для ключей Word64 вам придется создать массив массивов.
Пример хранилища ByteString есть в исходном коде, но это всё равно лишняя работа;
- и, наконец, на C я могу написать все это напрямую! У нас есть Haskell или где?
Результаты ВНЕЗАПНЫЕ: В куче выделено 5 569 024 484 байта 4 241 345 748 байт скопировано во время сборки мусора Время MUT 18,55 с (прошло 18,77 с) Время GC 12,66 с (прошло 13,07 с) %GC время 40,6% (прошло 41,1%) Всего на 10% медленнее, чем CuckooHashTable, и никакого сравнения с Data.HashTable. Готовая иллюстрация к «не надо думать, просто потрясти»: зачем все эти танцы, если можно написать совершенно простой код и потери почти незаметны? И финальный аккорд — unordered-контейнеры с Data.HashMap.Strict, мгновенная замена Data.Map: достаточно изменить импорт и тип структуры, остальное совместимо.
В куче выделено 5 688 939 936 байт. 3 659 088 964 байта скопировано во время сборки мусора Максимальная резидентность 227 864 212 байт (23 образца(ов)) Время MUT 10,16 с (прошло 10,75 с) Время GC 8,93 с (прошло 9,61 с) %GC времени 46,8% (прошло 47,2%) Много копирования; в профиле четко виден повторный выбор стола.
Попробуем сразу добавить памяти, +RTS -A250M. В куче выделено 5 663 421 460 байт. 887 689 168 байт скопировано во время сборки мусора Время MUT 11:40 с (прошло 11,70 с) Время GC 3,61 с (прошло 3,83 с) %GC времени 24,1% (прошло 24,7%) Та-да! Это не доходит до Джуди, но все остальные варианты остаются позади.
В качестве бесплатных бонусов те же вкусности, что и у Data.Map: не надо писать собственное преобразование ключа в хеш, как в хэш-таблицах, не надо всё запихивать в монады, код в два раза короче.
Ну и традиционный вывод: преждевременная оптимизация — корень всех зол.
Фронтальное решение вполне может оказаться быстрее остальных.
Теги: #haskell #haskell
-
Как Конвертировать 3Gp В Ipod - Hodosoft
19 Oct, 24 -
Арон, Реймон
19 Oct, 24 -
Обновления Построителя Моделей Ml.net
19 Oct, 24
