正規表現ライブラリの機能比較とベンチマーク

Question

テーマ、知りたいこと

C++で使えるUnicode対応した正規表現ライブラリでこれいいよ！みたいなのとか、いいベンチマークを知ってる人がいたら教えてください。

背景、状況

なんとなく普段何気なく使っている正規表現って実は遅いのでは？と思って気になって調べてみました。
以下はLF(\n)、半角空白、全角空白の3文字を消すというだけの処理をpythonでreplaceを3つ並べたものと、正規表現で実施したものを比較しています。

class SubRepl:
    def __init__(self, callback):
        self.found = False
        self.callback = callback
    def get_callback(self):
        def real_callback(m):
            self.found = True
            return self.callback(m)
        return real_callback

import re
repl = SubRepl(lambda m: '')
regex = re.compile('[\n 　]')
callback = repl.get_callback()

def hoge_normal(str):
    return str.replace('\n','').replace(' ', '').replace('　', '')
def hoge_regexp(str):
    return regex.sub('', str)
def hoge_regexp2(str):
    return regex.sub(callback, str)

import timeit
print(timeit.timeit(lambda: hoge_normal('hoge\nfuga\npiyo')))
print(timeit.timeit(lambda: hoge_regexp('hoge\nfuga\npiyo')))
print(timeit.timeit(lambda: hoge_regexp2('hoge\nfuga\npiyo')))

# 出力例)
# 0.36671502102399245
# 0.8715399430366233
# 1.347482957993634

hoge_regexp2はsubのrepl部分に関数を使ってさらに重たくなっちゃってますが(マッチしたのかどうかを判定するため。これの速度影響を調べようとしたのが事の発端)、問題は最初の2つの比較で、正規表現思ったより遅いなという印象でした。パターンマッチする文字列の数が多くなるほど正規表現の方が有利なのは分かるのですが、ではどれくらいの数だとどちらがどの程度速い/遅いのかはちょっと気になります。

ただ、pythonでやってたのではよく分からないので、C++でやるとどうなるのか？を見てみたのです。こちらはさらに厄介で、C++標準の正規表現std::regexがstd::wstringでしかunicode対応できないと分かり、じゃあ遅いのを我慢してstd::stringを都度std::wstringにしようかと考えたら<codecvt>がC++17で非推奨になってて詰んでました。std::stringをutf-8に限定し、utf-8<->utf16(be/le)/utf-8<->utf32(be/le)だけどっかから拾ってくれば比較的プラットフォーム依存を抑えて実装出来そうですが、もう後回しにして、utf-8を直接扱える正規表現ライブラリ
を探すことにしてみました。

調べたところ、

• pcre2
• re2
• boost::regex/xpressive

あたりが使えそうでした。とりあえずうちの環境でインストールせずに使えそうな、pcre2を使ってみたところ、

#include <iostream>
#include <chrono>
#include <string>
#include <array>
#include <vector>
#include <sstream>

#define PCRE2_CODE_UNIT_WIDTH 8
#include <pcre2.h>

using namespace std;
using namespace chrono;

template<typename Func>
auto measure(Func func, size_t count = 1000000) {
    auto begin = high_resolution_clock::now();
    for (;count > 0; --count) func();
    auto end = high_resolution_clock::now();
    return duration_cast<milliseconds>(end - begin).count();
}

string replace_normal(const string& str) {
    static const array<string, 3> search_strings{"\n", " ", "　"};
    string result(str);
    for (const auto& s: search_strings) {
        string::size_type idx = 0;
        string::size_type pos = 0;
        while (idx != string::npos) {
            idx = result.find(s, pos);
            if (idx != string::npos) {
                result.erase(idx, s.length());
                pos = idx;
            }
        }
    }
    return result;
}

struct pcre2_wrap {
    int errorcode = 0;
    string errormessage;
    PCRE2_SIZE erroroffset = 0;
    pcre2_code* re = NULL;
    pcre2_match_data *match_data = NULL;
    int rc = 0;

    bool compile(const string& pattern, uint32_t option) {
        re = pcre2_compile(reinterpret_cast<const unsigned char*>(pattern.c_str()), pattern.length(), option, &errorcode, &erroroffset, NULL);
        if (re == NULL) {
            vector<PCRE2_UCHAR> buffer(256);
            pcre2_get_error_message(errorcode, buffer.data(), buffer.size());
            ostringstream sstream;
            sstream << "コンパイル失敗。オフセットは" << static_cast<int>(erroroffset) << ": " << reinterpret_cast<const char*>(buffer.data()) << "です。" << endl;
            errormessage = sstream.str();
        } else {
            match_data = pcre2_match_data_create_from_pattern(re, NULL);
        }
        return re != NULL;
    }
    bool match(const string& str, PCRE2_SIZE pos) {
        rc = pcre2_match(re, reinterpret_cast<const unsigned char*>(str.c_str()), str.length(), pos, 0, match_data, NULL);
        return rc >= 0;
    }
    pcre2_wrap() {}
    pcre2_wrap(const string& pattern, uint32_t option) {compile(pattern, option);}
    ~pcre2_wrap() {
        pcre2_match_data_free(match_data);
        match_data = NULL;
        pcre2_code_free(re);
        re = NULL;
    }
};

string replace_regexp(const string& str) {
    static pcre2_wrap re("[\n 　]", 0);
    string result = str;
    PCRE2_SIZE pos = 0;
    while (re.match(result, pos)) {
        PCRE2_SIZE *ovector = pcre2_get_ovector_pointer(re.match_data);
        //cout << "Match succeeded at offset " << (int)ovector[0] << '-' << (int)ovector[1] << endl;
        result.erase(ovector[0], ovector[1] - ovector[0]);
        pos = ovector[0];
    }
    return result;
}

int main() {
    cout << replace_normal("hoge　fuga　piyo") << endl;
    cout << (double)(measure([]{replace_normal("hoge\nfuga\npiyo");})) / 1000 << endl;
    //cout << (double)(measure([]{replace_normal("hoge\nfuga\npiyo\nhoge\nfuga\npiyo\nhoge\nfuga\npiyo\nhoge\nfuga\npiyo\nhoge\nfuga\npiyo\nhoge\nfuga\npiyo\n");})) / 1000 << endl;
    cout << replace_regexp("hoge　fuga　piyo") << endl;
    cout << (double)(measure([]{replace_regexp("hoge\nfuga\npiyo");})) / 1000 << endl;
    //cout << (double)(measure([]{replace_regexp("hoge\nfuga\npiyo\nhoge\nfuga\npiyo\nhoge\nfuga\npiyo\nhoge\nfuga\npiyo\nhoge\nfuga\npiyo\nhoge\nfuga\npiyo\n");})) / 1000 << endl;
    return 0;
}
// コンパイル例)
// g++ -g -Wall -O3 replace_vs_regex.cpp -lpcre2-8 -o replace_vs_regex
// 出力例)
// hogefugapiyo
// 0.091
// hogefugapiyo
// 0.414

こんな感じになりました。遅いな…と。(上のコードは実用に耐えないコードなので注意)

私がやったからなのかもしれないと、ベンチマークを調べたところ、あまり新しいのが見つかりませんでした。Unicode対応した正規表現ライブラリでこれいいよ！みたいなのとか、いいベンチマークを知ってる人がいたら教えてください。嘘か真かRustやNimでいい結果が出てるベンチマークも見たので、この言語なら！みたいのでもいいですよ。自由に語ってください。

※片手間にやってることなので、そんな急いでません