🦀
Rustのマクロで正規表現のmatchを高速で行えるクレートを作ってみた...?
はじめに
こんにちは。aq2rです。
最近Rustのマクロ、特に procedural macro が面白いなーと思いはまっています。
そこで、何かマクロを書きたいけどいい感じのネタないかなーと思っていたところ、
正規表現をもとにコンパイル時にif文に展開できれば高速で正規表現の判定ができるんじゃない？
というのを思いついたので、このようなクレートを作って見ました。
(crates.ioへの公開はしていません。)
比較
Rustコード
use regex::Regex;
macro_rules! time_measure {
($expr:expr) => {{
let now = std::time::Instant::now();
let expr_result = $expr;
let elp = now.elapsed();
(expr_result, elp)
}};
}
fn main() {
// discord msg url
let mut input_text_1 = String::new();
input_text_1 +=
"https://discord.com/channels/1234567890123456789/1234567890123456789/1234567890123456789";
let mut input_text_2 = String::new();
input_text_2 +=
"https://discord.com/channels/9876543210987654321/9876543210987654321/9876543210987654321";
let mut input_text_3 = String::new();
input_text_3 +=
"https://discord.com/channels/9876543210987654321/9876543210987654321/9876543ABCDE7654321";
println!("{}", "-".repeat(100));
let (regex, regex_new_elp) = time_measure! {
Regex::new(r"^https?://discord\.com/channels(/[0-9]+){3}/?$").unwrap()
};
let (reif, reif_new_elp) = time_measure! {
reif::new!(r"^https?://discord\.com/channels(/[0-9]+){3}/?$")
};
println!("regex_new_elp: {regex_new_elp:?}");
println!("reif_new_elp: {reif_new_elp:?}");
println!("{}", "-".repeat(100));
for i in [input_text_1, input_text_2, input_text_3] {
let (regex_result, regex_match_elp) = time_measure!({ regex.is_match(&i) });
let (reif_result, reif_match_elp) = time_measure!({ reif.is_match(&i) });
assert_eq!(reif_result, regex_result);
println!("{i}: {reif_result}");
println!("Regex: {regex_match_elp:?}");
println!("Reif: {reif_match_elp:?}");
}
println!("{}", "-".repeat(100));
}
実行結果
----------------------------------------------------------------------------------------------------
regex_new_elp: 191.8µs
reif_new_elp: 0ns
----------------------------------------------------------------------------------------------------
https://discord.com/channels/1234567890123456789/1234567890123456789/1234567890123456789: true
Regex: 45.1µs
Reif: 400ns
https://discord.com/channels/9876543210987654321/9876543210987654321/9876543210987654321: true
Regex: 1.4µs
Reif: 300ns
https://discord.com/channels/9876543210987654321/9876543210987654321/9876543ABCDE7654321: false
Regex: 2.3µs
Reif: 400ns
----------------------------------------------------------------------------------------------------
Regex::new と reif::new! の実行時間については、reif::new!はコンパイル時に展開されるため実行時のコストはほぼ0です。
そして実際に文字列を比較する部分においては、1回目はRegexにおいてはコンパイルがあるのか時間がかかっていますが、2回目以降はReifの方が4 ~ 6倍程度高速な程度になっています。
Regexって思ってたよりかなり早いんですね...
実装について
正規表現の解析については regex-syntax クレートを使用しています。
if文に展開する部分は regex-syntaxのHirのEnum ごとに TokenStream を作成して、部品を組み合わせるような形で作成しています。
展開例
例1
展開前:
reif::new!(r"[0-9]{3}-[0-9]{4}");
展開後:
// Recursive expansion of new! macro
// ==================================
{
reif::Reif {
process: |input: &str| -> bool {
for i in {
let char_boundaries: Vec<usize> =
input.char_indices().map(|(i, _)| i).collect();
if char_boundaries.is_empty() {
<[_]>::into_vec(
#[rustc_box]
alloc::boxed::Box::new([0]),
)
} else {
char_boundaries
}
} {
let mut rest = &input[i..];
let result = (|| -> bool {
{
let mut cycle_count = 0;
loop {
if cycle_count >= 3u32 {
break;
}
{
let Some(c) = rest.chars().next() else {
break;
};
let result = match c {
'0'..='9' => true,
_ => false,
};
if result {
rest = &rest[c.len_utf8()..];
} else {
break;
}
}
cycle_count += 1;
}
if !(3u32 <= cycle_count && cycle_count <= 3u32) {
return false;
}
}
{
if rest.starts_with("-") {
rest = &rest["-".len()..];
} else {
return false;
}
}
{
let mut cycle_count = 0;
loop {
if cycle_count >= 4u32 {
break;
}
{
let Some(c) = rest.chars().next() else {
break;
};
let result = match c {
'0'..='9' => true,
_ => false,
};
if result {
rest = &rest[c.len_utf8()..];
} else {
break;
}
}
cycle_count += 1;
}
if !(4u32 <= cycle_count && cycle_count <= 4u32) {
return false;
}
}
true
})();
if result {
return true;
}
}
false
},
}
}
例2
展開前:
reif::new!(r"^https?://discord\.com/channels(/[0-9]+){3}/?$");
展開後:
// Recursive expansion of new! macro
// ==================================
{
reif::Reif {
process: |input: &str| -> bool {
for i in (0..1) {
let mut rest = &input[i..];
let result = (|| -> bool {
{
if rest.starts_with("http") {
rest = &rest["http".len()..];
} else {
return false;
}
}
{
let mut cycle_count = 0;
loop {
if cycle_count >= 1u32 {
break;
}
{
if rest.starts_with("s") {
rest = &rest["s".len()..];
} else {
break;
}
}
cycle_count += 1;
}
if !(0u32 <= cycle_count && cycle_count <= 1u32) {
return false;
}
}
{
if rest.starts_with("://discord.com/channels") {
rest = &rest["://discord.com/channels".len()..];
} else {
return false;
}
}
{
let mut cycle_count = 0;
loop {
if cycle_count >= 3u32 {
break;
}
if {
|| -> bool {
{
if rest.starts_with("/") {
rest = &rest["/".len()..];
} else {
return false;
}
}
{
let mut cycle_count = 0;
loop {
if cycle_count >= 4294967295u32 {
break;
}
{
let Some(c) = rest.chars().next() else {
break;
};
let result = match c {
'0'..='9' => true,
_ => false,
};
if result {
rest = &rest[c.len_utf8()..];
} else {
break;
}
}
cycle_count += 1;
}
if !(1u32 <= cycle_count
&& cycle_count <= 4294967295u32)
{
return false;
}
}
true
}()
} {
} else {
break;
}
cycle_count += 1;
}
if !(3u32 <= cycle_count && cycle_count <= 3u32) {
return false;
}
}
{
let mut cycle_count = 0;
loop {
if cycle_count >= 1u32 {
break;
}
{
if rest.starts_with("/") {
rest = &rest["/".len()..];
} else {
break;
}
}
cycle_count += 1;
}
if !(0u32 <= cycle_count && cycle_count <= 1u32) {
return false;
}
}
let matched_part = &input[0..(input.len() - rest.len())];
if !input.ends_with(matched_part) || !(input.len() == matched_part.len()) {
return false;
}
true
})();
if result {
return true;
}
}
false
},
}
}
まとめ
実際に活用できるかというよりはマクロを書きたい目的で作成したので、本当に高速かどうかはわかりません。
もしかしたらRegexクレートよりも高速かもしれませんが、機能が少なく is_match しか使えません。
captureなど便利な機能は使えないため、普通にRegexを使用した方がいいと思います。
もともと procedural macro を書き始める前は難しそうだなーと思って少し避けていたのですが、実際に触ってみるとそのマクロの中だけで有効なプログラミング言語を定義しているというくらいに自由度が高くてとても面白いと思いました。
これからもRustのマクロで遊びたいなーと思っています。
Discussion