python - Pyre2 比内置 re 模块慢？

Question

使用 pyre2 ( https://github.com/axiak/pyre2 ) 时，我遇到了性能问题(匹配时间)。

我有三个程序:

1. 使用内置 re 模块的纯 Python:https://gist.github.com/1873402

2. 使用 Pyre2 的 Python:https://gist.github.com/1873402 。 (大部分代码与no.1程序相同。除了使用内置re时，它将把utf-8字符串解码为unicode，这在使用pyre2时不需要)

3. 使用 re2 的 C/C++:https://gist.github.com/1873417

我测量了两次:正则表达式预编译时间和匹配时间。

• 1号节目:1.65s 1.25s

• 2号程序:0.04s 1.8s

• 3号程序:0.02s 0.8s

它们都由相同的正则表达式和输入提供。 (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}

但是搜索仍然占用很多时间(总计 10.060)。

谁能找出问题所在吗？

Answer 1

嗯，这取决于...pyre2 渐近更快，但对于每个特定正则表达式不一定更快。原因是 re2 生成 NFA 并同时在所有事件状态上行走。 re(如果我是对的)一次只尝试 NFA 中的一条路径，如果失败，它会回溯并尝试另一条路径。这意味着 re 可以做各种奇特的事情，比如前瞻等，因为它总是记住与给定字符串匹配的路径，而 re2 只记住当前的事件状态。这意味着 re2 会告诉您字符串是否与正则表达式匹配，但它无法执行您可以使用 re 对组执行的所有奇特计算。因此，pyre2 具有线性渐近时间复杂度(以不支持内置 re 的某些语法为代价)，而 re 具有指数渐近复杂度。然而，这并不意味着对于基本的简单正则表达式，pyre2 必须表现得更好。

还有一点要记住:

您是否从facebook repository下载了pyre2？或来自python package index ？如果你从 python 包索引下载，如果它无法处理给定的正则表达式，它将回退到内置的 re 库(所以我想那里可能会有一些小的开销) - 无论如何，如果你匹配的正则表达式是pyre2不支持，它将回退到重新，并且至少不会表现得更好。

因此，如果没有看到您的正则表达式，很难说，但我猜测 re2 速度较慢，原因之一是:

• 您的正则表达式和与之匹配的字符串都非常简单(在这种情况下，使用 re2 没有任何优势)

• 或者您从 pypi 下载了pyre2，并且您正在捕获组并使用前瞻，而 re2 不支持它，因此它会回退到 re)

由于您设法在 C re2 库中编译相同的正则表达式，我猜这是第一个原因，而不是第二个。