RFR: 8302871: Speed up StringLatin1.regionMatchesCI
Eirik Bjorsnos
duke at openjdk.org
Mon Feb 20 13:19:20 UTC 2023
On Sat, 18 Feb 2023 19:04:24 GMT, David Schlosnagle <duke at openjdk.org> wrote:
>> This PR suggests we can speed up `StringLatin1.regionMatchesCI` by applying 'the oldest ASCII trick in the book'.
>>
>> The new static method `CharacterDataLatin1.equalsIgnoreCase` compares two latin1 bytes for equality ignoring case. `StringLatin1.regionMatchesCI` is updated to use `equalsIgnoreCase`
>>
>> To verify the correctness of `equalsIgnoreCase`, a new test is added to `EqualsIgnoreCase` with an exhaustive verification that all 256x256 latin1 code point pairs have an `equalsIgnoreCase` consistent with Character.toUpperCase, Character.toLowerCase.
>>
>> Performance is tested for matching and mismatching cases of code point pairs picked from the ASCII letter, ASCII number and latin1 letter ranges. Results in the first comment below.
>
> src/java.base/share/classes/java/lang/CharacterDataLatin1.java.template line 181:
>
>> 179: return ( U <= 'Z' // In range A-Z
>> 180: || (U >= 0xC0 && U <= 0XDE && U != 0xD7)) // ..or A-grave-Thorn, excl. multiplication
>> 181: && U == (b2 & 0xDF); // b2 has same uppercase
>
> I'm curious if the order of comparisons could alter performance to a small degree. For example, it might be interesting to compare various permutations like below to short circuit reject unequal uppercased b2
>
> Suggestion:
>
> // uppercase b1 using 'the oldest ASCII trick in the book'
> int U = b1 & 0xDF;
> return (U == (b2 & 0xDF))
> && ((U >= 'A' && U <= 'Z') // In range A-Z
> || (U >= 0xC0 && U <= 0XDE && U != 0xD7)) // ..or A-grave-Thorn, excl. multiplication
Yeah, as you noticed this code is tricky and sensitive to the order of operations. I did some quite extensive exploration before ending on the current structure. This particular one seems to improve rejection somewhat at the cost of matches.
Since rejection is relatively speaking already very fast, I think we should favour fast matching here.
Results:
enchmark (codePoints) (size) Mode Cnt Score Error Units
RegionMatchesIC.Latin1.regionMatchesIC ascii-match 1024 avgt 15 917.796 ± 20.285 ns/op
RegionMatchesIC.Latin1.regionMatchesIC ascii-mismatch 1024 avgt 15 4.367 ± 0.348 ns/op
RegionMatchesIC.Latin1.regionMatchesIC number-match 1024 avgt 15 399.656 ± 10.703 ns/op
RegionMatchesIC.Latin1.regionMatchesIC number-mismatch 1024 avgt 15 4.361 ± 0.664 ns/op
RegionMatchesIC.Latin1.regionMatchesIC lat1-match 1024 avgt 15 1384.443 ± 22.199 ns/op
RegionMatchesIC.Latin1.regionMatchesIC lat1-mismatch 1024 avgt 15 4.119 ± 0.451 ns/op
-------------
PR: https://git.openjdk.org/jdk/pull/12632
More information about the core-libs-dev
mailing list