Эффективный код против конкатенации строк. Разбор кода на Java™
Октябрь 27, 2021
БЕЛЛСОФТ запускает серию постов под названием «Разбор Java-кода». Все просто: инженеры дают небольшой фрагмент кода, а затем объясняют, что с ним не так.
Итак, вот наш первый пример:
int n = 100;
String s = "1";
for(int i = 0; i < n; i++)
s = s + 1;
Цикл повторяется n раз и прибавляет «1» к строке s с присвоенным значением «1».
Вы можете оценить сложность этого алгоритма?
Это не так уж и просто.
Казалось бы, временная сложность алгоритма, при котором цикл повторяется n раз, равна O(n). Но давайте запустим программу. Следует обратить внимание на то, что это конкатенация строкового аккумулятора и строкового представления целого числа. При каждом повторении цикла s увеличивается:
1
11
111
....
Поскольку строки в Java являются неизменяемым, увеличение происходит за счет копирования всего предыдущего содержимого. Количество скопированных символов составит
(1) + (1 + 1) + (1 + 1 + 1) + … ,
что представляет собой сумму n членов арифметической прогрессии, равную (n^2-n)/2. Таким образом, временная сложность алгоритма будет квадратичной O(n^2).
Давайте посмотрим, что происходит «под капотом», и как ведут себя бенчмарки. Следующее объяснение относится к версиям Java, более новым, чем 8, так как в них этот код более эффективен. Если вас интересует Java 8, вы можете ознакомиться с соответствующими материалами1. Все примеры составлены с применением Liberica JDK (с 2022 года - Axiom JDK).
Если мы посмотрим на байт-код в версиях Java 9+, мы увидим такие фрагменты как вызовы invokedynamic для конкатенации строк:
14: invokedynamic #4, 0 // InvokeDynamic #0:makeConcatWithConstants:(Ljava/lang/String;)Ljava/lang/String;
и
BootstrapMethods:
0: #38 REF_invokeStatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/String;[Ljava/lang/Object;)Ljava/lang/invoke/CallSite;
Но в целом, стандартное поведение аналогично тому, что можно увидеть в коде, который собирается для Java 8 как целевой версии, когда javac (первичный компилятор Java) генерирует код, вызывающий конкатенацию
s = new StringBuilder().append(s).append(1).toString();
Что нас интересует в этом примере? Производительность JVM, и насколько она высокая. Давайте выполним несколько тестов.
@State(Scope.Thread)
public class ConcatBench {
@Param({"100", "400"})
int n;
@Benchmark
public String chain() {
String s = "1";
for(int i = 0; i < n; i++)
s = s + 1;
return s;
}
@Benchmark
public String sameSB() {
String s = "1";
StringBuilder sb = new StringBuilder(s);
for(int i = 0; i < n; i++)
sb.append(1);
return sb.toString();
}
@Benchmark
public String newSB() {
String s = "1";
for(int i = 0; i < n; i++) {
s = new StringBuilder().append(s).append(1).toString();
}
return s;
}
}
Есть еще третий вариант, при котором вне цикла создается StringBuilder.
Если мы будем компилировать с помощью javac с целевой платформой Java 16 и выполним бенчмарк на JDK 16, мы получим следующий результат:
Benchmark (n) Score Error Units
ConcatBench.chain 100 940733.514 ± 39773.301 ops/s
ConcatBench.newSB 100 867987.506 ± 10770.221 ops/s
ConcatBench.sameSB 100 4937177.165 ± 166843.186 ops/s # 5.2x faster than chain
ConcatBench.chain 400 128595.073 ± 819.279 ops/s # 7.3x slower than n=100
ConcatBench.newSB 400 127075.294 ± 1383.764 ops/s
ConcatBench.sameSB 400 1403760.812 ± 37459.769 ops/s # 3.5x slower than n=100, 11x faster than chain
Когда n увеличится в 4 раза, выполнение кода, в котором повторно используется StringBuilder, замедлится в 3,5 раза (близко к линейному), а кода, где StringBuilder создается заново, — в 7,3 раза. Точное квадратичное замедление составляет 16 раз. Однако следует отметить дополнительные издержки и оптимизацию при копировании данных (см. StubRoutines::jbyte_disjoint_arraycopy в коде OpenJDK).
В качестве эксперимента можете запустить бенчмарки на своем оборудовании. Поиграйте с javac и версиями JDK и сравните байт-код 7, 8, 11 и 16 на JDK 7, 8, 11 и 16.
Итог: конкатенация дорого обходится
Сложность алгоритма будет квадратичной — выражается в виде суммы n членов арифметической прогрессии — и будет то же соотношение как количества операций, так и потребляемой памяти. Всему виной конкатенация строк, с которой в Java нужно обращаться с осторожностью. Производительность JVM — удивительная штука, не правда ли?
Хотите больше таких постов? Подпишитесь на нашу рассылку и получайте новые статьи первыми!
Полезные ссылки
