我正在编写一种编程语言并创建我自己的正则表达式实现。我要拿BaseChar block ，它有一堆范围:
BaseChar ::= [#x0041-#x005A] | [#x0061-#x007A] | [#x00C0-#x00D6] | [#x00D8-#x00F6] | [#x00F8-#x00FF] | [#x0100-#x0131] | [#x0134-#x013E] | [#x0141-#x0148] | [#x014A-#x017E] | [#x0180-#x01C3] | [#x01CD-#x01F0] | [#x01F4-#x01F5] | [#x01FA-#x0217] | [#x0250-#x02A8] | [#x02BB-#x02C1] | #x0386 | [#x0388-#x038A] | #x038C | [#x038E-#x03A1] | [#x03A3-#x03CE] | [#x03D0-#x03D6] | #x03DA | #x03DC | #x03DE | #x03E0 | [#x03E2-#x03F3] | [#x0401-#x040C] | [#x040E-#x044F] | [#x0451-#x045C] | [#x045E-#x0481] | [#x0490-#x04C4] | [#x04C7-#x04C8] | [#x04CB-#x04CC] | [#x04D0-#x04EB] | [#x04EE-#x04F5] | [#x04F8-#x04F9] | [#x0531-#x0556] | #x0559 | [#x0561-#x0586] | [#x05D0-#x05EA] | [#x05F0-#x05F2] | [#x0621-#x063A] | [#x0641-#x064A] | [#x0671-#x06B7] | [#x06BA-#x06BE] | [#x06C0-#x06CE] | [#x06D0-#x06D3] | #x06D5 | [#x06E5-#x06E6] | [#x0905-#x0939] | #x093D | [#x0958-#x0961] | [#x0985-#x098C] | [#x098F-#x0990] | [#x0993-#x09A8] | [#x09AA-#x09B0] | #x09B2 | [#x09B6-#x09B9] | [#x09DC-#x09DD] | [#x09DF-#x09E1] | [#x09F0-#x09F1] | [#x0A05-#x0A0A] | [#x0A0F-#x0A10] | [#x0A13-#x0A28] | [#x0A2A-#x0A30] | [#x0A32-#x0A33] | [#x0A35-#x0A36] | [#x0A38-#x0A39] | [#x0A59-#x0A5C] | #x0A5E | [#x0A72-#x0A74] | [#x0A85-#x0A8B] | #x0A8D | [#x0A8F-#x0A91] | [#x0A93-#x0AA8] | [#x0AAA-#x0AB0] | [#x0AB2-#x0AB3] | [#x0AB5-#x0AB9] | #x0ABD | #x0AE0 | [#x0B05-#x0B0C] | [#x0B0F-#x0B10] | [#x0B13-#x0B28] | [#x0B2A-#x0B30] | [#x0B32-#x0B33] | [#x0B36-#x0B39] | #x0B3D | [#x0B5C-#x0B5D] | [#x0B5F-#x0B61] | [#x0B85-#x0B8A] | [#x0B8E-#x0B90] | [#x0B92-#x0B95] | [#x0B99-#x0B9A] | #x0B9C | [#x0B9E-#x0B9F] | [#x0BA3-#x0BA4] | [#x0BA8-#x0BAA] | [#x0BAE-#x0BB5] | [#x0BB7-#x0BB9] | [#x0C05-#x0C0C] | [#x0C0E-#x0C10] | [#x0C12-#x0C28] | [#x0C2A-#x0C33] | [#x0C35-#x0C39] | [#x0C60-#x0C61] | [#x0C85-#x0C8C] | [#x0C8E-#x0C90] | [#x0C92-#x0CA8] | [#x0CAA-#x0CB3] | [#x0CB5-#x0CB9] | #x0CDE | [#x0CE0-#x0CE1] | [#x0D05-#x0D0C] | [#x0D0E-#x0D10] | [#x0D12-#x0D28] | [#x0D2A-#x0D39] | [#x0D60-#x0D61] | [#x0E01-#x0E2E] | #x0E30 | [#x0E32-#x0E33] | [#x0E40-#x0E45] | [#x0E81-#x0E82] | #x0E84 | [#x0E87-#x0E88] | #x0E8A | #x0E8D | [#x0E94-#x0E97] | [#x0E99-#x0E9F] | [#x0EA1-#x0EA3] | #x0EA5 | #x0EA7 | [#x0EAA-#x0EAB] | [#x0EAD-#x0EAE] | #x0EB0 | [#x0EB2-#x0EB3] | #x0EBD | [#x0EC0-#x0EC4] | [#x0F40-#x0F47] | [#x0F49-#x0F69] | [#x10A0-#x10C5] | [#x10D0-#x10F6] | #x1100 | [#x1102-#x1103] | [#x1105-#x1107] | #x1109 | [#x110B-#x110C] | [#x110E-#x1112] | #x113C | #x113E | #x1140 | #x114C | #x114E | #x1150 | [#x1154-#x1155] | #x1159 | [#x115F-#x1161] | #x1163 | #x1165 | #x1167 | #x1169 | [#x116D-#x116E] | [#x1172-#x1173] | #x1175 | #x119E | #x11A8 | #x11AB | [#x11AE-#x11AF] | [#x11B7-#x11B8] | #x11BA | [#x11BC-#x11C2] | #x11EB | #x11F0 | #x11F9 | [#x1E00-#x1E9B] | [#x1EA0-#x1EF9] | [#x1F00-#x1F15] | [#x1F18-#x1F1D] | [#x1F20-#x1F45] | [#x1F48-#x1F4D] | [#x1F50-#x1F57] | #x1F59 | #x1F5B | #x1F5D | [#x1F5F-#x1F7D] | [#x1F80-#x1FB4] | [#x1FB6-#x1FBC] | #x1FBE | [#x1FC2-#x1FC4] | [#x1FC6-#x1FCC] | [#x1FD0-#x1FD3] | [#x1FD6-#x1FDB] | [#x1FE0-#x1FEC] | [#x1FF2-#x1FF4] | [#x1FF6-#x1FFC] | #x2126 | [#x212A-#x212B] | #x212E | [#x2180-#x2182] | [#x3041-#x3094] | [#x30A1-#x30FA] | [#x3105-#x312C] | [#xAC00-#xD7A3]
并将其转换为最优的条件分支。现在，就好像它这样做了:
if (x > 10 && x < 20) {
return true
}
if (x > 30 && x < 40) {
return true
}
if (x > 50 && x < 60) {
return true
}
// 100 more range checks...
return false
我应该对每个范围执行 if/then 操作，还是有一些技巧可以使其更加优化，因此，如果我们有一个与范围列表中最后一项匹配的值，则不必检查所有内容在它之前？是否有任何特殊技术可以应用于此处进行优化？
这个范围 BaseChar 是每个字符的，所以如果我们的字符与模式中的最后一项匹配，并且我们有一个包含 10000 个项目的字符串，它将执行 100 * 10000 个条件(假设有100 个模式)，而不仅仅是 1 * 10000。
最佳答案
使用这样的条件检查结果效率不高，尤其是当有很多范围需要检查时。当处理器无法预测条件时(例如随机/数据相关行为)或条件太多时(CPU 预测器有一个缓存来记住条件是否经常成功/失败，但该缓存非常小)，则条件很慢)。平均而言，如果所采用的分支的概率分布是均匀的，则一半的条件将被执行，或者如果仔细选择范围，则可能会执行更少的条件(更频繁的必须首先出现以切断计算)。
加快此过程的一种解决方案是使用查找表 (LUT)。如果在循环中完成此计算，查找表可以很好地提高该计算的吞吐量，但当代码很少执行时，它们也会带来高延迟开销。这个想法是为代表 x 的每个单元格预先计算一个 bool 值数组。值(value)。第一个天真的尝试是创建一个大小为 0x10000 的 bool 数组。生成的代码将只是 return lut[x];例如 lut[0] == false , lut[10] == false , lut[11] == true等
LUT 必须保持较小。事实上，LUT 越大，计算速度就越慢(由于将 LUT 保存在缓存中以及可能从 RAM 加载它、生成它等的额外开销)。第一个优化是生成大小为 0x2200 的 LUT (小 8 倍)并仅在 x < 0x2000 时检查它(覆盖 > 95% 的测试范围)这应该非常频繁。否则，使用初始慢速方法测试 <5% 的剩余范围。结果代码如下所示:
if(x < 0x2000)
return lut[x];
return x == 0x2126 || x > x212A && x < 0x212B || ...;
另一种可能的优化是使用位打包来压缩LUT。这个想法是每个字节打包 8 个 bool 值，以便 LUT 只占用 1 KB(在主流平台上)。如果您的目标语言是 C++，请注意 std::vector<bool>已经实现了。否则，必须修改 LUT 的生成，并且lut[x]应替换为 (lut[x >> 3] >> (x & 0x07)) & 0x01 。对于用例来说，这可能会更快，也可能不会更快。
最后，SIMD 指令可用于大幅加快计算速度。事实上，几乎 x86-64 处理器都提供能够计算每条指令 16 个字节或 8 个 16 位值的 SSE 指令集。最新 x86-64 处理器上提供的较新 AVX/AVX2 指令集能够计算每条指令两倍的数据量。最新的 AVX-512 指令集仅在少数最新的 x86-64 处理器上可用，与 AVX/AVX2 相比，每条指令计算的数据量是 AVX/AVX2 的两倍(因此是 SSE 的 4 倍)。如果您知道大多数字符位于特定范围内，则此策略特别好:例如，如果大多数字符是 ASCII 字符，那么您可以非常快速地检查 16/32/64 个字符是否是 ASCII 字符，并仅在 SIMD 中完全执行范围检查一个 ASCII 范围，否则您可以回退到更昂贵的计算(可能使用 LUT 或仍然使用 SIMD 指令)。
我认为在您的情况下使用(可能压缩的)LUT 是最好的策略，因为该方法相对简单(与使用 SIMD 指令相比)并且应该已经比原始解决方案快得多。
关于regex - 如何优化正则表达式中的边界检查？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/69006690/