正则表达式匹配速度提升 200 倍
On the Edge of Ruby
一个关于 Ruby、性能和并发的博客
Written by Benoit Daloze @eregontp on March 14, 2025
正则表达式匹配速度提升 200 倍
TLDR: 正则表达式的速度可以比 C 代码甚至手写的 SIMD 代码更快。
你可能已经看过 @byroot 撰写的关于优化 json gem 的精彩博客系列。从第一篇博客文章中可以清楚地看出，生成 JSON 的大部分时间都花在 generate_json_string() 中，特别是在 convert_UTF8_to_JSON() 中，也就是将 Ruby 字符串转换为 JSON 字符串。
因为这是 JSON 生成中的一个热点部分，所以受到了很多关注。在第 3 部分中，@byroot 展示了一种 查找表方法 来实现 convert_UTF8_to_JSON()，现在已经在 json gem 中使用。
此后，已经有 一些 尝试 使用 SIMD 指令进一步优化它。然而，这在 C 语言中非常困难和繁琐，因为它类似于编写内联汇编（N 次，N 是 SIMD 变体的数量），而且它不具有可移植性，因此需要编译时和运行时检测来选择正确的 SIMD 变体。
在这篇博文中，我们将比较 3 个用于将 Ruby 字符串转换为 JSON 字符串的方案。
纯 Ruby 版本非常简单，只需几行代码（和一个大的 Hash 字面量）：
ESCAPE_MAP = {
"\x0" => '\u0000', "\x1" => '\u0001', "\x2" => '\u0002', "\x3" => '\u0003',
"\x4" => '\u0004', "\x5" => '\u0005', "\x6" => '\u0006', "\x7" => '\u0007',
"\b" => '\b', "\t" => '\t', "\n" => '\n', "\xb" => '\u000b',
"\f" => '\f', "\r" => '\r', "\xe" => '\u000e', "\xf" => '\u000f',
"\x10" => '\u0010', "\x11" => '\u0011', "\x12" => '\u0012', "\x13" => '\u0013',
"\x14" => '\u0014', "\x15" => '\u0015', "\x16" => '\u0016', "\x17" => '\u0017',
"\x18" => '\u0018', "\x19" => '\u0019', "\x1a" => '\u001a', "\x1b" => '\u001b',
"\x1c" => '\u001c', "\x1d" => '\u001d', "\x1e" => '\u001e', "\x1f" => '\u001f',
'"' => '\"', '\\' => '\\\\',
}
def utf8_to_json(string)
'"' + if /["\\\x0-\x1f]/.match?(string)
string.gsub(/["\\\x0-\x1f]/, ESCAPE_MAP)
else
string
end + '"'
end
ESCAPE_MAP 有点冗长，但它是一种简单的方式来详尽地存储如何转义每个需要转义的字符。match? 不是严格必需的，但它可以避免为没有字符需要转义的常见情况分配新的字符串。
我们使用 ruby/json 的 字符串编码基准测试，并进行了一个小的修改来只运行这些基准测试：
diff --git a/benchmark/encoder.rb b/benchmark/encoder.rb
index f0a05db..efbac2b 100644
--- a/benchmark/encoder.rb
+++ b/benchmark/encoder.rb
@@ -33,6 +33,8 @@ def implementations(ruby_obj)
end
def benchmark_encoding(benchmark_name, ruby_obj, check_expected: true, except: [])
+ return unless ["mixed utf8", "mostly utf8"].include?(benchmark_name)
json_output = JSON.dump(ruby_obj)
puts "== Encoding #{benchmark_name} (#{json_output.bytesize} bytes)"
@@ -40,6 +42,7 @@ def benchmark_encoding(benchmark_name, ruby_obj, check_expected: true, except: [
except.each { |i| impls.delete(i) }
Benchmark.ips do |x|
+ x.warmup = 5
expected = ::JSON.dump(ruby_obj) if check_expected
impls.values.each do |name, block|
begin
我们使用提前返回来选择我们想要的基准测试，并增加预热以提高基准测试结果的稳定性。我们使用 ONLY=json，因为 SIMD PR 没有 json_coder 变体（无论如何，这两个变体对于所选基准测试都给出了非常相似的结果）。
JSON 字符串转义基准测试
这些基准测试很简单：
# mixed utf8
JSON.generate([("a" * 5000) + "€" + ("a" * 5000)] * 500)
# mostly utf8
JSON.generate([("€" * 3333)] * 500)
它们都将包含 500 个字符串的数组转储为 JSON，并最终生成 5MB 的 JSON 结果。
以下是我的机器（AMD Ryzen 7 3700X 8-Core Processor）上的结果，禁用了频率缩放和 performance CPU 调控器：
使用 YJIT 的 CRuby 3.4.2 的 C 扩展（在 ruby/json master 上）：
$ ONLY=json ruby --yjit -Ilib:ext benchmark/encoder.rb
ruby 3.4.2 (2025-02-15 revision d2930f8e7a) +YJIT +PRISM [x86_64-linux]
mixed utf8 397.953 (± 4.5%) i/s (2.51 ms/i)
mostly utf8 402.388 (± 0.5%) i/s (2.49 ms/i)
我们将使用这个作为基线，特别是 mixed utf8 基准测试，以保持简单。
使用 YJIT 的 CRuby 3.4.2 的 C 扩展 + SIMD（在 SIMD PR 上）：
$ ONLY=json ruby --yjit -Ilib:ext benchmark/encoder.rb
ruby 3.4.2 (2025-02-15 revision d2930f8e7a) +YJIT +PRISM [x86_64-linux]
mixed utf8 1.498k (± 4.0%) i/s (667.68 μs/i)
mostly utf8 1.474k (± 1.6%) i/s (678.55 μs/i)
快了 3.76 倍，不错！
使用 TruffleRuby 24.1.1 JVM 的纯 Ruby 生成器（在 ruby/json master 上）：
$ ONLY=json ruby -Ilib:ext benchmark/encoder.rb
truffleruby 24.1.1, like ruby 3.2.4, Oracle GraalVM JVM [x86_64-linux]
mixed utf8 8.104k (± 0.6%) i/s (123.40 μs/i)
mostly utf8 8.070k (± 1.1%) i/s (123.91 μs/i)
比基线快 20 倍，比 SIMD 快 5.4 倍！而且，当然更简单，这只是一些 Ruby 代码和一个正则表达式。
如果你之前猜测 C 扩展代码 + SIMD 会是最快的，你可能会惊讶地发现纯 Ruby 版本 (在 TruffleRuby 上) 速度要快得多！这就是高级 JIT 编译器（如 TruffleRuby 的 JIT 编译器（称为 Graal））的优势：你可以编写漂亮、符合 Ruby 习惯的代码，而 JIT 编译器会完成为你的目标平台优化它的艰苦工作。
为了比较，这是使用 YJIT 的 CRuby 3.4.2 的纯 Ruby 生成器（在 ruby/json master 上）：
$ ONLY=json ruby --yjit -Ilib:ext benchmark/encoder.rb
ruby 3.4.2 (2025-02-15 revision d2930f8e7a) +YJIT +PRISM [x86_64-linux]
mixed utf8 39.551 (± 0.0%) i/s (25.28 ms/i)
mostly utf8 28.119 (± 0.0%) i/s (35.56 ms/i)
不幸的是，它比基线慢 10 倍，这表明正则表达式方法在 CRuby 上慢得多。但是，我们启用了 YJIT 运行，为什么它会慢这么多？
作为免责声明，在 JSON.generate 宏基准测试中，TruffleRuby（使用纯 Ruby 生成器）目前比使用 C 扩展的 CRuby 慢（除了 canada.json，它更快）。JSON 生成的其他方面需要在 TruffleRuby 上得到更好的优化。
Regexp#match? 基准测试
让我们简化基准测试，只关注 Regexp#match? 以更好地理解：
require 'benchmark/ips'
mixed_utf8 = ("a" * 5000) + "€" + ("a" * 5000)
Benchmark.ips do |x|
x.warmup = 5
x.report '/["\\\x0-\x1f]/.match?(mixed_utf8)' do
raise if /["\\\x0-\x1f]/.match?(mixed_utf8)
end
end
$ ruby --yjit bench_regexp_match.rb
ruby 3.4.2 (2025-02-15 revision d2930f8e7a) +YJIT +PRISM [x86_64-linux]
20.700k (± 2.4%) i/s (48.31 μs/i)
$ ruby bench_regexp_match.rb
truffleruby 24.1.1, like ruby 3.2.4, Oracle GraalVM JVM [x86_64-linux]
4.699M (± 0.3%) i/s (212.83 ns/i)
在这个基准测试中，TruffleRuby 比 CRuby 快 227 倍！TruffleRuby 在 213 纳秒内匹配 10003 个字节，即每纳秒 47 个字节，这大于我们每纳秒拥有的 CPU 周期数（此处理器的最大频率为 4.4 GHz），所以这里发生了什么？
正则表达式匹配在 TruffleRuby 上怎么会这么快？
原因有很多：
- TruffleRuby 上的正则表达式使用 TRegex，一种最先进的正则表达式引擎：
- TRegex 将正则表达式编译为 有限状态自动机，这意味着它永远不会在输入字符串中后退，并且最多读取每个字符一次。因此，它始终以线性时间运行。CRuby 使用回溯，可能会多次遍历输入字符串字符，这要慢得多。
- 当回溯过多时，回溯容易出现 ReDoS，而 有限状态自动机对 ReDoS 免疫。CRuby 3.2+ 通过使用某种形式的缓存来保护大多数正则表达式免受 ReDoS 的影响。虽然该缓存避免了许多 ReDoS，但它也通过需要每次可能回溯时检查或填充此缓存来减慢正则表达式的执行速度。
- TRegex 将正则表达式 JIT 编译 为本机代码。CRuby 将正则表达式编译为正则表达式字节码，然后使用解释器来运行该字节码。这意味着它有调度开销，不跨字节码优化等。YJIT 对该正则表达式解释器一无所知，因为它全部用 C 编写，所以它将其视为黑盒。
- TruffleRuby 使用 拆分，因此
Regexp#match?和其他与正则表达式相关的方法的每个调用点都有其自己的逻辑副本。有了这个，TruffleRuby 能够 内联 JIT 编译的代码，用于调用match?的 Ruby 方法中的特定正则表达式。 - TRegex 自动使用 SIMD，特别是运行处理器上可用的最佳 SIMD 变体。它能够做到这一点，因为 JIT 编译器会查询 CPU 以了解哪些 SIMD 变体可用。TRegex 不需要像 C 那样在不同的 SIMD 变体之间进行调度，因为 JIT 编译器知道可用的最佳 SIMD 变体。因此，我们可以使用 SIMD 指令，但我们不必为了受益而使 Ruby gem 复杂化。
特别是对于这个正则表达式，TRegex 在内部使用 ByteIndexOfCodePointSetNode，它自动为该正则表达式中的字符范围（["\\\x0-\x1f]）创建一个查找表，并且还自动使用 SIMD。如果你想了解更多关于 TRegex 的信息，TRegex 的创建者和我做了一个 在 RubyKaigi 2021 上的演讲。Kevin Menard 还在 RailsConf 2022 上发表了 关于 ReDoS 的演讲 和解决方案。
上面的 JSON 字符串转义示例不是 TruffleRuby 巧合地更快的孤立案例。拥有一个快速的正则表达式引擎允许更符合语言习惯的解决方案，并允许在 TruffleRuby 上运行的 Ruby 代码在许多情况下比 C 代码更快。这里还有两个真实世界的例子，其中 TruffleRuby 使用正则表达式并且比 C 代码更快！
Time.new(String)
自 Ruby 3.2 以来，Time.new 接受一个字符串参数。
CRuby 通过 在 C 中使用 char 指针解析大约 80 行代码中的字符串 来实现它。TruffleRuby 在 使用正则表达式的直接方式中 来实现它。
require 'benchmark/ips'
NOW_STRING = Time.now.to_s
Benchmark.ips do |x|
x.report("Time.new(String)") do
Time.new(NOW_STRING)
end
end
$ ruby --yjit bench_time_new_string.rb
ruby 3.4.2 (2025-02-15 revision d2930f8e7a) +YJIT +PRISM [x86_64-linux]
Time.new(String) 1.595M (± 0.5%) i/s (626.84 ns/i)
$ ruby bench_time_new_string.rb
truffleruby 24.1.1, like ruby 3.2.4, Oracle GraalVM JVM [x86_64-linux]
Time.new(String) 3.923M (± 5.4%) i/s (254.90 ns/i)
TruffleRuby 在这里快 2.5 倍，同时具有更简单、更清晰的实现。
让我们只对正则表达式进行基准测试，尽管我们在这里使用 match，因为我们需要捕获组：
require 'benchmark/ips'
NOW_STRING = Time.now.to_s
TIME_REGEXP = /\A (?<year>\d{4,5})
(?:
- (?<month>\d{2})
- (?<mday> \d{2})
[ T] (?<hour> \d{2})
: (?<min> \d{2})
: (?<sec> \d{2})
(?:\. (?<usec> \d+) )?
(?:\s* (?<offset>\S+))?
)?\z/x
Benchmark.ips do |x|
x.report("TIME_REGEXP.match(NOW_STRING)") do
raise unless TIME_REGEXP.match(NOW_STRING)
end
end
$ ruby --yjit bench_time_new_string_regexp.rb
ruby 3.4.2 (2025-02-15 revision d2930f8e7a) +YJIT +PRISM [x86_64-linux]
TIME_REGEXP.match(NOW_STRING) 1.234M (± 0.8%) i/s (810.47 ns/i)
$ ruby bench_time_new_string_regexp.rb
truffleruby 24.1.1, like ruby 3.2.4, Oracle GraalVM JVM [x86_64-linux]
TIME_REGEXP.match(NOW_STRING) 33.448M (± 9.9%) i/s (29.90 ns/i)
TruffleRuby 对于这个正则表达式快 27 倍。因此，Time.new(String) 基准测试实际上花费了大量时间在创建和初始化 Time 对象上。
StringScanner#scan_integer
StringScanner#scan_integer 是一个 最近添加 到 StringScanner 的方法。
CRuby 在 114 行 C 代码中实现它。TruffleRuby 使用正则表达式在 18 行 Ruby 代码中实现它。我们在这里使用 TruffleRuby master，因为该方法是在上一个 TruffleRuby 版本之后引入的。
require 'benchmark/ips'
require 'strscan'
SCANNER = StringScanner.new("123456789")
Benchmark.ips do |x|
x.report("StringScanner#scan_integer") do
SCANNER.reset
raise unless 123456789 == SCANNER.scan_integer
end
end
$ ruby --yjit bench_scan_integer.rb
ruby 3.4.2 (2025-02-15 revision d2930f8e7a) +YJIT +PRISM [x86_64-linux]
StringScanner#scan_integer 10.530M (± 0.6%) i/s (94.97 ns/i)
$ ruby bench_scan_integer.rb
truffleruby 25.0.0-dev-48a0a626, like ruby 3.3.5, Oracle GraalVM JVM [x86_64-linux]
StringScanner#scan_integer 30.230M (± 3.0%) i/s (33.08 ns/i)
TruffleRuby 快了大约 3 倍。顺便说一句，TruffleRuby 完全在 Ruby 代码中实现 StringScanner。Ruby 代码不仅更短、更具表现力，而且也更正确。为此，在实现新的 StringScanner 方法时，我们发现了 6 个问题 与 StringScanner 的 C 扩展实现有关：2 个段错误和 4 个不一致/不正确的行为。
为了完整起见，让我们也对正则表达式进行基准测试：
require 'benchmark/ips'
INPUT = "123456789"
Benchmark.ips do |x|
x.report("/\A[+-]?\d+/.match(INPUT)") do
raise unless /\A[+-]?\d+/.match(INPUT)
end
end
$ ruby --yjit bench_scan_integer_regexp.rb
ruby 3.4.2 (2025-02-15 revision d2930f8e7a) +YJIT +PRISM [x86_64-linux]
/A[+-]?d+/.match(INPUT) 1.972M (± 0.8%) i/s (507.00 ns/i)
$ ruby bench_scan_integer_regexp.rb
truffleruby 25.0.0-dev-48a0a626, like ruby 3.3.5, Oracle GraalVM JVM [x86_64-linux]
/A[+-]?d+/.match(INPUT) 61.086M (± 6.9%) i/s (16.37 ns/i)
TruffleRuby 对于这个正则表达式快 31 倍。
结论
有时，例如在这篇博文中显示的案例中，符合语言习惯的纯 Ruby 解决方案也是最快的，甚至比 C 代码或内联汇编更快。这在 TruffleRuby 上并不新鲜，纯 Ruby 代码通常比其他任何东西都快，包括 CRuby 上的 C 扩展。Ruby 代码更具表现力且更高级别，这使得一些优化成为可能，而如果用较低级别的语言编写，则不可能实现这些优化。
如果你想快速运行符合 Ruby 习惯的代码，请尝试 TruffleRuby。
→ Top © 2025 Benoit Daloze. Opinions are my own. Atom/RSS Feed. Made with Jekyll using the Tale theme. Favicon: TruffleRuby logo Copyright © 2017 Talkdesk, Inc. Licensed under CC BY 4.0.