Add fast path for ASCII case folding #159
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
I've cherry-picked the newly added benchmarks on top of master as well for a baseline comparison (this is available at https://github.com/mszabo-wikia/re2j/tree/case-insensitive-benchmark). I executed the benchmarks using OpenJDK 8u332 on a 2021 M1 Pro. Here are the baseline results: And the results with the ASCII case folding improvements from this patch: |
adonovan
reviewed
Jul 7, 2022
| // for the likely scenario where both runes are ASCII characters. | ||
| static boolean equalsIgnoreCase(int r1, int r2) { | ||
| // Runes already match, or one of them is EOF | ||
| if (r1 < 0 || r2 < 0 || r1 == r2) { |
There was a problem hiding this comment.
That -1 means EOF should be noted in the doc comment above.
adonovan
approved these changes
Jul 7, 2022
One of our production services uses re2j to match several hundred mostly case-insensitive patterns of varying complexity against text. We observed that approximately 12% of CPU time was being spent in toLowerCase() as called from simpleFold(), due to the necessity of doing at least one character data lookup per Inst.Rune in the common case that the input rune being examined did not match the instruction. As a fix, implement a method equalsIgnoreCase() that performs Unicode-aware case-insensitive comparison between two runes, with a fast path for the common case where both input runes are ASCII, and use it in Inst for single-rune case-insensitive comparison. This takes character data lookups out of the hot path. The existing re2j benchmarks did not exercise case-insensitive patterns, so add a new benchmark that executes a mostly ASCII regex pattern on a text containing a mix of ASCII and Unicode characters (generated using a Hungarian "lorem ipsum" text generator). Also add unit tests for the new equality comparison logic. Signed-off-by: Máté Szabó <mszabo@fandom.com>
784eac3 to
da63ef6
Compare
Codecov Report
@@ Coverage Diff @@
## master #159 +/- ##
==========================================
- Coverage 89.13% 89.06% -0.08%
==========================================
Files 19 19
Lines 3029 3037 +8
Branches 613 618 +5
==========================================
+ Hits 2700 2705 +5
- Misses 188 189 +1
- Partials 141 143 +2
Continue to review full report at Codecov.
|
|
Thanks! |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
One of our production services uses re2j to match several hundred mostly
case-insensitive patterns of varying complexity against text.
We observed that approximately 12% of CPU time was being spent in
toLowerCase() as called from simpleFold(), due to the necessity of doing
at least one character data lookup per Inst.Rune in the common case that
the input rune being examined did not match the instruction.
As a fix, implement a method equalsIgnoreCase() that performs
Unicode-aware case-insensitive comparison between two runes, with a fast
path for the common case where both input runes are ASCII, and use it in
Inst for single-rune case-insensitive comparison. This takes character
data lookups out of the hot path.
The existing re2j benchmarks did not exercise case-insensitive patterns,
so add a new benchmark that executes a mostly ASCII regex pattern on a
text containing a mix of ASCII and Unicode characters (generated using
a Hungarian "lorem ipsum" text generator).
Also add unit tests for the new equality comparison logic.