C++ vs .NET正则表达式性能

Question

在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,并使用正则表达式将字符串并行拆分四次,返回拆分字符串长度的总和(in为了避免分配).

在面向64位的发布版本中,在Visual Studio(为MP和OpenMP启用C++)中运行,C++需要43.5秒,而F#需要3.28秒(超过13倍).这并不让我感到惊讶,因为我相信.NET JIT将正则表达式编译为本机代码,而C++ stdlib解释它但我想要一些同行评审.

我的C++代码中是否存在perf错误,或者这是编译与解释正则表达式的结果？

编辑: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倍).

Answer 1

这些基准测试并不具有可比性--C++和.NET实现了完全不同的正则表达式语言(ECMAScript与Perl),并且由完全不同的正则表达式引擎提供支持..NET(据我所知)受益于GRETA项目,它产生了一个绝对精彩的正则表达式引擎,已经过多年的调整.std::regex相比之下,C++ 是最近添加的(至少在MSVC++上,我假设你使用非标准类型__int64和朋友).

你可以看到GRETA是如何做到与更成熟的std::regex实施boost::regex,这里(尽管测试在Visual Studio 2003中进行).

您还应该记住,正则表达式性能高度依赖于源字符串和正则表达式.一些正则表达式引擎花费大量时间解析正则表达式以更快地通过更多源文本; 只有在解析大量文本时才有意义的权衡.一些正则表达式引擎折衷扫描速度以使得匹配相对昂贵(因此匹配的数量会产生影响).这里有大量的权衡; 一对输入确实会让故事黯然失色.

所以更明确地回答你的问题:这种变化在正则表达式引擎中是正常的,无论是编译还是解释.看看上面的boost测试,通常最快和最慢的实现之间的差异是数百倍的不同 - 根据您的使用情况,17x并不是那么奇怪.