Слышал много раз, что в cl регекспы hardly rocks по скорости (вроде бы что-то о метакомпиляции из шаблона). Сегодня с преподом завязалась дискуссия по поводу "компиляция `на-лету` не нужна". Я в качестве примера почему-то забыл привести слайсер карт, но сказал о общем абстрактном классе задач с обработкой данных по-шаблону, и как пример, попытался привести cl-ppcre, но зафейлил - убедительности не хватило. У меня доводы были, что один раз скомпилировать шаблон и сто раз использовать быстрее, чем сто раз интерпретировать, но препод грит, что gcc/g++ со своими pcre там всё смемоизируют, еще как-нибудь соптимизируют и будут быстрее, а мои доводы - религиозный фанатизм. Хочу провести бенчмарк, но не уверен, что знаю, как правильно готовить cl-ppcre. Более того, я даже не нашел, где там компиляция шаблона. create-scanner - это она и есть? Дизассембл у простенького "a*b" - "война и мир". Посоветуйте, пожалста, чего, чтобы хорошенько обогнать c/cpp lib-pcre :)

> но препод грит, что gcc/g++ со своими pcre там всё смемоизируют, еще как-нибудь соптимизируют> и будут быстрее, а мои доводы - религиозный фанатизм
И скорее всего он прав ;)
> "компиляция `на-лету` не нужна".
Прежде всего она нужна для удобства разработки, не для скорости.

Здесь есть сравнительный benchmark cl-ppcre против Perl
А уж Perl заоптимизирован не меньше, чем PCRE
Результаты многх тестов  в разы луше у CL-PPCRE

> Прежде всего она нужна для удобства разработки
Согласен, это надо было в первую очередь сказать :(
> И скорее всего он прав ;)
Ну смотри, допустим есть шаблон "(a|b)+s?", если метапрограммировать, то получится
string match-my-regex (string input)
{
string result;
while ( ! end-of-string (input) )
{
while ( first (input) == 'a'
|| first (input) == 'b')
{
result += first (input);
++ input;
}
if ( result . size != 0
&& first (input) == 's')
{
return (result += 's');
}
else
{
++ input;
result . clear ();
}
}
return result;
}
Если же статика, то нужен как минимум лексический анализ шаблона, state-машина etc :
string match-regex (string pattern, string input)
{
list <token> tokens
= regexLexer . getTokens ();
string result;
byte state;
while ( ! end-of-string (input) )
{
switch (state) ...
if ( is_letter (token) )
...
else if ...
...
else switch (token)
{
case '+':
...
case '*':
...
...
}
...
}
return result;
}
Если первый пример - полное решение на псевдокоде, то во втором всё очень схематично и компактно, на самом деле там будет дофигища логики, переменных, проверок, джампов и т.д.

Ещё тут есть бенчмарк. Но там уже немного другие результаты.
"Компиляция на лету" может позволить превратить строку (char*) шаблона в какую-либо другую структуру (вложенные списки, выражающие собой семантику шаблона) для которой алгоритмы могут быть гораздо эффективнее чем для исходного строкового шаблона.

> "Компиляция на лету" может позволить превратить строку (char*) шаблона в какую-либо другую структуру
Да это и без неё можно сделать. Профит в том, чтобы вообще избавиться от шаблона. Один раз по нему сгенерить if'ы, кейсы и прочий код, его скомпилить, и юзать.
> Ещё тут есть бенчмарк
Спасибо, отлично  - это как-раз то, что мне нужно. И как раз так, как я это себе представлял :)

> Но там уже немного другие результаты.
Кажется, что здесь некорректно измеряли:
тест прокручивали всего по 1000 раз, при этом для CL-PPCRE включалось время компиляции, которое и занимало большую часть времени.

>> Профит в том, чтобы вообще избавиться от шаблона. Один раз по нему сгенерить if'ы, кейсы и прочий код, его скомпилить, и юзать.
Генерировать (макросом-транслятором?) из шаблона функцию (в случае SBCL - машинный код), воплощающую собой механизм матчинга именно с этим шаблоном, и принимающую на вход строку претендент?

И в CL-PPCRE и в той библиотеке, как я понял, включалось время компиляции в бенчмарк. Т.е. полное время. В случае если сначала (и там и там) скомпилировать шаблон и мерить время, то это будет уже другой бенчмарк именно для cl-ppcre и той библиотеки, т.к. остальные варианты не позволяют использовать компиляцию шаблона.

В остальных вариантах: Perl, Ruby, Python  шаблон тоже всегда компилируется в некий, при загрузке исходника. При этом время компиля

В остальных вариантах: Perl, Ruby, Python  шаблон тоже всегда компилируется в некий байт-код, при загрузке исходника. При этом время компиляции незначительное по сравнению с CL-PPCRE, так как язык regex узкоспециализированый.

Да, именно так. Первый псевдокод в >>3594 - это как-раз пример полученной по шаблону функции. Схема такая: шаблон -> транслятор -> код -> компилятор -> машинный код.
@ _lee, таки да, scan'ят без заранее подготовленного scanner'а:
;; cl-ppcre
(defun find-it (buf)
  (declare (optimize speed))
  (cl-ppcre:scan "indecipherable|undecipherable" buf))
(let ((buf (slurp-file "test-data")))
  (let ((len (find-it buf)))
    (let ((start (get-internal-real-time)))
      (loop repeat 1000 do
            (assert (= len (find-it buf))))
      (let ((end (get-internal-real-time)))
        (format t "~A ~$~&" len (/ (- end start) internal-time-units-per-second))))))
;; cl-irregsexp
(defun find-it (buf)
  (declare (optimize speed))
  (cl-irregsexp:match-bind (before (or "indecipherable" "undecipherable"))
      buf
    (length before)))
(let ((buf (slurp-file "test-data")))
  (let ((len (find-it buf)))
    (let ((start (get-internal-real-time)))
      (loop repeat 1000 do
            (assert (= len (find-it buf))))
      (let ((end (get-internal-real-time)))
        (format t "~A ~$~&" len (/ (- end start) internal-time-units-per-second))))))
Но как видно, в тесте с cl-irregsexp тоже ничего заранее не готовят, и тоже каждый раз компилится, так что всё объективно.

только там ошибочка - '?' убрать из шаблона.

match-bind оказался макросом, раскрывающимся в макрос, компилирующий регексп и замыкающий тело относительно скомпиленного результата. Так что я решил сделать пообъективнее бенч и вот результаты:
(defpackage :ppcre-vs-irregsexp
  (:use :cl
        :cl-ppcre
        :cl-irregsexp))
        
(in-package :ppcre-vs-irregsexp)
(defvar *ppcre-scanner* (create-scanner "a+(\\S+)b"))
(time
  (dotimes (_ 100000000)
    (scan-to-strings *ppcre-scanner* "xaaaa77bd")))
    
Evaluation took:
 393.167 seconds of real time
 392.810517 seconds of total run time (391.780911 user, 1.029606 system)
 [ Run times consist of 4.622 seconds GC time, and 388.189 seconds non-GC time. ]
 99.91% CPU
 836,615,161,054 processor cycles
 28,000,274,192 bytes consed    
       
(time
  (dotimes (_ 100000000)
    (match-bind (_ (+ "a") result "b")
          "xaaaa77bd"
      result)))
      
Evaluation took:
 50.606 seconds of real time
 50.606724 seconds of total run time (50.372723 user, 0.234001 system)
 [ Run times consist of 1.656 seconds GC time, and 48.951 seconds non-GC time. ]
 100.00% CPU
 107,671,584,766 processor cycles
 9,600,109,512 bytes consed
Так что здесь выгода от on-fly вполне неиллюзорна. Кроме того, этот cl-irregsexp выглядит очень прототипно - мне кажется, там можно еще много соптимизировать.