[PATCH] Enhancement proposal for java.util.StringJoiner

Сергей Цыпанов sergei.tsypanov at yandex.ru
Sun Feb 16 21:24:35 UTC 2020


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.christian at 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/op
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sj_final.patch
Type: text/x-diff
Size: 9205 bytes
Desc: not available
URL: <https://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20200216/efa8fcf0/sj_final-0001.patch>


More information about the core-libs-dev mailing list