Matcher: Avoid excessive String copies.

We avoid calls to GetStringChars on every JNI call to find or findNext.
Given that we now have a moving collector, we always copy on GetStringChars.
Moreover, on Android O, we incur the cost of these copies even if the
String in question is in a non-moveable space because the String might
be compressed. The cost of these calls can quickly add up, especially
for the case where the pattern in question occurs several times in the
string.

Relevant benchmark results are included below. This shows that for a
String size of 64kb with near worst case repetition of patterns, the new
implementation takes ~1/100th the time (8ms vs 737ms)

BEFORE:
Experiment {instrument=runtime, benchmarkMethod=timeReplaceAllTrivialPatternSingleOccurence, vm=default, parameters={s=NON_MOVEABLE}}
  runtime(ns): min=1832194.71, 1st qu.=1865190.38, median=1918799.21, mean=1951987.04, 3rd qu.=2032988.61, max=2171749.44
Experiment {instrument=runtime, benchmarkMethod=timeReplaceTrivialPatternAllRepeated, vm=default, parameters={s=MOVEABLE_256}}
  runtime(ns): min=91264.94, 1st qu.=91999.01, median=92500.85, mean=92864.29, 3rd qu.=94001.42, max=94304.77
Experiment {instrument=runtime, benchmarkMethod=timeReplaceTrivialPatternAllRepeated, vm=default, parameters={s=MOVEABLE_1024}}
  runtime(ns): min=460049.96, 1st qu.=464198.96, median=473150.38, mean=477171.31, 3rd qu.=489764.60, max=508391.29
Experiment {instrument=runtime, benchmarkMethod=timeReplaceTrivialPatternAllRepeated, vm=default, parameters={s=NON_MOVEABLE}}
  runtime(ns): min=736209191.00, 1st qu.=736360924.50, median=737412847.00, mean=737419384.78, 3rd qu.=738278240.00, max=738760545.00

AFTER:
Experiment {instrument=runtime, benchmarkMethod=timeReplaceAllTrivialPatternSingleOccurence, vm=default, parameters={s=NON_MOVEABLE}}
  runtime(ns): min=1518890.99, 1st qu.=1528913.92, median=1637897.87, mean=1626845.46, 3rd qu.=1712046.38, max=1750239.83
Experiment {instrument=runtime, benchmarkMethod=timeReplaceTrivialPatternAllRepeated, vm=default, parameters={s=MOVEABLE_256}}
  runtime(ns): min=61491.55, 1st qu.=62453.80, median=63083.26, mean=63023.21, 3rd qu.=63730.98, max=64245.10
Experiment {instrument=runtime, benchmarkMethod=timeReplaceTrivialPatternAllRepeated, vm=default, parameters={s=MOVEABLE_1024}}
  runtime(ns): min=175484.27, 1st qu.=176039.91, median=177751.78, mean=179295.87, 3rd qu.=183334.40, max=187095.50
Experiment {instrument=runtime, benchmarkMethod=timeReplaceTrivialPatternAllRepeated, vm=default, parameters={s=NON_MOVEABLE}}
  runtime(ns): min=8268762.61, 1st qu.=8396197.28, median=8662951.07, mean=8596467.31, 3rd qu.=8731159.36, max=8973943.49

bug: 36366255
bug: 36818684
Test: cts -m CtsLibcoreTestCases
Test: benchmark

Change-Id: Iff07cf2c2ebe89f04289bfa92bcd2469fec349e7

1 files changed, 76 insertions, 0 deletions

diff --git a/benchmarks/src/benchmarks/regression/StringReplaceAllBenchmark.java b/benchmarks/src/benchmarks/regression/StringReplaceAllBenchmark.java
new file mode 100644
index 0000000000..73e797996f
--- /dev/null
+++ b/benchmarks/src/benchmarks/regression/StringReplaceAllBenchmark.java
@@ -0,0 +1,76 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package benchmarks.regression;
+
+import com.google.caliper.Param;
+
+public class StringReplaceAllBenchmark {
+    // NOTE: These estimates of MOVEABLE / NON_MOVEABLE are based on a knowledge of
+    // ART implementation details. They make a difference here because JNI calls related
+    // to strings took different paths depending on whether the String in question was
+    // moveable or not.
+    enum StringLengths {
+        EMPTY(""),
+        MOVEABLE_16(makeString(16)),
+        MOVEABLE_256(makeString(256)),
+        MOVEABLE_1024(makeString(1024)),
+        NON_MOVEABLE(makeString(64 * 1024)),
+        BOOT_IMAGE(java.util.jar.JarFile.MANIFEST_NAME);
+
+        private final String value;
+
+        StringLengths(String s) {
+            this.value = s;
+        }
+    }
+
+    private static final String makeString(int length) {
+        final String sequence8 = "abcdefghijklmnop";
+        final int numAppends = (length / 16) - 1;
+        StringBuilder stringBuilder = new StringBuilder(length);
+
+        // (n-1) occurences of "abcdefghijklmnop"
+        for (int i = 0; i < numAppends; ++i) {
+            stringBuilder.append(sequence8);
+        }
+
+        // and one final occurence of qrstuvwx.
+        stringBuilder.append("qrstuvwx");
+
+        return stringBuilder.toString();
+    }
+
+    @Param private StringLengths s;
+
+    public void timeReplaceAllTrivialPatternNonExistent(int reps) {
+        for (int i = 0; i < reps; ++i) {
+            s.value.replaceAll("fish", "0");
+        }
+    }
+
+    public void timeReplaceTrivialPatternAllRepeated(int reps) {
+        for (int i = 0; i < reps; ++i) {
+            s.value.replaceAll("jklm", "0");
+        }
+    }
+
+    public void timeReplaceAllTrivialPatternSingleOccurence(int reps) {
+        for (int i = 0; i < reps; ++i) {
+            s.value.replaceAll("qrst", "0");
+        }
+    }
+}