Регистрация

[Java] Ах, эти строки

Ответить на тему
Автор Сообщение
news_bot ®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

Создавать темы news_bot ® написал(а)
13-Авг-2020 14:32
Цитировать

Это текстовая версия моего доклада "Ах, эти строки" на конференции JPoint-2020.
Дабы не тратить время читателей зря, сразу расставим все точки над "ё".
О чём статья?
Статья об эффективном (или не очень) использовании строк.
Для кого статья?
Статья для разработчиков, занимающихся производительностью, и им сочувствующих.
Откуда всё это?
Что-то выловлено в коде проекта, что-то — во фреймворках и библиотеках.
Что, чем и на чём измеряли?
  • код бенчмарков и результаты прогонов доступны на ГитХабе
  • для измерения использовался JMH 1.23
  • замеры проводились на рабочей машине с Intel Core i7-7700 (сами по себе цифры не важны, важны соотношения между ними и выявленные закономерности)
  • по умолчанию использовался JDK 11, но также 8 и 14 (явно прописаны на соответствующих страницах)
  • режим бенчмарков: среднее время выполнения + расход памяти (меньше значит лучше)

Пакет java.lang и его обитатели
Работающие с явой знают, что java.lang — это ядро языка и если вам понадобится внести туда изменения, то протолкнуть их очень непросто, т. к. язык консервативный и для любого даже самого полезного улучшения необходимы железные доказательства того, что
а) это точно ничего не сломает
б) это действительно нужно
Но есть класс неподвластный консерватизму: java.lang.String. Ниже список последних предложений по его улучшению (или улучшению работы с ним), многие из них уже реализованы:
  • JEP 192: String Deduplication in G1
  • JEP 250: Store Interned Strings in CDS Archives
  • JEP 254: Compact Strings
  • JEP 280: IndifyString Concatenation
  • JEP 326: Raw String Literals (Preview)
  • JEP 355: Text Blocks (Preview)
  • JEP 348: Compiler Intrinsics for Java SE APIs (в основном это пока про String.format())

Обратите внимание на сжатые строки — они затрагивают основы основ — если сравнить содержимое java.lang.String в "восьмёрке" и в "девятке", то изменилось решительно всё.
Почему именно строки
Повышенное внимание разработчиков платформы к строкам тоже понятно и подробно изложено в классическом докладе Катехизис java.lang.String. Вкратце:
  • они [строки] везде
  • они съедают весомую часть кучи
  • они [при неправильном использовании] могут ухудшить производительность
  • когда им хорошо, то хорошо всем

Подходы к прокачиванию производительности
Когда мы улучшаем производительность, то становимся перед выбором:
  • наращивать объём исполняемого
  • уменьшать / переупорядочивать объём исполняемого

Первый подход только на первый взгляд выглядит нелогичным, на деле же это не что иное как кэширование: приложению очень часто всё равно, откуда берётся то или иное значение, важна лишь его правильность. Значит можно прикрутить к приложению кэш, хранить там значения дорогих вычислений и переиспользовать их. Когда мы говорим про строки, то тут есть сразу два похожих механизма: интернирование и дедуплицирование (JEP 192). Подчёркиваю красным: это не кэширование в привычном смысле (хотя иногда может быть похоже как две капли воды).
Поскольку большинство из нас — это рядовые разработчики и влезть в плюсовый адъ внутри ВМ и сделать там что-то осмысленное могут не только лишь все (мало кто может это сделать), то для нас более перспективным является второй подход — делать меньше получая больше. О нём и поговорим.
Основная проблема строк
Проистекает она из JLS 15.18.1 и означает, что [почти] любое преобразование строки порождает новую строку, поэтому зачастую для получения прироста нужно лишь избавиться от ненужных преобразований, при чём многие из них легко формализуются и обращаются в правила статического анализатора.
Отсюда плавно вытекает стратегия и тактика улучшения работы со строками:
  • стратегия: не использовать строки там, где это возможно
  • тактика: по возможности избегать преобразования строк

Ключи и словари
Строки очень часто используются в качестве ключей (внезапно). Причиной является набор уникальных свойств, доступный прямо из коробки:
  • строки неизменяемы
  • строки определяют equals() / hashCode()
  • строки кэшируют хэш-код
  • строки сериализуемы и реализуют java.lang.Comparable (их можно класть в TreeMap)
  • строки особо реализуют Object.equals()
  • любой объект можно представить в виде строки вызвав obj.toString()

Многие знают, что набор постоянных строк-ключей можно представить в виде перечисления, что даёт возможность отказаться от HashMap в пользу EnumMap:
Map<String, ?> map = new HashMap<>();
class Constants {
  static final String MarginLeft = "margl";
  static final String MarginRight = "margr";
  static final String MarginTop = "margt";
  static final String MarginBottom = "margb";
}

легко заменяется на
Map<String, ?> map = new EnumMap<>(Constants.class);
enum Constants {
  MarginLeft,
  MarginRight,
  MarginTop,
  MarginBottom
}

что даёт более легковесный и быстрый словарь:
@Benchmark
public Object hm() {
  var map = new HashMap<>();
  map.put(Constants.MarginLeft, 1);
  map.put(Constants.MarginRight, 2);
  map.put(Constants.MarginTop, 3);
  map.put(Constants.MarginBottom, 4);
  return map;
}
@Benchmark
public Object em() {
  var map = new EnumMap<>(ConstantsEnum.class);
  map.put(ConstantsEnum.MarginLeft, 1);
  map.put(ConstantsEnum.MarginRight, 2);
  map.put(ConstantsEnum.MarginTop, 3);
  map.put(ConstantsEnum.MarginBottom, 4);
  return map;
}

Прирост ощутим:
Mode    Score    Error   Units
enumMap                        avgt   23.487 ±  0.694   ns/op
hashMap                        avgt   67.480 ±  2.395   ns/op
enumMap:·gc.alloc.rate.norm    avgt   72.000 ±  0.001    B/op
hashMap:·gc.alloc.rate.norm    avgt  256.000 ±  0.001    B/op

Перебор также пойдёт бодрее:
@Benchmark
public void hashMap(Data data, Blackhole bh) {
  Map<String, Integer> map = data.hashMap;
  for (String key : data.hashMapKeySet) {
    bh.consume(map.get(key));
  }
}
@Benchmark
public void enumMap(Data data, Blackhole bh) {
  Map<ConstantsEnum, Integer> map = data.enumMap;
  for (ConstantsEnum key : data.enumMapKeySet) {
    bh.consume(map.get(key));
  }
}

что даёт
Mode    Score    Error   Units
enumMap                        avgt   36.397 ±  3.080   ns/op
hashMap                        avgt   55.652 ±  4.375   ns/op

В сложных случаях так не получается:
// org.springframework.aop.framework.CglibAopProxy
Map<String, Integer> map = new HashMap<>();
getCallbacks(Class<?> rootClass) {
  Method[] methods = rootClass.getMethods();
  for (intx = 0; x < methods.length; x++) {
    map.put(methods[x].toString(), x);          // <------
  }
}
// зеркальный метод
accept(Method method) {
  String key = method.toString();
  // key используется тут в качестве ключа
}

Проблема понятна: вызов java.lang.reflect.Method.toString() порождает новую строку. Много ли теряем?
@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class MethodToStringBenchmark {
  private Method method;
  @Setup
  public void setup() throws Exception {
    method = getClass().getMethod("toString");
  }
  @Benchmark
  public String methodToString() { return method.toString(); }
}

Это простейший случай — вызов method.toString() возвращает строку:
"public java.lang.String java.lang.Object.toString()"

а стоит это удовольствие немало:
Mode  Score  Error   Units
methodToString                         avgt   85,4 ±  1,3   ns/op
methodToString:·gc.alloc.rate.norm     avgt  344,0 ±  0,0    B/op

Если мы провернём это в более жизненном ключе, например:
public class MethodToStringBenchmark {
  private Method method;
  @Setup
  public void setup() throws Exception {
    method = getClass().getMethod("getInstance");
  }
  @Benchmark
  public String methodToString() { return method.toString(); }
  MethodToStringBenchmark getInstance() throws ArrayIndexOutOfBoundsException {
    return null;
  }
}

то расценки существенно вырастут:
Mode     Score    Error   Units
methodToString                         avgt   199.765 ±  3.807   ns/op
methodToString:·gc.alloc.rate.norm     avgt  1126.400 ±  9.817    B/op

ведь возвращается уже более внушительная строка:
"public tsypanov.strings.reflection.MethodToStringBenchmark tsypanov.strings.reflection.MethodToStringBenchmark.getInstance() throws java.lang.ArrayIndexOutOfBoundsException"

На первый взгляд всё безнадёжно, ведь никаких enum-ов не напасёшься на все проксируемые методы. Давайте лучше присмотримся к самому классу java.lang.reflect.Method. Уже поверхностный осмотр показывает, что он вполне может быть ключом вместо строки:
  • реализует equals() / hashCode()
  • неизменяемый *

Почему неизменяемый со звёздочкой?

не торопитесь открывать, подумайте

SPL
Всё из-за него:
public final class Method extends Executable {
  @Override
  @CallerSensitive
  public void setAccessible(boolean flag) {
      AccessibleObject.checkPermission();
      if (flag) checkCanSetAccessible(Reflection.getCallerClass());
      setAccessible0(flag);
  }
}

Это тот самый случай, когда теория запрещает использовать объект этого класса в качестве ключа, ведь у него есть изменяющий состояние метод, а крестьянская смекалка говорит "Можно!". Ведь сколько бы мы ни дёргали за ручку Method.setAccessible() поведение его equals()/hashCode() не изменится.

Есть и недостатки:
  • java.lang.reflect.Method не реализует Comparable
  • хэш-код объекта Method не равен хэш-коду строки (и он не кэшируется)

В данном случае нам важно только положить пару "ключ-значение" в словарь и получить значение по ключу, следовательно меняем String на Method.
Будет ли толк от нашей заплатки в боевом приложении? Проверим на примере, который и подтолкнул меня покопаться в CglibAopProxy:
@Configuration
public class AspectConfig {
  @Bean
  ServiceAspect serviceAspect() { return new ServiceAspect(); }
  @Bean
  @Scope(BeanDefinition.SCOPE_PROTOTYPE)
  AspectedService aspectedService() { return new AspectedServiceImpl(); }
  @Bean
  AbstractAutoProxyCreator proxyCreator() {
    var factory = new AnnotationAwareAspectJAutoProxyCreator();
    factory.setProxyTargetClass(true);
    factory.setFrozen(true);           // <--- обратите внимание
    return factory;
  }
}

Небольшое пояснение: у нас есть некий компонент-прототип (это нужно, чтобы хранить состояние) с 1 методом, обёрнутым в 1 аспект. Поскольку в нашем случае мы знаем, что цепочка проброса неизменна, то её можно "заморозить", что позволяет "Спрингу" выполнить под капотом некоторые оптимизации (см. документацию).
Вычислим стоимость создания этого бина:
@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public class AspectPrototypeBenchmark {
  private AnnotationConfigApplicationContext context;
  @Setup
  public void setUp() {
    context = new AnnotationConfigApplicationContext(AspectConfig.class);
  }
  @Benchmark
  public AspectedService getAdvisedBean() {
    return context.getBean(AspectedService.class);
  }
  @TearDown
  public void closeContext() { context.close(); }
}

Имеем:
Mode      Score     Error   Units
before
getAdvisedBean                         avgt     14.024 ±   0.164   us/op
getAdvisedBean:·gc.alloc.rate.norm     avgt  10983.307 ±  14.193    B/op
after
getAdvisedBean                         avgt      8.150 ±   0.202   us/op
getAdvisedBean:·gc.alloc.rate.norm     avgt   7133.664 ±   5.594    B/op

Неплохо, как для такого простого изменения.
З.Ы. Обратите внимание, что этот бенчмарк лежит в другом репозитории, где собраны бенчмарки для "Спринга".
Составные ключи
В JDK есть класс ObjectStreamClass, использующийся при сериализации, в нём — вложенный класс FieldReflectorKey, а там внутри проблема.
public class ObjectStreamClass implements Serializable {
  private static class Caches {
    static final ConcurrentMap<FieldReflectorKey, Reference<?>> reflectors =
            new ConcurrentHashMap<>();
  }
  private static class FieldReflectorKey extends WeakReference<Class<?>> {
    private final String sigs;
    private final int hash;
    private final boolean nullClass;
    // ...
}

Фамилия имя и отчество виновного известны: JDK-6996807 FieldReflectorKey hash code computation can be improved. Уже из заголовка понятно: вычисление хэш-кода стоит неоправданно дорого. Больное место находится в конструкторе:
FieldReflectorKey(Class<?> cl, ObjectStreamField[] fields,
                    ReferenceQueue<Class<?>> queue)
{
  super(cl, queue);
  nullClass = (cl == null);
  StringBuilder sbuf = new StringBuilder();  // <---- !!!
  for (int i = 0; i < fields.length; i++) {
    ObjectStreamField f = fields[i];
    sbuf.append(f.getName()).append(f.getSignature());
  }
  sigs = sbuf.toString();
  hash = System.identityHashCode(cl) + sigs.hashCode();
}

После внесения изменений получаем:
FieldReflectorKey(Class<?> cl, ObjectStreamField[] fields,
                  ReferenceQueue<Class<?>> queue)
{
  super(cl, queue);
  nullClass = (cl == null);
  sigs = new String[2 * fields.length];
  for (int i = 0, j = 0; i < fields.length; i++) {
    ObjectStreamField f = fields[i];
    sigs[j++] = f.getName();
    sigs[j++] = f.getSignature();
  }
  hash = System.identityHashCode(cl) + Arrays.hashCode(sigs);
}

Теперь вместо цельной строки создаётся массив, заполняемый именами и сигнатурами классов, что даёт небольшой прирост:
SPECjvm2008:serial improves a little bit with this patch, and the allocation rate is down ~5%.
Ровно та же проблема была выловлена в "Спринге" в o.s.context.support.StaticMessageSource:
public class StaticMessageSource extends AbstractMessageSource {
  private final Map<String, String> messages = new HashMap<>();
  @Override
  protected String resolveCodeWithoutArguments(String code, Locale locale) {
    return this.messages.get(code + '_' + locale.toString());
  }
  public void addMessage(String code, Locale locale, String msg) {
    // ...
    this.messages.put(code + '_' + locale.toString(), msg);
  }
}

Измерить производительность можно с помощью бенчмарка:
private final String code = "code1";
private final Locale locale = Locale.getDefault();
@Benchmark
public Object concatenation(Data data) {
  return data.stringObjectMap.get(data.code + '_' + data.locale);
}

Что даёт
concatenation                          avgt     53.241 ±   1.494   ns/op
concatenation:·gc.alloc.rate.norm      avgt    120.000 ±   0.001    B/op

Решение — составной ключ, который может быть представлен в виде отдельного класса
@EqualsHashCode
@RequiredArgsConstructor
private static final class Key {
  private final String code;
  private final Locale locale;
}

списка:
Arrays.asList(code, locale);
// или в старших JDK
List.of(code, locale)

или даже записи (если вы красавчик и у вас Java 14)
private static record KeyRec(String code, Locale locale) {}

Рассмотрим их показатели:
Mode      Score     Error   Units
compositeKey                           avgt      6.065 ±   0.415   ns/op
concatenation                          avgt     53.241 ±   1.494   ns/op
list                                   avgt     31.001 ±   1.621   ns/op
compositeKey:·gc.alloc.rate.norm       avgt     ≈ 10⁻⁶              B/op
concatenation:·gc.alloc.rate.norm      avgt    120.000 ±   0.001    B/op
list:·gc.alloc.rate.norm               avgt     80.000 ±   0.001    B/op

Обратите внимание, что на создание 1 составного ключа мы выделили 0 байт, т. е. анализ области видимости отработал на отлично (чего не скажешь о списке), поэтому я предложил именно такой вариант. Однако Ёрген Холлер, занимавшийся этим изменением рассудил иначе. На первый взгляд, решение несколько странное, ведь последовательный поиск в двух словарях очевидно дороже:
Mode      Score     Error   Units
compositeKey                           avgt      6.065 ±   0.415   ns/op
mapInMap                               avgt      9.330 ±   1.010   ns/op
mapInMap:·gc.alloc.rate.norm           avgt     ≈ 10⁻⁵              B/op
compositeKey:·gc.alloc.rate.norm       avgt     ≈ 10⁻⁶              B/op

Но дороже он будет только при действенном анализе области видимости, а с этим иногда напряжёнка:
этот же бенчмарк на JDK 14
                                       Mode      Score     Error   Units
compositeKey                           avgt      7.803 ±   0.647   ns/op
mapInMap                               avgt      9.330 ±   1.010   ns/op
record                                 avgt     13.240 ±   0.691   ns/op
list                                   avgt     37.316 ±   6.355   ns/op
concatenation                          avgt     69.781 ±   7.604   ns/op
compositeKey:·gc.alloc.rate.norm       avgt     24.001 ±   0.001    B/op
mapInMap:·gc.alloc.rate.norm           avgt     ≈ 10⁻⁵              B/op
record:·gc.alloc.rate.norm             avgt     24.001 ±   0.001    B/op
list:·gc.alloc.rate.norm               avgt    105.602 ±   9.786    B/op
concatenation:·gc.alloc.rate.norm      avgt    144.004 ±   0.001    B/op

Оп-па! А ключ-то составной теперь создаётся в куче! Мораль сей басни такова: скаляризация и анализ области видимости — очень хрупкие вещи, которые не прописаны в спецификации языка и ВМ, и которые нам никто не обещает.
Вывод для разработчика простой: склейка строк для создания ключа — это плохо, ибо
  • требует относительно много времени и доппамяти
  • при частом обращении может стать узким местом

Выход есть – отдельный класс для составного ключа (в крайнем случае подойдёт массив или Arrays.asList() / List.of()).
Склеивание строк
Когда речь заходит о склейке мы часто задаём неправильный вопрос: какой способ самый лучший? Правильный вопрос, ПМСМ, звучит так: а нужно ли вообще их клеить? Для примера рассмотрим часть метода org.springframework.core.ResolvableType.toString():
StringBuilder result = new StringBuilder(this.resolved.getName());
if (hasGenerics()) {
  result.append('<');
  result.append(StringUtils.arrayToDelimitedString(getGenerics(), ", "));
  result.append('>');
}
return result.toString();

Переберём все возможные исполнения, благо их аж целых 2:
1) hasGenerics() возвращается истину и мы честно клеим строки
2) hasGenerics() возвращается ложь и мы переливаем значение this.resolved.getName() в StringBuilder, а оттуда — снова в строку
Очевидно, что во втором случае (он наиболее частый, т. к. большинство бинов нетипизированы) на выходе мы получим ту же строку, что и из this.resolved.getName(), поэтому код можно упростить, повысив одновременно его производительность:
if (hasGenerics()) {
  return this.resolved.getName()
    + '<'
    + StringUtils.arrayToDelimitedString(getGenerics(), ", ")
    + '>';
}
return this.resolved.getName();

Обратите внимание: после внесения StringBuilder-а внутрь условного блока мы можем отказаться от него в пользу + (об этом чуть ниже).
Склейка: если всё-таки нужно
Рассмотрим задачу преобразования массива байт в шестнадцатеричный вид. Решение следующее:
private static String bytesToHexString(byte[] bytes) {
  StringBuilder sb = new StringBuilder();
  for (int i = 0; i < bytes.length; i++) {
    sb.append(Integer.toString((bytes[i] & 0xff) + 0x100, 16).substring(1));
  }
  return sb.toString();
}

Вопиющая неэффективность метода bytesToHexString очевидна даже новичку: преобразование байта в строку, взятие подстроки, добавление в StringBuilder. На этом варианте останавливаться не будем (хотя он и был выловлен в коде двух проектов). Существует похожий (и тоже неэффективный) вариант решения задачи (взят из статьи про p6spy):
public String toHexString(byte[] bytes) {
  StringBuilder sb = new StringBuilder();
  for (byte b : bytes) {
    int temp = (int) b & 0xFF;
    sb.append(HEX_CHARS[temp / 16]);
    sb.append(HEX_CHARS[temp % 16]);
  }
  return sb.toString();
}

При первом же рассмотрении разработчик наверняка обратит внимание на создание StringBuilder-а конструктором по умолчанию, хотя нам известно количество проходов по циклу, а также тот факт, что при каждом проходе добавляются два знака шестнадцатеричного алфавита. Вырисовывается очевидное улучшение:
public String toHexStringPatched(byte[] bytes) {
  StringBuilder sb = new StringBuilder(bytes.length * 2);
  for (byte b : bytes) {
    int temp = (int) b & 0xFF;
    sb.append(HEX_CHARS[temp / 16]);
    sb.append(HEX_CHARS[temp % 16]);
  }
  return sb.toString();
}

Если мы прогоним через оба метода 1 Мб данных, то обнаружим, что второй даёт существенную экономию памяти при незначительном приросте по времени:
original                          avgt        4167,950 ±     82,704   us/op
patched                           avgt        3972,118 ±     34,817   us/op
original:·gc.alloc.rate.norm      avgt    13631776,184 ±      0,005    B/op
patched:·gc.alloc.rate.norm       avgt     8388664,173 ±      0,002    B/op

Оказывается, что львиную долю занимает проверка выхода за пределы массива и доступ к самому массиву:
@Override
public AbstractStringBuilder append(char c) {
  ensureCapacityInternal(count + 1);
  value[count++] = c;
  return this;
}

Обратите внимание: несмотря на точно заданный размер хранилища и известное количество проходов не существует никакого механизма, который мог бы подсказать исполнению, что проверки доступа можно выбросить. Поэтому правильным решением является отказ от StringBuilder-а в пользу голого массива:
public String toHexString(byte[] bytes) {
  char[] result = new char[bytes.length * 2];
  int idx = 0;
  for (byte b : bytes) {
    int temp = (int) b & 0xFF;
    result[idx++] = HEX_CHARS[temp / 16];
    result[idx++] = HEX_CHARS[temp % 16];
  }
  return new String(result);
}

И вот теперь мы получим существенный прирост:
original                          avgt        4167,950 ±     82,704   us/op
patched                           avgt        3972,118 ±     34,817   us/op
chars                             avgt        1377,829 ±      4,861   us/op
original:·gc.alloc.rate.norm      avgt    13631776,184 ±      0,005    B/op
patched:·gc.alloc.rate.norm       avgt     8388664,173 ±      0,002    B/op
chars:·gc.alloc.rate.norm         avgt     6291512,057 ±      0,001    B/op

Любопытно, что если запустить этот же код на старших версиях JDK, то неожиданно возникает просадка по памяти:
original                          avgt        3813,358 ±     75,014   us/op
patched                           avgt        3733,343 ±     90,589   us/op
chars                             avgt        1377,829 ±      4,861   us/op
original:·gc.alloc.rate.norm      avgt     6816056,159 ±      0,005    B/op
patched:·gc.alloc.rate.norm       avgt     4194360,157 ±      0,006    B/op
chars:·gc.alloc.rate.norm         avgt     6291512,057 ±      0,001    B/op   <----

Совершенно не очевидно для нас показатель потребления памяти для массива вернулся на прежний уровень. Причина в реализации работы со сжатыми строками:
abstract class AbstractStringBuilder implements Appendable, CharSequence {
  byte[] value;
  public AbstractStringBuilder append(char c) {
    this.ensureCapacityInternal(this.count + 1);
    if (this.isLatin1() && StringLatin1.canEncode(c)) {
      this.value[this.count++] = (byte)c;                     // <-----
    } else {
      // ...
    }
    return this;
  }
}

Если на вход StringBuilder.append(char) пришел знак, входящий в множество ASCII (а шестнадцатеричный алфавит входит туда по умолчанию), то его старший байт усекается, а младший кладётся в хранилище. Если же используется голый массив, то в него всегда кладётся полновесный char о двух байтах. Поэтому если у вас на проекте JDK 9 и выше, то шестнадцатеричный алфавит нужно объявлять как массив байт, а char[] менять на byte[].
Вывод для разработчика: иногда склейка строк сводится к задаче о буферизации с известными узкими местами:
  • проверкой выхода за пределы хранилища
  • расширением хранилища
  • переносом данных при расширении

Универсальное решение: семь раз отмерь — один раз отрежь.
Необходимо отметить, что выше описан редкий случай — известно количество проходов и объём данных, записываемых на каждом проходе. Обычно же имеем дело со следующими разновидностями:
// сложение
String str = s1 + s2 + s3;
// склеивание цепочкой
String str = new StringBuilder().append(str1).append(str2).append(str3).toString();
// склеивание путём раздельного добавления
StringBuilder sb = new StringBuilder();
sb.append(str1);
sb.append(str2);
sb.append(str3);
String str = sb.toString();

Измерим производительность с помощью бенчмарка:
private final String str1 = "1".repeat(10);
private final String str2 = "2".repeat(10);
private final String str3 = "3".repeat(10);
private final String str4 = "4".repeat(10);
private final String str5 = "5".repeat(10);
@Benchmark public String concatenation() { /*...*/ }
@Benchmark public String chainedAppend() { /*...*/ }
@Benchmark public String newLineAppend() { /*...*/ }

Ожидаемо побеждает сложение, в затылок ему дышит склеивание цепочкой:
Mode     Score     Error   Units
chainedAppend                       avgt    33,973 ±   0,974   ns/op
concatenation                       avgt    36,189 ±   1,260   ns/op
newLineAppend                       avgt    71,083 ±   5,180   ns/op
chainedAppend:·gc.alloc.rate.norm   avgt    96,000 ±   0,001    B/op
concatenation:·gc.alloc.rate.norm   avgt    96,000 ±   0,001    B/op
newLineAppend:·gc.alloc.rate.norm   avgt   272,000 ±   0,001    B/op

Из этого давно уже сделан простой и очевидный вывод: в большинстве случаев скрипач StringBuilder не нужен, сложение строк будет и проще, и производительнее. Дело в интринзификации: исполнение распознаёт подобные цепочки и обнаружив, что размер складываемых строк известен, прямо выделяет нужный объём памяти и переносит данные без использования StringBuilder-а. Логичное и несложное улучшение.
Теперь поставим вопрос иначе. Предположим, у нас есть цепочка сложения / StringBuilder.append() и логика приложения заставляет разорвать её:
StringBuilder sb = new StringBuilder()
        .append(str1)
        .append(str2)
        .append(str3);
if (smth) sb.append(str4);
return sb.append(str5).toString();

Ухудшится ли производительность и если да, то будет ли она зависеть от точки разрыва? Оказывается, что одного единственного разрыва достаточно для слома интринзификации, а без неё мы откатываемся к раздельному добавлению:
Mode     Score     Error   Units
chainedAppend                       avgt    33,973 ±   0,974   ns/op
concatenation                       avgt    36,189 ±   1,260   ns/op
newLineAppend                       avgt    71,083 ±   5,180   ns/op
tornAppend                          avgt    66,261 ±   2,095   ns/op
chainedAppend:·gc.alloc.rate.norm   avgt    96,000 ±   0,001    B/op
concatenation:·gc.alloc.rate.norm   avgt    96,000 ±   0,001    B/op
newLineAppend:·gc.alloc.rate.norm   avgt   272,000 ±   0,001    B/op
tornAppend:·gc.alloc.rate.norm      avgt   272,000 ±   0,001    B/op

Это подводит нас уже к менее очевидному выводу: сшивание цепочки даёт конские приросты и позволяет упростить код (вспомните пример с ResolvableType.toString()). Рассмотрим часть встроенного в "Спринг" профилировщика:
// o.s.a.interceptor.AbstractMonitoringInterceptor
String createInvocationTraceName(MethodInvocation invocation) {
  StringBuilder sb = new StringBuilder(getPrefix());                    // < ----
  Method method = invocation.getMethod();
  Class<?> clazz = method.getDeclaringClass();
  if (logTargetClassInvocation && clazz.isInstance(invocation.getThis())) {
    clazz = invocation.getThis().getClass();
  }
  sb.append(clazz.getName());
  sb.append('.').append(method.getName());
  sb.append(getSuffix());
  return sb.toString();
}

Обратите внимание: между объявлением переменной sb и её использованием находится другой код, а значит объявление можно сместить:
String createInvocationTraceName(MethodInvocation invocation) {
  Method method = invocation.getMethod();
  Class<?> clazz = method.getDeclaringClass();
  if (logTargetClassInvocation && clazz.isInstance(invocation.getThis())) {
    clazz = invocation.getThis().getClass();
  }
  StringBuilder sb = new StringBuilder(getPrefix());                    // < ----
  sb.append(clazz.getName());
  sb.append('.').append(method.getName());
  sb.append(getSuffix());
  return sb.toString();
}

Тут же "Идея" поможет нам всё это ужать и сделать совсем красиво:
protected String createInvocationTraceName(MethodInvocation invocation) {
  Method method = invocation.getMethod();
  Class<?> clazz = method.getDeclaringClass();
  if (logTargetClassInvocation && clazz.isInstance(invocation.getThis())) {
    clazz = invocation.getThis().getClass();
  }
  return getPrefix() + clazz.getName() + '.' + method.getName() + getSuffix();
}

Этот код не только проще и выразительнее, но и должен быть производительнее. Проверим:

Гладко вписано в бумаги, да забыли про овраги...

SPL
Mode      Score     Error   Units
before                          avgt     97,273 ±   0,974   ns/op
after                           avgt     89,089 ±   1,260   ns/op
before:·gc.alloc.rate.norm      avgt    728,000 ±   0,001    B/op
after:·gc.alloc.rate.norm       avgt    728,000 ±   0,001    B/op

Ёлки-палки, нормально же общались! Буквально пол-страницы назад в похожем как две капли воды коде ровно такой же финт ушами давал хороший прирост, а тут что-то пошло нет так. Чтобы разобраться давайте выведем наименьший пример, на котором проблема воспроизведётся:
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Fork(jvmArgsAppend = {"-Xms2g", "-Xmx2g", "-XX:+UseParallelGC"})
public class BrokenConcatenationBenchmark {
  @Benchmark
  public String slow(Data data) {
    Class<? extends Data> clazz = data.clazz;
    return "class " + clazz.getName();
  }
  @Benchmark
  public String fast(Data data) {
    Class<? extends Data> clazz = data.clazz;
    String clazzName = clazz.getName();
    return "class " + clazzName;
  }
  @State(Scope.Thread)
  public static class Data {
    Class<? extends Data> clazz = getClass();
    @Setup
    // explicitly load name via Class.getName0()
    public void setup() { clazz.getName(); }          <---- обратите внимание
  }
}

Внешне этот пример очень похож на JDK-8043677. Теперь метод Class.getName():
public String getName() {
  String name = this.name;
  if (name == null) {
    this.name = name = this.getName0();
  }
  return name;
}
private native String getName0();

Это обычный ленивый геттер: при первом обращении полю присваивается значение, дальше оно только возвращается. Теперь вспомним, что мы явно вызываем этот метод в setup(), иными словами во время прогона никаких сторонних эффектов уже быть не может. Тем не менее, просадка по производительности стабильно воспроизводится.
Признаюсь, я не нашел объяснения самостоятельно, поэтому задал вопрос на StackOverflow. На выручку пришел apangin, за что ему огромная благодарность. Дело тут вот в чём:
Виртуальная машина собирает статистику исполнения байт-кода. Если один и тот же код исполняется в разных контекстах, то итоговый профиль объединяет в себе статистику по каждому из них. Это называется отравление профиля.
Очевидно, что Class.getName() вызывается не только из кода бенчмарка. И ещё до того, как JIT начинает компиляцию бенчмарка, он уже знает, что условие
if (name == null) {
this.name = name = getName0();
}

было удовлетворено множество раз. По крайней мере, количество вхождений внутрь условного блока оказалось достаточным, чтобы эта ветвь исполнения стала статистически значимой. Поэтому компилятор не может исключить её, что ломает склейку строк.
По ссылке есть пример достижения ровно такого же эффекта без использования нативного метода. В нашем случае нужно извлечь выражение Class.getName() в отдельную переменную.
И вот теперь у нас есть желаемый прирост:
Mode      Score     Error   Units
before                          avgt     97,273 ±   0,974   ns/op
after                           avgt     13,301 ±   0,411   ns/op
before:·gc.alloc.rate.norm      avgt    728,000 ±   0,001    B/op
after:·gc.alloc.rate.norm       avgt    280,000 ±   0,001    B/op

Выводы для разработчика:
  • сшивание цепочки = упрощение кода + производительность
  • с старых изданиях JDK (<9) держи в уме угловые случаи

Склейка: среди if-ов как среди рифов
Наш следующий гость — библиотека ASM, использующаяся для работы с байт-кодом. Рассмотрим один из методов класса org.objectweb.asm.Type:
void appendDescriptor(final Class<?> clazz, final StringBuilder sb) {
  String name = clazz.getName();
  for (int i = 0; i < name.length(); ++i) {
    char car = name.charAt(i);
    sb.append(car == '.' ? '/' : car);
  }
  sb.append(';');
}

Имеем уже описанную выше проблему: данные складываются в хранилище познаково, что медленно, т. к. каждый StringBuilder.append(char) означает отдельную проверку выхода за пределы массива и доступ к нему. Чтобы обратить это в массовое добавление, нужно выразить алгоритм одним словом. И это слово — замена, ведь точка заменяется косой чертой, а все прочие знаки остаются без изменений. Значит мы можем переписать код так:
void appendDescriptor(final Class<?> clazz, final StringBuilder sb) {
  sb.append(clazz.getName().replace('.', '/'));
}

Теперь нужно проверить: выиграем или нет. Ведь у изменённого варианта есть недостаток: при одном единственном вхождении искомого знака String.replace(char, char) создаёт новую строку, что требует времени и доппамяти (чего не наблюдалось в прежнем издании).
Прогоним бенчмарк для класса java.lang.String:
@State(Scope.Thread)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(value = Mode.AverageTime)
@Fork(jvmArgsAppend = {"-Xms2g", "-Xmx2g"})
public class CharacterReplaceBenchmark {
  private final Class<?> klass = String.class;
  @Benchmark
  public StringBuilder manualReplace() {
    return ineffective(klass, new StringBuilder());
  }
  @Benchmark
  public StringBuilder stringReplace() {
    return effective(klass, new StringBuilder());
  }
}

Итог неоднозначен:
Mode     Score     Error   Units
manualReplace                        avgt    43,312 ±   1,767   ns/op
stringReplace                        avgt    30,741 ±   3,247   ns/op
manualReplace:·gc.alloc.rate.norm    avgt    56,000 ±   0,001    B/op
stringReplace:·gc.alloc.rate.norm    avgt   112,000 ±   0,001    B/op

С одной стороны имеем существенный выигрыш по времени, с другой — двукратную просадку по памяти. Если вместо java.lang.String полю klass присвоить значение
private final Class<?> klass = CharacterReplaceBenchmark.class;

то результат снова удивит:
Mode     Score     Error   Units
manualReplace                        avgt   160,336 ±   2,628   ns/op
stringReplace                        avgt    67,258 ±   1,535   ns/op
manualReplace:·gc.alloc.rate.norm    avgt   200,000 ±   0,001    B/op
stringReplace:·gc.alloc.rate.norm    avgt   240,000 ±   0,001    B/op

Время выполнения сократится более чем в 2,5 раза, при этом разница в потреблении памяти составит всего 20%. Если же имя класса будет ещё длиннее
private final Class<?> klass = org.springframework.objenesis.instantiator.perc.PercSerializationInstantiator.class;

то String.replace(char, char) будет выигрывать как по времени, так и по памяти:
Mode     Score     Error   Units
manualReplace                        avgt   212,368 ±   3,370   ns/op
stringReplace                        avgt    75,503 ±   1,028   ns/op
manualReplace:·gc.alloc.rate.norm    avgt   360,000 ±   0,001    B/op
stringReplace:·gc.alloc.rate.norm    avgt   272,000 ±   0,001    B/op

Причина в том, что StringBuilder выделяет место с запасом, а из-за отсутствия механизма предсказания совокупного объёма расширение массива всегда происходит по одной и той же формуле независимо от того, сколько данных осталось записать:
// java.lang.AbstractStringBuilder
private int newCapacity(int minCapacity) {
  // overflow-conscious code
  int newCapacity = (value.length << 1) + 2;
  if (newCapacity - minCapacity < 0) {
    newCapacity = minCapacity;
  }
  return newCapacity <= 0 || MAX_ARRAY_SIZE - newCapacity < 0
          ? hugeCapacity(minCapacity)
          : newCapacity;
}

Поэтому в примере выше потребление памяти выглядит следующим образом:
java.lang.String                        16 знаков – 16 ячеек
t.s.b.s.CharacterReplaceBenchmark       58 знаков – 70 ячеек
o.s.o.i.p.PercSerializationInstantiator 77 знаков – 142 ячейки

В худшем случае только около половины массива заполнено живыми данными, а всё остальное — пустые ячейки.
Несмотря на всё сказанное выше, существуют случаи, когда познаковый перебор и замена оказываются более выгодными:
// com.intellij.internal.statistic.beans.ConvertUsagesUtil
char c = text.charAt(i);
switch (c) {
  case GROUP_SEPARATOR:
  case GROUPS_SEPARATOR:
  case GROUP_VALUE_SEPARATOR:
  case '\'':
  case '"':
  case '=' :
    escaped.append(' ');
    break;
  default:
    escaped.append(c);
    break;
}

Если переписать это с использованием String.replace(char, char), то получится следующая цепочка:
return text
  .replace(GROUP_SEPARATOR, ' ')
  .replace(GROUPS_SEPARATOR, ' ')
  .replace(GROUP_VALUE_SEPARATOR, ' ')
  .replace('\'', ' ')
  .replace('"', ' ')
  .replace('=' , ' ');

Здесь в худшем случае (есть хотя бы 1 вхождение каждого искомого знака) мы получим 6 новых строк и 6 полных переборов. Множественные поиск/замена относительно редки, но иногда встречаются:
Выводы для разработчика:
  • неразрывное действие лучше, чем цикл
  • разовое выделение памяти быстрее, чем многократное
  • массовые операции в 99 случаях из 100 выигрывают у одиночных
  • из любого правила бывают исключения в 1 случае из 100

StringJoiner: склеивание через разделитель
Смотревшие доклад lany Java 9-14: Маленькие оптимизации знают про JDK-8054221, а именно улучшенную реализацию StringJoiner-а:
// было
public final class StringJoiner {
  private final String prefix;
  private final String delimiter;
  private final String suffix;
  private StringBuilder value;
}
// стало
public final class StringJoiner {
  private final String prefix;
  private final String delimiter;
  private final String suffix;
  private String[] elts;
  private int size;
  private int len;
}

Самое праздничное во всём этом: StringBuilder.toString():
char[] chars = new char[len + addLen];
int k = getChars(prefix, chars, 0);
if (size > 0) {
  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);
return new String(chars);

Зная подробности реализации можно использовать StringJoiner в задаче склеивания множества строк без разделителя:
StringBuilder pathBuilder = new StringBuilder();
for (PathComponent pathComponent : pathComponents) {
  pathBuilder.append(pathComponent.getPath());
}
return pathBuilder.toString();

лёгким движением руки превращается в
StringJoiner pathBuilder = new StringJoiner("");
for (PathComponent pathComponent : pathComponents) {
    pathBuilder.add(pathComponent.getPath());
}
return pathBuilder.toString();

что даёт прирост на больших объёмах данных, особенно для нелатинских строк:
latin  length    Mode     Score    Error   Units
sb                        true      10    avgt     122,2 ±    5,0   ns/op
sb                        true     100    avgt     463,5 ±   42,6   ns/op
sb                        true    1000    avgt    3446,6 ±  109,1   ns/op
sj                        true      10    avgt     141,1 ±    5,3   ns/op
sj                        true     100    avgt     356,0 ±    6,9   ns/op
sj                        true    1000    avgt    2522,1 ±  287,7   ns/op
sb                       false      10    avgt     229,8 ±   14,7   ns/op
sb                       false     100    avgt     932,4 ±    8,7   ns/op
sb                       false    1000    avgt    7456,4 ±  527,2   ns/op
sj                       false      10    avgt     192,6 ±   70,8   ns/op
sj                       false     100    avgt     577,7 ±   60,3   ns/op
sj                       false    1000    avgt    3541,9 ±  135,0   ns/op
sb:·gc.alloc.rate.norm    true      10    avgt     512,0 ±    0,0    B/op
sb:·gc.alloc.rate.norm    true     100    avgt    4376,0 ±    0,0    B/op
sb:·gc.alloc.rate.norm    true    1000    avgt   41280,0 ±    0,0    B/op
sj:·gc.alloc.rate.norm    true      10    avgt     536,0 ±   14,9    B/op
sj:·gc.alloc.rate.norm    true     100    avgt    3232,0 ±   12,2    B/op
sj:·gc.alloc.rate.norm    true    1000    avgt   30232,0 ±   12,2    B/op
sb:·gc.alloc.rate.norm   false      10    avgt    1083,2 ±    7,3    B/op
sb:·gc.alloc.rate.norm   false     100    avgt    9744,0 ±    0,0    B/op
sb:·gc.alloc.rate.norm   false    1000    avgt   93448,0 ±    0,0    B/op
sj:·gc.alloc.rate.norm   false      10    avgt     768,0 ±   12,2    B/op
sj:·gc.alloc.rate.norm   false     100    avgt    5264,0 ±    0,0    B/op
sj:·gc.alloc.rate.norm   false    1000    avgt   50264,0 ±    0,0    B/op

Теперь посмотрите на код и постарайтесь найти в нём недоработку:
char[] chars = new char[len + addLen];
int k = getChars(prefix, chars, 0);
if (size > 0) {
  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);
return new String(chars);

Ответ

SPL
char[] chars = new char[len + addLen];     // почему char[], а не byte[] ?!!
int k = getChars(prefix, chars, 0);
if (size > 0) {
  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);
return new String(chars);

А вот это уже совсем другая история. Если совсем коротко, то причина в пакете: StringJoiner лежит в java.util, а весь функционал связанный со сжатыми строками — в java.lang. Поэтому внутри StringBuider-а массив байтов, а в StringJoiner всё ещё char[]. О попытках это исправить я подробно писал в прошлой статье.
Выводы:
  • старайтесь избегать выражений вроде map.get(/* new String */) / map.put(/* new String */)
  • составной ключ вида "_" + smth почти всегда можно заменить
  • при буферизации обращайте внимание на объём данных и размер буфера
  • клейте строки через «+», зачастую StringBuilder не нужен
  • одиночные преобразования почти всегда проигрывают массовым
  • помните о StringJoiner-e и используйте его для типовых задач

Пишите свои примеры в комментариях, будем разбирать.
 ===========
 Источник:
habr.com
===========
Похожие новости: Теги для поиска: #_java, #_java, #_proizvoditelnost (производительность), #_jpoint, #_stroki (строки), #_java
Профиль  ЛС 
Показать сообщения:     
Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 23-Ноя 02:08
Часовой пояс: UTC + 5