Разбор решения занявшего второе (пока что) место в конкурсе Hola по программированию почтовых фильтров на JavaScript

В ноябре прошлого (уже) года, Hola объявила конкурс по программированию почтовых фильтров на js ^[1], и недавно опубликовала его результаты ^[2].

Я разделил второе место с Ильей Макаровым, и сейчас я расскажу…

Как это было

Решив принять участие в конурсе и задумавшись над поставленной задачей, я довольно быстро осознал, что заданные шаблоны email'ов могут быть преобразованы в регулярные выражения простой заменой '*' на '.*' и '?' на '.' и экранированием всех специальных символов. На этом можно было и успокоиться, как и поступил Надав Ивги, получивший специальный приз за самое короткое решение ^[3].

Но это решение обладает фатальным недостатком — сложностью O((кол-во правил)*(кол-во сообщений)), так как каждое сообщение нужно проверить на соответствие каждому правилу.

Есть лучший путь. Во первых, две регулярки для полей .from и .to, можно соединить ^[4] в одну, отделив их друг от друга неиспользуемым символом (скажем 'x1F', так как по условию используются только символы от 'x20' до 'x7F' включительно), и то же самое проделывать с соответствующими полями сообщений:

     {from: 'john.doe@foo.org', to: '*@hola.*', action: 'act1'}
->
     {signature: 'alex@foo.orgx1F*@hola.*', action: 'act1'} 

Это уменьшает количество необходимых тестов вдвое.

Во вторых, эти регулярки можно скомпилировать в один детерминированный конечный автомат (DFA) ^[5], сложность работы которого не зависит от их колчества. Здесь стандартный RegExp ^[6] нам уже не поможет.

Именно это и делала первая версия ^[7] моего решения.

Успешно протестировав её на данных из задания я решил автоматизировать процесс и реализовал генератор исходных данных и сравнение результатов с reference implementation ^[8]. Как оказалось не зря, в процедуре минимизации DFA обнаружился баг, и я временно исключил её из алгоритма ^[9] (её наличие не влияет на корретность, только производительность).

Мой скрипт долбился в reference implementation с масимально возможно частотой, и через пару дней Hola ввели ограничение на частоту запросов. Хех. Я пожал плечами и ввел задержку между запросами ^[10]. Тестирование стало проходить медленнее, но жить было можно.

Тут началась оптимизация. Первая идея состояла в компиляции DFA в огромный switch на js ^[11], как это делает lex ^[12] и другие подобные инструменты.

Реализовав такой кодогенератор, я понял что не имею возможности оценить, улучшил ли я результат, и что для этого мне нужен куда более объемный набор тестовых данных. Я решил, что не смогу так просто сгенерировать датасет со вменяемыми статистическими характеристиками, и неплохо бы использовать реальный. Довольно быстро я нашёл Enron Email Dataset ^[13] — email архив обанкротившейся компании с соответствующим названием. Пара скриптов на Python ^[14] извлекли сообщения и сгенерировали из их адресов правила, и бенчмарк был готов.

Я запустил его и… подрвался на комбинаторной мине ^[15]. Дело в том, что алгоритм построения DFA ^[16] имеет экспоненциальную сложность (O(2^(кол-во состояний недетерминированного конечного автомата (NFA)))) и я недооценил насколько это ужасно. Я не мог дождаться конца завершения построения автомата для всего лишь двадцати правил. Вместо того чтобы решать эту алгоритмическую проблему, я потратил время на оптимизацию и без того высокопроизводительной части системы. Воистину, premature optimization is the root of all evil ^[17].

Ощутив просветление, первым делом я разделил .from и .to обратно, получив таким образом один автомат оперирующий только на .from для всех правил, и по одному автомату оперирующему на .to для каждой группы правил, .from которых приводят к одному и тому же конечному состоянию первого автомата:

Это уменьшило размеры каждого NFA как минимум вдвое, а значит и существенно уменьшился размеры соответствующих DFA. Производительность поднялась на порядок, теперь уже можно было дождаться построения автомата для сотни правил.

Но это всё равно было слишком долго. Пришло понимание, что нужно менять концепцию, а где-то через неделю пришло и озарение: не нужно строить весь детерминированный автомат сразу, можно строить его лениво, по одному состоянию за шаг. Реализация этой концепции ^[18] меня сильно удивила: она была в несколько раз быстрее предудущей версии на тех же входных данных, более того, она могла без труда прожёвывать входные данные куда большей размерности. Видимо большая часть состояний полного DFA не посещаются. Я даже заново распарсил датасет Enron'а, чтобы извлечь больше данных.

Я решил, что это то, что мне нужно, и принялся за оптимизацию.

Оптимизация

Я попробовал несколько разных вещей, опишу те, что дали ощутимый результат.

Мемоизация

Не замерял, но имею основания полагать, что времени экономит больше всего остального. Используется в двух местах:

• Ленивое построение DFA запоминает однажды пройденные состояния ^[19], а не создает из заново каждый проход.
• Запоминается конечное состояние автомата для каждого email'а ^[20], тем самым избавляя от необходимости повторно проходить по графу DFA. Так как в типичном email архиве сообщений зачастую много больше чем адресов, между которыми они пересылаются, выгода существенна. В частности, это приводит к тому, что в результате filter сообщения, имеющие одинаковые массивы действией, на самом деле ссылаются на один и тот же объект массива. Массивы действий не заполняются заново для каждого нового сообщения.

Поиск состояния DFA соответствущего множеству состояний NFA

Потратил на это больше всего времени. Суть такова: нужно эффективное отображение из множества Object'ов (состояний NFA) в другой Object (соcтояние DFA). Так как в js нету нормальных хештаблиц c нестроковыми ключами, пришлось изворачиваться.

Сделал следующее: в каждое состояние NFA поместил уникальный инт .id при создании NFA (простым инкрементом). Имея множество таких состояний, кладу их .id в Buffer ^[21], сортирую, и интерпретирую как строковый ключ ^[22] с помощью .toString() ^[23].

Исспользование специфики структуры NFA

NFA, получающийся из шаблонов email'ов, имеет особенности:

• Каждая вершина-состояние имеет не более двух исходящих дуг-переходов. Изначально это было реализовано в виде массивов для произвольного числа элементов. Когда я реализовал это в виде пар свойств ^[24] время выполнения уменьшилось на 20%.
• Во время создания, состояния NFA можно нумеровать ^[25] (заполнять .id) таким образом, что построенные в дальнейшем множества оных будут уже отсортированы, убирая необходимость сортировки для построения строкового ключа (описано выше)

Минимизация частоты аллокаций памяти

• При построении DFA постоянно создаются массивы состояний NFA, которые зачастую выкидываются после того, как по ним построен строковый ключ и найдено соответствующее состояние DFA (если не найдено, то создается новое, и массив становится его частью)
• При построении строкового ключа буфер содержащий .id NFA состояний выкидывается вообще всегда.

В обоих случаях можно создать массив и буфер максимально необходимых размеров ^[26] при создании DFA и многократно их использовать без перевыделения памяти.

Финальная оценка корректности

К этому моменту у меня заканчивались возможности для оптимизации, а полной уверенности в корректности решения не было. Чтобы исправить это досадное упущение, я написал ещё один скрипт на питоне ^[27], который медленно, за несколько дней, прогнал маленький кусочек датасета Enron'а (около 500 сообщений, для 1000 правил) через reference implementation. И, как оказалось, не зря. Получившиеся тестовые примеры выявили баг на edge-case'е, когда в шаблоне email'a две звездочки отделены друг от друга одним символом. Его было трудно найти но легко исправить ^[28].

Комментарий к методике оценки решений

Бенчмарк организаторов запускает тестируемые модули через модуль vm Node'a ^[29], вместо простого require ^[30]. Что, как выяснилось ^[31], имеет неожиданные эффекты на производительности. Организаторы решили пересмотреть результаты.

Также я был удивлен относительно малой размерностью входных данных, которые были использованы для оценки решений. Финальную версию я гонял на 500000 сообщений и 1000 правил, и ожидал ещё больших размеров в бенчмарке организаторов. На таком датасете и с запуском через require тройка официальных лидеров показывает следующие результаты:

• Юрий Килочек ~2300мс (я)
• Дениса Крешихин ~2850мс
• Илья Макаров ~7500мс

Для желающих, я выложил свое решение вместе с бенчмарками ^[32]. Предлагаю в будущем, во избежание подобных недоразумений, усреднять результат по разным размерностям входных данных, или организовывать соревнования в разных 'весовых категориях'.

Автор: tymofey

Источник ^[33]