LINUX.ORG.RU

В Rust добавлены compile-time регулярные выражения

 , ,


1

6

В стандартную библиотеку языка Rust добавлены регулярные выражения, реализованные через макросы (компилируются во время компиляции программы).

Подробности:

http://blog.burntsushi.net/rust-regex-syntax-extensions

Обсуждения:

http://www.reddit.com/r/rust/comments/243bw9/syntax_extensions_and_regular_ex...

http://www.reddit.com/r/programming/comments/2441r9/syntax_extensions_and_reg...

https://news.ycombinator.com/item?id=7654361


неплохо, в теории самый быстрый вариант, правда хотелось бы сравнения с реализациями в других ЯП

wota ★★ ()
Ответ на: комментарий от wota

в теории самый быстрый вариан

ИМХО, единственная полезная фишка такой реализации - сообщения об ошибках в регэкспах на этапе компиляции.

tailgunner ★★★★★ ()
Ответ на: комментарий от wota

это ты про compile-time регулярные выражения? или скапитанил про макросы?

Ну так теоретически макросы в Common Lisp написаны на Common Lisp и, таким образом, почти всё что доступно в рантайме доступно так же и в компайлтайме.

Bad_ptr ★★★★★ ()
Ответ на: комментарий от Bad_ptr

и, таким образом, почти всё что доступно в рантайме доступно так же и в компайлтайме.

ну, во-первых в CL вообще нет регулярных выражений в стандарте как в C++, Rust, D etc., во-вторых сторонняя реализация cl-ppcre просто отстойна в плане скорости:

http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang=...

C++ g++ 5.27 3.55 198,920 695 9% 49% 69% 26%
Lisp SBCL 41.02 19.36 929,636 1948 91% 38% 43% 41%

в-третьих есть большая разница между «доступно так же и в компайлтайме» и тем, что сделали в Rust

wota ★★ ()
Последнее исправление: wota (всего исправлений: 1)
Ответ на: комментарий от wota

cl-ppcre просто отстойна в плане скорости

ну, это уже другой вопрос ☺

есть большая разница между «доступно так же и в компайлтайме» и тем, что сделали в Rust

Нету там никакой большой разницы(точнее есть, но не в пользу Rust).
Тем более что в статье по ссылке сказано:

Note that I am not the first to do this. D has ctRegex which claims to do something similar. There is also xpressive in Boost, but native regexes must be written with template syntax. Finally, there is also CL-PPCRE for Common Lisp which also claims to have native regexes.

Bad_ptr ★★★★★ ()
Ответ на: комментарий от Bad_ptr

Нету там никакой большой разницы

есть, это как сделать re.compile заранее vs приведенный выше re2c, два разных способа, это если говорить про «доступно так же и в компайлтайме»

which also claims to have native regexes.

тем удивительнее ее низкая производительность

wota ★★ ()
Ответ на: комментарий от wota

Боюсь, что данная конкретная реализация в данный конкретный момент далеко не самая быстрая на свете. Смысл тут скорее показать, что Rust-овские макросы такое могут.

В статье есть ссылка, данные оттуда не такие радужные :) :

https://github.com/BurntSushi/regexp/tree/master/benchmark/regex-dna

ozkriff ()
Ответ на: комментарий от stopitplease

В питоне можно один раз в рантайме скомпилировать и эффект тот же

Не уверен: регулярное выражение, скомпилированное во время выполнения, будет байткодом и выполняться будет на виртуальной машине, если я не ошибаюсь.

ozkriff ()
Ответ на: комментарий от Bad_ptr

Все уже где-то было :) . Разработчики Rust, как я понимаю, не претендуют на новизну идей, скорее на грамотную компоновку уже известных идей и концепций и выкидывание всякого лишнего и ненужного.

ozkriff ()
Ответ на: комментарий от tailgunner

ИМХО, единственная полезная фишка такой реализации - сообщения об ошибках в регэкспах на этапе компиляции.

А как же (теоретическое, естественно) повышение производительности?

ozkriff ()
Ответ на: комментарий от ozkriff

Правда, lifetimes довольно оригинальная идея. Не знаю других языков, где такое есть.

ozkriff ()
Ответ на: комментарий от ozkriff

По поводу скорости, в конце статьи есть заметка про то, что можно еще долго-долго оптимизировать:

Future work

There are still many more optimizations that can be performed:

- Creating a “one pass” NFA where no backtracking need occur.

- Attempt to do state compression in the code generator via a more intelligent analysis on the sequence of instructions.

- The big one: implement a DFA, similar to how RE2/C++ works.

ozkriff ()
Ответ на: комментарий от ozkriff

А как же (теоретическое, естественно) повышение производительности?

Я думаю, что оно так и останется теоретическим.

tailgunner ★★★★★ ()
Последнее исправление: tailgunner (всего исправлений: 1)
Ответ на: комментарий от wota

в теории самый быстрый вариантв теории самый быстрый вариант

регулярки сами по себе не очень быстрые. И AFAIK обычно время компиляции мало по сравнению со временем исполнения. Если RE не очень простое. А если простое, то зачем оно нужно?

правда хотелось бы сравнения с реализациями в других ЯП

для начала с glibc.

emulek ()

в продолжение лиспосрача ^_^, вот код на С++:

http://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexdna&la...

вот код на Rust:

https://github.com/BurntSushi/regexp/blob/master/benchmark/regex-dna/regex-dn...

вот PHP:

http://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexdna&la...

Ruby:

http://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexdna&la...

А теперь «ужас летящий на крыльях ночи», Common Lisp:

http://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexdna&la...

который проигрывает и PHP, и Ruby, и С++ (Rust пока просто нет в списке)

wota ★★ ()
Ответ на: комментарий от tailgunner

сообщения об ошибках в регэкспах на этапе компиляции.

только синтаксических. Не нужно. Или это ЯП для обезьян?

emulek ()
Ответ на: комментарий от emulek

регулярки сами по себе не очень быстрые. И AFAIK обычно время компиляции мало по сравнению со временем исполнения. Если RE не очень простое. А если простое, то зачем оно нужно?

ты просто не понял идею

wota ★★ ()
Ответ на: комментарий от wota

ты просто не понял идею

что тут непонятного? Компиляция regex во время компиляции. Ну и что? Regex всю жизнь отдельно компилировались, хоть и в рантайме.

man 3 regcomp

DESCRIPTION POSIX regex compiling regcomp() is used to compile a regular expression into a form that is suitable for subsequent regexec() searches.

можешь выдрать оттуда regex_t, и записать её в C/C++ код. Только так никто не делает, ибо проще посчитать. Считать можно всего один раз, например на старте программы. Сколько в твоём коде регулярок?

Типичная экономия на спичках. Тут куда как полезнее использование SSE и многопоточность.

emulek ()
Ответ на: комментарий от wota

не, ты слишком много хочешь от Ъ. На кой ляд ЛОР вообще тогда нужен?

emulek ()

Не понимаю массового дроча на регулярные выражения. Для чего-то действительно сложного они просто неюзабельны (или монструозны и в силу этого неподдерживаемы). Для мелочей типа матчинга IPадреса или е-мэйла - годится, но зачем тогда на них так заострять внимание?

То ли дело (типизированные) парсер комбинаторы!

yoghurt ★★★★★ ()
Ответ на: комментарий от yoghurt

Про то, что комбинаторные парсеры в других языках есть, я знаю, просто ни разу не приходилось видеть, чтобы их реально использовали.

theNamelessOne ★★★★★ ()
Ответ на: комментарий от yoghurt

Я ссылку тут запостил, потому что макросы Ржавчины теперь такое могут, а не из-за самих регулярок.

ozkriff ()
Ответ на: комментарий от ozkriff

Правильно, что не уверен. Пайтоновский модуль re это питоновская обертка к frozen модулю (т.е. «вшитый» непосредственно в интерпретатор и нативный) _sre. Вся работа с регулярками выполняется этим сишным движком Perl-совместимых регэкспов.

Можно работать с шаблонами-строками, передавая их в функции модуля, либо предварительно компилировать шаблонную строку в специальный объект и работать с его методами, одноименными упомянутым функциям.

Virtuos86 ★★★★★ ()
Ответ на: комментарий от NeXTSTEP

Ждём compile-time регекспы на крестовых шаблонах.

зачем их ждать - есть уже boost xpressive, например

wota ★★ ()
Ответ на: комментарий от Virtuos86

Я не про питоновскую VM говорил, а про ту, что внутри сишного RE-движка сидит. Я никогда внурь не лез, но мне думается, что там должен быть компилятор в промежутчное представление и интерпретатор или jit-компилятор.

ozkriff ()
Ответ на: комментарий от Virtuos86

Судя по тому, что написано по первой ссылке, в Расте такая же схема, и никакого jit нет, обычная VM.

Судя по тому, что написано по первой ссылке, в Rust из регулярного выражения генерируется AST матчера, который компилируется в машинный код. Никакой VM.

tailgunner ★★★★★ ()
Ответ на: комментарий от tailgunner

Лучей добра тебе. Мне нравится, когда меня поправляют.

Virtuos86 ★★★★★ ()
Ответ на: комментарий от tailgunner

Судя по тому, что написано по первой ссылке, в Rust из регулярного выражения генерируется AST матчера, который компилируется в машинный код. Никакой VM.

Это когда у тебя есть строковый литерал известный во время компиляции. А если регулярное выражение задается во время выполнения, то там байткод и VM, макросы тут не помогут.

ozkriff ()
Ответ на: комментарий от Virtuos86

Ну, в конце концов, если очень нужны молниеносные регулярки в рантайме, то можно подключить сишную библиотеку.

ozkriff ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.