Мы уже говорили про дополнительные виртуальные машины в 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 | Чат |