在正则表达式引擎的开发领域，F# 可能并非首选语言。然而，正是这种看似 “非主流” 的选择，让 RE# 引擎获得了令人惊叹的性能表现。本文将深入探讨如何利用 F# 与 .NET 平台的特性，构建世界上最快的正则表达式引擎，并重点剖析有限状态机（Finite State Machine，FSM）的向量化与 SIMD 优化策略。
为什么选择 F# 构建高性能正则引擎
RE# 引擎的核心开发者在阐述技术选型时指出，F# 的优势并非来自语言本身的运行时性能，而是源于其对 .NET 底层基础设施的无缝访问。.NET 平台提供了极为丰富的 SIMD 原语和向量化 API，而 F# 能够直接调用这些接口，无需任何互操作成本。更关键的是，RyuJIT 编译器的代码生成效率可与原生语言相媲美，这意味着用 F# 编写的热点代码在经过 JIT 编译后，能够产生与 C++ 不相上下的机器码。
具体而言，F# 开发者可以直接使用 System.Numerics.Vector<T> 进行向量运算，利用 System.Buffers.SearchValues<T> 执行高度优化的字符搜索，还能调用 System.Runtime.Intrinsics 中的硬件内在函数实现精细控制。这些 API 大多数情况下由手写汇编或编译器 intrinsic 实现，性能远超过依赖自动向量化的普通代码。
核心架构：基于导数的惰性确定性自动机
与传统正则引擎不同，RE# 采用了基于 Brzozowski 导数的确定性自动机设计。这一方法源自 1964 年的经典论文，其核心思想极其简洁：给定一个正则表达式 R 和字符 c，R 关于 c 的导数就是匹配完第一个字符后剩余的部分。例如，正则 hello 关于字符 h 的导数是 ello，而 abc 关于字符 x 的导数则是空集 ∅。
这种设计的精妙之处在于，导数运算天然支持交（&）和补（~）运算，无需额外的复杂机制。正则 .*a.*&.*b.* 关于字符 a 的导数直接化简为 .*b.*，整个过程简洁而优雅。通过这种方式，RE# 成为首个支持交和补运算且保持线性时间复杂度的工业级正则引擎。
在状态机构建方面，RE# 采用惰性策略：在匹配过程中按需创建新状态，而非预先构建完整的确定性有限自动机（DFA）。这与 RE2 和 Rust 正则引擎的惰性 DFA 思路一致，但关键区别在于 RE# 跳过了 NFA 构建阶段，直接从正则表达式通过导数运算构造 DFA 状态。这一技术源自 .NET NonBacktracking 引擎的研究成果。
最小项压缩： alphabets 的极致优化
朴素实现可能需要为 Unicode 平面中的每个字符（最多 65536 个）计算状态转移，这显然是灾难性的。最小项（Minterm）压缩通过将字符空间划分为等价类来解决这一问题：在同一等价类中的所有字符对正则表达式的行为完全相同。
以正则 [a-zA-Z] 为例，引擎只需区分两类字符 —— 字母和非字母。字母（包括 a 到 z、A 到 Z）被映射到最小项 ID 1，非字母映射到 ID 0。这种压缩效果是惊人的：对于匹配 Unicode 单词边界 \b\w{12,}\b 的正则，RE# 的速度是第二名引擎的七倍以上，原因在于 \w 包含数万种字符，若不压缩将产生同样数量的状态转移。
在实际实现中，最小项映射表是一个字符到最小项 ID 的查找表，位于热路径之外预先计算完成。匹配循环因此简化为两个极其紧凑的步骤：根据字符查表获取最小项 ID，再根据状态和最小项 ID 查表获取下一状态。这正是 SIMD 向量化可以大显身手的环节。
SIMD 向量化策略：三层实现方案
在 .NET 8 及更高版本上，F# 开发者拥有三种可行的 SIMD 方案，各有其适用场景。
第一种方案是 SearchValues<T> 快速成员测试。这是 .NET 9 引入的 Teddy 多字符串搜索算法的底层实现，专门用于 “在字符类中查找下一个字符” 或 “跳过不属于某类的字符” 等高频操作。例如，要找到下一个字母位置，只需构造 SearchValues<char>.Create("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ") 并在输入上调用 IndexOfAny。该 API 内部已实现向量化，在大多数场景下比手写循环快数倍，且对边界情况的处理更为健壮。
第二种方案是 System.Numerics.Vector<T> 批量数值运算。当字符映射或预处理逻辑是数值化且简单的情况下，向量类型非常有用。例如，可以将 ASCII 字节批量转换为最小项 ID，或并行执行掩码运算以检测单词边界。编写这类循环时，需要确保每次迭代处理 Vector<byte>.Count 或 Vector<int>.Count 个元素，再用标量代码处理尾部余数。
第三种方案是硬件内在函数 System.Runtime.Intrinsics 用于最大控制权。当需要实现经典的 SIMD 算法（如细粒度的字节模式扫描或字符类匹配）时，直接调用 AVX2 或 SSE 指令可以获得极致性能。不过，这通常仅用于实现被高频复用的核心原语，而非在所有位置内联使用。
双向扫描与最左最长匹配
自动向量化的 JIT 编译并不总是可靠，因此显式使用上述 API 通常比依赖编译器自动向量化更为稳妥。RE# 采用了双向扫描策略来实现 POSIX 标准的 “最左最长” 语义：从右向左运行 DFA 找到所有可能的匹配起始位置，再从左向右运行反向 DFA 找到匹配结束位置。最左的起始位置配以最右的结束位置即为最终结果。这一方法的优势在于，两次扫描都是纯线性的，没有任何回溯，完全适合向量化优化。
工程实现的关键参数
在实际 F# 项目中应用这些优化时，以下参数值得特别关注。首先，热循环应当保持短小、分支稀少，并操作在 Span<byte> 或 ReadOnlySpan<char> 上，以最大化 JIT 优化效果。其次，应将解析和编译与匹配过程分离：正则表达式编译为最小项表示的紧凑 DFA 只需执行一次，匹配时仅运行向量化扫描和 DFA 状态更新。第三，字符类的设计应当与最小项和 SIMD 扫描对齐，将常见类（如字母、数字、单词字符）归入同一最小项，使单个 SearchValues<char> 或 SIMD 掩码能快速完成分类。最后，对于 IsMatch 操作，方向无关差别，可以直接停止于第一个匹配以获得最优首次匹配性能。
RE# 引擎的 benchmark 数据表明，在大规模工业标准测试集上，其性能不仅超越所有 .NET 内置引擎，还优于 RE2、Rust 正则等业界领先方案。更重要的是，它提供了交、补和形式化 lookaround 的能力，同时保持 O (n) 的搜索时间复杂度，这在此前被认为是不可能的任务。F# 与 .NET SIMD 基础设施的结合，为高性能系统编程提供了一个极具说服力的案例。
参考资料：本文技术细节主要参考 RE# 引擎开发者 Ian Erik Varatalu 发表的技术博客及 POPL 2025 论文，RE# 引擎源码见 GitHub：ieviev/resharp-dotnet。