C++ 向后正则表达式搜索

Question

我需要构建一个超高效的日志解析器 (~1GB/s)。我从 Intel 实现了 Hyperscan 库 ( https://www.hyperscan.io )，它适用于:

• 计算指定事件的发生次数
• 给出匹配的结束位置

其中一个限制是无法报告捕获组，只能报告结束偏移量。对于大多数匹配，我只使用计数，但对于其中 10% 的匹配，必须解析匹配以计算进一步的统计数据。

挑战在于高效运行正则表达式以获得 Hyperscan 匹配，只知道结束偏移量。目前，我尝试过:

string data(const string * block) const {
   std::regex nlexpr("\n(.*)\n$");
   std::smatch match;
   std::regex_search((*block).begin(), (*block).begin() + end, match, nlexpr);
   return match[1];
}

• block 指向内存中加载的文件(2GB，因此无法复制)。
• end 是与正则表达式匹配的已知偏移量。

但是当要匹配的字符串在 block 中很远时，它的效率非常低。我原以为“$”会使操作非常快，因为偏移量是作为结束位置给出的，但事实并非如此。如果 end = 100000000，操作需要 ~1s。

可以从 Hyperscan 开始匹配，但是对性能的影响非常大(测试后大约每 2 分之一)，因此这不是一个选项。

知道如何实现吗？我正在使用 C++ 11(因此 std 实现了 boost 正则表达式)。

最好的问候

编辑:由于问题出现在评论中，我无法控制要使用的正则表达式。

Answer 1

我没有足够的声誉来评论 XD。我不认为以下是答案，它更像是一个替代方案，但我必须做出一个答案，否则我无法联系到你。

我想您不会找到使性能独立于位置的技巧(猜猜对于这种简单的正则表达式或其他什么，它是线性的)。

一个非常简单的解决方案是用例如替换这个可怕的正则表达式库。 posix regex.h(旧但黄金；)或提升正则表达式。

这是一个例子:

#include <iostream>
#include <regex>
#include <regex.h>
#include <chrono>
#include <boost/regex.hpp>
inline auto now = std::chrono::steady_clock::now;
inline auto toMs = [](auto &&x){
    return std::chrono::duration_cast<std::chrono::milliseconds>(x).count();
};

void cregex(std::string const&s, std::string const&p)
{
    auto start = now();
    regex_t r;
    regcomp(&r,p.data(),REG_EXTENDED);
    std::vector<regmatch_t> m(r.re_nsub+1);
    regexec(&r,s.data(),m.size(),m.data(),0);
    regfree(&r);
    std::cout << toMs(now()-start) << "ms " << std::string{s.cbegin()+m[1].rm_so,s.cbegin()+m[1].rm_eo} << std::endl;
}

void cxxregex(std::string const&s, std::string const&p)
{
    using namespace std;
    auto start = now();
    regex r(p.data(),regex::extended);
    smatch m;
    regex_search(s.begin(),s.end(),m,r);
    std::cout << toMs(now()-start) << "ms " << m[1] << std::endl;
}
void boostregex(std::string const&s, std::string const&p)
{
    using namespace boost;
    auto start = now();
    regex r(p.data(),regex::extended);
    smatch m;
    regex_search(s.begin(),s.end(),m,r);
    std::cout << toMs(now()-start) << "ms " << m[1] << std::endl;
}

int main()
{
    std::string s(100000000,'x');
    std::string s1 = "yolo" + s;
    std::string s2 = s + "yolo";
    std::cout << "yolo + ... -> cregex "; cregex(s1,"^(yolo)");
    std::cout << "yolo + ... -> cxxregex "; cxxregex(s1,"^(yolo)");
    std::cout << "yolo + ... -> boostregex "; boostregex(s1,"^(yolo)");
    std::cout << "... + yolo -> cregex "; cregex(s2,"(yolo)$");
    std::cout << "... + yolo -> cxxregex "; cxxregex(s2,"(yolo)$");
    std::cout << "... + yolo -> boostregex "; boostregex(s2,"(yolo)$");
}

给予:

yolo + ... -> cregex 5ms yolo
yolo + ... -> cxxregex 0ms yolo
yolo + ... -> boostregex 0ms yolo
... + yolo -> cregex 69ms yolo
... + yolo -> cxxregex 2594ms yolo
... + yolo -> boostregex 62ms yolo