Hello,
I've complitely reworked the patch according to investigation in [1].
1) usage of JavaLangAccess allows to rid reflection completely and access
package-private String.isLatin1 via SharedSecrets only,
so no black wizardry any more
2) now we have only a few cases with noticeable regeression (in statistics I've
marked corresponding rows with exclamation marks)
3) usage of non-copying constructor of String in StringLatin1.newString(byte[])
allows to reduce memory consumption significantly
4) there still could be a patological case when we join an array or collection
with lots of latin Strings and 1 non-latin String as the last element.
In this case we fall back to char[] but waste some time to latiness check.
5) current implementataion is almost regresion-free for non-latin Strings both
in terms of time and memory
6) in general proposed changes are trivial
The benchmarking results can be found below, I've used benchmark [2]
P. S. I've added Martin as according to the first comment [1] he is responsible
for this optimization
With best regards,
Sergey Tsypanov
1. https://bugs.openjdk.java.net/browse/JDK-8148937
2.
https://github.com/stsypanov/strings/blob/master/src/jmh/java/tsypanov/strings/join/StringJoinerBenchmark.java
https://github.com/stsypanov/strings/blob/master/src/main/java/tsypanov/strings/source/string/Joiner.java
Benchmark (count) (latin) (length) Original
Error Patched Error Units
stringJoiner 1 true 1 27.7 ±
1.2 22.1 ± 0.2 ns/op
stringJoiner 1 true 5 27.7 ±
0.1 22.3 ± 0.0 ns/op
stringJoiner 1 true 10 29.0 ±
0.6 23.2 ± 0.0 ns/op
stringJoiner 1 true 100 51.4 ±
0.1 31.4 ± 0.1 ns/op
stringJoiner 5 true 1 71.1 ±
0.4 64.9 ± 0.3 ns/op
stringJoiner 5 true 5 79.5 ±
0.3 65.5 ± 0.3 ns/op
stringJoiner 5 true 10 81.2 ±
0.3 67.7 ± 0.2 ns/op
stringJoiner 5 true 100 150.0 ±
0.4 86.5 ± 0.5 ns/op
stringJoiner 10 true 1 145.5 ±
0.7 142.5 ± 0.4 ns/op
stringJoiner 10 true 5 160.0 ±
0.8 145.6 ± 0.2 ns/op
stringJoiner 10 true 10 165.6 ±
0.4 150.8 ± 0.3 ns/op
stringJoiner 10 true 100 340.2 ±
1.2 189.3 ± 0.4 ns/op
stringJoiner 100 true 1 1114.3 ±
15.9 1372.7 ± 53.0 ns/op !
stringJoiner 100 true 5 1184.2 ±
18.5 1385.9 ± 56.0 ns/op !
stringJoiner 100 true 10 1345.8 ±
13.9 1369.0 ± 2.7 ns/op !
stringJoiner 100 true 100 3156.1 ±
19.1 1844.1 ± 4.1 ns/op
stringJoiner 1 false 1 33.5 ±
0.4 34.9 ± 0.1 ns/op
stringJoiner 1 false 5 33.3 ±
0.3 35.9 ± 0.1 ns/op
stringJoiner 1 false 10 33.8 ±
0.1 35.9 ± 0.1 ns/op
stringJoiner 1 false 100 57.5 ±
0.2 58.3 ± 0.1 ns/op
stringJoiner 5 false 1 82.9 ±
0.5 82.0 ± 0.8 ns/op
stringJoiner 5 false 5 86.0 ±
0.5 84.8 ± 0.9 ns/op
stringJoiner 5 false 10 96.9 ±
0.5 92.5 ± 0.6 ns/op
stringJoiner 5 false 100 224.2 ±
0.6 226.7 ± 0.7 ns/op
stringJoiner 10 false 1 165.7 ±
0.9 167.6 ± 3.2 ns/op
stringJoiner 10 false 5 178.4 ±
0.7 179.6 ± 2.1 ns/op
stringJoiner 10 false 10 191.7 ±
0.9 195.9 ± 2.2 ns/op
stringJoiner 10 false 100 534.4 ±
1.4 534.5 ± 1.3 ns/op
stringJoiner 100 false 1 1435.9 ±
9.5 1428.2 ± 3.2 ns/op
stringJoiner 100 false 5 1618.5 ±
14.3 1595.2 ± 3.7 ns/op
stringJoiner 100 false 10 1898.1 ±
9.4 1860.8 ± 4.7 ns/op
stringJoiner 100 false 100 4247.4 ±
60.7 4150.1 ± 9.1 ns/op
stringJoiner:·gc.alloc.rate.norm 1 true 1 124.0 ±
4.0 96.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 1 true 5 128.0 ±
0.0 96.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 1 true 10 144.0 ±
0.0 104.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 1 true 100 416.0 ±
0.0 192.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 5 true 1 144.0 ±
0.0 104.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 5 true 5 200.0 ±
0.0 120.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 5 true 10 272.0 ±
0.0 144.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 5 true 100 1632.0 ±
0.0 600.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 10 true 1 256.0 ±
0.0 192.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 10 true 5 376.0 ±
0.0 232.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 10 true 10 520.0 ±
0.0 280.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 10 true 100 3224.1 ±
0.0 1184.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 100 true 1 1752.1 ±
5.4 1328.2 ± 5.4 B/op
stringJoiner:·gc.alloc.rate.norm 100 true 5 2952.2 ±
5.4 1728.2 ± 5.4 B/op
stringJoiner:·gc.alloc.rate.norm 100 true 10 4444.4 ±
4.0 2216.2 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 100 true 100 31445.6 ±
4.0 11216.7 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 1 false 1 144.0 ±
0.0 144.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 1 false 5 160.0 ±
0.0 160.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 1 false 10 184.0 ±
0.0 184.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 1 false 100 640.0 ±
0.0 640.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 5 false 1 184.0 ±
0.0 184.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 5 false 5 280.0 ±
0.0 280.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 5 false 10 400.0 ±
0.0 400.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 5 false 100 2664.1 ±
0.0 2664.1 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 10 false 1 320.0 ±
0.0 320.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 10 false 5 520.0 ±
0.0 520.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 10 false 10 760.0 ±
0.0 760.0 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 10 false 100 5264.2 ±
0.0 5264.2 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 100 false 1 2208.2 ±
0.0 2168.2 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 100 false 5 4196.3 ±
6.2 4168.3 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 100 false 10 6704.6 ±
0.0 6664.5 ± 0.0 B/op
stringJoiner:·gc.alloc.rate.norm 100 false 100 51698.1 ±
5.4 51666.3 ± 0.0 B/op
13.02.2020, 21:49, "Brent Christian" <brent.christ...@oracle.com>:
> As a point of interest, some investigation of updating StringJoiner for
> CompactStrings was done a while back.
>
> See https://bugs.openjdk.java.net/browse/JDK-8148937
>
> -Brent
>
> On 2/3/20 2:38 PM, Сергей Цыпанов wrote:
>> Hello,
>>
>> as of JDK14 java.util.StringJoiner still uses char[] as a storage of glued
>> Strings.
>>
>> This applies for the cases when all joined Strings as well as delimiter,
>> prefix and suffix contain only ASCII symbols.
>>
>> As a result when StringJoiner.toString() is invoked, byte[] stored in
>> String is inflated in order to fill in char[] and
>> finally char[] is compressed when constructor of String is called:
>>
>> String delimiter = this.delimiter;
>> char[] chars = new char[this.len + addLen];
>> int k = getChars(this.prefix, chars, 0);
>> if (size > 0) {
>> k += getChars(elts[0], chars, k); // inflate byte[] -> char[]
>>
>> for(int i = 1; i < size; ++i) {
>> k += getChars(delimiter, chars, k);
>> k += getChars(elts[i], chars, k);
>> }
>> }
>>
>> k += getChars(this.suffix, chars, k);
>> return new String(chars); // compress char[] -> byte[]
>>
>> This can be improved by detecting cases when String.isLatin1() returns true
>> for all involved Strings.
>>
>> I've prepared a patch along with benchmark proving that this change is
>> correct and brings improvement.
>> The only concern I have is about String.isLatin1(): as far as String
>> belongs to java.lang and StringJoiner to java.util
>> package-private String.isLatin1() cannot be directly accessed, we need to
>> make it public for successful compilation.
>>
>> Another solution is to create an intermediate utility class located in
>> java.lang which delegates the call to String.isLatin1():
>>
>> package java.lang;
>>
>> public class StringHelper {
>> public static boolean isLatin1(String str) {
>> return str.isLatin1();
>> }
>> }
>>
>> This allows to keep java.lang.String intact and have access to it's
>> package-private method outside of java.lang package.
>>
>> Below I've added results of benchmarking for specified case (all Strings
>> are Latin1). The other case (at least one String is UTF-8) uses existing
>> code so there will be only a tiny regression due to several if-checks.
>>
>> With best regards,
>> Sergey Tsypanov
>>
>> (count) (length) Original
>> Patched Units
>> stringJoiner 1 1 26.7 ± 1.3 38.2 ± 1.1 ns/op
>> stringJoiner 1 5 27.4 ± 0.0 40.5 ± 2.2 ns/op
>> stringJoiner 1 10 29.6 ± 1.9 38.4 ± 1.9 ns/op
>> stringJoiner 1 100 61.1 ± 6.9 47.6 ± 0.6 ns/op
>> stringJoiner 5 1 91.1 ± 6.7 83.6 ± 2.0 ns/op
>> stringJoiner 5 5 96.1 ± 10.7 85.6 ± 1.1 ns/op
>> stringJoiner 5 10 105.5 ± 14.3 84.7 ± 1.1 ns/op
>> stringJoiner 5 100 266.6 ± 30.1 139.6 ± 14.0 ns/op
>> stringJoiner 10 1 190.7 ± 23.0 162.0 ± 2.9 ns/op
>> stringJoiner 10 5 200.0 ± 16.9 167.5 ± 11.0 ns/op
>> stringJoiner 10 10 216.4 ± 12.4 164.8 ± 1.7 ns/op
>> stringJoiner 10 100 545.3 ± 49.7 282.2 ± 12.0 ns/op
>> stringJoiner 100 1 1467.0 ± 90.3 1302.0 ± 18.5 ns/op
>> stringJoiner 100 5 1491.8 ± 166.2 1493.0 ± 135.4 ns/op
>> stringJoiner 100 10 1768.8 ± 160.6 1760.8 ± 111.4 ns/op
>> stringJoiner 100 100 3654.3 ± 113.1 3120.9 ± 175.9 ns/op
>>
>> stringJoiner:·gc.alloc.rate.norm 1 1 120.0 ± 0.0 120.0 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 1 5 128.0 ± 0.0 120.0 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 1 10 144.0 ± 0.0 136.0 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 1 100 416.0 ± 0.0 312.0 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 5 1 144.0 ± 0.0 136.0 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 5 5 200.0 ± 0.0 168.0 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 5 10 272.0 ± 0.0 216.0 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 5 100 1632.0 ± 0.0 1128.0 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 10 1 256.0 ± 0.0 232.0 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 10 5 376.0 ± 0.0 312.0 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 10 10 520.0 ± 0.0 408.0 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 10 100 3224.1 ± 0.0 2216.1 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 100 1 1760.2 ± 14.9 1544.2 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 100 5 2960.3 ± 14.9 2344.2 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 100 10 4440.4 ± 0.0 3336.3 ± 0.0 B/op
>> stringJoiner:·gc.alloc.rate.norm 100 100 31449.3 ± 12.2 21346.7 ± 14.7 B/opdiff --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
+++ b/src/java.base/share/classes/java/lang/StringLatin1.java
@@ -764,8 +764,19 @@
}
public static String newString(byte[] val, int index, int len) {
- return new String(Arrays.copyOfRange(val, index, index + len),
- LATIN1);
+ byte[] copy = Arrays.copyOfRange(val, index, index + len);
+ return newString(copy);
+ }
+
+ /**
+ * Unlike in {@link StringLatin1#newString(byte[], int, int)} here we
+ * assume that {@param val} is never shared so we don't need to create a copy.
+ *
+ * @param val bytes to be turned into String
+ * @return new instance of {@link java.lang.String}
+ */
+ public static String newString(byte[] val) {
+ return new String(val, LATIN1);
}
public static void fillNull(byte[] val, int index, int end) {
diff --git a/src/java.base/share/classes/java/lang/System.java b/src/java.base/share/classes/java/lang/System.java
--- a/src/java.base/share/classes/java/lang/System.java
+++ b/src/java.base/share/classes/java/lang/System.java
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1994, 2019, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1994, 2020, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -2282,6 +2282,14 @@
assert library.indexOf(java.io.File.separatorChar) < 0;
ClassLoader.loadLibrary(caller, library, false);
}
+
+ public boolean isLatin1(String str) {
+ return str.isLatin1();
+ }
+
+ public String newLatin1String(byte[] bytes) {
+ return StringLatin1.newString(bytes);
+ }
});
}
}
diff --git a/src/java.base/share/classes/java/util/StringJoiner.java b/src/java.base/share/classes/java/util/StringJoiner.java
--- a/src/java.base/share/classes/java/util/StringJoiner.java
+++ b/src/java.base/share/classes/java/util/StringJoiner.java
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2013, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2013, 2020, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -24,6 +24,9 @@
*/
package java.util;
+import jdk.internal.access.SharedSecrets;
+import jdk.internal.access.JavaLangAccess;
+
/**
* {@code StringJoiner} is used to construct a sequence of characters separated
* by a delimiter and optionally starting with a supplied prefix
@@ -60,9 +63,12 @@
*
* @see java.util.stream.Collectors#joining(CharSequence)
* @see java.util.stream.Collectors#joining(CharSequence, CharSequence, CharSequence)
- * @since 1.8
-*/
+ * @since 1.8
+ */
public final class StringJoiner {
+
+ private static final JavaLangAccess jla = SharedSecrets.getJavaLangAccess();
+
private final String prefix;
private final String delimiter;
private final String suffix;
@@ -77,7 +83,7 @@
private int len;
/**
- * When overridden by the user to be non-null via {@link setEmptyValue}, the
+ * When overridden by the user to be non-null via {@link #setEmptyValue}, the
* string returned by toString() when no elements have yet been added.
* When null, prefix + suffix is used as the empty value.
*/
@@ -153,6 +159,13 @@
return len;
}
+ @SuppressWarnings("deprecation")
+ private static int getBytes(String s, byte[] bytes, int start) {
+ int len = s.length();
+ s.getBytes(0, len, bytes, start);
+ return len;
+ }
+
/**
* Returns the current value, consisting of the {@code prefix}, the values
* added so far separated by the {@code delimiter}, and the {@code suffix},
@@ -173,20 +186,43 @@
compactElts();
return size == 0 ? "" : elts[0];
}
- final String delimiter = this.delimiter;
+ boolean useBytes = psdAreLatin1() && allLatin1(elts, size);
+ if (useBytes) {
+ return bytesToString(elts, size, addLen);
+ }
+ return charsToString(elts, size, addLen);
+ }
+
+ private String charsToString(String[] elts, int size, int addLen) {
final char[] chars = new char[len + addLen];
int k = getChars(prefix, chars, 0);
if (size > 0) {
+ final String delimiter = this.delimiter;
k += getChars(elts[0], chars, k);
for (int i = 1; i < size; i++) {
k += getChars(delimiter, chars, k);
k += getChars(elts[i], chars, k);
}
}
- k += getChars(suffix, chars, k);
+ getChars(suffix, chars, k);
return new String(chars);
}
+ private String bytesToString(String[] elts, int size, int addLen) {
+ final byte[] bytes = new byte[len + addLen];
+ int k = getBytes(prefix, bytes, 0);
+ if (size > 0) {
+ final String delimiter = this.delimiter;
+ k += getBytes(elts[0], bytes, k);
+ for (int i = 1; i < size; i++) {
+ k += getBytes(delimiter, bytes, k);
+ k += getBytes(elts[i], bytes, k);
+ }
+ }
+ getBytes(suffix, bytes, k);
+ return jla.newLatin1String(bytes);
+ }
+
/**
* Adds a copy of the given {@code CharSequence} value as the next
* element of the {@code StringJoiner} value. If {@code newElement} is
@@ -239,18 +275,40 @@
private void compactElts() {
if (size > 1) {
- final char[] chars = new char[len];
- int i = 1, k = getChars(elts[0], chars, 0);
- do {
- k += getChars(delimiter, chars, k);
- k += getChars(elts[i], chars, k);
- elts[i] = null;
- } while (++i < size);
- size = 1;
- elts[0] = new String(chars);
+ if (allLatin1(elts, size)) {
+ compactBytes();
+ } else {
+ compactChars();
+ }
}
}
+ private void compactBytes() {
+ final byte[] bytes = new byte[len];
+ int i = 1;
+ int k = getBytes(elts[0], bytes, 0);
+ do {
+ k += getBytes(delimiter, bytes, k);
+ k += getBytes(elts[i], bytes, k);
+ elts[i] = null;
+ } while (++i < size);
+ size = 1;
+ elts[0] = jla.newLatin1String(bytes);
+ }
+
+ private void compactChars() {
+ final char[] chars = new char[len];
+ int i = 1;
+ int k = getChars(elts[0], chars, 0);
+ do {
+ k += getChars(delimiter, chars, k);
+ k += getChars(elts[i], chars, k);
+ elts[i] = null;
+ } while (++i < size);
+ size = 1;
+ elts[0] = new String(chars);
+ }
+
/**
* Returns the length of the {@code String} representation
* of this {@code StringJoiner}. Note that if
@@ -265,4 +323,21 @@
return (size == 0 && emptyValue != null) ? emptyValue.length() :
len + prefix.length() + suffix.length();
}
+
+ private static boolean allLatin1(String[] strings, int size) {
+ for (int i = 0; i < size; i++) {
+ String str = strings[i];
+ if (!jla.isLatin1(str)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private boolean psdAreLatin1() {
+ return jla.isLatin1(delimiter)
+ && jla.isLatin1(prefix)
+ && jla.isLatin1(suffix);
+ }
+
}
diff --git a/src/java.base/share/classes/jdk/internal/access/JavaLangAccess.java b/src/java.base/share/classes/jdk/internal/access/JavaLangAccess.java
--- a/src/java.base/share/classes/jdk/internal/access/JavaLangAccess.java
+++ b/src/java.base/share/classes/jdk/internal/access/JavaLangAccess.java
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2003, 2019, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2003, 2020, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -319,4 +319,21 @@
* @param library name of the library to load
*/
void loadLibrary(Class<?> caller, String library);
+
+ /**
+ * Returns true in case all characters of argument {@link String} are ASCII symbols
+ *
+ * @param str String to be checked
+ * @return whether all characters of argument {@link String} are ASCII symbols
+ */
+ boolean isLatin1(String str);
+
+ /**
+ * Returns new String made of bytes proven to be Latin1
+ *
+ * @param bytes array of bytes where each must be Latin1
+ * @return new instance of {@link java.lang.String}
+ */
+ String newLatin1String(byte[] bytes);
+
}
