RFR: 8302163: Speed up various String comparison methods with ArraysSupport.mismatch [v2]

[Eirik Bjorsnos]

On Mon, 13 Feb 2023 16:10:14 GMT, Claes Redestad <redestad at openjdk.org> wrote:

>> We can improve various String methods such as `startsWith`, `endsWith` and `regionMatches` by leveraging the intrinsified mismatch methods in `ArraysSupport`.
>
> Claes Redestad has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Clarify coder shift in startsWith

Case-insensitive regionMatches could be improved by using ArraysSupport.mismatch to skip over long common substrings:

PR:


Benchmark                          (size)  (utf16)  Mode  Cnt    Score   Error  Units
StringComparisons.regionMatchesCI       6    false  avgt   15    8.248 ± 0.427  ns/op
StringComparisons.regionMatchesCI      15    false  avgt   15   11.408 ± 0.429  ns/op
StringComparisons.regionMatchesCI    1024    false  avgt   15  328.796 ± 7.191  ns/op


Arrays.mismatch:

Benchmark                          (size)  (utf16)  Mode  Cnt   Score   Error  Units
StringComparisons.regionMatchesCI       6    false  avgt   15  10.608 ± 0.302  ns/op
StringComparisons.regionMatchesCI      15    false  avgt   15   8.772 ± 0.347  ns/op
StringComparisons.regionMatchesCI    1024    false  avgt   15  31.070 ± 1.783  ns/op


Patch on top of your PR:


Index: src/java.base/share/classes/java/lang/StringLatin1.java
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/src/java.base/share/classes/java/lang/StringLatin1.java b/src/java.base/share/classes/java/lang/StringLatin1.java
--- a/src/java.base/share/classes/java/lang/StringLatin1.java	(revision 6cac333d8f9f34e16168447c60f28a6b0d31623f)
+++ b/src/java.base/share/classes/java/lang/StringLatin1.java	(date 1676305817928)
@@ -384,6 +384,14 @@
                                           byte[] other, int ooffset, int len) {
         int last = toffset + len;
         while (toffset < last) {
+            int mismatch = ArraysSupport.mismatch(value, toffset, other, ooffset, len);
+            if (mismatch == -1) {
+                return true;
+            } else {
+                toffset += mismatch;
+                ooffset += mismatch;
+                len -= mismatch + 1;
+            }
             char c1 = (char)(value[toffset++] & 0xff);
             char c2 = (char)(other[ooffset++] & 0xff);
             if (c1 == c2) {
Index: test/micro/org/openjdk/bench/java/lang/StringComparisons.java
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/test/micro/org/openjdk/bench/java/lang/StringComparisons.java b/test/micro/org/openjdk/bench/java/lang/StringComparisons.java
--- a/test/micro/org/openjdk/bench/java/lang/StringComparisons.java	(revision 6cac333d8f9f34e16168447c60f28a6b0d31623f)
+++ b/test/micro/org/openjdk/bench/java/lang/StringComparisons.java	(date 1676305817914)
@@ -49,6 +49,7 @@
     public String endsWithA;
     public String endsWithB;
     public String startsWithA;
+    public String endsWitha;
 
     @Setup
     public void setup() {
@@ -56,6 +57,7 @@
         string = c.repeat(size);
         equalString = c.repeat(size);
         endsWithA = c.repeat(size).concat("A");
+        endsWitha = c.repeat(size).concat("a");
         endsWithB = c.repeat(size).concat("B");
         startsWithA = "A" + (c.repeat(size));
     }
@@ -75,6 +77,11 @@
         return endsWithA.regionMatches(0, endsWithB, 0, endsWithB.length());
     }
 
+    @Benchmark
+    public boolean regionMatchesIC() {
+        return endsWithA.regionMatches(true,0, endsWitha, 0, endsWitha.length());
+    }
+
     @Benchmark
     public boolean regionMatchesRange() {
         return startsWithA.regionMatches(1, endsWithB, 0, endsWithB.length() - 1);

-------------

PR: https://git.openjdk.org/jdk/pull/12528