Ну во-первых, там всё-таки не 256 символов ширина. Если у нас регулярка вида /[a-z]@([a-z]\.)*[a-z]*/ (типа мы e-mail валидируем), то нас не интересует в точности текущий символ, а интересно лишь, что это: буква, собачка, точка или что-то ещё. Соответственно, кладём рядом табличку преобразования 256 байтов в 4 класса симоволов, а таблица переходов автомата индексируется уже классами и потому ощутимо худеет.
Наиболее простой способ ускорения, который есть и в re2, и в pire, применим в том случае, если из данного состояния дуги по всем символам, кроме одного (в re2) или двух (в pire) ведут в то же состояние. Тогда можно запустить просто strchr() или strcspn() и посмотреть, где мы остановились. Понять, что "а вот тут кусок регулярки сводится к вызову strstr()" пока не получилсь :)
Что касается генерации кода -- то при сравнении с ragel-ем (который как раз компилирует регулярку в C-код) pire всё-таки работал быстрее, хотя и на единицы процентов. Я не знаю, как описаннный в посте цикл эффективнее впихать в x86-код :)
Comments 1
Наиболее простой способ ускорения, который есть и в re2, и в pire, применим в том случае, если из данного состояния дуги по всем символам, кроме одного (в re2) или двух (в pire) ведут в то же состояние. Тогда можно запустить просто strchr() или strcspn() и посмотреть, где мы остановились. Понять, что "а вот тут кусок регулярки сводится к вызову strstr()" пока не получилсь :)
Что касается генерации кода -- то при сравнении с ragel-ем (который как раз компилирует регулярку в C-код) pire всё-таки работал быстрее, хотя и на единицы процентов. Я не знаю, как описаннный в посте цикл эффективнее впихать в x86-код :)
Reply
Leave a comment