Моя попытка номер 5

в 10:00, , рубрики: java, java 9, производительность, сжатые строки

А я пропатчил, я пропатчил SJ
Опять, опять, опять…
Ох, как намаялся я с тобой
Моя попытка номер пять.

Крутилось в голове

Это небольшой большой рассказ о попытке привнести сжатые строки в StringJoiner, а также о трудностях, вставших на моём пути. Предупреждение: внутри расчленёнка и кишки, уберите от мониторов детей и впечатлительных лиц.

Постановка задачи

Если вы джава-разработчик, то наверняка знаете про сжатые строки (JEP 254), появившиеся в Java 9. Предельно упрощённо это улучшение описывается так: в старых версиях (до 8 включительно) внутри java.lang.String содержимое строки было представлено в виде char[], после — в виде byte[], что позволяет сократить потребеление памяти строками, все знаки которых относятся к ASCII (т. е. для их представления достаточно 1 байта). Более подробно и в доступной форме изложено здесь. Также изменениям подвергся java.lang.AbstractStringBuilder, наследниками которого являются java.lang.StringBuilder и java.lang.StringBuffer.

А вот с java.util.StringJoiner-ом всё иначе. Начиная с Java 9 внутри находится массив строк, которые объединяются через разделитель в методе toString():

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);        // расширяем 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);                    // сжимаем char[] -> byte[]

Если склеиваемые строки содержат знаки, не входящие в ASCII (знак представлен 2 байтами), то данная реализация понятна. Но что происходит в обратном случае? Происходит очень неприятная вещь: сначала byte[] из сжатой строки раздувается до char[] (при чём старший байт всегда 0), а потом в конструкторе строки происходит обратный процесс: старший байт усекается. Всё это стОит. Попробуем исправить положение.

Первая кровь

Итак, вскрываем StringJoiner (JDK 14, малоинтересные подробности опущены):

public final class StringJoiner {
  private final String prefix;
  private final String delimiter;
  private final String suffix;

  /** Contains all the string components added so far. */
  private String[] elts;

  /** The number of string components added so far. */
  private int size;

  /** Total length in chars so far, excluding prefix and suffix. */
  private int len;

  // ...
  public StringJoiner(CharSequence delimiter,
                        CharSequence prefix,
                        CharSequence suffix) {
    // ...
    this.prefix = prefix.toString();
    this.delimiter = delimiter.toString();
    this.suffix = suffix.toString();
  }

  // ...
  public StringJoiner add(CharSequence newElement) {
    final String elt = String.valueOf(newElement);
    if (elts == null) {
      elts = new String[8];
    } else {
      if (size == elts.length)
        elts = Arrays.copyOf(elts, 2 * size);
      len += delimiter.length();
    }
    len += elt.length();
    elts[size++] = elt;
    return this;
  }
  // ...
}

Здесь мы видим шестерёнки крупным планом: строки складываются в массив, их общая длина записывается в поле len, а общее количество строк — в поле size. Эти поля используются в методе toString() для однократного выделения памяти. Нам нужно как-то определять состояние, в котором все добавленые строки относятся к основной латинице. Тогда исполнение можно разделить на 2 ветки: существующую (использующую char[]) и "сжатую" (использующую byte[]) Решение в лоб: завести флаг allLatin1 и по его значению разграничивать логику:

public final class StringJoiner {
  private boolean allLatin1;

  public StringJoiner(CharSequence delimiter,
                      CharSequence prefix,
                      CharSequence suffix) {
    // ...
    this.allLatin1 = this.prefix.isLatin1() && this.delimiter.isLatin1() && this.suffix.isLatin1();
  }

  public StringJoiner add(CharSequence newElement) {
    final String elt = String.valueOf(newElement);
    //...
    this.allLatin1 &= elt.isLatin1();
    return this;
  }
}

Да, вот так просто :). Теперь метод toString():

@Override
public String toString() {
  final String[] elts = this.elts;
  if (elts == null && emptyValue != null) {
    return emptyValue;
  }
  final int size = this.size;
  final int addLen = prefix.length() + suffix.length();
  if (addLen == 0) {
    compactElts();
    return size == 0 ? "" : elts[0];
  }
  if (allLatin1) {
    return bytesToString(elts, size, addLen);
  }
  return charsToString(elts, size, addLen);
}

Прежняя реализация уехала в charsToString(), а её незаконнорождённым братом-близнецом стал bytesToString(), всё отличие которого заключается в использование byte[]:

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 new String(bytes);
}

@SuppressWarnings("deprecation")
private static int getBytes(String s, byte[] bytes, int start) {
  int len = s.length();
  s.getBytes(0, len, bytes, start);
  return len;
}

Данное решения — тупое повторение методов с заменой char[] на byte[] и одно логическое поле. Правда, есть проблема:

// JDK 14
public final class String {

  boolean isLatin1() {
    return COMPACT_STRINGS && coder == LATIN1;
  }
}

Внезапно оказываеццо, что StringJoiner живёт в java.util, а метод String.isLatin1() видим только внутри пакета java.lang. Стоит отметить — так было не всегда:

// JDK 11
public final class String {

  private boolean isLatin1() {                   // private !
    return COMPACT_STRINGS && coder == LATIN1;
  }
}

Однажды встав на эту дорожку и расширив область видимости метода, почему бы не сделать это ещё раз?

public final class String {

  public boolean isLatin1() {                    // а х*ли?
    return COMPACT_STRINGS && coder == LATIN1;
  }
}

Тем более, что метод никак не меняет состояние объекта, для которого он вызван. Так родился первый патч, отправленый вместе с сопроводительным письмом и бенчмарками в core-libs-dev (ссылка на сам патч в конце письма).

Чё там с производительностью?

Для измерений использовался самопальный бенчмарк (тело, утилитный класс), который на моей машине дал следующие результаты для параметра latin = true (все складываемые строки являются latin1, проседание отмечено восклицательным знаком):

                       count length         Original  Patched          Units
sj                         1      1     26.7 ±   1.3     38.2 ±   1.1  ns/op !
sj                         1      5     27.4 ±   0.0     40.5 ±   2.2  ns/op !
sj                         1     10     29.6 ±   1.9     38.4 ±   1.9  ns/op !
sj                         1    100     61.1 ±   6.9     47.6 ±   0.6  ns/op
sj                         5      1     91.1 ±   6.7     83.6 ±   2.0  ns/op
sj                         5      5     96.1 ±  10.7     85.6 ±   1.1  ns/op
sj                         5     10    105.5 ±  14.3     84.7 ±   1.1  ns/op
sj                         5    100    266.6 ±  30.1    139.6 ±  14.0  ns/op
sj                        10      1    190.7 ±  23.0    162.0 ±   2.9  ns/op
sj                        10      5    200.0 ±  16.9    167.5 ±  11.0  ns/op
sj                        10     10    216.4 ±  12.4    164.8 ±   1.7  ns/op
sj                        10    100    545.3 ±  49.7    282.2 ±  12.0  ns/op
sj                       100      1   1467.0 ±  90.3   1302.0 ±  18.5  ns/op
sj                       100      5   1491.8 ± 166.2   1493.0 ± 135.4  ns/op
sj                       100     10   1768.8 ± 160.6   1760.8 ± 111.4  ns/op
sj                       100    100   3654.3 ± 113.1   3120.9 ± 175.9  ns/op
sj:·gc.alloc.rate.norm     1      1    120.0 ±   0.0    120.0 ±   0.0   B/op
sj:·gc.alloc.rate.norm     1      5    128.0 ±   0.0    120.0 ±   0.0   B/op
sj:·gc.alloc.rate.norm     1     10    144.0 ±   0.0    136.0 ±   0.0   B/op
sj:·gc.alloc.rate.norm     1    100    416.0 ±   0.0    312.0 ±   0.0   B/op
sj:·gc.alloc.rate.norm     5      1    144.0 ±   0.0    136.0 ±   0.0   B/op
sj:·gc.alloc.rate.norm     5      5    200.0 ±   0.0    168.0 ±   0.0   B/op
sj:·gc.alloc.rate.norm     5     10    272.0 ±   0.0    216.0 ±   0.0   B/op
sj:·gc.alloc.rate.norm     5    100   1632.0 ±   0.0   1128.0 ±   0.0   B/op
sj:·gc.alloc.rate.norm    10      1    256.0 ±   0.0    232.0 ±   0.0   B/op
sj:·gc.alloc.rate.norm    10      5    376.0 ±   0.0    312.0 ±   0.0   B/op
sj:·gc.alloc.rate.norm    10     10    520.0 ±   0.0    408.0 ±   0.0   B/op
sj:·gc.alloc.rate.norm    10    100   3224.1 ±   0.0   2216.1 ±   0.0   B/op
sj:·gc.alloc.rate.norm   100      1   1760.2 ±  14.9   1544.2 ±   0.0   B/op
sj:·gc.alloc.rate.norm   100      5   2960.3 ±  14.9   2344.2 ±   0.0   B/op
sj:·gc.alloc.rate.norm   100     10   4440.4 ±   0.0   3336.3 ±   0.0   B/op
sj:·gc.alloc.rate.norm   100    100  31449.3 ±  12.2  21346.7 ±  14.7   B/op

Наблюдаем регрессию в случаях, когда добавляется 1 небольшая строка, что закономерно: на небольших объёмах данных сильное влияние оказывают инфраструктурные расходы, а их у нас прибавилось. Также небольшая регрессия времени выполнения наблюдается для нелатинских строк и объясняется она избыточным механизмом проверки "латинскости" (об этом ниже, пока попробуйте додуматься самостоятельно).

Набиваем шишки

Конечно, я подозревал, что решение дерзкое и подзатыльников не миновать. Поэтому предусмотрительно был предложен запасной вариант: область видимости String.isLatin1() не расширять, а намутить что-то вроде:

package java.lang;

public class StringHelper {
  public static boolean isLatin1(String str) {
    return str.isLatin1();
  }
}

Реми Фора забраковал оба подхода:

You can not change the implementation anymore, by example if instead of having a split between latin1 and non latin1, we decide in the future to split between utf8 and non utf8.

If you want to optimize StringJoiner, the best way to do it is to use the shared secret mechanism so a java.util class can see implementation details of a java.lang class without exposing those details publicly. As an example, take a look to EnumSet and its implementations.

Доводы веские: сейчас внешние классы ничего не знают про то, как реализованы сжатые строки, поэтому существует свобода выбора подхода и реализации. Если же мы подписываемся на разграничение по линии latin1 / не latin1, то иная реализация будет уже невозможна (например, разграничение между UTF-8 / не UTF-8). Одновременно указан способ обойти межпакетные преграды — таинственный SharedSecrets.

Глубже! Ещё глубже!

Следующий наш подопытный — jdk.internal.access.SharedSecrets (в ранних изданиях фигурант проходит как jdk.internal.misc.SharedSecrets). Читаем:

/** A repository of "shared secrets", which are a mechanism for
    calling implementation-private methods in another package without
    using reflection. A package-private class implements a public
    interface and provides the ability to call package-private methods
    within that package; the object implementing that interface is
    provided through a third package to which access is restricted.
    This framework avoids the primary disadvantage of using reflection
    for this purpose, namely the loss of compile-time checking. */

Выглядит обнадёживающе, правда, я так и не смог обнаружить готовый метод, позволяющий определить "латинскость" строки, так что ничего не оставалось, кроме как последовать совету Реми и создать его самому:

yes!
crossing package boundary in a non public way is not free, but given that StringJoiner is used quite often (directly or indirectly using Collectors.joining()), it may worth the cost.

Решение состоит из нескольких частей. Первым описан интерфейс, позволяющий пользователю определять "латинскость" строки:

package jdk.internal.access;

public interface JavaLangStringAccess {
  boolean isLatin1(String str);
}

Далее реализация (пока с использованием рефлексии):

class StringAccess implements jdk.internal.access.JavaLangStringAccess {
  static {
    SharedSecrets.setJavaLangStringAccess(new StringAccess());
  }

  private final Method isLatin1;

  StringAccess() {
    this.isLatin1 = initIsLatin1Method();
  }

  @Override
  public boolean isLatin1(String str) {
    try {
      return (boolean) isLatin1.invoke(str);
    } catch (IllegalAccessException | InvocationTargetException e) {
      throw new RuntimeException(e);
    }
  }

  private static Method initIsLatin1Method() {
    try {
      Method isLatin1 = String.class.getDeclaredMethod("isLatin1");
      isLatin1.setAccessible(true);
      return isLatin1;
    } catch (NoSuchMethodException e) {
      throw new Error(e);
    }
  }
}

Ну и сам SharedSecrets (обратите внимание на любопытный подход к ленивому созданию объекта StringAccess):

public class SharedSecrets {
  private static final Unsafe unsafe = Unsafe.getUnsafe();

  private static JavaLangStringAccess javaLangStringAccess;

  // ...

  public static JavaLangStringAccess getJavaLangStringAccess() {
    if (javaLangStringAccess == null) {
      unsafe.ensureClassInitialized(StringAccess.class);
    }
    return javaLangStringAccess;
  }

  public static void setJavaLangStringAccess(JavaLangStringAccess stringAccess) {
    javaLangStringAccess = stringAccess;
  }
}

Соответственно, в методе StringJoiner.add() и конструкторе теперь вызывается статический метод, передающий вызов в JavaLangStringAccess.isLatin1():

public final class StringJoiner {
  private boolean allLatin1;

  public StringJoiner add(CharSequence newElement) {
    final String elt = String.valueOf(newElement);
    //...
    this.allLatin1 &= isLatin1(elt);
    return this;
  }

  private static boolean isLatin1(String str) {
    return SharedSecrets.getJavaLangStringAccess().isLatin1(str);
  }
}

Уже сейчас очевидно, что теперь регрессия станет ещё сильнее, ведь рефлексия — удовольствие не из дешёвых. Также очевидно, что наиболее сильным проседание будет у нелатинских строк, т. к. там на существующие расходы накладываются ещё проверки "латинскости". Выше я упоминал, что предложенный алгоритм несовершенен:

public final class StringJoiner {
  private boolean allLatin1;

  public StringJoiner(CharSequence delimiter,
                      CharSequence prefix,
                      CharSequence suffix) {
    // ...
    this.allLatin1 = isLatin1(this.prefix) && isLatin1(this.delimiter) && isLatin1(this.suffix);
  }

  public StringJoiner add(CharSequence newElement) {
    final String elt = String.valueOf(newElement);
    //...
    this.allLatin1 &= isLatin1(elt);
    return this;
  }
}

Предположим, мы складываем 10 нелатинских строк. Уже после добавления первой из них значение поля allLatin1 становится false, делая дальнейшие проверки бессмысленными, ведь значение уже не будет меняться. Всего одной нелатинской строки достаточно для отката к char[].

Таким образом, улучшение лежит на поверхности: удалим поле allLatin1 и будем принимать решение непосредственно при вызове toString(). Это даст возможность для первой же нелатинской строки сразу вернуть false, что сгладит проседание по времени:

private static boolean allLatin1(String[] strings, int size) {
  for (int i = 0; i < size; i++) {
    String str = strings[i];
    if (!SharedSecrets.getJavaLangStringAccess().isLatin1(str)) {
      return false;
    }
  }
  return true;
}

private boolean psdLatin1() {
  return SharedSecrets.getJavaLangStringAccess().isLatin1(delimiter)
      && SharedSecrets.getJavaLangStringAccess().isLatin1(prefix)
      && SharedSecrets.getJavaLangStringAccess().isLatin1(suffix)
}

Теперь toString():

@Override
public String toString() {
  final String[] elts = this.elts;
  if (elts == null && emptyValue != null) {
    return emptyValue;
  }
  final int size = this.size;
  final int addLen = prefix.length() + suffix.length();
  if (addLen == 0) {
    compactElts();
    return size == 0 ? "" : elts[0];
  }
  if (psdLatin1() && allLatin1(elts, size)) {
    return bytesToString(elts, size, addLen);
  }
  return charsToString(elts, size, addLen);
}

Пришло время проверить, будет ли вообще толк от нашего творчества:

Боль - это боль, как её ты не назови...

Benchmark      count    latin  len        Original          Patched
sj                 1     true    1    26.9 ±   0.7     48.8 ±   2.2 ns/op !
sj                 1     true    5    30.5 ±   1.0     46.1 ±   2.1 ns/op !
sj                 1     true   10    31.2 ±   0.6     47.3 ±   1.3 ns/op !
sj                 1     true  100    62.5 ±   3.3     79.9 ±   4.8 ns/op !
sj                 5     true    1    78.2 ±   1.6    110.3 ±   2.9 ns/op !
sj                 5     true    5    94.2 ±   8.7    116.6 ±   0.7 ns/op !
sj                 5     true   10    95.3 ±   6.9    100.1 ±   0.4 ns/op
sj                 5     true  100   188.0 ±  10.2    136.0 ±   0.4 ns/op
sj                10     true    1   160.3 ±   4.5    172.9 ±   0.8 ns/op
sj                10     true    5   169.0 ±   4.7    180.2 ±   9.1 ns/op
sj                10     true   10   205.7 ±  16.4    182.7 ±   1.1 ns/op
sj                10     true  100   366.5 ±  17.0    284.5 ±   3.1 ns/op
sj               100     true    1  1117.6 ±  11.1   2123.7 ±  11.1 ns/op !
sj               100     true    5  1270.7 ±  40.2   2163.6 ±  12.4 ns/op !
sj               100     true   10  1364.4 ±  14.0   2283.8 ±  16.1 ns/op !
sj               100     true  100  3592.9 ± 164.8   3535.2 ±  29.9 ns/op

sj                 1    false    1    35.6 ±   1.2     59.1 ±   3.0 ns/op !
sj                 1    false    5    39.3 ±   1.2     52.6 ±   2.5 ns/op !
sj                 1    false   10    42.2 ±   1.6     53.6 ±   0.3 ns/op !
sj                 1    false  100    70.5 ±   1.8     86.4 ±   0.4 ns/op !
sj                 5    false    1    89.0 ±   3.5    102.2 ±   1.0 ns/op !
sj                 5    false    5    87.6 ±   0.7    106.5 ±   1.2 ns/op !
sj                 5    false   10   109.0 ±   5.6    116.5 ±   1.2 ns/op !
sj                 5    false  100   324.0 ±  16.5    221.9 ±   0.5 ns/op
sj                10    false    1   183.9 ±   5.9    204.7 ±   5.5 ns/op !
sj                10    false    5   198.7 ±   9.7    202.4 ±   1.5 ns/op !
sj                10    false   10   196.7 ±   6.9    226.7 ±   6.4 ns/op !
sj                10    false  100   535.8 ±   2.3    553.0 ±   5.6 ns/op !
sj               100    false    1  1674.6 ± 122.1   1940.8 ±  16.2 ns/op !
sj               100    false    5  1791.9 ±  58.1   2158.1 ±  12.0 ns/op !
sj               100    false   10  2124.1 ± 193.3   2364.0 ±  25.2 ns/op !
sj               100    false  100  4323.4 ±  29.2   4675.5 ±  11.8 ns/op !

sj:·gc.a.r.n       1     true    1   120.0 ±   0.0    120.0 ±   0.0  B/op
sj:·gc.a.r.n       1     true    5   128.0 ±   0.0    120.0 ±   0.0  B/op
sj:·gc.a.r.n       1     true   10   144.0 ±   0.0    136.0 ±   0.0  B/op
sj:·gc.a.r.n       1     true  100   416.0 ±   0.0    312.0 ±   0.0  B/op
sj:·gc.a.r.n       5     true    1   144.0 ±   0.0    136.0 ±   0.0  B/op
sj:·gc.a.r.n       5     true    5   200.0 ±   0.0    168.0 ±   0.0  B/op
sj:·gc.a.r.n       5     true   10   272.0 ±   0.0    216.0 ±   0.0  B/op
sj:·gc.a.r.n       5     true  100  1632.0 ±   0.0   1128.0 ±   0.0  B/op
sj:·gc.a.r.n      10     true    1   256.0 ±   0.0    232.0 ±   0.0  B/op
sj:·gc.a.r.n      10     true    5   376.0 ±   0.0    316.8 ±   4.9  B/op
sj:·gc.a.r.n      10     true   10   520.0 ±   0.0    408.0 ±   0.0  B/op
sj:·gc.a.r.n      10     true  100  3224.1 ±   0.0   2236.9 ±  21.2  B/op
sj:·gc.a.r.n     100     true    1  1748.1 ±   4.0   1592.2 ±   0.0  B/op
sj:·gc.a.r.n     100     true    5  2948.2 ±   4.0   2392.3 ±   0.0  B/op
sj:·gc.a.r.n     100     true   10  4444.3 ±   4.0   3384.3 ±   0.0  B/op
sj:·gc.a.r.n     100     true  100  1441.4 ±   0.0  21385.4 ±   0.0  B/op

sj:·gc.a.r.n       1    false    1   144.0 ±   0.0    144.0 ±   0.0  B/op
sj:·gc.a.r.n       1    false    5   160.0 ±   0.0    160.0 ±   0.0  B/op
sj:·gc.a.r.n       1    false   10   184.0 ±   0.0    184.0 ±   0.0  B/op
sj:·gc.a.r.n       1    false  100   640.0 ±   0.0    640.0 ±   0.0  B/op
sj:·gc.a.r.n       5    false    1   184.0 ±   0.0    184.0 ±   0.0  B/op
sj:·gc.a.r.n       5    false    5   280.0 ±   0.0    280.0 ±   0.0  B/op
sj:·gc.a.r.n       5    false   10   400.0 ±   0.0    400.0 ±   0.0  B/op
sj:·gc.a.r.n       5    false  100  2664.1 ±   0.0   2664.1 ±   0.0  B/op
sj:·gc.a.r.n      10    false    1   320.0 ±   0.0    334.4 ±   7.4  B/op
sj:·gc.a.r.n      10    false    5   520.0 ±   0.0    520.0 ±   0.0  B/op
sj:·gc.a.r.n      10    false   10   760.0 ±   0.0    769.6 ±   6.5  B/op
sj:·gc.a.r.n      10    false  100  5264.2 ±   0.0   5273.8 ±   6.5  B/op
sj:·gc.a.r.n     100    false    1  2204.2 ±   4.0   2216.3 ±   0.0  B/op
sj:·gc.a.r.n     100    false    5  4196.3 ±   6.2   4216.4 ±   0.0  B/op
sj:·gc.a.r.n     100    false   10  6696.5 ±   5.4   6712.6 ±   0.0  B/op
sj:·gc.a.r.n     100    false  100  1702.0 ±   4.1  51714.4 ±   0.0  B/op

Да, сохраняется выигрыш по памяти, но проседание по времени стало почти всеобщим и катастрофическим. Опыт показывает, что в деле определения "латинскости" рефлексия нам не товарищ.

Реплика из зала

В какой-то момент в обсуждении нарисовался lany и оставил несколько ценных замечаний. Я выделил важнейшие (на мой взгляд):

Hello!

In many tests, I see little or no performance improvements. E.g.:
stringJoiner 100 10 1768.8 ±160.6 1760.8 ± 111.4 ns/op

How would you explain that this code change doesn't improve the performance for given count and length?

Also, you are using new String(bytes) assuming that the platform charset is latin1-compatible. This is not always true, so your code would produce incorrect results depending on this setting. In general, decoding via charset is tons of extra work. Instead, I would experiment with pre-sized StringBuilder inside compactElts, instead of char[] array. While it does some extra checks, StringBuilder already can use the compact string representation, so if it's properly pre-sized, no extra memory will be allocated.

Finally, if you optimize for the case when X is true you should always benchmark what happens when X is false. It's great that in some cases we see a speedup for latin1 strings. But what if not all of the strings are latin1? Is there any performance degradation? If yes, can we tolerate it?

Первым же предложением сразу под дых. Действительно, если мы внимательно почитаем код java.lang.String, то найдём там интересную документацию:

public final class String {
  private final byte coder;

 /**
  * @implNote
  * The actual value for this field is injected by JVM. The static       <--- !!!
  * initialization block is used to set the value here to communicate
  * that this static final field is not statically foldable, and to
  * avoid any possible circular dependency during vm initialization.
  */
  static final boolean COMPACT_STRINGS;

  static {
    COMPACT_STRINGS = true;
  }

  boolean isLatin1() {
    return COMPACT_STRINGS && coder == LATIN1;
  }
}

Возможна ли с нашими изменениями ситуация, при которой все строки будут определены как латинские при выключенном сжатии строк? Для проверки нужно запустить виртуальную машину с флагом -XX:-CompactStrings и посмотреть в отладчике значение String.COMPACT_STRINGS (при запуске без флагов оно true). Запускаем, смотрим — String.COMPACT_STRINGS возвращает false. Помним, что

public final class String {

  boolean isLatin1() {
    return COMPACT_STRINGS && coder == LATIN1;
  }
}

т. е. если метод isLatin1() вернул true, то сжатые строки включены. Вроде как можно выдохнуть: если мы дошли до вызова bytesToString(), то значит, все складываемые строки латинские, а раз они определены как латинские, то сжатые строки включены на уровен ВМ. Едем дальше:

In general, decoding via charset is tons of extra work. Instead, I would experiment with pre-sized StringBuilder inside compactElts, instead of char[] array. While it does some extra checks, StringBuilder already can use the compact string representation, so if it's properly pre-sized, no extra memory will be allocated.

Причина проседания в моём коде — использование рефлексии для разграничения char[] / byte[], но эта функциональность уже реализована в StringBuilder-е, который по счастливому стечению обстоятельств объявлен в пакете java.lang.

Что же, попробуем:

@Override
public String toString() {
  final String[] elts = this.elts;
  if (elts == null && emptyValue != null) {
    return emptyValue;
  }
  final int size = this.size;
  final int addLen = prefix.length() + suffix.length();
  if (addLen == 0) {
    compactElts();
    return size == 0 ? "" : elts[0];
  }
  StringBuilder sb = new StringBuilder(len + addLen).append(prefix);
  if (size > 0) {
    sb.append(elts[0]);
    String delimiter = this.delimiter;
    for (int i = 1; i < size; i++) {
      sb.append(delimiter).append(elts[i]);
    }
  }
  return sb.append(suffix).toString();
}

Да, вот так просто. Больше нам не нужно проверять строки, это сделает за нас стандратная библиотека:

public AbstractStringBuilder append(String str) {
  if (str == null) {
    return appendNull();
  }
  int len = str.length();
  ensureCapacityInternal(count + len);
  putStringAt(count, str);
  count += len;
  return this;
}

private final void putStringAt(int index, String str) {
  if (getCoder() != str.coder()) {
    inflate();
  }
  str.getBytes(value, index, coder);
}

По идее это должно решить наши проблемы. Проверим:

Очередной провал

Benchmark     count  latin   len          Original     StringBuilder
sj                1   true     1      26.9 ±   0.7      33.4 ±   0.2  ns/op !
sj                1   true     5      30.5 ±   1.0      33.0 ±   0.1  ns/op !
sj                1   true    10      31.2 ±   0.6      34.3 ±   0.3  ns/op !
sj                1   true   100      62.5 ±   3.3      44.4 ±   0.1  ns/op
sj                5   true     1      78.2 ±   1.6      87.8 ±   0.8  ns/op !
sj                5   true     5      94.2 ±   8.7      88.2 ±   0.9  ns/op
sj                5   true    10      95.3 ±   6.9      91.6 ±   0.6  ns/op
sj                5   true   100     188.0 ±  10.2     126.1 ±   0.7  ns/op
sj               10   true     1     160.3 ±   4.5     177.6 ±   0.8  ns/op !
sj               10   true     5     169.0 ±   4.7     179.4 ±   1.0  ns/op !
sj               10   true    10     205.7 ±  16.4     189.5 ±   1.2  ns/op
sj               10   true   100     366.5 ±  17.0     290.0 ±   0.8  ns/op
sj              100   true     1    1117.6 ±  11.1    1563.8 ±   2.8  ns/op !
sj              100   true     5    1270.7 ±  40.2    1592.4 ±   4.0  ns/op !
sj              100   true    10    1364.4 ±  14.0    1773.7 ±  57.7  ns/op !
sj              100   true   100    3592.9 ± 164.8    2899.2 ±  51.0  ns/op

sj                1  false     1      35.6 ±   1.2      52.7 ±   1.2  ns/op !
sj                1  false     5      39.3 ±   1.2      54.4 ±   1.6  ns/op !
sj                1  false    10      42.2 ±   1.6      52.2 ±   1.0  ns/op !
sj                1  false   100      70.5 ±   1.8      78.6 ±   1.2  ns/op !
sj                5  false     1      89.0 ±   3.5     116.3 ±   3.8  ns/op !
sj                5  false     5      87.6 ±   0.7     115.2 ±   2.9  ns/op !
sj                5  false    10     109.0 ±   5.6     126.5 ±   0.5  ns/op !
sj                5  false   100     324.0 ±  16.5     288.9 ±   0.5  ns/op 
sj               10  false     1     183.9 ±   5.9     261.2 ±   7.7  ns/op !
sj               10  false     5     198.7 ±   9.7     253.3 ±   6.7  ns/op !
sj               10  false    10     196.7 ±   6.9     274.3 ±   7.0  ns/op !
sj               10  false   100     535.8 ±   2.3     677.3 ±   6.4  ns/op !
sj              100  false     1    1674.6 ± 122.1    2212.5 ±  32.2  ns/op !
sj              100  false     5    1791.9 ±  58.1    2492.8 ±  30.9  ns/op !
sj              100  false    10    2124.1 ± 193.3    2611.7 ±  17.5  ns/op !
sj              100  false   100    4323.4 ±  29.2    5501.3 ±  21.1  ns/op !

sj:·gc.a.r.n      1   true     1     120.0 ±   0.0     144.0 ±   0.0   B/op !
sj:·gc.a.r.n      1   true     5     128.0 ±   0.0     144.0 ±   0.0   B/op !
sj:·gc.a.r.n      1   true    10     144.0 ±   0.0     160.0 ±   0.0   B/op !
sj:·gc.a.r.n      1   true   100     416.0 ±   0.0     336.0 ±   0.0   B/op 
sj:·gc.a.r.n      5   true     1     144.0 ±   0.0     160.0 ±   0.0   B/op !
sj:·gc.a.r.n      5   true     5     200.0 ±   0.0     192.0 ±   0.0   B/op 
sj:·gc.a.r.n      5   true    10     272.0 ±   0.0     240.0 ±   0.0   B/op 
sj:·gc.a.r.n      5   true   100    1632.0 ±   0.0    1152.0 ±   0.0   B/op 
sj:·gc.a.r.n     10   true     1     256.0 ±   0.0     256.0 ±   0.0   B/op 
sj:·gc.a.r.n     10   true     5     376.0 ±   0.0     336.0 ±   0.0   B/op 
sj:·gc.a.r.n     10   true    10     520.0 ±   0.0     432.0 ±   0.0   B/op 
sj:·gc.a.r.n     10   true   100    3224.1 ±   0.0    2240.1 ±   0.0   B/op 
sj:·gc.a.r.n    100   true     1    1748.1 ±   4.0    1568.2 ±   0.0   B/op 
sj:·gc.a.r.n    100   true     5    2948.2 ±   4.0    2368.2 ±   0.0   B/op 
sj:·gc.a.r.n    100   true    10    4444.3 ±   4.0    3364.3 ±   4.0   B/op 
sj:·gc.a.r.n    100   true   100   31441.4 ±   0.0   21365.1 ±   4.1   B/op 

sj:·gc.a.r.n      1  false     1     144.0 ±   0.0     192.0 ±   0.0   B/op !
sj:·gc.a.r.n      1  false     5     160.0 ±   0.0     208.0 ±   0.0   B/op !
sj:·gc.a.r.n      1  false    10     184.0 ±   0.0     240.0 ±   0.0   B/op !
sj:·gc.a.r.n      1  false   100     640.0 ±   0.0     784.0 ±   0.0   B/op !
sj:·gc.a.r.n      5  false     1     184.0 ±   0.0     240.0 ±   0.0   B/op !
sj:·gc.a.r.n      5  false     5     280.0 ±   0.0     349.6 ±   2.4   B/op !
sj:·gc.a.r.n      5  false    10     400.0 ±   0.0     496.0 ±   0.0   B/op !
sj:·gc.a.r.n      5  false   100    2664.1 ±   0.0    3216.1 ±   0.0   B/op !
sj:·gc.a.r.n     10  false     1     320.0 ±   0.0     384.0 ±   0.0   B/op !
sj:·gc.a.r.n     10  false     5     520.0 ±   0.0     624.0 ±   0.0   B/op !
sj:·gc.a.r.n     10  false    10     760.0 ±   0.0     912.0 ±   0.0   B/op !
sj:·gc.a.r.n     10  false   100    5264.2 ±   0.0    6320.3 ±   0.0   B/op !
sj:·gc.a.r.n    100  false     1    2204.2 ±   4.0    2436.3 ±   6.8   B/op !
sj:·gc.a.r.n    100  false     5    4196.3 ±   6.2    4832.4 ±   6.6   B/op !
sj:·gc.a.r.n    100  false    10    6696.5 ±   5.4    7844.7 ±   4.0   B/op !
sj:·gc.a.r.n    100  false   100   51702.0 ±   4.1   61838.6 ±   6.2   B/op !

Увы, регрессия теперь почти везде. Мы всё ещё неплохо выигрываем по памяти для латинских строк (чего не скажешь про нелатинские), однако время выполнения стало сильно хуже.

Призрак АШ

Мы испробовали несколько подходов, давших неудовлетворительные результаты. Дёрнуть напрямую String.isLatin1() запрещено, вызывать его рефлексией — сильно бить по времени выполнения, использование StringBuilder-а больше вредит, чем помогает. Всё пропало? Оказалось, не всё.

В обсуждении появился Брент Кристиан собственной персоной — создатель того самого JEP 254:

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

По ссылке живёт существующая ещё с 2016 задача с похожим описанием:

This is seems to be a performance optimization, but it clashes with Compact Strings which now have to re-compress the resulting char[] array into byte[]. We may want to extend this mechanism by figuring out the coders for arguments, and creating byte[] with appropriate coder, then using a private String constructor that does not re-compress.

По это же ссылке находим ссылку на предложенные изменения. Из любопытного:
1) В ранних версиях у StringJoiner-а был доступ к SharedSecrets (строка 89 в "до")
2) Использующийся алгоритм коренным образом отличается от описанного выше. char[] не используется вовсе, а вместо явного деления на латинские/нелатинские строки используется кодировщик.
3) Для преодоления межпакетных барьеров без использования рефлексии помогает JavaLangAccess

Для наших изменений наибольший интерес представляет, как ни странно, последний пункт. До этого приходилось писать свой интерфейс и реализацию для доступа к закрытым методам строки. Теперь используя связку SharedSecrets -> JavaLangAccess -> java.lang.System рефлексию можно выбросить, ведь String.isLatin1() виден классу System!

Выходит, всё, что нам нужно для разграничения, это:

public interface JavaLangAccess {
  //...
  boolean isLatin1(String str);
}

public final class System {
  //...
  public boolean isLatin1(String str) {
    return str.isLatin1();
  }
}

Теперь накладные расходы по большей части сведены на нет. Но сложности остаются. Ещё раз перечитаем Тагира:

In general, decoding via charset is tons of extra work.

Хм, в нашем коде мы вызываем конструктор new String(byte[]):

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 new String(bytes);
}

а в него-то я не смотрел… Пришло время взглянуть правде в глаза:

public String(byte[] bytes) {
  this(bytes, 0, bytes.length);
}

public String(byte bytes[], int offset, int length) {
  checkBoundsOffCount(offset, length, bytes.length);
  StringCoding.Result ret = StringCoding.decode(bytes, offset, length); // адЪ
  this.value = ret.value;
  this.coder = ret.coder;
}

Прямой вызов new String(byte[]) пахнет плохой производительностью. Увернуться нам поможет, как ни странно, StringBuilder:

@Override
@HotSpotIntrinsicCandidate
public String toString() {
  // Create a copy, don't share the array
  return isLatin1() 
       ? StringLatin1.newString(value, 0, count)   // <---
       :  StringUTF16.newString(value, 0, count);
}

final class StringLatin1 {
  public static String newString(byte[] val, int index, int len) {
    return new String(Arrays.copyOfRange(val, index, index + len), LATIN1);
  }
}

Обратите внимание, что в конструктор строки мы передаём копию массива, т. к. метод StringBuilder.toString() может быть вызван несколько раз. Более того, между несколькими вызовами сам StringBuilder может измениться. В нашем же случае массив создаётся при каждом вызове StringJoiner.toString() и используется полностью, поэтому копирование нам не нужно. Добавим свой метод StringLatin1.newString(byte[]):

final class StringLatin1 {
  public static String newString(byte[] val, int index, int len) {
    byte[] copy = Arrays.copyOfRange(val, index, index + len);
    return newString(copy);
  }

  public static String newString(byte[] val) {
    return new String(val, LATIN1);
  }
}

Теперь собираем всё воедино, делаем замеры и отправляем письмо с результатами (патч в самом низу по ссылке). Теперь у нас почти нет регрессии, а потребление памяти во многих случаях сократилось почти втрое!

И последнее: давайте сравним наши изменения и патч АШ. Для этого приспособим его изменения к кодовой базе JDK 14, а далее по накатанной.

Подведём итоги

        latin cnt  len        Original            Mine             ASh

sj       true   1    1     27.7 ±  1.2     22.1 ±  0.2     19.7 ±  0.2  ns/op
sj       true   1    5     27.7 ±  0.1     22.3 ±  0.0     19.8 ±  0.0  ns/op
sj       true   1   10     29.0 ±  0.6     23.2 ±  0.0     20.1 ±  0.1  ns/op
sj       true   1  100     51.4 ±  0.1     31.4 ±  0.1     32.9 ±  0.1  ns/op
sj       true   5    1     71.1 ±  0.4     64.9 ±  0.3     53.8 ±  0.1  ns/op
sj       true   5    5     79.5 ±  0.3     65.5 ±  0.3     54.8 ±  0.1  ns/op
sj       true   5   10     81.2 ±  0.3     67.7 ±  0.2     56.1 ±  0.1  ns/op
sj       true   5  100    150.0 ±  0.4     86.5 ±  0.5     78.5 ±  0.3  ns/op
sj       true  10    1    145.5 ±  0.7    142.5 ±  0.4    127.1 ±  0.5  ns/op
sj       true  10    5    160.0 ±  0.8    145.6 ±  0.2    130.8 ±  0.3  ns/op
sj       true  10   10    165.6 ±  0.4    150.8 ±  0.3    138.9 ±  0.4  ns/op
sj       true  10  100    340.2 ±  1.2    189.3 ±  0.4    175.2 ±  0.7  ns/op
sj       true 100    1   1114.3 ± 15.9   1372.7 ± 53.0   1197.4 ± 34.0  ns/op !
sj       true 100    5   1184.2 ± 18.5   1385.9 ± 56.0   1159.0 ± 32.3  ns/op
sj       true 100   10   1345.8 ± 13.9   1369.0 ±  2.7   1233.5 ± 32.9  ns/op
sj       true 100  100   3156.1 ± 19.1   1844.1 ±  4.1   1727.9 ± 37.6  ns/op

sj      false   1    1     33.5 ±  0.4     34.9 ±  0.1     19.6 ±  0.0  ns/op
sj      false   1    5     33.3 ±  0.3     35.9 ±  0.1     20.1 ±  0.1  ns/op
sj      false   1   10     33.8 ±  0.1     35.9 ±  0.1     20.6 ±  0.0  ns/op
sj      false   1  100     57.5 ±  0.2     58.3 ±  0.1     39.6 ±  0.1  ns/op
sj      false   5    1     82.9 ±  0.5     82.0 ±  0.8     64.2 ±  1.3  ns/op
sj      false   5    5     86.0 ±  0.5     84.8 ±  0.9     66.6 ±  0.8  ns/op
sj      false   5   10     96.9 ±  0.5     92.5 ±  0.6     76.9 ±  0.7  ns/op
sj      false   5  100    224.2 ±  0.6    226.7 ±  0.7    125.1 ±  0.6  ns/op
sj      false  10    1    165.7 ±  0.9    167.6 ±  3.2    152.1 ±  1.0  ns/op
sj      false  10    5    178.4 ±  0.7    179.6 ±  2.1    163.7 ±  0.9  ns/op
sj      false  10   10    191.7 ±  0.9    195.9 ±  2.2    172.5 ±  0.8  ns/op
sj      false  10  100    534.4 ±  1.4    534.5 ±  1.3    305.2 ±  1.1  ns/op
sj      false 100    1   1435.9 ±  9.5   1428.2 ±  3.2   1333.0 ±  4.7  ns/op
sj      false 100    5   1618.5 ± 14.3   1595.2 ±  3.7   1379.7 ± 10.4  ns/op
sj      false 100   10   1898.1 ±  9.4   1860.8 ±  4.7   1531.5 ± 13.7  ns/op
sj      false 100  100   4247.4 ± 60.7   4150.1 ±  9.1   2423.8 ± 11.9  ns/op

g.a.r.n  true   1    1    124.0 ±  4.0     96.0 ±  0.0     96.0 ±  0.0   B/op
g.a.r.n  true   1    5    128.0 ±  0.0     96.0 ±  0.0     96.0 ±  0.0   B/op
g.a.r.n  true   1   10    144.0 ±  0.0    104.0 ±  0.0    104.0 ±  0.0   B/op
g.a.r.n  true   1  100    416.0 ±  0.0    192.0 ±  0.0    192.0 ±  0.0   B/op
g.a.r.n  true   5    1    144.0 ±  0.0    104.0 ±  0.0     96.0 ±  0.0   B/op
g.a.r.n  true   5    5    200.0 ±  0.0    120.0 ±  0.0    120.0 ±  0.0   B/op
g.a.r.n  true   5   10    272.0 ±  0.0    144.0 ±  0.0    144.0 ±  0.0   B/op
g.a.r.n  true   5  100   1632.0 ±  0.0    600.0 ±  0.0    592.0 ±  0.0   B/op
g.a.r.n  true  10    1    256.0 ±  0.0    192.0 ±  0.0    184.0 ±  0.0   B/op
g.a.r.n  true  10    5    376.0 ±  0.0    232.0 ±  0.0    224.0 ±  0.0   B/op
g.a.r.n  true  10   10    520.0 ±  0.0    280.0 ±  0.0    272.0 ±  0.0   B/op
g.a.r.n  true  10  100   3224.1 ±  0.0   1184.0 ±  0.0   1168.0 ±  0.0   B/op
g.a.r.n  true 100    1   1752.1 ±  5.4   1328.2 ±  5.4   1244.1 ±  9.5   B/op
g.a.r.n  true 100    5   2952.2 ±  5.4   1728.2 ±  5.4   1627.3 ±  7.6   B/op
g.a.r.n  true 100   10   4444.4 ±  4.0   2216.2 ±  0.0   2140.2 ±  9.5   B/op
g.a.r.n  true 100  100  31445.6 ±  4.0  11216.7 ±  0.0  11135.0 ±  9.3   B/op

g.a.r.n false   1    1    144.0 ±  0.0    144.0 ±  0.0     96.0 ±  0.0   B/op
g.a.r.n false   1    5    160.0 ±  0.0    160.0 ±  0.0    104.0 ±  0.0   B/op
g.a.r.n false   1   10    184.0 ±  0.0    184.0 ±  0.0    112.0 ±  0.0   B/op
g.a.r.n false   1  100    640.0 ±  0.0    640.0 ±  0.0    288.0 ±  0.0   B/op
g.a.r.n false   5    1    184.0 ±  0.0    184.0 ±  0.0    104.0 ±  0.0   B/op
g.a.r.n false   5    5    280.0 ±  0.0    280.0 ±  0.0    144.0 ±  0.0   B/op
g.a.r.n false   5   10    400.0 ±  0.0    400.0 ±  0.0    192.0 ±  0.0   B/op
g.a.r.n false   5  100   2664.1 ±  0.0   2664.1 ±  0.0   1088.0 ±  0.0   B/op
g.a.r.n false  10    1    320.0 ±  0.0    320.0 ±  0.0    192.0 ±  0.0   B/op
g.a.r.n false  10    5    520.0 ±  0.0    520.0 ±  0.0    272.0 ±  0.0   B/op
g.a.r.n false  10   10    760.0 ±  0.0    760.0 ±  0.0    368.0 ±  0.0   B/op
g.a.r.n false  10  100   5264.2 ±  0.0   5264.2 ±  0.0   2168.1 ±  0.0   B/op
g.a.r.n false 100    1   2208.2 ±  0.0   2168.2 ±  0.0   1317.7 ±  5.7   B/op
g.a.r.n false 100    5   4196.3 ±  6.2   4168.3 ±  0.0   2123.4 ±  7.6   B/op
g.a.r.n false 100   10   6704.6 ±  0.0   6664.5 ±  0.0   3123.4 ±  7.6   B/op
g.a.r.n false 100  100  51698.1 ±  5.4  51666.3 ±  0.0  21124.3 ±  7.6   B/op

Таким образом, проседание осталось только в одном случае, но теперь у нас есть выигрыш по памяти во всех случаях! В комментариях к JDK-8148937 отмечено, что регрессия (в то время) была обусловлена JDK-8149758. Но теперь проседания вроде бы нет. Поэтому я решил написать ещё одно письмо, чтобы обратить внимание сообщества на JDK-8148937. Согласитесь, 1,5-2 -кратные приросты по времени и памяти того стоят.

Выводы

  • системная разработка — это сложно. Вот казалось бы, возьми существующий подход (придумывать ничего не нужно) и примени к существующему коду. Начинаешь — и тут же сталкиваешься со многими неочевидными и сложными вещами. Нужно не только писать свой код, но и изучать чужой, читать переписку, исследовать полученные ранее результаты
  • при попытке залить что-то в JDK вычитка будет беспощадной. Наши предложения кажутся нам самыми верными, но часто это иллюзия. Не принимайте критику, даже и разгромную, близко к сердцу
  • даже самые крутые приросты не обещают внимания разработчиков. В одной из прошлых статей я описывал полезные и вместе с тем небольшие и на 100% надёжные изменения, которые также пока убраны под сукно просто из-за малой значимости или иной расстановки приоритетов

Вместо послесловия

Уже через неделю с небольшим начнётся весна, желаю с первым теплом ощутить прилив сил и смело браться за сложные задачи, уметь безболезненно признавать свои ошибки и учиться, учиться, и снова учиться :)

Автор: tsypanov

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js