pyre2 медленнее, чем встроенный модуль re? - PullRequest
Новая
       4

pyre2 медленнее, чем встроенный модуль re?

3 голосов
/ 21 февраля 2012

При использовании pyre2 (https://github.com/axiak/pyre2), я столкнулся с проблемой производительности (время совпадения).

У меня есть три программы:

  1. чистый Pythonс использованием встроенного модуля re: https://gist.github.com/1873402

  2. Python с использованием Pyre2: https://gist.github.com/1873402. (Большая часть кода такая же, как у программы № 1. За исключением случаев использования встроенногоre, он будет декодировать строку utf-8 в unicode, что НЕ обязательно при использовании pyre2)

  3. C / C ++ с использованием re2: https://gist.github.com/1873417

Я измерил два времени: время предварительной компиляции регулярного выражения и время сопоставления.

  • № 1 программа: 1,65 с 1,25 с

  • № 2программа: 0,04 с 1,8 с

  • № 3 программа: 0,02 с 0,8 с

Все они подаются с одним и тем же регулярным выражением и входом. (Все регулярные выражения поддерживаются re2)

Затем я следовал документации по профилированию в Cython. Получил следующий результат: 

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   652884   16.477    0.000   25.349    0.000 re2.pyx:394(_search)
     9479    6.059    0.001   41.806    0.004 export_plain.py:60(match)
   652884    4.243    0.000   33.602    0.000 {method 'search' of 're2.Pattern' objects}
   652884    4.010    0.000   29.359    0.000 re2.pyx:442(search)
   652884    3.056    0.000    3.056    0.000 re2.pyx:114(__init__)
   652953    2.145    0.000    2.145    0.000 {isinstance}
   652884    2.002    0.000    2.002    0.000 re2.pyx:123(__dealloc__)
   652953    1.911    0.000    1.911    0.000 re2.pyx:75(unicode_to_bytestring)
   652953    1.902    0.000    1.902    0.000 re2.pyx:86(pystring_to_bytestring)
        1    0.330    0.330   42.492   42.492 export_plain.py:98(export_fname)
     9479    0.173    0.000    0.173    0.000 {built-in method sub}
    10000    0.120    0.000    0.120    0.000 {method 'split' of 'str' objects}
     8967    0.063    0.000    0.099    0.000 re2.pyx:801(get)
    10069    0.061    0.000    0.061    0.000 {method 'strip' of 'str' objects}
       69    0.043    0.001    0.146    0.002 re2.pyx:806(prepare_pattern)
     9036    0.038    0.000    0.038    0.000 re2.pyx:788(__next)
       69    0.022    0.000    0.169    0.002 re2.pyx:905(_compile)
        1    0.005    0.005    0.177    0.177 export_plain.py:36(load)
       69    0.002    0.000    0.003    0.000 re2.pyx:784(__init__)
       69    0.001    0.000    0.170    0.002 re2.pyx:763(compile)
       38    0.001    0.000    0.001    0.000 {method 'write' of 'file' objects}
       69    0.001    0.000    0.171    0.002 {re2.compile}
        1    0.001    0.001   42.669   42.669 export_plain.py:160(main)
        3    0.000    0.000    0.000    0.000 {open}
       69    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
       19    0.000    0.000    0.000    0.000 {method 'join' of 'str' objects}
        1    0.000    0.000    0.000    0.000 genericpath.py:38(isdir)
        1    0.000    0.000   42.669   42.669 export_plain.py:153(run_re2_test)
        1    0.000    0.000    0.000    0.000 {posix.stat}
        4    0.000    0.000    0.000    0.000 {time.time}
        1    0.000    0.000    0.000    0.000 posixpath.py:59(join)
        1    0.000    0.000   42.670   42.670 :1()
        1    0.000    0.000    0.000    0.000 {method 'encode' of 'unicode' objects}
        3    0.000    0.000    0.000    0.000 {method 'rfind' of 'str' objects}
        2    0.000    0.000    0.000    0.000 posixpath.py:109(basename)
        1    0.000    0.000    0.000    0.000 posixpath.py:117(dirname)
        1    0.000    0.000    0.000    0.000 stat.py:40(S_ISDIR)
        2    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'extend' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'startswith' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {method 'endswith' of 'str' objects}
        1    0.000    0.000    0.000    0.000 stat.py:24(S_IFMT)
        1    0.000    0.000    0.000    0.000 {method '__enter__' of 'file' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Похоже, что функция _search (re2.pyx: 393) занимать слишком много времени. Но я неКак это может отличаться между этой версией и чистой версией C.

PS: редакция Pyre2: фиксация 543f228

редакция re2: набор изменений: 79:0c439a6bd795

Полагаю, что действительная функция Match (re2.pyx: 424) в этой функции стоит большую часть времени.

Затем я реорганизую функцию Match в функцию cdef _my_match, чтобы я могла ее увидетьв результате в профиле также выполняется рефакторинг StringPiece присвоения функции cdef _alloc_sp.(Детали модификации: https://gist.github.com/1873993) Перепрофилируйте его, затем получите: 

Mon Feb 20 20:52:47 2012    Profile.prof

         3975043 function calls in 28.265 CPU seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   652884   10.060    0.000   20.230    0.000 re2.pyx:452(search)
   652884    4.131    0.000   28.201    0.000 {method 'search' of 're2.Pattern' objects}
   652884    3.647    0.000    3.647    0.000 re2.pyx:394(_my_match)
     9479    3.037    0.000   31.238    0.003 export_plain.py:62(match)
   652884    2.901    0.000    2.901    0.000 re2.pyx:443(_alloc_sp)
   652953    1.814    0.000    1.814    0.000 re2.pyx:86(pystring_to_bytestring)
   652953    1.808    0.000    1.808    0.000 re2.pyx:75(unicode_to_bytestring)
        1    0.332    0.332   31.926   31.926 export_plain.py:96(export_fname)
     9479    0.169    0.000    0.169    0.000 {built-in method sub}
    10000    0.122    0.000    0.122    0.000 {method 'split' of 'str' objects}
     8967    0.065    0.000    0.099    0.000 re2.pyx:849(get)
    10069    0.064    0.000    0.064    0.000 {method 'strip' of 'str' objects}
       69    0.042    0.001    0.142    0.002 re2.pyx:854(prepare_pattern)
     9036    0.035    0.000    0.035    0.000 re2.pyx:836(__next)
       69    0.023    0.000    0.166    0.002 re2.pyx:953(_compile)
        1    0.003    0.003   32.103   32.103 export_plain.py:158(main)
        1    0.003    0.003    0.174    0.174 export_plain.py:36(load)
       69    0.002    0.000    0.168    0.002 re2.pyx:811(compile)
       38    0.001    0.000    0.001    0.000 {method 'write' of 'file' objects}
       69    0.001    0.000    0.169    0.002 {re2.compile}
       69    0.001    0.000    0.001    0.000 re2.pyx:832(__init__)
        1    0.001    0.001   32.104   32.104 export_plain.py:151(run_re2_test)
        1    0.000    0.000   32.105   32.105 :1()
        2    0.000    0.000    0.000    0.000 {len}
        3    0.000    0.000    0.000    0.000 {open}
        1    0.000    0.000    0.000    0.000 {method 'extend' of 'list' objects}
       69    0.000    0.000    0.000    0.000 {isinstance}
       69    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
       19    0.000    0.000    0.000    0.000 {method 'join' of 'str' objects}
        4    0.000    0.000    0.000    0.000 {time.time}
        1    0.000    0.000    0.000    0.000 {method 'encode' of 'unicode' objects}
        1    0.000    0.000    0.000    0.000 posixpath.py:59(join)
        1    0.000    0.000    0.000    0.000 {posix.stat}
        1    0.000    0.000    0.000    0.000 genericpath.py:38(isdir)
        2    0.000    0.000    0.000    0.000 posixpath.py:109(basename)
        3    0.000    0.000    0.000    0.000 {method 'rfind' of 'str' objects}
        1    0.000    0.000    0.000    0.000 posixpath.py:117(dirname)
        1    0.000    0.000    0.000    0.000 stat.py:40(S_ISDIR)
        1    0.000    0.000    0.000    0.000 {method 'startswith' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {method 'endswith' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {method '__enter__' of 'file' objects}
        1    0.000    0.000    0.000    0.000 stat.py:24(S_IFMT)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Но search все еще занимает так много времени (10,060 всего).

Любойможете разобраться в чем проблема?

1 Ответ

4 голосов
/ 13 мая 2015

Ну, это зависит ... pyre2 асимптотически быстрее, но не обязательно быстрее для каждого конкретного регулярного выражения. Причина в том, что re2 генерирует NFA и обходит все активные состояния одновременно. re (если я прав) пробует только один путь в NFA за раз, и если он терпит неудачу, он возвращается и пробует другой. Это означает, что re может выполнять всякие причудливые вещи, такие как lookaheads и т. Д., Поскольку он всегда запоминает путь, соответствующий данной строке, а re2 запоминает только текущие активные состояния. Это означает, что re2 скажет вам, соответствует ли строка регулярному выражению или нет, но он не сможет выполнить все необычные вычисления, которые вы можете сделать с группами, используя re. Как следствие, pyre2 имеет линейную асимптотическую сложность по времени (за счет отсутствия поддержки некоторого синтаксиса встроенного re), тогда как re имеет экспоненциальную асимптотическую сложность. Однако это не означает, что для простых простых регулярных выражений pyre2 должен работать лучше.

Еще одна вещь, которую нужно иметь в виду:

Вы загружали pyre2 из репозитория facebook или из индекса пакета python ? Если вы загрузили из индекса пакета python, он откатится к встроенной библиотеке re, если не сможет обработать заданное регулярное выражение (поэтому я предполагаю, что там могут быть небольшие издержки) - в любом случае, если вы сопоставляете регулярные выражения с pyre2 не поддерживает, он откатится к ре и по крайней мере не будет работать лучше.

Так что, не видя ваших регулярных выражений, трудно сказать, но я предполагаю, что re2 работает медленнее по одной из следующих причин:

  • либо ваши регулярные выражения и строки, с которыми вы сопоставляете их, очень просты (в этом случае использование re2 не дает никаких преимуществ)

  • или вы загрузили pyre2 из pypi, и вы захватываете группы и используете lookaheads, которые re2 не поддерживает и возвращается к re)

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

...