5

在使用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（匹配）
   652884 4.243 0.000 33.602 0.000 {“re2.Pattern”对象的“搜索”方法}
   652884 4.010 0.000 29.359 0.000 re2.pyx:442（搜索）
   652884 3.056 0.000 3.056 0.000 re2.pyx:114(__init__)
   652953 2.145 0.000 2.145 0.000 {实例}
   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 {内置方法子}
    10000 0.120 0.000 0.120 0.000 {“str”对象的“拆分”方法}
     8967 0.063 0.000 0.099 0.000 re2.pyx:801（获取）
    10069 0.061 0.000 0.061 0.000 {方法'str'对象的'strip'}
       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（加载）
       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（编译）
       38 0.001 0.000 0.001 0.000 {“文件”对象的“写入”方法}
       69 0.001 0.000 0.171 0.002 {re2.compile}
        1 0.001 0.001 42.669 42.669 export_plain.py:160（主要）
        3 0.000 0.000 0.000 0.000 {开}
       69 0.000 0.000 0.000 0.000 {“列表”对象的“附加”方法}
       19 0.000 0.000 0.000 0.000 {“str”对象的“join”方法}
        1 0.000 0.000 0.000 0.000 通用路径.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 {时间.时间}
        1 0.000 0.000 0.000 0.000 posixpath.py:59（加入）
        1 0.000 0.000 42.670 42.670 :1()
        1 0.000 0.000 0.000 0.000 {“unicode”对象的“编码”方法}
        3 0.000 0.000 0.000 0.000 {“str”对象的“rfind”方法}
        2 0.000 0.000 0.000 0.000 posixpath.py:109（基本名称）
        1 0.000 0.000 0.000 0.000 posixpath.py:117（目录名）
        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 {“列表”对象的“扩展”方法}
        1 0.000 0.000 0.000 0.000 {“str”对象的“startswith”方法}
        1 0.000 0.000 0.000 0.000 {“str”对象的方法“endswith”}
        1 0.000 0.000 0.000 0.000 stat.py:24(S_IFMT)
        1 0.000 0.000 0.000 0.000 {“文件”对象的方法“__enter__”}
        1 0.000 0.000 0.000 0.000 {方法'禁用''_lsprof.Profiler'对象}

看起来_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 ）重新配置它，然后得到：

2012 年 2 月 20 日星期一 20:52:47 Profile.prof

         3975043 次函数调用在 28.265 CPU 秒内

   排序：内部时间

   ncalls tottime percall cumtime percall filename:lineno(function)
   652884 10.060 0.000 20.230 0.000 re2.pyx:452（搜索）
   652884 4.131 0.000 28.201 0.000 {“re2.Pattern”对象的“搜索”方法}
   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（匹配）
   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 {内置方法子}
    10000 0.122 0.000 0.122 0.000 {“str”对象的“拆分”方法}
     8967 0.065 0.000 0.099 0.000 re2.pyx:849（获取）
    10069 0.064 0.000 0.064 0.000 {方法'str'对象的'strip'}
       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（主要）
        1 0.003 0.003 0.174 0.174 export_plain.py:36（加载）
       69 0.002 0.000 0.168 0.002 re2.pyx:811（编译）
       38 0.001 0.000 0.001 0.000 {“文件”对象的“写入”方法}
       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 {开}
        1 0.000 0.000 0.000 0.000 {“列表”对象的“扩展”方法}
       69 0.000 0.000 0.000 0.000 {实例}
       69 0.000 0.000 0.000 0.000 {“列表”对象的“附加”方法}
       19 0.000 0.000 0.000 0.000 {“str”对象的“join”方法}
        4 0.000 0.000 0.000 0.000 {时间.时间}
        1 0.000 0.000 0.000 0.000 {“unicode”对象的“编码”方法}
        1 0.000 0.000 0.000 0.000 posixpath.py:59（加入）
        1 0.000 0.000 0.000 0.000 {posix.stat}
        1 0.000 0.000 0.000 0.000 通用路径.py:38(isdir)
        2 0.000 0.000 0.000 0.000 posixpath.py:109（基本名称）
        3 0.000 0.000 0.000 0.000 {“str”对象的“rfind”方法}
        1 0.000 0.000 0.000 0.000 posixpath.py:117（目录名）
        1 0.000 0.000 0.000 0.000 stat.py:40(S_ISDIR)
        1 0.000 0.000 0.000 0.000 {“str”对象的“startswith”方法}
        1 0.000 0.000 0.000 0.000 {“str”对象的方法“endswith”}
        1 0.000 0.000 0.000 0.000 {“文件”对象的方法“__enter__”}
        1 0.000 0.000 0.000 0.000 stat.py:24(S_IFMT)
        1 0.000 0.000 0.000 0.000 {方法'禁用''_lsprof.Profiler'对象}

但是search仍然占用了很多时间（总共 10.060）。

任何人都可以弄清楚是什么问题？

4

1 回答 1

6

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

还有一件事要记住：

您是从facebook 存储库还是从python 包索引下载 pyre2 的？如果您从 python 包索引下载，如果它无法处理给定的正则表达式，它将回退到内置的 re 库（所以我想那里可能会有一些小的开销） - 无论如何，如果您匹配 pyre2 的正则表达式不支持，它会退回到 re 并且至少不会表现得更好。

因此，如果没有看到您的正则表达式，很难说，但我的猜测是 re2 由于以下原因之一而变慢：

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

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

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

于 2015-05-13T09:33:31.720 回答