Одна из оптимизаций в регулярных выражениях, поисках по строкам и подобных state transition алгоритмов заключается в достаточно хитрой оптимизации инструкций.
Пусть у вас есть какой-то граф, по которому надо ходить в зависимости от одного из 255 символов:
Вы по нему будете ходить как-то в роде:
Одна из оптимизаций может заключаться в том, чтобы склеить NUM_STATES в один или несколько регистров. Скажем, если у вас битность ваших стейтов максимум 64 / NUM_STATES, то вы можете поместить это всё в один регистр и тогда таблицу и переход по состояниям графа можно описать как:
Тем, что на самом деле мы можем предпосчитать state * 6, когда будете создавать таблицу переходов. Тогда переход вообще будет выглядеть как
Инструкция shrx занимает 1 такт, в итоге мы получаем алгоритм, который проходит по графу за 1 такт на символ, когда у вас есть граф переходов, и получается
1. Если всего вершин не более 10
2. Вы можете предпосчитать таблицу переходов умножая на 6
3. Без SIMD ходить по графу за 1 такт на символ
Это невероятно мощное свойство, потому что вы можете так представить
1. Поиск по строке очень многих строк (надо чтобы строка, по которой ищете была не очень длинной (порядка 9 символов (плюс 1 для обозначения терминального стейта))
2. Проверка на ASCII: всего 2 стейта, ASCII или нет
3. Регулярные выражения с не очень большим автоматом в 10 стейтов (ДКА/DFA)
4. Ходить по деревьям Хаффмана и раскодировать данные, если стейт не очень большой
Как ни странно, это огромное количество человеческих юзкейсов. Понятное дело есть SIMD, который старается искать меньше, чем за 1 такт на символ, но описанное сверху свойство показывает, что можно писать на чистом C и получать невероятную скорость.
Количества бит можно выбирать другие: например, без предосчёта BITS_PER_STATE = 4, NUM_STATES = 16, но тогда будет 2 такта на символ, что всё ещё лучше, чем адресоваться к памяти. Можно 2 регистра на state. Играться можно много.
Такая оптимизация есть в RE2, рассматривается в Golang и вообще является достаточно мощной техникой перевода ДКА на инженерный код.
В RE2 ещё забавное происходит, что если у вас есть какое-то регулярное выражение, то оно вряд ли использует много символов, скорее всего оно использует единичные символы и какие-нибудь range символов ([0-9], [a-z] и тд). Из-за этого в RE2 происходит так называется консолидация алфавита, где алфавит преобретает цвета -- range в роде [0-9] становится одним символов, в подстроках типа
Эта статья основана на блоге pervognsen.
Godbolt на код из RE2
Пусть у вас есть какой-то граф, по которому надо ходить в зависимости от одного из 255 символов:
Вы по нему будете ходить как-то в роде:
uint8_t table[256][NUM_STATES];
uint8_t state;state = table[input[i]][state];
То есть если у вас есть state, символ, вы идёте по таблице инструкций от символа и переходите по state. Так можно делать в цикле, так одна из проблем заключается в том, что мы должны 2 раза обратиться к памяти, что в целом не очень хорошо, так как обращения к памяти достаточно тяжелые.Одна из оптимизаций может заключаться в том, чтобы склеить NUM_STATES в один или несколько регистров. Скажем, если у вас битность ваших стейтов максимум 64 / NUM_STATES, то вы можете поместить это всё в один регистр и тогда таблицу и переход по состояниям графа можно описать как:
uint64_t table[256];
state = (table[input[i]] >> (state * BITS_PER_STATE)) & ((1 << BITS_PER_STATE) - 1);
Если выбрать BITS_PER_STATE = 6, то в один регистр можно запихать 10 стейтов (6 * 10 < 64 < 6 * 11) и тогда переход будет записан какstate = (table[input[i]] >> (state * 6)) & 63
Чем это выражение хорошо?Тем, что на самом деле мы можем предпосчитать state * 6, когда будете создавать таблицу переходов. Тогда переход вообще будет выглядеть как
old_state * 6 = ((table[input[i]] >> state) & 63)
В итоге это эквивалентно выглядит какstate = table[input[i]] >> (state & 63); // bits are lowered automatically
...
return state & 63; // lower the bits
Прелесть такого shift алгоритма в том, что на x86 оно транслируется в инструкцию shrx (сдвиги и так делаются по модулю 64)Инструкция shrx занимает 1 такт, в итоге мы получаем алгоритм, который проходит по графу за 1 такт на символ, когда у вас есть граф переходов, и получается
1. Если всего вершин не более 10
2. Вы можете предпосчитать таблицу переходов умножая на 6
3. Без SIMD ходить по графу за 1 такт на символ
Это невероятно мощное свойство, потому что вы можете так представить
1. Поиск по строке очень многих строк (надо чтобы строка, по которой ищете была не очень длинной (порядка 9 символов (плюс 1 для обозначения терминального стейта))
2. Проверка на ASCII: всего 2 стейта, ASCII или нет
3. Регулярные выражения с не очень большим автоматом в 10 стейтов (ДКА/DFA)
4. Ходить по деревьям Хаффмана и раскодировать данные, если стейт не очень большой
Как ни странно, это огромное количество человеческих юзкейсов. Понятное дело есть SIMD, который старается искать меньше, чем за 1 такт на символ, но описанное сверху свойство показывает, что можно писать на чистом C и получать невероятную скорость.
Количества бит можно выбирать другие: например, без предосчёта BITS_PER_STATE = 4, NUM_STATES = 16, но тогда будет 2 такта на символ, что всё ещё лучше, чем адресоваться к памяти. Можно 2 регистра на state. Играться можно много.
Такая оптимизация есть в RE2, рассматривается в Golang и вообще является достаточно мощной техникой перевода ДКА на инженерный код.
В RE2 ещё забавное происходит, что если у вас есть какое-то регулярное выражение, то оно вряд ли использует много символов, скорее всего оно использует единичные символы и какие-нибудь range символов ([0-9], [a-z] и тд). Из-за этого в RE2 происходит так называется консолидация алфавита, где алфавит преобретает цвета -- range в роде [0-9] становится одним символов, в подстроках типа
bar, лишь 3 символа, поэтому они будут покрашены отдельными цветами. В итоге такая эвристика сильно уменьшает алфавит, количество состояний и помогает использовать оптимизацию, описанную сверху, чаще.Эта статья основана на блоге pervognsen.
Godbolt на код из RE2