Table based vs switch-if vs pull
Мне удалось написать вариант лексического сканера пригодного как к push так pull моделям использования. естественно он базируется на основе конечного автомата и перенимает все нехорошие особенности самого первого push-варианта.
Конечный автомат я описал в виде своебразного DSL, который легкой магией Си-макросов может разворачиваться в исходниках в енумерацию токенов, состояний и, самое главное, в функцию вычисления следующего состояния конечного автомата. Что-бы не быть голословным, приведу ключевые моменты, как автоматически формируется перечисления токенов и состояний, и функция состояния конечного автомата:
При реализации pull-модели функция transition_fsm вызывается внутри цикла функции lexer_scan_text до тех пор пока не закончатся входной текст или не будет продетектирован очередной токен на базе просмотреного текста. При реализации push-модели функция transition_fsm вызывается внутри lexer_scan_char для каждого нового входного символа.
Всё просто и довольно прямолинейно. Но вот дальше начинается самое интересное:
Оказывается в таком варианте реализация лексера (fms3-bench) по скорости почти догоняет оригинальную pull-реализацию. Без всяких ручных оптимизаций, со свитчом и if-ами, компилятор состворил чудо.
Но дальше начинается смое интересное. На первый взгляд - чувствуется месиво из джампов в коде должно работать как-то медленно. Поэтому я решил реализовать transition функцию таблично. Ну, типа в теории, берем два параметра - текущее состояние и входной символ и по двухмерной табличке берем следующее состояние конечного автомата, все как по учебникам. При этом есть нюансы - поскольку входной алфавит как правило довольно сильное подмножество всех символов, а количество состояний довольно большое (в моем случае 98 штук), то таблицы "в-лоб" получаются очень большими и разрежеными. И это наводит на нехорошие мысли про cache-miss. Поэтому таблицы надо представлять в каком-то альтернативном виде. Существует много разных техник, но одна из самых очевидных - это существенно сузить входной алфавит: отсеять неиспользуемые символы и обьединить символы которые дают одинаковые переходы состояний конечного автомата. Таким образом, одно из первых действий, - это преобразовать входной символ в алфавит "символьных классов". Это позволяет в разы уменьшить размер таблиц, но все равно не дает желаемого. На второе действие меня навело случайное прочтение патента US007411418B2 "Efficient representation of state transition tables". Нет, конечно я не стал реализовывать написаное там, просто вспомнил про иерархические таблицы. В моем случае также две стадии поиска - первая таблица по номеру состояния и коду блока символьного класса содержит смещение во второй таблице, в которой по этому смещению и смещению внутри блока символьного класса лежит искомое следующее состояние конечного автомата. Пока я не стал запариваться с компресией самих блоков во второй таблице, поскольку оба этих действия дают просто космический коэффициент сжатия таблиц переходов. Ниже небольшой выхлоп со статистикой:
Поскольку описание конечного автомата дружественно к языку макросов Си, то нет никакой необходимости в ручном чтении и парсинге этого описания - генератор таблиц просто включает его внутри себя точно также как это было реализовано выше, а всем парсингом занимается препроцессор и компилятор языка Си.
Функция transition_fsm внезапно прияла вот такой вот вид:
Выглядит она так необычно потому что там есть еще некоторые оптимизации которые позволяют обойтись без умножения при доступе к двухмерной таблице st1tab. Это как раз таблица смещения блоков внутри таблицы st2tab. Таблица трансляции символа в код его символьного класса содержится неявно в таблице смещений offtab.
Но это мы увлеклить техническими тонкостями.
А теперь переходим к самому интересному:
Вариант с табличной реализацией конечного автомата оказался медленее почти в два раза своего неоптимизированного аналога! Ебать!
Посмотрим статистику:
В случае "оптимизированого" табличного варианта - огромное кол-во ошибок предсказателя ветвлений и плохое спаривание инструкций (~2.0 инструкции на цикл против ~3.35 в первом случае). Вот это да.
Посмотрим где предсказатель проебывается больше всего:
Видно, что в почти 43% случаев предсказатель ветвлений ошибается при переходе на метку 66. 0x14 - это кол-во акшенов которые должны выполняться при переходе между состояниями конечного автомата, полностью от этого свитча отказаться не удалось т.к. помимо лексического сканирования сканер еще и занимается конвертацией числовых и стороковых токенов соответсвенно в числа (как int так float) так и в строковые литералы с распознованием по дороге различных C-escape последовательностей. Видно, что сам свитч компилятор выразил в джампах по табличке с индексацией через регистр rax. Но это совершенно не фатально в неоптимизированом варианте который "прямо с пера", а в случае табличного варианта сносит крышу предсказателю переходов.
Вот так вот мы ручками и дооптимизировались до в 2 раза хуже!