Fast-path ASCII character class matching

milseman commented 1 year ago

Based on top of https://github.com/apple/swift-experimental-string-processing/pull/689.

Needs the same bounds checking story fixed as https://github.com/apple/swift-experimental-string-processing/pull/689
Need to refactor AsciiBitset
- Inverting a bitset and inverting the semantics are two separate things
- E.g. 😀 never matches an ASCII bitset no matter what bits are set or inverted, but it will match an inverted ASCII character class because that inversion affects the semantics of a match
- String processing logic doesn't really belong on the type, this is the only usage place
Need to refactor some of the quickASCIICharacter for more refined semantics
- Take isScalarSemantics, take allow-CR-LF, etc.

Performance relative to https://github.com/apple/swift-experimental-string-processing/pull/689 (which in turn is a significant improvement over main):

=== Regressions ======================================================================
- symDiffCCC_All                          48.5ms    48.2ms  342µs       0.7%
- SubtractionCCC_All                      21.2ms    20.9ms  243µs       1.2%
- Words_All_Scalar                        12.4ms    12.3ms  117µs       0.9%
- LiteralSearchNotFound_All               6.6ms 6.51ms  90.9µs      1.4%
- LiteralSearchNotFound_All_Scalar        5.88ms    5.83ms  48.5µs      0.8%
- EagarQuantWithTerminal_Whole_Scalar     845µs 812µs   33.5µs      4.1%
=== Improvements =====================================================================
- EmailLookahead_All                      19.9ms    39.1ms  -19.2ms     -49.2%
- EmailLookaheadNoMatches_All             24.9ms    39.1ms  -14.2ms     -36.2%
- EmailLookaheadList                      4ms   9.35ms  -5.35ms     -57.2%
- EmailRFC_All                            59.4ms    63.4ms  -4.04ms     -6.4%
- EmailLookahead_All_Scalar               17.8ms    21.7ms  -3.85ms     -17.8%
- CaseInsensitiveCCC_All_Scalar           6.32ms    10.1ms  -3.73ms     -37.1%
- CaseInsensitiveCCC_All                  6.36ms    9.95ms  -3.59ms     -36.1%
- EmailLookaheadNoMatches_All_Scalar      22.7ms    26.1ms  -3.4ms      -13.0%
- InvertedCCC_All                         16.8ms    20.1ms  -3.24ms     -16.1%
- InvertedCCC_All_Scalar                  16.8ms    20ms    -3.15ms     -15.8%
- BasicRangeCCC_All                       6.36ms    9.14ms  -2.77ms     -30.3%
- BasicCCC_All                            5.93ms    8.68ms  -2.75ms     -31.6%
- BasicCCC_All_Scalar                     5.94ms    8.65ms  -2.71ms     -31.3%
- BasicRangeCCC_All_Scalar                6.43ms    9.13ms  -2.7ms      -29.5%
- EmailRFCNoMatches_All_Scalar            124ms 126ms   -2.66ms     -2.1%
- EmailRFC_All_Scalar                     45.7ms    47.1ms  -1.4ms      -3.0%
- IPv6Address                             2.58ms    3.77ms  -1.19ms     -31.5%
- EmojiRegex_All                          71.6ms    72.7ms  -1.09ms     -1.5%
- EmailLookaheadList_Scalar               3.9ms 4.92ms  -1.02ms     -20.8%
- MACAddress                              2.37ms    2.8ms   -429µs      -15.3%
- Css_All                                 3.31ms    3.7ms   -392µs      -10.6%
- GraphemeBreakNoCap_All                  3.39ms    3.76ms  -370µs      -9.8%
- LiteralSearch_All                       6.77ms    7.13ms  -363µs      -5.1%
- BasicBuiltinCharacterClass_All          8.26ms    8.49ms  -225µs      -2.7%
- HangulSyllable_All                      6.91ms    7.14ms  -224µs      -3.1%
- GraphemeBreakNoCap_All_Scalar           3.16ms    3.38ms  -221µs      -6.5%
- IPv4Address                             2.34ms    2.55ms  -203µs      -8.0%
- IPv6Address_Scalar                      2.41ms    2.61ms  -202µs      -7.7%
- ReluctantQuantWithTerminal_Whole_Scalar 6.42ms    6.59ms  -169µs      -2.6%
- MACAddress_Scalar                       2.29ms    2.42ms  -135µs      -5.6%
- HangulSyllable_All_Scalar               6.24ms    6.37ms  -133µs      -2.1%
- LiteralSearch_All_Scalar                5.99ms    6.1ms   -103µs      -1.7%
- Css_All_Scalar                          3.05ms    3.15ms  -97µs       -3.1%
- ReluctantQuantWithTerminal_Whole        6.46ms    6.56ms  -95.5µs     -1.5%
- AnchoredNotFound_Whole_Scalar           5.44ms    5.5ms   -56µs       -1.0%
- IPv4Address_Scalar                      2.2ms 2.25ms  -51µs       -2.3%
- Lines_All_Scalar                        1.71ms    1.74ms  -35.2µs     -2.0%
- Lines_All                               1.73ms    1.76ms  -25.7µs     -1.5%
- EagarQuantWithTerminal_Whole            815µs 834µs   -18.7µs     -2.2%

milseman commented 1 year ago

It makes sense to pull out isInverted into the instruction encoding, which also motivates some more refactoring of instruction payload encoding. I'll be working on some cleanups and refactorings to help motivate and enable this first.

milseman commented 10 months ago

Reviving this to focus on just the ASCII-character fast path. These are the perf numbers now:

=== Regressions ======================================================================
- AnchoredNotFound_First                  9.86ms    8.92ms  941µs       10.5%
- AnchoredNotFound_All                    14.6ms    13.7ms  901µs       6.6%
- AnchoredNotFound_First_Scalar           5.99ms    5.38ms  616µs       11.5%
- BasicBuiltinCharacterClass_All_Scalar   7.7ms 7.11ms  589µs       8.3%
- AnchoredNotFound_All_Scalar             9.67ms    9.1ms   570µs       6.3%
- DiceRollsInText_All                     41.9ms    41.4ms  563µs       1.4%
- DiceRollsInText_All_Scalar              39.3ms    38.9ms  356µs       0.9%
- Numbers_All                             6.01ms    5.83ms  184µs       3.2%
- Numbers_All_Scalar                      5.26ms    5.09ms  178µs       3.5%
- IntersectionCCC_All                     22.1ms    21.9ms  178µs       0.8%
- IntersectionCCC_All_Scalar              22.2ms    22ms    168µs       0.8%
- LiteralSearchNotFound_All_Scalar        5.69ms    5.54ms  157µs       2.8%
- SubtractionCCC_All_Scalar               21.3ms    21.1ms  148µs       0.7%
- Words_All_Scalar                        12.2ms    12ms    147µs       1.2%
- SubtractionCCC_All                      21.3ms    21.1ms  146µs       0.7%
- LiteralSearch_All                       6.81ms    6.67ms  140µs       2.1%
- LiteralSearch_All_Scalar                5.87ms    5.74ms  133µs       2.3%
- NotFound_All                            7.31ms    7.19ms  118µs       1.6%
- LiteralSearchNotFound_All               6.61ms    6.5ms   110µs       1.7%
- NotFound_All_Scalar                     6.33ms    6.23ms  100µs       1.6%
- HangulSyllable_First_Scalar             2.92ms    2.85ms  72.8µs      2.6%
- HangulSyllable_First                    3.37ms    3.3ms   70.2µs      2.1%
=== Improvements =====================================================================
- EmailLookahead_All                      19.5ms    40.6ms  -21.1ms     -52.1%
- EmailLookaheadNoMatches_All             23ms  39.1ms  -16.1ms     -41.2%
- EmailLookaheadList                      3.94ms    9.7ms   -5.77ms     -59.4%
- EmailRFC_All                            64ms  68.8ms  -4.81ms     -7.0%
- CaseInsensitiveCCC_All_Scalar           6.46ms    11ms    -4.54ms     -41.3%
- EmailLookahead_All_Scalar               17.3ms    21.6ms  -4.32ms     -20.0%
- CaseInsensitiveCCC_All                  6.47ms    10.7ms  -4.25ms     -39.6%
- BasicCCC_All                            6.03ms    9.56ms  -3.53ms     -36.9%
- BasicCCC_All_Scalar                     6.03ms    9.56ms  -3.52ms     -36.9%
- BasicRangeCCC_All                       6.5ms 10ms    -3.52ms     -35.1%
- BasicRangeCCC_All_Scalar                6.51ms    10ms    -3.5ms      -34.9%
- EmailLookaheadNoMatches_All_Scalar      20.7ms    23.9ms  -3.26ms     -13.6%
- InvertedCCC_All_Scalar                  16.8ms    19.8ms  -2.99ms     -15.1%
- EmailRFCNoMatches_All                   161ms 164ms   -2.96ms     -1.8%
- InvertedCCC_All                         17ms  19.9ms  -2.93ms     -14.7%
- IPv6Address                             2.58ms    3.86ms  -1.28ms     -33.2%
- EmailLookaheadList_Scalar               3.7ms 4.82ms  -1.12ms     -23.2%
- EmailRFC_All_Scalar                     45.3ms    46.3ms  -1.05ms     -2.3%
- EmailRFCNoMatches_All_Scalar            122ms 123ms   -801µs      -0.7%
- MACAddress                              2.4ms 2.82ms  -417µs      -14.8%
- Css_All                                 3.27ms    3.67ms  -401µs      -10.9%
- CompilerMessages_All_Scalar             75.1ms    75.5ms  -371µs      -0.5%
- BasicBuiltinCharacterClass_All          8.27ms    8.62ms  -343µs      -4.0%
- ReluctantQuantWithTerminal_Whole_Scalar 5.22ms    5.49ms  -270µs      -4.9%
- GraphemeBreakNoCap_All                  3.53ms    3.77ms  -241µs      -6.4%
- IPv6Address_Scalar                      2.42ms    2.6ms   -181µs      -7.0%
- ReluctantQuantWithTerminal_Whole        5.29ms    5.46ms  -170µs      -3.1%
- IPv4Address                             2.24ms    2.4ms   -159µs      -6.6%
- HangulSyllable_All                      6.82ms    6.94ms  -111µs      -1.6%
- MACAddress_Scalar                       2.28ms    2.39ms  -106µs      -4.4%
- ReluctantQuant_Whole_Scalar             9.2ms 9.3ms   -102µs      -1.1%
- HangulSyllable_All_Scalar               6.03ms    6.13ms  -98.9µs     -1.6%
- GraphemeBreakNoCap_All_Scalar           3.12ms    3.17ms  -56.5µs     -1.8%
- Css_All_Scalar                          2.91ms    2.96ms  -47µs       -1.6%
- IPv4Address_Scalar                      2.07ms    2.1ms   -23µs       -1.1%
- EagarQuantWithTerminal_Whole_Scalar     781µs 790µs   -8.83µs     -1.1%

milseman commented 10 months ago

@swift-ci please test

swiftlang / swift-experimental-string-processing

Fast-path ASCII character class matching #690