Это текстовая версия моего доклада "Ах, эти строки" на конференции 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() - неизменяемый *
Почему неизменяемый со звёздочкой?
Всё из-за него:
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();
}Этот код не только проще и выразительнее, но и должен быть производительнее. Проверим:
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 полных переборов. Множественные поиск/замена относительно редки, но иногда встречаются:
- ConvertUsagesUtil.ensureProperKey()
- JdkUtil.quoteArg()
- EntityUtil.encode()
- SSHConfig.parseFileName()
Выводы для разработчика:
- неразрывное действие лучше, чем цикл
- разовое выделение памяти быстрее, чем многократное
- массовые операции в 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);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 и используйте его для типовых задач
Пишите свои примеры в комментариях, будем разбирать.
ElegantBoomerang
Суровая статья, никто не комментирует. Много хороших советов, спасибо!
tsypanov Автор
Рад, что советы оказались полезными :) Пользуйтесь!