teddy

Teddy是一个SIMD加速的多子串匹配算法，这是其在Rust中的实现。名称和算法中的核心思想是从Hyperscan项目中学到的。

安装和用法

目前，Teddy仅支持带有SSSE3 SIMD指令的x86和x86_64处理器。此外，它需要一个nightly rust编译器。要将Teddy设置到你的rust项目中，请将以下内容添加到你的Cargo.toml文件的[dependencies]部分：

teddy = { version = "0.1", features = "simd-accel" }

然后，你需要配置rustc以支持所需的SIMD指令。假设你只在你自己的机器上编译，你可以通过以下命令编译你的项目来完成此操作：

RUSTFLAGS="-C target-cpu=native" cargo build

如果你想要对所使用的SIMD指令集有更多控制，你可以使用以下命令（或者这些功能的一个子集——目前，至少需要+ssse3或+avx2中的一个）：

RUSTFLAGS="-C target-feature=+ssse3,+sse4.1,+avx2" cargo build

(或这些功能的一个子集——目前，至少需要+ssse3或+avx2中的一个）。

以下是Teddy使用的基本示例

extern crate teddy;
use teddy::Teddy;

fn main() {
  let patterns = vec![b"cat", b"dog", b"fox"];
  let ted = Teddy::new(patterns.iter().map(|s| &s[..])).unwrap();
  println!("{:?}", ted.find(b"The quick brown fox jumped over the laxy dog."));
}

有关更多信息，请参阅API文档。

背景

Teddy的关键思想是进行打包子串匹配。在文献中，打包子串匹配是指同时检查针线中的多个字节以检测匹配。例如，memchr（它检测单个字节的匹配）的实现已经这样做多年。最近，随着各种SIMD指令的引入，这已被扩展到子串匹配。例如，PCMPESTRI指令（及其相关指令）在硬件中实现了子串匹配。然而，它仅限于长度为16字节或更短的子串，但在正则表达式引擎中，这个限制是可以接受的，因为我们很少关心在搜索16字节文本和16 + N文本之间的性能差异——16已经足够长。PCMPESTRI指令的关键缺点（至少在2016年的CPU上）是其延迟和吞吐量。因此，使用Boyer-Moore变体和适当位置上的memchr进行子串搜索通常更快。

关于紧凑子串匹配的文献结果较少，而对于紧凑多重子串匹配则更少。Ben-Kiki 等人[2]描述了PCMPESTRI在子串匹配中的应用，但主要停留在理论层面，并未涉及性能。Bille[3]也进行了其他一些理论研究。

据我所知，该领域的其他工作主要由Faro和Kulekci完成，主要聚焦于多重模式搜索。他们的第一篇论文[4a]引入了指纹的概念，为每个模式的N字节块计算指纹。然后以N字节为单位扫描草稿，并按相同方式计算指纹。如果指纹与模式中找到的指纹对应，则进行验证步骤以确认具有对应指纹的子串实际上在当前位置匹配。采用了各种实现技巧来确保指纹查找快速；通常是通过截断指纹。当然，这可能会在验证过程中增加更多步骤，因此需要权衡。

[4a]的主要缺点是子串的最小长度为32字节，这可能是由于算法使用了某些SIMD指令。这实际上使其在通用正则表达式匹配中无用，因为在通用正则表达式匹配中，小数量的短模式更为常见。

Faro和Kulekci还发表了一篇论文[4b]，在概念上与[4a]非常相似。关键区别在于它使用CRC32指令（作为SSE 4.2的一部分引入）来计算指纹值。这使得算法能够有效地在长度至少为7字节、窗口大小为4字节的情况下对子串进行处理。不幸的是，7字节仍然太长。窗口大小可以从技术上缩小到2字节，从而将最小长度减少到3，但小窗口大小最终抵消了大多数性能优势——这可能是通用正则表达式引擎中的常见情况。

Faro和Kulekci还发表了[4c]，似乎旨在替代PCMPESTRI的使用。特别是，它特别受到PCMPESTRI高吞吐量/延迟时间的影响，因此选择了更快的SIMD指令。虽然这种方法对短子串有效，但我个人没有看到将其推广到多重子串搜索的方法。

Faro和Kulekci还有一篇论文[4d]，我因为付费墙而未能阅读。

Teddy

最后，我们来到了Teddy。如果上述文献综述是完整的，那么Teddy似乎是一个新颖的算法。更确切地说，根据我的经验，它在短子串方面彻底击败了竞争对手，这正是我们在通用正则表达式引擎中想要的。再次强调，该算法似乎是由Hyperscan的作者开发的。Hyperscan在2015年底开源，没有找到更早的历史记录。因此，追踪算法与已发表的文献的准确来源似乎很困难。

免责声明：我对Teddy的理解仅限于阅读自动生成的C代码、其反汇编代码和观察其运行行为。

从高层次来看，Teddy的工作方式与Faro和Kulekci发表的手指算法类似，但它以一种更好地扩展的方式工作。具体来说

1. Teddy的核心算法以16或32字节块扫描草稿，具体取决于您的处理器。我们将在这里描述16字节块算法，但32字节的情况类似。
2. 对每个块进行位操作以发现其任何区域是否与来自模式的预计算指纹集匹配。如果有匹配项，则执行验证步骤。在此实现中，我们的验证步骤是简单的。这可以进一步改进。

使这个功能正常工作的细节相当巧妙。首先，我们必须选择如何选择我们的指纹。在Hyperscan的实现中，我 认为 他们使用每个子串的最后N个字节，其中N必须至少是正在搜索的集合中任何子串的最小长度。在这个实现中，我们使用每个子串的前N个字节。（这些选择之间的权衡对我来说还不清楚。）然后，我们必须找出如何快速测试模式集合中任何指纹的出现是否在haystack的16字节块中。为了使事情简单，让我们假设N = 1，并考察一些例子来激发这种方法。以下是我们的模式

foo
bar
baz

对于N = 1，相应的指纹是 f， b 和 b。现在让我们将我们的16字节块设置为

bat cat foo bump
xxxxxxxxxxxxxxxx

直接进入正题，Teddy通过使用位集工作。具体来说，Teddy创建一个掩码，允许我们快速计算指纹在16字节块中的成员资格，同时也告诉我们该指纹对应哪个模式。在这种情况下，我们的指纹是一个字节，所以一个合适的抽象是将单个字节映射到包含该指纹的模式列表

f |--> foo
b |--> bar, baz

现在，我们只需要弄清楚如何在这个映射中代表向量空间，并使用正常的SIMD操作进行查找。我们可以做的第一个简化是将我们的模式表示为占用单个字节的位字段。这很重要，因为单个SIMD向量可以存储16字节。

f |--> 00000001
b |--> 00000010, 00000100

我们如何进行查找呢？实际上，SSSE3引入了一个非常酷的指令，称为PSHUFB。该指令接受两个SIMD向量，A 和 B，并返回一个第三个向量 C。所有向量都被视为16个8位整数。C 是通过 C[i] = A[B[i]] 形成的。（这是一个简化，但适用于这个算法。对于完整细节，请参阅 Intel的Intrinsics Guide。）这实质上允许我们使用 B 中的值在 A 中查找值。

如果我们能以某种方式使 B 包含我们的16字节块，并且如果 A 可以包含我们的位掩码，那么我们将得到类似如下的 A

    0x00 0x01 ... 0x62      ... 0x66      ... 0xFF
A = 0    0        00000001      00000110      0

如果 B 包含我们的haystack窗口，我们可以使用shuffle从 B 中取值，并使用这些值在 A 中查找位集。但当然，我们无法这样做，因为上述例子中的 A 包含256字节，这比SIMD向量的尺寸大得多。

Nybbles来拯救！一个nybble是4位。我们不是用一个掩码来存储所有的位集，而是可以用两个掩码，其中一个掩码对应于我们的指纹的较低四位，另一个掩码对应于较高四位。因此，我们的映射现在看起来像

'f' & 0xF = 0x6 |--> 00000001
'f' >> 4  = 0x6 |--> 00000111
'b' & 0xF = 0x2 |--> 00000110
'b' >> 4  = 0x6 |--> 00000111

请注意，每个半字节对应的位集是对包含该半字节的指纹的并集。例如，f和b的较高4位相同，但较低4位不同。将它们结合起来，我们得到A0、A1和B，其中A0是较低半字节的掩码，A1是较高半字节的掩码，而B是从稻草中获取的16字节块。

      0x00 0x01 0x02      0x03 ... 0x06      ... 0xF
A0 =  0    0    00000110  0        00000001      0
A1 =  0    0    0         0        00000111      0
B  =  b    a    t         _        t             p
B  =  0x62 0x61 0x74      0x20     0x74          0x70

当然，我们目前不能使用B与PSHUFB，因为它的值是8位，我们需要最多4位的索引（对应于16个值之一）。我们可以像处理A一样，对B应用相同的转换，将其分割成较低和较高半字节。同样地，B0对应较低半字节，而B1对应较高半字节。

     b   a   t   _   c   a   t   _   f   o   o   _   b   u   m   p
B0 = 0x2 0x1 0x4 0x0 0x3 0x1 0x4 0x0 0x6 0xF 0xF 0x0 0x2 0x5 0xD 0x0
B1 = 0x6 0x6 0x7 0x2 0x6 0x6 0x7 0x2 0x6 0x6 0x6 0x2 0x6 0x7 0x6 0x7

现在我们有一个很好的对应关系。 B0可以索引A0，而B1可以索引A1。以下是应用C0 = PSHUFB(A0, B0)时得到的结果。

     b         a        ... f         o         ... p
     A0[0x2]   A0[0x1]      A0[0x6]   A0[0xF]       A0[0x0]
C0 = 00000110  0            00000001  0             0

和C1 = PSHUFB(A1, B1)

     b         a        ... f         o        ... p
     A1[0x6]   A1[0x6]      A1[0x6]   A1[0x6]      A1[0x7]
C1 = 00000111  00000111     00000111  00000111     0

请注意，C0或C1本身并不能保证总是报告完全正确的结果。例如，C1声称b是模式foo的指纹（因为A1中0x6的位置为00000111），并且o是所有模式的指纹。但如果我们用AND操作结合C0和C1。

     b         a        ... f         o        ... p
C  = 00000110  0            00000001  0            0