C++与.NET正则表达式性能比较

Question

C++与.NET正则表达式性能比较

4

受Konrad Rudolph在相关问题的评论的启发，我编写了以下程序来测试F#中正则表达式的性能：

open System.Text.RegularExpressions
let str = System.IO.File.ReadAllText "C:\\Users\\Jon\\Documents\\pg10.txt"
let re = System.IO.File.ReadAllText "C:\\Users\\Jon\\Documents\\re.txt"
for _ in 1..3 do
  let timer = System.Diagnostics.Stopwatch.StartNew()
  let re = Regex(re, RegexOptions.Compiled)
  let res = Array.Parallel.init 4 (fun _ -> re.Split str |> Seq.sumBy (fun m -> m.Length))
  printfn "%A %fs" res timer.Elapsed.TotalSeconds

以及在C++中的等价代码：

#include "stdafx.h"

#include <windows.h>
#include <regex>
#include <vector>
#include <string>
#include <fstream>
#include <cstdio>
#include <codecvt>

using namespace std;

wstring load(wstring filename) {
    const locale empty_locale = locale::empty();
    typedef codecvt_utf8<wchar_t> converter_type;
    const converter_type* converter = new converter_type;
    const locale utf8_locale = locale(empty_locale, converter);
    wifstream in(filename);
    wstring contents;
    if (in)
    {
        in.seekg(0, ios::end);
        contents.resize(in.tellg());
        in.seekg(0, ios::beg);
        in.read(&contents[0], contents.size());
        in.close();
    }
    return(contents);
}

int count(const wstring &re, const wstring &s){
    static const wregex rsplit(re);
    auto rit = wsregex_token_iterator(s.begin(), s.end(), rsplit, -1);
    auto rend = wsregex_token_iterator();
    int count=0;
    for (auto it=rit; it!=rend; ++it)
        count += it->length();
    return count;
}

int _tmain(int argc, _TCHAR* argv[])
{
    wstring str = load(L"pg10.txt");
    wstring re = load(L"re.txt");

    __int64 freq, tStart, tStop;
    unsigned long TimeDiff;
    QueryPerformanceFrequency((LARGE_INTEGER *)&freq);
    QueryPerformanceCounter((LARGE_INTEGER *)&tStart);

    vector<int> res(4);

#pragma omp parallel num_threads(4)
    for(auto i=0; i<res.size(); ++i)
        res[i] = count(re, str);

    QueryPerformanceCounter((LARGE_INTEGER *)&tStop);
    TimeDiff = (unsigned long)(((tStop - tStart) * 1000000) / freq);
    printf("(%d, %d, %d, %d) %fs\n", res[0], res[1], res[2], res[3], TimeDiff/1e6);
    return 0;
}

两个程序都以Unicode字符串形式加载两个文件（我使用的是《圣经》副本），构建一个非平凡的Unicode正则表达式\w?\w?\w?\w?\w?\w并使用该正则表达式四次并行分裂字符串，返回分割字符串长度之和（以避免分配）。

在针对64位目标的发行版中，通过Visual Studio（启用了C++的MP和OpenMP），C++花费了43.5秒，而F#只需3.28秒（快了13倍以上）。这并不让我感到惊讶，因为我认为.NET JIT将正则表达式编译为本地代码，而C++ stdlib则解释它，但我需要一些同行评审。

我的C++代码是否存在性能问题，还是这是编译与解释正则表达式的后果？

编辑：Billy ONeal指出.NET可能对\w有不同的解释，因此我已在新的正则表达式中明确说明。

[0-9A-Za-z_]?[0-9A-Za-z_]?[0-9A-Za-z_]?[0-9A-Za-z_]?[0-9A-Za-z_]?[0-9A-Za-z_]

这实际上使得.NET代码（C++同样如此）大幅加速，将F#的时间从3.28秒缩短至2.38秒（快了17倍以上）。

- J D

2

如果你想要出色的正则表达式性能，使用Perl吧 ;) - paulsm4

你使用的工具集和标准库是什么？ - Mgetz

1

就我而言，这并不让我感到惊讶。除了对编译的担忧之外，C++中的正则表达式库简直令人发指 - 我们经常在C++聊天中谈论它。话虽如此，为了使代码更具可比性，我会删除并行处理...虽然我并不指望会有太大的改变。 - Konrad Rudolph

1

@Ben 公平地说，（相关部分的）Boost.Xpressive 仅限于编译时创建的正则表达式。这可能不是Jon想要比较的内容。 - Konrad Rudolph

1

你的问题让我想要学习函数式编程。 - Nils

显示剩余7条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Billy ONeal · Accepted Answer

这些基准测试并不真正可比——C++和.NET实现完全不同的正则表达式语言（ECMAScript vs. Perl），并由完全不同的正则表达式引擎驱动。在这里，.NET（据我所知）受益于GRETA项目，该项目产生了一款经过多年调整的绝对精彩的正则表达式引擎。相比之下，C++的std::regex是最近添加的（至少在MSVC++上是这样，在此假设您使用的是非标准类型__int64及其朋友们）。

您可以在这里看到GRETA与更成熟的std::regex实现boost::regex的性能比较（尽管该测试是在Visual Studio 2003上完成的）。

您还应该记住，正则表达式的性能高度依赖于源字符串和正则表达式本身。有些正则表达式引擎花费大量时间解析正则表达式以更快地处理更多源文本；这种权衡只有在解析大量文本时才有意义。有些正则表达式引擎通过牺牲扫描速度来使匹配相对昂贵（因此匹配次数会产生影响）。这里有巨大的权衡；一对输入确实会模糊故事情节。

因此，更明确地回答您的问题：这种变化在编译或解释的正则表达式引擎中都是正常的。从上面的boost测试结果来看，最快和最慢实现之间的差异通常相差几百倍——根据您的用例，17倍并不奇怪。