swiftlang / swift-experimental-string-processing

An early experimental general-purpose pattern matching engine for Swift.
Apache License 2.0
278 stars 47 forks source link

Overhaul quantification fast-path #689

Closed milseman closed 1 year ago

milseman commented 1 year ago

Overhaul quantification save points and fast path logic, for significant wins in simplicity and performance.

milseman commented 1 year ago
=== Regressions ======================================================================
=== Improvements =====================================================================
- CompilerMessages_All                    93.9ms    102ms   -7.82ms     -7.7%
- CompilerMessages_All_Scalar             78.2ms    85ms    -6.86ms     -8.1%
- DiceRollsInText_All                     43.2ms    46.9ms  -3.71ms     -7.9%
- EmailRFCNoMatches_All                   135ms 138ms   -3.36ms     -2.4%
- DiceRollsInText_All_Scalar              41.1ms    44.3ms  -3.24ms     -7.3%
- CaseInsensitiveCCC_All_Scalar           9.81ms    11.7ms  -1.94ms     -16.5%
- BasicCCC_All_Scalar                     8.67ms    10.6ms  -1.94ms     -18.2%
- BasicCCC_All                            8.65ms    10.6ms  -1.93ms     -18.3%
- CaseInsensitiveCCC_All                  9.81ms    11.7ms  -1.93ms     -16.4%
- BasicRangeCCC_All_Scalar                9.16ms    11ms    -1.89ms     -17.1%
- EmailLookaheadNoMatches_All             39.2ms    41.1ms  -1.88ms     -4.6%
- BasicRangeCCC_All                       9.29ms    11ms    -1.73ms     -15.7%
- EmailLookaheadNoMatches_All_Scalar      26.1ms    27.8ms  -1.72ms     -6.2%
- Numbers_All_Scalar                      5.4ms 6.84ms  -1.45ms     -21.1%
- symDiffCCC_All                          48.3ms    49.6ms  -1.34ms     -2.7%
- symDiffCCC_All_Scalar                   48.2ms    49.5ms  -1.32ms     -2.7%
- Numbers_All                             5.9ms 7.18ms  -1.28ms     -17.8%
- EmailLookahead_All                      38.8ms    39.9ms  -1.06ms     -2.7%
- EmailLookahead_All_Scalar               21.7ms    22.6ms  -899µs      -4.0%
- EmojiRegex_All_Scalar                   48.9ms    49.7ms  -882µs      -1.8%
- Words_All                               12.8ms    13.6ms  -805µs      -5.9%
- EmailRFC_All                            62.8ms    63.6ms  -767µs      -1.2%
- EagarQuantWithTerminal_Whole            830µs 1.49ms  -657µs      -44.2%
- InvertedCCC_All                         19.9ms    20.5ms  -613µs      -3.0%
- EagarQuantWithTerminal_Whole_Scalar     813µs 1.4ms   -588µs      -41.9%
- InvertedCCC_All_Scalar                  19.9ms    20.4ms  -539µs      -2.6%
- GraphemeBreakNoCap_All                  3.77ms    4.28ms  -516µs      -12.0%
- Words_All_Scalar                        12.5ms    13ms    -513µs      -3.9%
- BasicBuiltinCharacterClass_All          8.37ms    8.87ms  -493µs      -5.6%
- GraphemeBreakNoCap_All_Scalar           3.29ms    3.73ms  -436µs      -11.7%
- IntersectionCCC_All_Scalar              21.5ms    21.9ms  -360µs      -1.6%
- EmailLookaheadList                      9.34ms    9.68ms  -341µs      -3.5%
- DiceNotation                            4.65ms    4.99ms  -332µs      -6.7%
- SubtractionCCC_All                      21ms  21.3ms  -313µs      -1.5%
- SubtractionCCC_All_Scalar               21ms  21.3ms  -292µs      -1.4%
- IntersectionCCC_All                     21.6ms    21.9ms  -284µs      -1.3%
- AnchoredNotFound_Whole                  8.62ms    8.88ms  -258µs      -2.9%
- EmailLookaheadList_Scalar               4.91ms    5.16ms  -249µs      -4.8%
- DiceNotation_Scalar                     4.43ms    4.67ms  -240µs      -5.1%
- IPv6Address_Scalar                      2.59ms    2.81ms  -229µs      -8.1%
- LiteralSearch_All                       6.78ms    6.99ms  -211µs      -3.0%
- AnchoredNotFound_Whole_Scalar           5.45ms    5.64ms  -193µs      -3.4%
- EmailBuiltinCharacterClass_All_Scalar   12.3ms    12.5ms  -178µs      -1.4%
- ReluctantQuantWithTerminal_Whole        6.48ms    6.61ms  -127µs      -1.9%
- NotFound_All                            7.19ms    7.31ms  -122µs      -1.7%
- ReluctantQuantWithTerminal_Whole_Scalar 6.48ms    6.58ms  -104µs      -1.6%
- Css_All_Scalar                          3.15ms    3.25ms  -102µs      -3.1%
- LiteralSearchNotFound_All               6.58ms    6.68ms  -100µs      -1.5%
- Css_All                                 3.64ms    3.74ms  -99.4µs     -2.7%
- HangulSyllable_All                      7.01ms    7.11ms  -98.4µs     -1.4%
- Lines_All                               1.75ms    1.85ms  -95.8µs     -5.2%
- BasicBuiltinCharacterClass_All_Scalar   7.59ms    7.68ms  -94.4µs     -1.2%
- MACAddress                              2.81ms    2.91ms  -92.8µs     -3.2%
- EmailBuiltinCharacterClass_All          12.6ms    12.6ms  -90.4µs     -0.7%
- IPv6Address                             3.76ms    3.85ms  -90µs       -2.3%
- MACAddress_Scalar                       2.45ms    2.52ms  -67µs       -2.7%
- HangulSyllable_First                    3.37ms    3.43ms  -60.2µs     -1.8%
- HangulSyllable_All_Scalar               6.26ms    6.31ms  -55µs       -0.9%
- NotFound_All_Scalar                     6.47ms    6.51ms  -41.3µs     -0.6%
- HangulSyllable_First_Scalar             3.01ms    3.05ms  -34.6µs     -1.1%
- Lines_All_Scalar                        1.73ms    1.77ms  -32.5µs     -1.8%
milseman commented 1 year ago

Updated numbers:

=== Regressions ======================================================================
- EmailRFCNoMatches_All                   157ms 155ms   1.47ms      0.9%
- IntersectionCCC_All_Scalar              22.4ms    21.9ms  579µs       2.7%
- EmailRFC_All                            67.1ms    66.6ms  537µs       0.8%
- SubtractionCCC_All                      21.5ms    21ms    493µs       2.3%
- SubtractionCCC_All_Scalar               21.5ms    21ms    457µs       2.2%
=== Improvements =====================================================================
- CompilerMessages_All                    92.9ms    98.4ms  -5.49ms     -5.6%
- DiceRollsInText_All                     42.6ms    46.8ms  -4.24ms     -9.1%
- EmailLookaheadNoMatches_All             39.9ms    42.8ms  -2.86ms     -6.7%
- CompilerMessages_All_Scalar             77.3ms    80.1ms  -2.84ms     -3.5%
- DiceRollsInText_All_Scalar              40.2ms    42.9ms  -2.62ms     -6.1%
- CaseInsensitiveCCC_All                  10.4ms    12.8ms  -2.35ms     -18.4%
- CaseInsensitiveCCC_All_Scalar           10.5ms    12.8ms  -2.33ms     -18.2%
- BasicCCC_All                            9.31ms    11.6ms  -2.32ms     -19.9%
- BasicCCC_All_Scalar                     9.31ms    11.6ms  -2.3ms      -19.9%
- BasicRangeCCC_All                       9.72ms    12ms    -2.24ms     -18.7%
- BasicRangeCCC_All_Scalar                9.73ms    12ms    -2.23ms     -18.6%
- EmailLookahead_All                      38.9ms    41ms    -2.11ms     -5.2%
- EmailLookaheadNoMatches_All_Scalar      25.8ms    27.2ms  -1.44ms     -5.3%
- Numbers_All                             5.85ms    7.26ms  -1.41ms     -19.5%
- Numbers_All_Scalar                      5.22ms    6.37ms  -1.15ms     -18.1%
- Words_All                               12.4ms    13.4ms  -996µs      -7.5%
- NotFound_All                            6.98ms    7.61ms  -630µs      -8.3%
- Words_All_Scalar                        12ms  12.6ms  -600µs      -4.7%
- AnchoredNotFound_All                    13.2ms    13.8ms  -597µs      -4.3%
- InvertedCCC_All_Scalar                  19.7ms    20.2ms  -573µs      -2.8%
- EmailLookahead_All_Scalar               21.6ms    22.1ms  -567µs      -2.6%
- AnchoredNotFound_First_Scalar           5.41ms    5.94ms  -531µs      -8.9%
- EmailLookaheadList                      9.35ms    9.88ms  -529µs      -5.3%
- GraphemeBreakNoCap_All                  3.74ms    4.18ms  -445µs      -10.6%
- AnchoredNotFound_First                  8.54ms    8.92ms  -380µs      -4.3%
- HangulSyllable_All                      7ms   7.37ms  -371µs      -5.0%
- LiteralSearch_All                       6.98ms    7.34ms  -360µs      -4.9%
- DiceNotation                            4.53ms    4.89ms  -352µs      -7.2%
- InvertedCCC_All                         19.8ms    20.2ms  -350µs      -1.7%
- GraphemeBreakNoCap_All_Scalar           3.19ms    3.48ms  -286µs      -8.2%
- EmojiRegex_All_Scalar                   48.4ms    48.7ms  -285µs      -0.6%
- EagarQuantWithTerminal_Whole_Scalar     813µs 1.09ms  -280µs      -25.6%
- LiteralSearchNotFound_All               6.79ms    7.06ms  -277µs      -3.9%
- DiceNotation_Scalar                     4.32ms    4.54ms  -226µs      -5.0%
- IPv6Address                             3.66ms    3.88ms  -221µs      -5.7%
- AnchoredNotFound_All_Scalar             9.1ms 9.32ms  -219µs      -2.4%
- Css_All                                 3.66ms    3.85ms  -190µs      -4.9%
- MACAddress_Scalar                       2.3ms 2.48ms  -181µs      -7.3%
- EagarQuantWithTerminal_Whole            824µs 1e+03µs -176µs      -17.6%
- symDiffCCC_All_Scalar                   56.1ms    56.2ms  -164µs      -0.3%
- BasicBuiltinCharacterClass_All_Scalar   7.15ms    7.3ms   -153µs      -2.1%
- NotFound_All_Scalar                     6.16ms    6.31ms  -148µs      -2.3%
- MACAddress                              2.78ms    2.92ms  -140µs      -4.8%
- LiteralSearchNotFound_All_Scalar        5.63ms    5.77ms  -140µs      -2.4%
- BasicBuiltinCharacterClass_All          8.05ms    8.18ms  -132µs      -1.6%
- HangulSyllable_All_Scalar               6ms   6.12ms  -124µs      -2.0%
- LiteralSearch_All_Scalar                5.85ms    5.97ms  -118µs      -2.0%
- HangulSyllable_First                    3.5ms 3.61ms  -116µs      -3.2%
- ReluctantQuantWithTerminal_Whole        6.32ms    6.4ms   -78.5µs     -1.2%
- Css_All_Scalar                          3.01ms    3.09ms  -76.9µs     -2.5%
- HangulSyllable_First_Scalar             2.88ms    2.95ms  -70.3µs     -2.4%
- Lines_All                               1.75ms    1.81ms  -57.9µs     -3.2%
- IPv4Address                             2.43ms    2.47ms  -40.7µs     -1.6%
- Lines_All_Scalar                        1.68ms    1.72ms  -39.1µs     -2.3%
milseman commented 1 year ago

@swift-ci please test