Проект Google Re2 (C++) — успешная попытка [вос]создать промышленный regex движок, свободный от экспоненциальной зависимости от входных данных. Этот проект, выполненный Рассом Коксом (Russ Cox), дал возможность гуглу эффективно выполнять поиск по регулярным выражениям в программном коде, найденном гуглом в интернете...
В сентябре 2010 мир пополнится ещё одним таким must-read ресурсом по регулярным выражениям. Пьеса (!) A Play on Regular Expressions (http://sebfisch.github.com/haskell-regexp/regexp-play.pdf) (via antilamer) описывает создание ленивого, чисто функционального алгоритма, основывающегося на всё том же подходе превращения регулярки в конечный автомат. Описанный в статье алгоритм позволяет строить матчер выражений, поддерживающий любые контекстно-свободные (sic!!) грамматики.
Алгоритм, и соответствующая ему имплементация, Weighted RegExp Matching на простых выражениях обычно медленнее, чем другие библиотеки типа pcre, но у неё асимптотически лучшее поведение: O(nm) от длины входных данных и размера выражения. Пользуясь ленивостью, на некоторых бенчмарках (.*a.{20}a.*) эта Haskell-имплементация обгоняет Re2, описанный выше, по абсолютному времени выполнения.
Самое интересное, что тот же алгоритм был написан ещё и на C++ и Java, и на Java получился в два раза быстрее, несмотря на то, что алгоритм очень хорошо ложится на ОО, и может быть переносим между ОО-языками без особых изменений:
Implementation язык chars/s speedup over pure Python
Pure Python code Python 12'200 1
Python re module C 2'500'000 205
Google's re2 implementation C++ 550'000 45
RPython implementation
translated to C Python 720'000 59
C++ implementation C++ 750'000 61
Java implementation Java 1'920'000 157
RPython implementation
with JIT Python 16'500'000 1352
Это, в частности, подтверждает тезис о том, что C++ не нужен: современные языки с GC и JIT просто уделывают его на традиционных для C/C++ задачах.
Комментарии по ссылке тоже рулят, но, просьба, не набегать туда, а ограничиться КСВ
Здравствуйте, Mamut, Вы писали: M>Это, в частности, подтверждает тезис о том, что C++ не нужен: современные языки с GC и JIT просто уделывают его на традиционных для C/C++ задачах.
Я так понимаю, у pypy регекспы поддерживаются jit-ом, т.е. конпелируются в машинный код. Наверняка что-то подобное сделано в жаве. А имплементация гугла на плюсах — это интерпретатор. Конпеляция в очередной раз победила интерпретацию. Ура-ура.
Просто подтверждает, что для написания быстрых программ на C++ нужен IQ выше среднего, не более того.
Если есть быстрая реализация на C, ВСЕГДА можно создать эквивалентную по производительности на С++. Если авторы этого делать не стали и поюзали std::string, исключения и т.п. где надо и где не надо, это их проблемы...
Здравствуйте, Mr.Cat, Вы писали:
MC>Здравствуйте, Mamut, Вы писали: M>>Это, в частности, подтверждает тезис о том, что C++ не нужен: современные языки с GC и JIT просто уделывают его на традиционных для C/C++ задачах. MC>Я так понимаю, у pypy регекспы поддерживаются jit-ом, т.е. конпелируются в машинный код. Наверняка что-то подобное сделано в жаве. А имплементация гугла на плюсах — это интерпретатор. Конпеляция в очередной раз победила интерпретацию. Ура-ура.
MC>Ах, да. Плюсы, GC, КСВ при чем тут они?
Да все притом. Подход с компиляцией регэкспов в машинный код на С++ невозможен (или очень проблематичен).
Здравствуйте, gandjustas, Вы писали:
MC>>Ах, да. Плюсы, GC, КСВ при чем тут они? G>Да все притом. Подход с компиляцией регэкспов в машинный код на С++ невозможен (или очень проблематичен).
LLVM
Было бы интересно сделать на ней генерацию конечного автомата и посмотреть что получится.
Здравствуйте, gandjustas, Вы писали: G>Да все притом. Подход с компиляцией регэкспов в машинный код на С++ невозможен (или очень проблематичен).
Логично, что управляемым средам проще — они юзают уже присутствующий в них джит. Но есть же либы для джиттинга. Gnu Lightning например (не юзал).
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, gandjustas, Вы писали:
MC>>>Ах, да. Плюсы, GC, КСВ при чем тут они? G>>Да все притом. Подход с компиляцией регэкспов в машинный код на С++ невозможен (или очень проблематичен). C>LLVM
C>Было бы интересно сделать на ней генерацию конечного автомата и посмотреть что получится.
Кстати как у LLVM с runtime кодогенерацией? И как это можно использовать на C++?
Здравствуйте, gandjustas, Вы писали:
G>Подход с компиляцией регэкспов в машинный код на С++ невозможен (или очень проблематичен).
С какого перепугу то?
Если компиляция в байт код возможна то почему вдруг невозможно сгенерить машинный код?
Это будет банальный JIT.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Здравствуйте, gandjustas, Вы писали:
G>Кстати как у LLVM с runtime кодогенерацией? И как это можно использовать на C++?
Давай-ка зададим наводящий вопрос: на каком языке написан JIT для C#/Java?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, gandjustas, Вы писали:
G>>Подход с компиляцией регэкспов в машинный код на С++ невозможен (или очень проблематичен). CC>С какого перепугу то? CC>Если компиляция в байт код возможна то почему вдруг невозможно сгенерить машинный код? CC>Это будет банальный JIT.
Ну так напиши.
Говорить можно что угодно, а JIT для С++ пока еще никто не изобрел.
Здравствуйте, gandjustas, Вы писали:
G>>>Подход с компиляцией регэкспов в машинный код на С++ невозможен (или очень проблематичен). CC>>С какого перепугу то? CC>>Если компиляция в байт код возможна то почему вдруг невозможно сгенерить машинный код? CC>>Это будет банальный JIT. G>Ну так напиши. G>Говорить можно что угодно, а JIT для С++ пока еще никто не изобрел.
А нам и не надо JIT для компилируемого языка. Нам надо JIT для байт кода, который сгенерит regex по строке паттерна.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, gandjustas, Вы писали:
G>>Кстати как у LLVM с runtime кодогенерацией? И как это можно использовать на C++? CC>Давай-ка зададим наводящий вопрос: на каком языке написан JIT для C#/Java?
Для C# на Lisp с последующей трансляцией в C++. На java — понятия не имею.
Но вопрос был в том как использовать в C++ результаты runtime кодогенерации, с помощью того же LLVM
Здравствуйте, gandjustas, Вы писали:
C>>LLVM C>>Было бы интересно сделать на ней генерацию конечного автомата и посмотреть что получится. G>Кстати как у LLVM с runtime кодогенерацией? И как это можно использовать на C++?
Умм... LLVM — это фреймворк для кодогенерации, в том числе и runtime. И оно как бы на С++ написано и прекрасно с ним интерфейсится.
Здравствуйте, gandjustas, Вы писали:
G>>>Кстати как у LLVM с runtime кодогенерацией? И как это можно использовать на C++? CC>>Давай-ка зададим наводящий вопрос: на каком языке написан JIT для C#/Java? G>Для C# на Lisp с последующей трансляцией в C++.
Какой изврат! А что ж сразу на С++ ниасилили? Если странслировать оказалось возможно то и руками написать не проблема.
G>Но вопрос был в том как использовать в C++ результаты runtime кодогенерации, с помощью того же LLVM
Используя VirtualAlloc c PAGE_EXECUTE_READWRITE + переход туда по указателю (aka function pointer)
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, gandjustas, Вы писали:
G>>>>Подход с компиляцией регэкспов в машинный код на С++ невозможен (или очень проблематичен). CC>>>С какого перепугу то? CC>>>Если компиляция в байт код возможна то почему вдруг невозможно сгенерить машинный код? CC>>>Это будет банальный JIT. G>>Ну так напиши. G>>Говорить можно что угодно, а JIT для С++ пока еще никто не изобрел. CC>А нам и не надо JIT для компилируемого языка. Нам надо JIT для байт кода, который сгенерит regex по строке паттерна.
Да пофигу. Даже гугл неспособен такое сделать, не надо мне доказывать что это несложная задача.
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, gandjustas, Вы писали:
C>>>LLVM C>>>Было бы интересно сделать на ней генерацию конечного автомата и посмотреть что получится. G>>Кстати как у LLVM с runtime кодогенерацией? И как это можно использовать на C++? C>Умм... LLVM — это фреймворк для кодогенерации, в том числе и runtime.
Спасибо, КО.
C>И оно как бы на С++ написано и прекрасно с ним интерфейсится.
Не все что написано на С++ прекрасно с ним интерфейсится.
Хотелось бы на примеры такого посмотреть.
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, gandjustas, Вы писали:
G>>>>Кстати как у LLVM с runtime кодогенерацией? И как это можно использовать на C++? CC>>>Давай-ка зададим наводящий вопрос: на каком языке написан JIT для C#/Java? G>>Для C# на Lisp с последующей трансляцией в C++. CC>Какой изврат!
Нормальная практика создания рабочего прототипа на высокоуровневом языке. А lisp бы выбран просто потому что так захотелось автору.
CC>А что ж сразу на С++ ниасилили? Если странслировать оказалось возможно то и руками написать не проблема.
Наверное если бы сразу стали писать на С++, то .NET появился бы на пару лет позже
