Хотели как лучше, а получилось как всегда.
Виктор Черномырдин,
русский государственный деятель
Бывают в жизни случаи, когда ты вроде бы всё делаешь правильно, но что-то идёт не так.
Этот рассказ об одном из таких случаев.
Однажды я смотрел на этот код и думал о его ускорении:
public String appendBounds(Data data) {
int beginIndex = data.beginIndex;
int endIndex = data.endIndex;
return new StringBuilder()
.append('L')
.append(data.str, beginIndex, endIndex)
.append(';')
.toString();
}
Сперва я хотел вычислять итоговую длину строки, использую переменные beginIndex
и endIndex
(а также тот факт, что кроме урезанной строки к StringBuilder
-у будет добавлено ещё 2 знака), и передавать это значение в конструктор StringBuilder
-а, чтобы сразу выделить массив нужного размера. Эта мысль показалась мне чересчур очевидной, поэтому я решил испробовать что-то ещё. К верной мысли меня подтолкнуло то обстоятельство, что данный код никак не подсвечивался "Идеей", хотя эта умница обычно предлагает заменить короткую цепочку из StringBuilder::append
на сложение строк, что короче и легче воспринимается.
Помехой для подобного упрощения является использование метода StringBuilder.append(CharSequence, int, int)
. Учитывая, что поле data.str
является строкой, с помощью String.substring(beginIndex, endIndex)
можно выделить из неё подстроку и передать методу StringBuilder.append(String)
.
Код после преобразования:
public String appendBounds(Data data) {
int beginIndex = data.beginIndex;
int endIndex = data.endIndex;
String subString = data.str.substring(beginIndex, endIndex);
return new StringBuilder()
.append('L')
.append(subString)
.append(';')
.toString();
}
И вот теперь "Идея" предлагает упрощение:
public String appendBounds(Data data) {
int beginIndex = data.beginIndex;
int endIndex = data.endIndex;
return 'L' + data.str.substring(beginIndex, endIndex) + ';';
}
Однако, нашей целью в данном случае является не столько читаемость, сколько производительность. Сравним оба способа:
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Fork(jvmArgsAppend = {"-Xms2g", "-Xmx2g"})
public class StringBuilderAppendBenchmark {
@Benchmark
public String appendSubString(Data data) {
String latinStr = data.latinStr;
String nonLatinStr = data.nonLatinStr;
int beginIndex = data.beginIndex;
int endIndex = data.endIndex;
String substring = data.nonLatin ?
nonLatinStr.substring(beginIndex, endIndex) :
latinStr.substring(beginIndex, endIndex);
return new StringBuilder()
.append('L')
.append(substring)
.append(';')
.toString();
}
@Benchmark
public String appendBounds(Data data) {
String latinStr = data.latinStr;
String nonLatinStr = data.nonLatinStr;
int beginIndex = data.beginIndex;
int endIndex = data.endIndex;
String appended = data.nonLatin ? nonLatinStr : latinStr;
return new StringBuilder()
.append('L')
.append(appended, beginIndex, endIndex)
.append(';')
.toString();
}
@State(Scope.Thread)
public static class Data {
String latinStr;
String nonLatinStr;
@Param({"true", "false"})
boolean nonLatin;
@Param({"5", "10", "50", "100", "500", "1000"})
private int length;
private int beginIndex;
private int endIndex;
private ThreadLocalRandom random = ThreadLocalRandom.current();
@Setup
public void setup() {
latinStr = randomString("abcdefghijklmnopqrstuvwxyz");
nonLatinStr = randomString("абвгдеёжзиклмнопрстуфхцчшщьыъэюя");
beginIndex = 1;
endIndex = length + 1;
}
private String randomString(String alphabet) {
char[] chars = alphabet.toCharArray();
StringBuilder sb = new StringBuilder(length + 2);
for (int i = 0; i < length + 2; i++) {
char c = chars[random.nextInt(chars.length)];
sb.append(c);
}
return sb.toString();
}
}
}
Бенчмарк прост как две копейки: к StringBuilder
-у добавляется случайная строка, размер которой определяется полем length
, а поскольку на дворе 2019 год, то проверять нужно как строку, содержащую только знаки основной латиницы (т. н. сжатая строка, в которой каждому знаку соответствует 1 байт), так и строку с нелатинскими знаками (каждый символ представлен 2 байтами).
При поверхностном рассмотрении метод appendSubString
представляется нам более медленным, ибо объём приклеиваемых данных совпадает с таковым в методе appendBounds
, однако в методе appendSubString
есть ещё и явное создание подстроки, т. е. выделение памяти на новый объект и копирование в него содержимого из data.latinStr
/ data.nonLatinStr
.
Тем более удивительными (но только на первый взгляд) кажутся итоги измерения, выполненного мной с помощью JDK11 на домашней машине (Intel Core i5-4690, 3.50 ГГц):
Benchmark nonLatin length Score Error Units
appendBounds true 5 44,6 ± 0,4 ns/op
appendBounds true 10 45,7 ± 0,7 ns/op
appendBounds true 50 129,0 ± 0,5 ns/op
appendBounds true 100 218,7 ± 0,8 ns/op
appendBounds true 500 907,1 ± 5,5 ns/op
appendBounds true 1000 1626,4 ± 13,0 ns/op
appendSubString true 5 28,6 ± 0,2 ns/op
appendSubString true 10 30,8 ± 0,2 ns/op
appendSubString true 50 65,6 ± 0,4 ns/op
appendSubString true 100 106,6 ± 0,6 ns/op
appendSubString true 500 430,1 ± 2,4 ns/op
appendSubString true 1000 839,1 ± 8,6 ns/op
appendBounds:·gc.alloc.rate.norm true 5 184,0 ± 0,0 B/op
appendBounds:·gc.alloc.rate.norm true 10 200,0 ± 0,0 B/op
appendBounds:·gc.alloc.rate.norm true 50 688,0 ± 0,0 B/op
appendBounds:·gc.alloc.rate.norm true 100 1192,0 ± 0,0 B/op
appendBounds:·gc.alloc.rate.norm true 500 5192,0 ± 0,0 B/op
appendBounds:·gc.alloc.rate.norm true 1000 10200,0 ± 0,0 B/op
appendSubString:·gc.alloc.rate.norm true 5 136,0 ± 0,0 B/op
appendSubString:·gc.alloc.rate.norm true 10 160,0 ± 0,0 B/op
appendSubString:·gc.alloc.rate.norm true 50 360,0 ± 0,0 B/op
appendSubString:·gc.alloc.rate.norm true 100 608,0 ± 0,0 B/op
appendSubString:·gc.alloc.rate.norm true 500 2608,0 ± 0,0 B/op
appendSubString:·gc.alloc.rate.norm true 1000 5104,0 ± 0,0 B/op
appendBounds false 5 20,8 ± 0,1 ns/op
appendBounds false 10 24,0 ± 0,2 ns/op
appendBounds false 50 66,4 ± 0,4 ns/op
appendBounds false 100 111,0 ± 0,8 ns/op
appendBounds false 500 419,2 ± 2,7 ns/op
appendBounds false 1000 840,4 ± 7,8 ns/op
appendSubString false 5 25,3 ± 0,3 ns/op
appendSubString false 10 25,7 ± 0,2 ns/op
appendSubString false 50 36,0 ± 0,1 ns/op
appendSubString false 100 52,8 ± 0,4 ns/op
appendSubString false 500 206,1 ± 6,1 ns/op
appendSubString false 1000 388,1 ± 1,6 ns/op
appendBounds:·gc.alloc.rate.norm false 5 80,0 ± 0,0 B/op
appendBounds:·gc.alloc.rate.norm false 10 88,0 ± 0,0 B/op
appendBounds:·gc.alloc.rate.norm false 50 320,0 ± 0,0 B/op
appendBounds:·gc.alloc.rate.norm false 100 544,0 ± 0,0 B/op
appendBounds:·gc.alloc.rate.norm false 500 2144,0 ± 0,0 B/op
appendBounds:·gc.alloc.rate.norm false 1000 4152,0 ± 0,0 B/op
appendSubString:·gc.alloc.rate.norm false 5 96,0 ± 0,0 B/op
appendSubString:·gc.alloc.rate.norm false 10 112,0 ± 0,0 B/op
appendSubString:·gc.alloc.rate.norm false 50 192,0 ± 0,0 B/op
appendSubString:·gc.alloc.rate.norm false 100 288,0 ± 0,0 B/op
appendSubString:·gc.alloc.rate.norm false 500 1088,0 ± 0,0 B/op
appendSubString:·gc.alloc.rate.norm false 1000 2088,0 ± 0,0 B/op
Опровергая наше предположение метод appendSubString
в подавляющем большинстве случаев (в т. ч. всегда для нелатинских строк) оказался и более быстрым, и менее прожорливым (и это при том, что String::substring
возвращает новый объект). Как же так получилось?
Смотрю в книгу, вижу фигу
Приподнять завесу тайны поможет изучение исходного кода StringBuilder
-а. Оба используемых метода передают вызов в такие же методы AbstractStringBuilder
-а:
public final class StringBuilder
extends AbstractStringBuilder
implements java.io.Serializable, Comparable<StringBuilder>, CharSequence {
@Override
public StringBuilder append(String str) {
super.append(str);
return this;
}
@Override
public StringBuilder append(CharSequence s, int start, int end) {
super.append(s, start, end);
return this;
}
}
Переходим к AbstractStringBuilder.append(String)
:
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);
}
Что здесь интересно? Метод AbstractStringBuilder::inflate
, как следует из названия, расширяет массив AbstractStringBuilder.value
при объединении разнородных строк. Перемещение же данных происходит в методе String::getBytes
:
void getBytes(byte[] dst, int dstBegin, byte coder) {
if (coder() == coder) {
System.arraycopy(value, 0, dst, dstBegin << coder, value.length);
} else { // this.coder == LATIN && coder == UTF16
StringLatin1.inflate(value, 0, dst, dstBegin, value.length);
}
}
Что важно? Если строки однородны, то для перемещения данных используется интринсифицированный System::arraycopy
, в противоположном случае — StringLatin1::inflate
, которые через делегирование приводит нас к методу StringUTF16::inflate
:
// inflatedCopy byte[] -> byte[]
@HotSpotIntrinsicCandidate
public static void inflate(byte[] src, int srcOff, byte[] dst, int dstOff, int len) {
// We need a range check here because 'putChar' has no checks
checkBoundsOffCount(dstOff, len, dst);
for (int i = 0; i < len; i++) {
putChar(dst, dstOff++, src[srcOff++] & 0xff);
}
}
@HotSpotIntrinsicCandidate
static void putChar(byte[] val, int index, int c) {
assert index >= 0 && index < length(val) : "Trusted caller missed bounds check";
index <<= 1;
val[index++] = (byte)(c >> HI_BYTE_SHIFT);
val[index] = (byte)(c >> LO_BYTE_SHIFT);
}
Таким образом, если строки однородны, то для перемещения данных используется платформенно-зависимый метод System::arraycopy
, в противном случае — цикл (тоже интринсифицированный). Это означает, что при склеивании двух строк, где все знаки входят в множество основной латиницы (проще говоря умещаются в 1 байт), производительность должна быть значительно лучше, чем при склеивании разнородных строк. Бенчмарк это подтверждает (см. вывод для nonLatin = false
).
Теперь метод AbstractStringBuilder.append(CharSequence, int, int)
:
@Override
public AbstractStringBuilder append(CharSequence s, int start, int end) {
if (s == null) {
s = "null";
}
checkRange(start, end, s.length());
int len = end - start;
ensureCapacityInternal(count + len);
appendChars(s, start, end);
return this;
}
private final void appendChars(CharSequence s, int off, int end) {
if (isLatin1()) {
byte[] val = this.value;
for (int i = off, j = count; i < end; i++) {
char c = s.charAt(i);
if (StringLatin1.canEncode(c)) {
val[j++] = (byte)c;
} else {
count = j;
inflate();
StringUTF16.putCharsSB(this.value, j, s, i, end);
count += end - i;
return;
}
}
} else {
StringUTF16.putCharsSB(this.value, count, s, off, end);
}
count += end - off;
}
Здесь подход схож с существующим в предыдущем примере: для однородных строк используется более простой механизм (тут — познаковое копирование в цикле), для разнородных — обращение к StringUTF16
, однако обратите внимание, что вызываемый метод StringUTF16::putCharsSB
не интринсифицирован.
public static void putCharsSB(byte[] val, int index, CharSequence s, int off, int end) {
checkBoundsBeginEnd(index, index + end - off, val);
for (int i = off; i < end; i++) {
putChar(val, index++, s.charAt(i));
}
}
Итак, внутреннее устройство обоих методов и причина их разной производительности для нас более-менее понятны. Закономерно возникает вопрос — что делать с полученным знанием дальше? Есть сразу несколько вариантов:
1) держать это в голове и при обнаружении подозрительного кода менять его руками
2) сходить к Тагиру и попросить его запилить проверку, которая будет делать работу вместо нас
3) внести изменения в JDK с тем, чтобы код вообще не менять.
Разумеется, начнём мы с третьего. Готовы рискнуть?
Погружение в пучину
Тренироваться будем на кошках на исходниках одинадцатой явы, скачать можно здесь.
Наиболее простой и очевидный способ улучшения — выделять подстроку уже внутри метода AbstractStringBuilder.append(CharSequence, int, int)
:
// было
public AbstractStringBuilder append(CharSequence s, int start, int end) {
if (s == null) {
s = "null";
}
checkRange(start, end, s.length());
int len = end - start;
ensureCapacityInternal(count + len);
appendChars(s, start, end);
return this;
}
// стало
public AbstractStringBuilder append(CharSequence s, int start, int end) {
if (s == null) {
s = "null";
}
checkRange(start, end, s.length());
return append(s.subSequence(start, end).toString());
}
Теперь нужно собрать JDK, прогнать тесты и запустить на нём бенчмарк StringBuilderAppendBenchmark::appendBounds
, результаты которого нужно сопоставить с результатами этого же бенчмарка на исходном JDK:
# здесь колонка before содержит данные прогона на исходном JDK,
# after - на изменённом
Benchmark nonLatin length before after Units
avgt true 5 44,6 64,4 ns/op
avgt true 10 45,7 66,3 ns/op
avgt true 50 129,0 168,9 ns/op
avgt true 100 218,7 281,9 ns/op
avgt true 500 907,1 1116,2 ns/op
avgt true 1000 1626,4 2002,5 ns/op
gc.alloc.rate.norm true 5 184,0 264,0 B/op
gc.alloc.rate.norm true 10 200,0 296,0 B/op
gc.alloc.rate.norm true 50 688,0 904,0 B/op
gc.alloc.rate.norm true 100 1192,0 1552,0 B/op
gc.alloc.rate.norm true 500 5192,0 6752,0 B/op
gc.alloc.rate.norm true 1000 10200,0 13256,0 B/op
avgt false 5 20,8 38,0 ns/op
avgt false 10 24,0 37,8 ns/op
avgt false 50 66,4 82,9 ns/op
avgt false 100 111,0 138,8 ns/op
avgt false 500 419,2 531,9 ns/op
avgt false 1000 840,4 1002,7 ns/op
gc.alloc.rate.norm false 5 80,0 152,0 B/op
gc.alloc.rate.norm false 10 88,0 168,0 B/op
gc.alloc.rate.norm false 50 320,0 440,0 B/op
gc.alloc.rate.norm false 100 544,0 688,0 B/op
gc.alloc.rate.norm false 500 2144,0 2688,0 B/op
gc.alloc.rate.norm false 1000 4152,0 5192,0 B/op
Что называется, внезапно! Улучшения не только не произошло, но произошло ухудшение. Чёрт возьми, но как?
Дело в том, что в самом начале, в описании метода StringBuilder::append
я сделал одно небольшое, но критически важное упущение. Метод был описан вот так:
public final class StringBuilder {
@Override
public StringBuilder append(String str) {
super.append(str);
return this;
}
}
А вот его полный вид:
public final class StringBuilder {
@Override
@HotSpotIntrinsicCandidate
public StringBuilder append(String str) {
super.append(str);
return this;
}
}
Ява-код, который мы рассматривали выше, будучи разогретым и скомпилированным на уровне С2, не имеет никакого значения, т. к. исполняется не он, а интринсик. Это легко доказать, сняв профиль используя async-profiler. Здесь и далее профиль снимается для length = 1000
и nonLatin = true
:
# профиль метода `appendSubString`, JDK без наших изменений
ns percent samples top
---------- ------- ------- ---
19096340914 43.57% 1897673 jbyte_disjoint_arraycopy <---------
13500185356 30.80% 1343343 jshort_disjoint_arraycopy <---------
4124818581 9.41% 409533 java.lang.String.<init> # создание подстроки
2177311938 4.97% 216375 java.lang.StringUTF16.compress # создание подстроки
1557269661 3.55% 154253 java.util.Arrays.copyOfRange # создание подстроки
349344451 0.80% 34823 appendSubString_avgt_jmhStub
279803769 0.64% 27862 java.lang.StringUTF16.newString
274388920 0.63% 27312 org.openjdk.jmh.infra.Blackhole.consume
160962540 0.37% 15946 SpinPause
122418222 0.28% 11795 __memset_avx2
Кодом StringBuilder
-а (да и AbstractStringBuilder
-а ) тут даже не пахнет, почти 3/4 профиля занимает интринсик. Примерно такую же картину хотелось бы наблюдать в профиле "улучшенного" нами StringBuilder.append(CharSequence, int, int)
.
В действительности имеем вот это:
ns percent samples top
---------- ------- ------- ---
19071221451 43.78% 1897827 jbyte_disjoint_arraycopy
6409223440 14.71% 638348 jlong_disjoint_arraycopy
3933622128 9.03% 387403 java.lang.StringUTF16.newBytesFor
2067248311 4.75% 204193 java.lang.AbstractStringBuilder.ensureCapacityInternal
1929218737 4.43% 194751 java.lang.StringUTF16.compress
1678321343 3.85% 166458 java.util.Arrays.copyOfRange
1621470408 3.72% 160849 java.lang.String.checkIndex
969180099 2.22% 96018 java.util.Arrays.copyOf
581600786 1.34% 57818 java.lang.AbstractStringBuilder.<init>
417818533 0.96% 41611 appendBounds_jmhTest
406565329 0.93% 40479 java.lang.String.<init>
340972882 0.78% 33727 java.lang.AbstractStringBuilder.append
299895915 0.69% 29982 java.lang.StringBuilder.toString
183885595 0.42% 18136 SpinPause
168666033 0.39% 16755 org.openjdk.jmh.infra.Blackhole.consume
Вы скажете: "Вот же они, интринсики, в самом верху!" Действительно, только это немного не те интринсики (в т. ч. сравните имя второго сверху). Вспомним:
public final class StringBuilder {
@Override
@HotSpotIntrinsicCandidate
public StringBuilder append(String str) {
super.append(str);
return this;
}
}
Здесь интринсик подменяет вызов StringBuilder.append(String)
, но в нашем-то патче этого вызова нет! Вызывается AbstractStringBuilder.append(String)
. Наблюдаемый нами вызов jbyte_disjoint_arraycopy
— это интринсик для StringLatin1::inflate
, вызываемого из AbstractStringBuider::putStringAt
через String::getBytes
. Т. е. в отличии от StringBuilder::append
отрабатывает не только платформенно-зависимый, но и ява-код,
С причиной провала разобрались, попробуем добиться успеха иначе. Несложно догадаться, что нам необходимо каким-то образом обратиться именно к StringBuilder::append
. Сделать это можно оторвав предыдущую заплатку и внеся изменения в сам StringBuilder
:
public final class StringBuilder {
// было
@Override
public StringBuilder append(CharSequence s, int start, int end) {
super.append(s, start, end);
return this;
}
// стало
@Override
public StringBuilder append(CharSequence s, int start, int end) {
if (s == null) {
s = "null";
}
checkRange(start, end, s.length());
return this.append(s.subSequence(start, end).toString());
}
}
Вот теперь всё сделано по уму: вызывается интринсифицированный StringBuilder::append.
Пересобираем, запускаем, сравниваем:
# здесь колонка before содержит данные прогона на исходном JDK,
# after - на изменённом
Benchmark nonLatin length before after Units
avgt true 5 44,6 60,2 ns/op
avgt true 10 45,7 59,1 ns/op
avgt true 50 129,0 164,6 ns/op
avgt true 100 218,7 276,2 ns/op
avgt true 500 907,1 1088,8 ns/op
avgt true 1000 1626,4 1959,4 ns/op
gc.alloc.rate.norm true 5 184,0 264,0 B/op
gc.alloc.rate.norm true 10 200,0 296,0 B/op
gc.alloc.rate.norm true 50 688,0 904,0 B/op
gc.alloc.rate.norm true 100 1192,0 1552,0 B/op
gc.alloc.rate.norm true 500 5192,0 6752,0 B/op
gc.alloc.rate.norm true 1000 10200,0 13256,0 B/op
avgt false 5 20,8 37,9 ns/op
avgt false 10 24,0 37,9 ns/op
avgt false 50 66,4 80,9 ns/op
avgt false 100 111,0 125,6 ns/op
avgt false 500 419,2 483,6 ns/op
avgt false 1000 840,4 893,8 ns/op
gc.alloc.rate.norm false 5 80,0 152,0 B/op
gc.alloc.rate.norm false 10 88,0 168,0 B/op
gc.alloc.rate.norm false 50 320,0 440,0 B/op
gc.alloc.rate.norm false 100 544,0 688,0 B/op
gc.alloc.rate.norm false 500 2144,0 2688,0 B/op
gc.alloc.rate.norm false 1000 4152,0 5187,2 B/op
Мне, право, очень грустно, но лучше не стало. Теперь новый профиль:
ns percent samples top
---------- ------- ------- ---
19614374885 44.12% 1953620 jbyte_disjoint_arraycopy
6645299702 14.95% 662146 jlong_disjoint_arraycopy
4065789919 9.15% 400167 java.lang.StringUTF16.newBytesFor
2374627822 5.34% 234746 java.lang.AbstractStringBuilder.ensureCapacityInternal
1837858014 4.13% 183822 java.lang.StringUTF16.compress
1472039604 3.31% 145956 java.util.Arrays.copyOfRange
1316397864 2.96% 130747 appendBounds_jmhTest
956823151 2.15% 94959 java.util.Arrays.copyOf
573091712 1.29% 56933 java.lang.AbstractStringBuilder.<init>
434454076 0.98% 43202 java.lang.String.<init>
368480388 0.83% 36439 java.lang.AbstractStringBuilder.append
304409057 0.68% 30442 java.lang.StringBuilder.toString
272437989 0.61% 26833 SpinPause
201051696 0.45% 19985 java.lang.StringBuilder.<init>
198934052 0.45% 19810 appendBounds_avgt_jmhStub
Мало что изменилось. Для меня остаётся непонятным, почему интринсик не сработал при обращении к StringBuilder.append(String)
изнутри StringBuilder
-а. Есть подозрение, что вклеивание (инлайнинг) тела метода StringBuilder.append(String)
в тело StringBuilder.append(CharSequence, int, int)
что-то меняет в обработке ВМ обращений к методам.
Как бы там ни было, это фиаско, братан. Подлатать JDK не удалось, но мы по прежнему можем делать замену вручную там, где это имеет смысл.
Ответная шифровка пришла через два дня. Навигатору совсем не хочется расставаться с «Ото Велара», с фирмой, которая строит удивительно быстрые и мощные военные корабли. Навигатору не хочется читать шифровку мне. Он просто повторяет ответ командного пункта: «Нет». Шифровка не разъясняет, почему «нет». «Нет» в любом случае означает, что он –личность известная большому компьютеру. Если бы о нем ничего не было известно, то ответ был бы положительным: пробуйте. Жаль. Жаль такого, интересного человека терять. А командиру, наверное, жаль меня. Может быть, первый раз жаль. Он видит, что я рвусь в варяги. И ему совсем не хочется вновь толкать меня в борзые.
Он молчит. Но я-то знаю, что в обеспечении дикая нехватка рабочих рук:
— Я, товарищ генерал, завтра в обеспечении работаю. Разрешите идти?
— Иди. — И вдруг улыбается. — Ты знаешь, нет худа без добра.
— У меня, товарищ генерал, всегда худо без добра.
— А вот и нет. Тебе запретили его встречать, это плохо. Но к сокровищам нашего опыта мы добавили еще одну крупицу.
Выводы:
- код методов JDK в некоторых случаях не имеет отношения к настоящему исполнению, т. к. вместо тела метода может выполнится интринсик, который укрыт в недрах ВМ.
- подобные методы можно распознать, в частности на них указывает метка
@HotSpotIntrinsicCandidate
, хотя некоторые методы интринсифицированы без каких бы то ни было намёков, напримерString::equals
(и многие-многие другие). - вывод, проистекающий из первых двух, — наши рассуждения о том, как работает код JDK могут противоречить действительности. C'est la vie
P. S.
Другая возможная замена:
StringBuilder sb = new StringBuilder();
sb.append(str, 0, endIndex);
// -->
StringBuilder sb = new StringBuilder(str.substring(o, endIndex));
P. P. S.
Разработчики "Оракла" справедливо указывают, что
It seems to me rather odd and surprising to introduce a code path into
sb.append(cs,int,int) that allocates memory in order to get at an intrinsic that
only sometimes makes things run faster. As you observed, the performance
tradeoffs aren't obvious.
Instead, if we want to optimize sb.append(cs,int,int) maybe we should just go
ahead and do that, possibly by adding or rearranging the intrinsics.
Предложенное решение — интринсификация StringBuilder.append(CharSequence, int, int)
.
> Задача
> Обсуждение
P. P. S.
Интересно, что в настоящий момент при написании чего-то вроде
StringBuilder sb = new StringBuilder();
sb.append(str.substring(0, endIndex));
"Идея" предлагает упростить код до
StringBuilder sb = new StringBuilder();
sb.append(s, 0, endIndex);
Если производительность именно в этом месте вам не очень важна, наверно более правильным будет использовать второй, упрощённый вариант. Всё-таки большую часть кода мы пишем для наших товарищей, а не для машин.
Комментарии (11)
Akon32
01.02.2019 11:38Первое, что бросается в глаза — не указана capacity в конструкторе StringBuilder. Она известна, и если её указать, для выходных строк длиной >16 память под StringBuilder не будет выделяться лишний раз, и будет меньше нагрузка на gc.
С хитрыми оптимизациями JIT, возможно, это не будет иметь значения, но, мне кажется, стоит попробовать.tsypanov Автор
01.02.2019 12:18+1Действительно, передав размер конечной строки сразу в конструктор StringBuilder-а можно выделить память только один раз и ровно столько, сколько нужно. Но это почти не даёт прироста.
Представьте такой код:
public class ToHexStringConverter { private static final char[] HEX_CHARS = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' }; 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(); } public String patched_toHexString(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(); } }
Здесь оба метода преобразовывают входной массив байт в его шестнадцатеричное представление. Первый метод исходный, второй — улучшенный. Смысл улучшения в том, что мы используем известный размер массива, а также тот факт, что каждый байт соответствует двум знакам, добавляемым к StringBuilder-у, для передачи ёмкости в конструктор.
Но увы, это не даёт значимого прироста. Возьмём 20 Мб и скормим обоим методам:
@State(Scope.Thread) @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MILLISECONDS) @Fork(jvmArgsAppend = {"-XX:+UseParallelGC", "-Xms2g", "-Xmx2g"}) public class SizedStringBuilderBenchmark { private byte[] bytes; private ToHexStringConverter converter; @Setup public void init() { bytes = new byte[1024 * 1024 * 20]; converter = new ToHexStringConverter(); ThreadLocalRandom.current().nextBytes(bytes); } @Benchmark public String original() { return converter.toHexString(bytes); } @Benchmark public String patched() { return converter.patched_toHexString(bytes); } }
На выходе имеем
Benchmark Mode Cnt Score Error Units original avgt 25 124,766 ± 1,610 ms/op patched avgt 25 113,763 ± 3,432 ms/op original:·gc.alloc.rate.norm avgt 25 192938425,434 ± 0,886 B/op patched:·gc.alloc.rate.norm avgt 25 83886183,845 ± 1,341 B/op
Действительно, выигрыш по памяти более чем двукратный, но разница во времени не столь велика.
Конкретно в этом случае ощутимый прирост даст выбрасывание StringBuilder-a:
public class ToHexStringConverter { private static final char[] HEX_CHARS = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' }; //... public String chars_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); } }
Берём тот же замер:
@State(Scope.Thread) @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MILLISECONDS) @Fork(jvmArgsAppend = {"-XX:+UseParallelGC", "-Xms2g", "-Xmx2g"}) public class SizedStringBuilderBenchmark { private byte[] bytes; private ToHexStringConverter converter; @Setup public void init() { bytes = new byte[1024 * 1024 * 20]; converter = new ToHexStringConverter(); ThreadLocalRandom.current().nextBytes(bytes); } @Benchmark public String original() { return converter.toHexString(bytes); } @Benchmark public String patched() { return converter.patched_toHexString(bytes); } @Benchmark public String chars() { return converter.chars_toHexString(bytes); } }
И вот тут получаем почти 4-х кратный прирост по времени:
Benchmark Mode Cnt Score Error Units original avgt 25 124,766 ± 1,610 ms/op patched avgt 25 113,763 ± 3,432 ms/op chars avgt 25 32,367 ± 0,656 ms/op original:·gc.alloc.rate.norm avgt 25 192938425,434 ± 0,886 B/op patched:·gc.alloc.rate.norm avgt 25 83886183,845 ± 1,341 B/op chars:·gc.alloc.rate.norm avgt 25 125829182,781 ± 0,242 B/op
Akon32
01.02.2019 17:15Оригинальная ваша задача
кодpublic String appendBounds(Data data) { int beginIndex = data.beginIndex; int endIndex = data.endIndex; return new StringBuilder() .append('L') .append(data.str, beginIndex, endIndex) .append(';') .toString(); }
tsypanov Автор
01.02.2019 18:45Вы правы, передача размера в StringBuilder даёт неплохой прирост в данном случае
@Benchmark public String appendBoundsSized(Data data) { int beginIndex = data.beginIndex; int endIndex = data.endIndex; return new StringBuilder(endIndex - beginIndex + 2) .append('L') .append(data.str, beginIndex, endIndex) .append(';') .toString(); }
Вывод
Benchmark length nonLatin Score rror Units appendBounds 10 true 41,3 ± 0,9 ns/op appendBounds 100 true 143,6 ± 8,1 ns/op appendBounds 1000 true 1206,5 ± 48,7 ns/op appendBoundsSized 10 true 42,6 ± 0,7 ns/op appendBoundsSized 100 true 116,2 ± 17,1 ns/op appendBoundsSized 1000 true 880,9 ± 33,7 ns/op appendBounds 10 false 28,4 ± 0,2 ns/op appendBounds 100 false 99,0 ± 3,9 ns/op appendBounds 1000 false 663,3 ± 44,5 ns/op appendBoundsSized 10 false 29,5 ± 0,9 ns/op appendBoundsSized 100 false 68,7 ± 3,9 ns/op appendBoundsSized 1000 false 485,6 ± 11,2 ns/op appendBounds:·gc.alloc.rate.norm 10 true 200,0 ± 0,0 B/op appendBounds:·gc.alloc.rate.norm 100 true 1192,0 ± 0,0 B/op appendBounds:·gc.alloc.rate.norm 1000 true 10200,0 ± 0,0 B/op appendBoundsSized:·gc.alloc.rate.norm 10 true 192,0 ± 0,0 B/op appendBoundsSized:·gc.alloc.rate.norm 100 true 736,0 ± 0,0 B/op appendBoundsSized:·gc.alloc.rate.norm 1000 true 6144,0 ± 0,0 B/op appendBounds:·gc.alloc.rate.norm 10 false 112,0 ± 0,0 B/op appendBounds:·gc.alloc.rate.norm 100 false 544,0 ± 0,0 B/op appendBounds:·gc.alloc.rate.norm 1000 false 4152,0 ± 0,0 B/op appendBoundsSized:·gc.alloc.rate.norm 10 false 112,0 ± 0,0 B/op appendBoundsSized:·gc.alloc.rate.norm 100 false 288,0 ± 0,0 B/op appendBoundsSized:·gc.alloc.rate.norm 1000 false 2096,0 ± 0,0 B/op
Интересно, что в этом случае (малое количество вызовов StringBuilder.append) точное выделение памяти даёт очень хороший прирост, чего не скажешь о случае, когда вызовов StringBuilder.append значительно больше.
rinaty
02.02.2019 13:17Мне кажется что даже в этом примере если вы будете не один 10 мб массив конвертировать, а по очереди 10000 массивов по 1 кб разница уже будет заметна. Потому что стрингбилдер скорее всего когда кончается буффер увеличивает буфер в 2 раза в итоге при конвертации 10 мб новых выделений памяти происходит всего несколько раз (java не знаю просто из общих рассуждений)
apangin
new StringBuilder().append()...append().toString();
JIT компилятор распознаёт подобные цепочки и транслирует их как единое целое. Называется OptimizeStringConcat. Про это уже писали и на Stack Overflow, и на Хабре.
tsypanov Автор
Спасибо за ссылку, я упустил эту особенность. Интересно, почему тогда javac не превращает
в
ещё на этапе компиляции исходного кода? Что мешает такому преобразованию?
apangin
Во-первых, это неэквивалентное преобразование. Во-вторых, javac — прямолинейный компилятор, оптимизации — не его задача.
tsypanov Автор
Вы имеете ввиду неэквивалентность байт-кода? Поведение обоих методов, насколько я понимаю, одинаковое:
apangin
Не совсем. Например, в первом случае есть переменная sb, которую можно найти по имени и посмотреть значение в дебаггере на середине выражения. А ещё код StringBuilder может быть инструментирован и вернуть внезапно не this.
tsypanov Автор
Спасибо! Уже не первый год работаю, но не устаю удивляться, как много тонкостей стоит вроде бы за простым кодом.