Виртуальная машина regex в Python Мы уже говорили про дополнительные виртуальные машины в CPython. Посмотрели на pickle, сегодня настала очередь re. Немного не в формате канала, что мы смотрим джуновские штуки, но все равно интересно, может быть какие-то детали будут незнакомы и сениор специалистам. Документация: https://docs.python.org/3/library/re.html Исходник: https://github.com/python/cpython/blob/main/Modules/_sre/sre.c Допустим у нас есть такой паттерн: re.compile(r'@[a-z\d]\d{2,}'). Начинается с @, далее буква латиницей в нижнем регистре или цифра, далее как минимум две цифры. И мы можем посмотреть opcod'ы для данного выражения: LITERAL 64 IN RANGE (97, 122) CATEGORY CATEGORY_DIGIT MAX_REPEAT 2 MAXREPEAT CATEGORY CATEGORY_DIGIT 0. INFO 8 0b1 4 MAXREPEAT (to 9) prefix_skip 1 prefix [0x40] ('@') overlap [0] 9: LITERAL 0x40 ('@') 11. IN 7 (to 19) 13. RANGE 0x61 0x7a ('a'-'z') 16. CATEGORY UNI_DIGIT 18. FAILURE 19: REPEAT_ONE 6 2 MAXREPEAT (to 26) 23. CATEGORY UNI_DIGIT 25. SUCCESS 26: SUCCESS re.compile('@[a-z\\d]\\d{2,}', re.DEBUG) Все опкоды можно посмотреть тут: https://github.com/python/cpython/blob/main/Modules/_sre/sre_constants.h Процесс компиляции Сам процесс компиляции написан на Python, он довольно понятный: https://github.com/python/cpython/blob/e9c9a339035c9b96a5ebca8337a13140725ecf2a/Lib/re/_compiler.py#L34 Есть куча оптимизаций, кешей, утилит для дебага. Тот же dis, вывод которого мы видим при использовании re.DEBUG выше. Данная часть довольно чувствительна к перформансу. Буквально сегодня видел свежий баг, когда ВДРУГ становится медленнее. Выполнение опкодов Раз мы можем скомпилировать инструкции для VM, то мы можем их и выполнить. Исходники самой VM: https://github.com/python/cpython/blob/main/Modules/_sre/sre_lib.h Сначала немного интересных фактов: - Для данной VM в некоторых местах тоже используются COMPUTED_GOTO, если они поддерживаются (пост о них) - Почему-то нет поддержки _Py_TAIL_CALL_INTERP, хотя возможно оно тоже дало бы неплохой буст. Очень интересная задачка на подумать. Может кто-то хочет взять и попробовать? (пост о нем) - В Python3.15 произошел глобальный рефакторинг re модуля: удалили модули sre_compile, sre_constants, sre_parse А вот так выглядят обработчик LITERAL опкодов: TARGET(SRE_OP_LITERAL): /* match literal string */ /* <LITERAL> <code> */ TRACE(("|%p|%p|LITERAL %d\n", pattern, ptr, *pattern)); if (ptr >= end || (SRE_CODE) ptr[0] != pattern[0]) RETURN_FAILURE; pattern++; ptr++; DISPATCH; Про DSL с TARGET и DISPATCH я уже рассказывал в посте про основную VM в питоне. Остальная логика очень простая: если встречаем другой символ, то просто возвращаем 0, если встречаем нужный - продолжаем. ptr++ и pattern++ берут следующий указатель на строку и следующий pattern для матча. Таким образом в DISPATCH попадет уже следующий опкод. Классика. Еще интересно глянуть REPEAT_ONE, который нам нужен в самом конце. Он довольно большой, я спрятал его под ссылку. Из интересного там могу выделить оптимизацию под повторение опкода LITERAL. Остальное - довольно стандартно. Проверяем размер строки, ее символы внутри. Оказывается, что регулярные выражения - довольно простые и понятные, если смотреть на них как на инструкции для выполнения. А не как на текст. И помните: > Если у вас есть проблема, и вы решили использовать регулярные выражения, чтобы её решить... Теперь у вас две проблемы Обсуждение: Любите ли вы писать regex? Поможет ли вам данный пост в дебаге сложных выражений? Есть ли у вас какие-то хитрые оптимизации на уме, которые можно было бы добавить в CPython? | Поддержать | YouTube | GitHub | Чат |
Открыть в TelegramПросмотры2 624−58%к среднему
Пересылки25
Реакции46
Комментарии64
