<i18n dev> RFR: 8365675: Add String Unicode Case-Folding Support [v6]
Xueming Shen
sherman at openjdk.org
Tue Oct 28 20:17:49 UTC 2025
On Sat, 18 Oct 2025 08:50:48 GMT, Xueming Shen <sherman at openjdk.org> wrote:
>> src/java.base/share/classes/java/lang/StringLatin1.java line 194:
>>
>>> 192: char[] folded2 = null;
>>> 193: int k1 = 0, k2 = 0, fk1 = 0, fk2 = 0;
>>> 194: while ((k1 < len1 || folded1 != null && fk1 < folded1.length) &&
>>
>> Many suggestions come to mind here on the algorithm, to optimize performance.
>> For example, many strings will have identical prefixes. Using Arrays.mismatch could quickly skip over the identical prefix.
>> Consider using code points (or a long, packing 4 chars) for the folded replacements, to avoid having to step through chars in char arrays. CaseFolding.foldIfDefined could return the full expansion as a long.
>> It may be profitable to use Arrays.mismatch again after expanded characters are determined to be equal.
>>
>> Take another look at the data structure storing and doing the lookup of foldIfDefined both to increase the lookup performance.
>
> With the following changes
>
> - Use int[] / code point storage instead of char[] / char for folding data.
> - Add a fast path for Latin-1 vs. Latin-1 comparisons.
> - Speed up the UTF-16 path as well.
>
> The only remaining “slow” path is Latin-1 vs. UTF-16 for now.
> Would appreciate some eagle eyes on the new fast-path implementation. The tests suggest it’s working as expected :-)
>
> **StringCompareToFoldCase.latin1UTF16 avgt 15 23.959 ± 2.357 ns/op
> StringCompareToFoldCase.latin1UTF16EQ avgt 15 22.455 ± 0.104 ns/op
> StringCompareToFoldCase.latin1UTF16EQFC avgt 15 32.782 ± 0.962 ns/op
> StringCompareToFoldCase.latin1UTF16FC avgt 15 32.581 ± 0.725 ns/op**
>
>
> Benchmark Mode Cnt Score Error Units
> StringCompareToFoldCase.asciiLower avgt 15 17.983 ± 0.208 ns/op
> StringCompareToFoldCase.asciiLowerEQ avgt 15 9.986 ± 0.254 ns/op
> StringCompareToFoldCase.asciiLowerEQFC avgt 15 10.781 ± 0.161 ns/op
> StringCompareToFoldCase.asciiLowerFC avgt 15 10.274 ± 0.136 ns/op
> StringCompareToFoldCase.asciiUpperLower avgt 15 12.465 ± 0.409 ns/op
> StringCompareToFoldCase.asciiUpperLowerEQ avgt 15 10.961 ± 0.407 ns/op
> StringCompareToFoldCase.asciiUpperLowerEQFC avgt 15 9.157 ± 0.166 ns/op
> StringCompareToFoldCase.asciiUpperLowerFC avgt 15 9.228 ± 0.254 ns/op
> StringCompareToFoldCase.asciiWithDFFC avgt 15 57.603 ± 1.540 ns/op
> StringCompareToFoldCase.greekLower avgt 15 39.593 ± 0.128 ns/op
> StringCompareToFoldCase.greekLowerEQ avgt 15 39.249 ± 0.032 ns/op
> StringCompareToFoldCase.greekLowerEQFC avgt 15 13.993 ± 0.346 ns/op
> StringCompareToFoldCase.greekLowerFC avgt 15 14.030 ± 0.454 ns/op
> StringCompareToFoldCase.greekUpperLower avgt 15 7.137 ± 0.130 ns/op
> StringCompareToFoldCase.greekUpperLowerEQ avgt 15 7.496 ± 0.104 ns/op
> StringCompareToFoldCase.greekUpperLowerEQFC avgt 15 6.203 ± 0.316 ns/op
> StringCompareToFoldCase.greekUpperLowerFC avgt 15 6.235 ± 0.256 ns/op
> StringCompareToFoldCase.latin1UTF16 avgt 15 23.959 ± 2.357 ns/op
> StringCompareToFoldCase.latin1UTF16EQ avgt 15 22.455 ± 0.104 ns/op
> StringCompareToFoldCase.latin1UTF16EQFC avgt 15 32.782 ± 0.962 ns/op
> StringCompareToFoldCase.latin1UTF16FC avgt 15 32.581 ± 0.725 ns/op
> StringCompareToFoldCase.supLower avgt 15 54.918 ± 0.809 ns/op
> StringCompa...
Experimenting with Arrays.mismatch at the beginning of the array iteration as
int k = ArraysSupport.mismatch(value, other, lim);
if (k < 0)
return len - olen;
for (; k < lim; k++) {
....
}
The benchmark results suggest that it does help 'dramatically' when the compared strings share with the same prefix. For example those "UpperLower" test cases (which shares the same upper cases text prefix. However it is also relatively expensive, with a 20%-ish overhead when the strings do not share the same string text but are case-insensitively equals. I would suggest let's leave it out for now?
### With Arrays.mismatch
Benchmark Mode Cnt Score Error Units
StringCompareToFoldCase.asciiLower avgt 15 15.044 ± 0.751 ns/op
StringCompareToFoldCase.asciiLowerEQ avgt 15 10.033 ± 0.366 ns/op
StringCompareToFoldCase.asciiLowerEQFC avgt 15 12.094 ± 0.288 ns/op
StringCompareToFoldCase.asciiLowerFC avgt 15 12.513 ± 0.290 ns/op
StringCompareToFoldCase.asciiUpperLower avgt 15 11.716 ± 0.471 ns/op
StringCompareToFoldCase.asciiUpperLowerEQ avgt 15 11.120 ± 0.458 ns/op
StringCompareToFoldCase.asciiUpperLowerEQFC avgt 15 7.544 ± 0.103 ns/op
StringCompareToFoldCase.asciiUpperLowerFC avgt 15 7.384 ± 0.167 ns/op
StringCompareToFoldCase.asciiWithDFFC avgt 15 54.949 ± 1.260 ns/op
StringCompareToFoldCase.greekLower avgt 15 39.492 ± 0.124 ns/op
StringCompareToFoldCase.greekLowerEQ avgt 15 39.266 ± 0.071 ns/op
StringCompareToFoldCase.greekLowerEQFC avgt 15 28.049 ± 0.292 ns/op
StringCompareToFoldCase.greekLowerFC avgt 15 28.272 ± 0.115 ns/op
StringCompareToFoldCase.greekUpperLower avgt 15 7.103 ± 0.052 ns/op
StringCompareToFoldCase.greekUpperLowerEQ avgt 15 7.439 ± 0.079 ns/op
StringCompareToFoldCase.greekUpperLowerEQFC avgt 15 2.716 ± 0.138 ns/op
StringCompareToFoldCase.greekUpperLowerFC avgt 15 2.628 ± 0.051 ns/op
StringCompareToFoldCase.latin1UTF16 avgt 15 23.147 ± 0.094 ns/op
StringCompareToFoldCase.latin1UTF16EQ avgt 15 22.626 ± 0.081 ns/op
StringCompareToFoldCase.latin1UTF16EQFC avgt 15 38.453 ± 0.697 ns/op
StringCompareToFoldCase.latin1UTF16FC avgt 15 38.464 ± 0.441 ns/op
StringCompareToFoldCase.supLower avgt 15 54.443 ± 0.162 ns/op
StringCompareToFoldCase.supLowerEQ avgt 15 54.980 ± 0.232 ns/op
StringCompareToFoldCase.supLowerEQFC avgt 15 25.552 ± 0.163 ns/op
StringCompareToFoldCase.supLowerFC avgt 15 25.477 ± 0.215 ns/op
StringCompareToFoldCase.supUpperLower avgt 15 14.525 ± 0.071 ns/op
StringCompareToFoldCase.supUpperLowerEQ avgt 15 14.691 ± 0.082 ns/op
StringCompareToFoldCase.supUpperLowerEQFC avgt 15 2.748 ± 0.166 ns/op
StringCompareToFoldCase.supUpperLowerFC avgt 15 2.616 ± 0.029 ns/op
vs
### Without Arrays.mismatch
Benchmark Mode Cnt Score Error Units
StringCompareToFoldCase.asciiLower avgt 15 15.793 ± 1.080 ns/op
StringCompareToFoldCase.asciiLowerEQ avgt 15 9.862 ± 0.221 ns/op
StringCompareToFoldCase.asciiLowerEQFC avgt 15 10.681 ± 0.133 ns/op
StringCompareToFoldCase.asciiLowerFC avgt 15 10.220 ± 0.105 ns/op
StringCompareToFoldCase.asciiUpperLower avgt 15 11.996 ± 0.649 ns/op
StringCompareToFoldCase.asciiUpperLowerEQ avgt 15 10.823 ± 0.353 ns/op
StringCompareToFoldCase.asciiUpperLowerEQFC avgt 15 9.199 ± 0.347 ns/op
StringCompareToFoldCase.asciiUpperLowerFC avgt 15 9.033 ± 0.144 ns/op
StringCompareToFoldCase.asciiWithDFFC avgt 15 54.892 ± 1.049 ns/op
StringCompareToFoldCase.greekLower avgt 15 39.568 ± 0.107 ns/op
StringCompareToFoldCase.greekLowerEQ avgt 15 39.287 ± 0.068 ns/op
StringCompareToFoldCase.greekLowerEQFC avgt 15 22.800 ± 0.347 ns/op
StringCompareToFoldCase.greekLowerFC avgt 15 22.794 ± 0.317 ns/op
StringCompareToFoldCase.greekUpperLower avgt 15 7.147 ± 0.072 ns/op
StringCompareToFoldCase.greekUpperLowerEQ avgt 15 7.499 ± 0.106 ns/op
StringCompareToFoldCase.greekUpperLowerEQFC avgt 15 6.958 ± 0.204 ns/op
StringCompareToFoldCase.greekUpperLowerFC avgt 15 7.179 ± 0.188 ns/op
StringCompareToFoldCase.latin1UTF16 avgt 15 25.787 ± 1.940 ns/op
StringCompareToFoldCase.latin1UTF16EQ avgt 15 22.602 ± 0.106 ns/op
StringCompareToFoldCase.latin1UTF16EQFC avgt 15 31.317 ± 0.668 ns/op
StringCompareToFoldCase.latin1UTF16FC avgt 15 30.881 ± 0.622 ns/op
StringCompareToFoldCase.supLower avgt 15 55.771 ± 0.718 ns/op
StringCompareToFoldCase.supLowerEQ avgt 15 55.444 ± 0.535 ns/op
StringCompareToFoldCase.supLowerEQFC avgt 15 31.180 ± 0.184 ns/op
StringCompareToFoldCase.supLowerFC avgt 15 31.269 ± 0.465 ns/op
StringCompareToFoldCase.supUpperLower avgt 15 14.386 ± 0.150 ns/op
StringCompareToFoldCase.supUpperLowerEQ avgt 15 14.780 ± 0.104 ns/op
StringCompareToFoldCase.supUpperLowerEQFC avgt 15 13.733 ± 0.284 ns/op
StringCompareToFoldCase.supUpperLowerFC avgt 15 13.607 ± 0.166 ns/op
-------------
PR Review Comment: https://git.openjdk.org/jdk/pull/27628#discussion_r2470912393
More information about the i18n-dev
mailing list