Antlr и сборка мусора
Сказ о том, что недостаточно сохранить логику работы программ, можно еще много где голову сложить - читаем про переписывание кода с Java на Go.
Нельзя просто взять и переписать программу с одного языка программирования на другой. Корректная синтаксически и эквивалентная семантически программа внезапно может начать вести себя совершенно не так, как ожидаешь.
…Ничего не предвещало беды. Написали мы парсер на Antlr/Go. Есть вполне работающая реализация, на которой небольшие тесты компилируются и работают замечательно. Проблемы стали появляться постепенно.
Сначала было небольшое замедление на некоторых тестах, по мере роста размера тестов в некоторых случаях наблюдалось экспоненциальное замедление скорости работы.
Стали разбираться. Часть проблем удалось снять сразу, например, реализованная, но не включенная мемоизация расчетов. То есть автор реализовал кеширование, но в какой-то момент закоммитил файл с отключенным кешированием.
Затем были более тонкие оптимизации вроде настройки расчета хешей.
В Java у объектов есть метод hashCode(), используемый для сравнения объектов. Это замечательная штука, но для того, чтобы выразить соответствующую семантику на другом языке, необходимо постараться, особенно без поддержки компилятора. Antlr/Go для расчета хеша объекта выбрали MurmurHash.
Функция вычисления хеша вызывается очень часто, поэтому любые микрооптимизации могут быть полезны. Экономия пары вызовов функций и использование сдвига вместо умножения дало заметный прирост производительности.
Всего удалось поднять скорость работы в случаях, когда парсер начинал медленно работать, в 7-10 раз, в зависимости от входа.
Но этого было недостаточно, падение производительности по экспоненте никак не перекрывалось кратным ростом. Причем мало того, что скорость падала, так еще и потребление памяти становилось огромным. Парсер потреблял всю память и завешивал компьютер.
Стали разбираться дальше.
Antlr позиционирует себя как «всеядный», есть очень мало грамматик, которые он не сможет обработать. Проект даже выбрал себе соответствующего маскота – медоеда. Но это не дается даром. В спорных случаях, когда налицо синтаксическая неоднозначность, Antlr начинает перебирать грамматические правила для разрешения неоднозначностей, производя при этом большое количество действий и порождая большое количество объектов. Детали этого процесса расписаны в соответствующей статье.
И вот тут начинается самое интересное.
Реализация на Java выполняет перебор и подбор грамматических правил практически мгновенно, хотя при этом создаются и уничтожаются миллионы объектов (для тестового примера, создается около 6 миллионов объектов за время разбора).
По завершению разбора они уничтожаются сборщиком мусора. В Java это практически не дает просадки производительности и не вызывает вопросов по потреблению памяти.
В Go ситуация же иная. Реализация на Go очень тщательно списана с Java и в целом ей следует. В том числе стратегией использования памяти. (В реализации на C++, например, отличие в том, что для управления памятью используются умные указатели).
В массово выделяемых объектах есть ссылки на другие объекты и на контексты разбора. И вот тут в полный рост встала разница работы сборщиков мусора в Java и Go.
В первом случае сборщик поколенческий, во втором – точный (precise), то есть различает integer и pointer. Но, при этом, для сборщика мусора в Go ссылки внутри структур представляют собой большую проблему, т.к. из-за отсутствия поколений ссылки внутри структур всегда остаются живыми до очистки стекового кадра, где эта структура была порождена.
В итоге оказалось, что для сборщика мусора Go большое количество объектов не является проблемой, а вот большое количество объектов со ссылками - огромная проблема. В структуре, которая аллоцируется в Antlr, 4 указателя. Когда удалось убрать один указатель, заменив его целочисленными индексами, производительность сразу возрасла на 25%, скорость потребления памяти упала примерно на те же 25%.
С этим программисты уже сталкивались, да и наши эксперименты подтверждают, алгоритм и используемые структуры придется переписать. Причем, не просто переписать, но и перепроектировать для исключения указателей из массовой аллокации.
Вывод из этого можно сделать такой. Детали реализации инструментария могут иметь столь глубокие фундаментальные различия, что это сразу не видно, а проявляется только под большой нагрузкой. Тестируйте свои инструменты в разных режимах.
Для нас это вылилось в то, что мы сделали давно назревшую задачу – написали ручной парсер, оставив Antlr только как референсную грамматику. Теперь разбор занимает столь незначительное время, что мы его даже не замеряем, а потребление памяти находится где-то в районе 0.