Перейти к основному содержимому

Советы по производительности строк

· 13 мин. чтения

Задача: Наибольшая подстрока палиндром

Для заданной строки s, верните наибольшую подстроку палиндром входящую в s. Подстрока — это непрерывная непустая последовательность символов внутри строки. Стока является палиндромом, если она читается одинаково в обоих направлениях...

ANDROMEDA 42

1. Введение

В этом руководстве мы сосредоточимся на аспекте производительности Java String API .

Мы углубимся в операции создания, преобразования и модификации строк , чтобы проанализировать доступные варианты и сравнить их эффективность.

Предложения, которые мы собираемся сделать, не обязательно подходят для каждого приложения. Но, конечно же, мы собираемся показать, как выиграть в производительности, когда критично время работы приложения.

2. Создание новой строки

Как вы знаете, в Java строки неизменяемы. Таким образом, каждый раз, когда мы создаем или объединяем объект String , Java создает новую строку — это может быть особенно затратным, если делать это в цикле.

2.1 . Использование конструктора

В большинстве случаев нам следует избегать создания строк с помощью конструктора, если мы не знаем, что делаем .

Давайте сначала создадим объект newString внутри цикла, используя конструктор new String() , а затем оператор = .

Чтобы написать наш тест, мы будем использовать инструмент JMH (Java Microbenchmark Harness).

Наша конфигурация:

@BenchmarkMode(Mode.SingleShotTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Measurement(batchSize = 10000, iterations = 10)
@Warmup(batchSize = 10000, iterations = 10)
public class StringPerformance {
}

Здесь мы используем режим SingeShotTime , который запускает метод только один раз. Поскольку мы хотим измерить производительность операций со строками внутри цикла, для этого доступна аннотация @Measurement .

Важно знать, что циклы бенчмаркинга непосредственно в наших тестах могут исказить результаты из-за различных оптимизаций, применяемых JVM .

Поэтому мы вычисляем только одну операцию и позволяем JMH позаботиться о цикле. Короче говоря, JMH выполняет итерации, используя параметр batchSize .

Теперь добавим первый микро-бенчмарк:

@Benchmark
public String benchmarkStringConstructor() {
return new String("foreach");
}

@Benchmark
public String benchmarkStringLiteral() {
return "foreach";
}

В первом тесте новый объект создается на каждой итерации. Во втором тесте объект создается только один раз. Для оставшихся итераций тот же объект возвращается из пула констант String .

Запустим тесты с количеством итераций цикла = 1 000 000 и посмотрим на результаты:

Benchmark                   Mode  Cnt  Score    Error     Units
benchmarkStringConstructor ss 10 16.089 ± 3.355 ms/op
benchmarkStringLiteral ss 10 9.523 ± 3.331 ms/op

Из значений Score мы можем ясно видеть, что разница значительна.

2.2. + Оператор

Давайте посмотрим на пример динамической конкатенации строк :

@State(Scope.Thread)
public static class StringPerformanceHints {
String result = "";
String foreach = "foreach";
}

@Benchmark
public String benchmarkStringDynamicConcat() {
return result + foreach;
}

В наших результатах мы хотим видеть среднее время выполнения. Формат выходного числа установлен в миллисекундах:

Benchmark                       1000     10,000
benchmarkStringDynamicConcat 47.331 4370.411

Теперь давайте проанализируем результаты. Как мы видим, добавление 1000 элементов в state.result занимает 47,331 миллисекунды. Следовательно, при увеличении количества итераций в 10 раз время выполнения вырастает до 4370,441 миллисекунд.

Таким образом, время выполнения увеличивается квадратично. Следовательно, сложность динамической конкатенации в цикле из n итераций составляет O(n^2) .

2.3. Строка.concat()

Еще один способ объединения строк — использование метода concat() :

@Benchmark
public String benchmarkStringConcat() {
return result.concat(foreach);
}

Единица времени вывода — миллисекунда, количество итераций — 100 000. Таблица результатов выглядит так:

Benchmark              Mode  Cnt  Score     Error     Units
benchmarkStringConcat ss 10 3403.146 ± 852.520 ms/op

2.4. Строка.формат()

Другой способ создания строк — использование метода String.format() . Под капотом он использует регулярные выражения для анализа ввода.

Давайте напишем тестовый пример JMH:

String formatString = "hello %s, nice to meet you";

@Benchmark
public String benchmarkStringFormat_s() {
return String.format(formatString, foreach);
}

После запускаем его и видим результаты:

Number of Iterations      10,000   100,000   1,000,000
benchmarkStringFormat_s 17.181 140.456 1636.279 ms/op

Хотя код с String.format() выглядит более чистым и читабельным, мы не выигрываем здесь с точки зрения производительности.

2.5. StringBuilder и StringBuffer

У нас уже есть статья , объясняющая StringBuffer и StringBuilder . Поэтому здесь мы покажем только дополнительную информацию об их производительности. StringBuilder использует массив с изменяемым размером и индекс, указывающий положение последней ячейки, используемой в массиве. Когда массив заполнен, он увеличивается в два раза и копирует все символы в новый массив. ``

Принимая во внимание, что изменение размера происходит не очень часто, мы можем рассматривать каждую операцию append() как постоянное время O(1) . С учетом этого весь процесс имеет сложность O(n) .

После изменения и запуска теста динамической конкатенации для StringBuffer и StringBuilder мы получаем:

Benchmark               Mode  Cnt  Score   Error  Units
benchmarkStringBuffer ss 10 1.409 ± 1.665 ms/op
benchmarkStringBuilder ss 10 1.200 ± 0.648 ms/op

Хотя разница в баллах невелика, мы можем заметить , что StringBuilder работает быстрее .

К счастью, в простых случаях нам не нужен StringBuilder , чтобы соединить одну строку с другой. Иногда статическая конкатенация с + может фактически заменить StringBuilder . Под капотом последние компиляторы Java будут вызывать StringBuilder.append() для объединения строк .

Это означает значительный выигрыш в производительности.

3. Коммунальные операции

3.1. StringUtils.replace() против String.replace()

Интересно знать, что версия Apache Commons для замены String работает лучше, чем собственный метод replace() String . Ответ на это различие лежит в их реализации. String.replace() использует шаблон регулярного выражения для соответствия String.

Напротив, StringUtils.replace() широко использует indexOf() , который работает быстрее.

Теперь пришло время тестов производительности:

@Benchmark
public String benchmarkStringReplace() {
return longString.replace("average", " average !!!");
}

@Benchmark
public String benchmarkStringUtilsReplace() {
return StringUtils.replace(longString, "average", " average !!!");
}

Установив размер партии в 100 000, мы представляем результаты:

Benchmark                     Mode  Cnt  Score   Error   Units
benchmarkStringReplace ss 10 6.233 ± 2.922 ms/op
benchmarkStringUtilsReplace ss 10 5.355 ± 2.497 ms/op

Хотя разница между числами не слишком велика, StringUtils.replace() имеет лучший результат. Конечно, числа и разрыв между ними могут варьироваться в зависимости от таких параметров, как количество итераций, длина строки и даже версия JDK.

С последними версиями JDK 9+ (наши тесты выполняются на JDK 10) обе реализации имеют примерно одинаковые результаты. Теперь давайте понизим версию JDK до 8 и снова проведем тесты:

Benchmark                     Mode  Cnt   Score    Error     Units
benchmarkStringReplace ss 10 48.061 ± 17.157 ms/op
benchmarkStringUtilsReplace ss 10 14.478 ± 5.752 ms/op

Разница в производительности сейчас огромна и подтверждает теорию, которую мы обсуждали в начале.

3.2. расколоть()

Прежде чем мы начнем, будет полезно проверить методы разделения строк, доступные в Java.

Когда возникает необходимость разделить строку с помощью разделителя, первая функция, которая приходит нам на ум, обычно это String.split(regex) . Однако это приводит к серьезным проблемам с производительностью, поскольку принимает аргумент регулярного выражения. В качестве альтернативы мы можем использовать класс StringTokenizer , чтобы разбить строку на токены.

Другой вариант — API -интерфейс Splitter от Guava. Наконец, старый добрый indexOf() также доступен для повышения производительности нашего приложения, если нам не нужны функциональные возможности регулярных выражений.

Теперь пришло время написать эталонные тесты для опции String.split() :

String emptyString = " ";

@Benchmark
public String [] benchmarkStringSplit() {
return longString.split(emptyString);
}

Pattern.split() :

@Benchmark
public String [] benchmarkStringSplitPattern() {
return spacePattern.split(longString, 0);
}

StringTokenizer :

List stringTokenizer = new ArrayList<>();

@Benchmark
public List benchmarkStringTokenizer() {
StringTokenizer st = new StringTokenizer(longString);
while (st.hasMoreTokens()) {
stringTokenizer.add(st.nextToken());
}
return stringTokenizer;
}

Строка.indexOf() :

List stringSplit = new ArrayList<>();

@Benchmark
public List benchmarkStringIndexOf() {
int pos = 0, end;
while ((end = longString.indexOf(' ', pos)) >= 0) {
stringSplit.add(longString.substring(pos, end));
pos = end + 1;
}
stringSplit.add(longString.substring(pos));
return stringSplit;
}

Разделитель гуавы :

@Benchmark
public List<String> benchmarkGuavaSplitter() {
return Splitter.on(" ").trimResults()
.omitEmptyStrings()
.splitToList(longString);
}

Наконец, мы запускаем и сравниваем результаты для batchSize = 100,000 :

Benchmark                     Mode  Cnt    Score    Error    Units
benchmarkGuavaSplitter ss 10 4.008 ± 1.836 ms/op
benchmarkStringIndexOf ss 10 1.144 ± 0.322 ms/op
benchmarkStringSplit ss 10 1.983 ± 1.075 ms/op
benchmarkStringSplitPattern ss 10 14.891 ± 5.678 ms/op
benchmarkStringTokenizer ss 10 2.277 ± 0.448 ms/op

Как видим, наихудшую производительность имеет метод BenchmarkStringSplitPattern , где мы используем класс Pattern . В результате мы можем узнать, что использование класса регулярного выражения с методом split() может привести к многократной потере производительности.

Аналогично, мы заметили, что самые быстрые результаты дают примеры с использованием indexOf() и split() .

3.3. Преобразование в строку

В этом разделе мы собираемся измерить показатели преобразования строк во время выполнения. Чтобы быть более конкретным, мы рассмотрим метод конкатенации Integer.toString() :

int sampleNumber = 100;

@Benchmark
public String benchmarkIntegerToString() {
return Integer.toString(sampleNumber);
}

String.valueOf() :

@Benchmark
public String benchmarkStringValueOf() {
return String.valueOf(sampleNumber);
}

[некоторое целочисленное значение] + «» :

@Benchmark
public String benchmarkStringConvertPlus() {
return sampleNumber + "";
}

Строка.формат() :

String formatDigit = "%d";

@Benchmark
public String benchmarkStringFormat_d() {
return String.format(formatDigit, sampleNumber);
}

После запуска тестов мы увидим вывод для batchSize = 10,000 :

Benchmark                     Mode  Cnt   Score    Error  Units
benchmarkIntegerToString ss 10 0.953 ± 0.707 ms/op
benchmarkStringConvertPlus ss 10 1.464 ± 1.670 ms/op
benchmarkStringFormat_d ss 10 15.656 ± 8.896 ms/op
benchmarkStringValueOf ss 10 2.847 ± 11.153 ms/op

Проанализировав результаты, мы видим, что тест для Integer.toString() имеет лучший результат — 0,953 миллисекунды . Напротив, преобразование, включающее String.format("%d") , имеет наихудшую производительность.

Это логично, потому что синтаксический анализ строки формата является дорогостоящей операцией.

3.4. Сравнение строк

Давайте оценим различные способы сравнения строк. Количество итераций равно 100 000 .

Вот наши тесты производительности для операции String.equals() :

@Benchmark
public boolean benchmarkStringEquals() {
return longString.equals(foreach);
}

String.equalsIgnoreCase() :

@Benchmark
public boolean benchmarkStringEqualsIgnoreCase() {
return longString.equalsIgnoreCase(foreach);
}

String.matches() :

@Benchmark
public boolean benchmarkStringMatches() {
return longString.matches(foreach);
}

String.compareTo() :

@Benchmark
public int benchmarkStringCompareTo() {
return longString.compareTo(foreach);
}

После запускаем тесты и выводим результаты:

Benchmark                         Mode  Cnt    Score    Error  Units
benchmarkStringCompareTo ss 10 2.561 ± 0.899 ms/op
benchmarkStringEquals ss 10 1.712 ± 0.839 ms/op
benchmarkStringEqualsIgnoreCase ss 10 2.081 ± 1.221 ms/op
benchmarkStringMatches ss 10 118.364 ± 43.203 ms/op

Как всегда, цифры говорят сами за себя. Matches () занимает больше всего времени, так как использует регулярное выражение для сравнения равенства.

Напротив, equals () и equalsIgnoreCase () являются лучшим выбором .

3.5. String.matches() против предварительно скомпилированного шаблона

Теперь давайте отдельно рассмотрим шаблоны String.matches() и Matcher.matches() . Первый принимает регулярное выражение в качестве аргумента и компилирует его перед выполнением.

Поэтому каждый раз, когда мы вызываем String.matches() , он компилирует Pattern:

@Benchmark
public boolean benchmarkStringMatches() {
return longString.matches(foreach);
}

Второй метод повторно использует объект Pattern :

Pattern longPattern = Pattern.compile(longString);

@Benchmark
public boolean benchmarkPrecompiledMatches() {
return longPattern.matcher(foreach).matches();
}

А теперь результаты:

Benchmark                      Mode  Cnt    Score    Error   Units
benchmarkPrecompiledMatches ss 10 29.594 ± 12.784 ms/op
benchmarkStringMatches ss 10 106.821 ± 46.963 ms/op

Как мы видим, сопоставление с предварительно скомпилированным регулярным выражением работает примерно в три раза быстрее.

3.6. Проверка длины

Наконец, давайте сравним метод String.isEmpty() :

@Benchmark
public boolean benchmarkStringIsEmpty() {
return longString.isEmpty();
}

и метод String.length() :

@Benchmark
public boolean benchmarkStringLengthZero() {
return emptyString.length() == 0;
}

Во-первых, мы вызываем их через longString = «Привет, foreach, я немного длиннее, чем другие строки в среднем». Размер партии составляет 10 000 :

Benchmark                  Mode  Cnt  Score   Error  Units
benchmarkStringIsEmpty ss 10 0.295 ± 0.277 ms/op
benchmarkStringLengthZero ss 10 0.472 ± 0.840 ms/op

После установим в longString="" пустую строку и снова запустим тесты:

Benchmark                  Mode  Cnt  Score   Error  Units
benchmarkStringIsEmpty ss 10 0.245 ± 0.362 ms/op
benchmarkStringLengthZero ss 10 0.351 ± 0.473 ms/op

Как мы заметили, методы BenchmarkStringLengthZero() и BenchmarkStringIsEmpty() в обоих случаях имеют примерно одинаковый балл. Однако вызов isEmpty() работает быстрее, чем проверка того, равна ли длина строки нулю .

4. Дедупликация строк

Начиная с JDK 8, функция дедупликации строк доступна для устранения потребления памяти. Проще говоря, этот инструмент ищет строки с одинаковым или повторяющимся содержимым, чтобы сохранить одну копию каждого отдельного строкового значения в пуле строк .

В настоящее время существует два способа обработки дубликатов строк :

  • используя String.intern() вручную
  • включение дедупликации строк

Давайте подробнее рассмотрим каждый вариант.

4.1. String.интерн()

Прежде чем двигаться дальше, будет полезно прочитать о ручном интернировании в нашей статье . С помощью String.intern() мы можем вручную установить ссылку на объект String внутри глобального пула строк .

Затем JVM может использовать возврат ссылки, когда это необходимо. С точки зрения производительности наше приложение может значительно выиграть от повторного использования строковых ссылок из пула констант.

Важно знать, что пул строк JVM не является локальным для потока. Каждая строка , которую мы добавляем в пул, также доступна для других потоков .

Однако есть и серьезные недостатки:

  • для правильной поддержки нашего приложения нам может потребоваться установить параметр JVM -XX:StringTableSize для увеличения размера пула. JVM требуется перезагрузка, чтобы увеличить размер пула
  • вызов String.intern() вручную занимает много времени . Он растет в линейном алгоритме времени со сложностью O (n)
  • кроме того, частые вызовы длинных строковых объектов могут вызвать проблемы с памятью.

Чтобы получить проверенные цифры, давайте проведем тестовый тест:

@Benchmark
public String benchmarkStringIntern() {
return foreach.intern();
}

Кроме того, выходные результаты указаны в миллисекундах:

Benchmark               1000   10,000  100,000  1,000,000
benchmarkStringIntern 0.433 2.243 19.996 204.373

Заголовки столбцов здесь представляют разное количество итераций от 1000 до 1 000 000 . Для каждого номера итерации у нас есть оценка производительности теста. Как мы видим, оценка резко возрастает в дополнение к количеству итераций.

4.2. Включить дедупликацию автоматически

Во-первых, эта опция является частью сборщика мусора G1. По умолчанию эта функция отключена. Поэтому нам нужно включить его с помощью следующей команды:

-XX:+UseG1GC -XX:+UseStringDeduplication

Важно отметить, что включение этого параметра не гарантирует дедупликации строк . Кроме того, он не обрабатывает молодые строки. Для управления минимальным возрастом обработки строк доступна опция XX:StringDeduplicationAgeThreshold=3 JVM. Здесь 3 — параметр по умолчанию.

5. Резюме

В этом уроке мы пытаемся дать несколько советов по более эффективному использованию строк в нашей повседневной жизни кодирования.

В результате мы можем выделить некоторые предложения, чтобы повысить производительность нашего приложения :

  • при объединении строк StringBuilder является наиболее удобным вариантом , который приходит на ум. Однако с маленькими строками операция + имеет почти такую же производительность. Под капотом компилятор Java может использовать класс StringBuilder для уменьшения количества строковых объектов.
  • чтобы преобразовать значение в строку, [some type].toString() ( например, Integer.toString() ) работает быстрее, чем String.valueOf() . Поскольку эта разница несущественна, мы можем свободно использовать String.valueOf() , чтобы не иметь зависимости от типа входного значения.
  • когда дело доходит до сравнения строк, пока ничто не сравнится с String.equals().
  • Дедупликация строк повышает производительность больших многопоточных приложений. Но чрезмерное использование String.intern() может привести к серьезным утечкам памяти, что замедлит работу приложения.
  • для разделения строк мы должны использовать indexOf() , чтобы выиграть в производительности . Однако в некоторых некритичных случаях может подойти функция String.split() .
  • Использование Pattern.match() значительно повышает производительность строки.
  • String.isEmpty() быстрее, чем String .length() == 0

Кроме того, имейте в виду, что цифры, которые мы представляем здесь, являются просто результатами тестов JMH, поэтому вам всегда следует тестировать в рамках вашей собственной системы и среды выполнения, чтобы определить влияние таких оптимизаций.

Наконец, как всегда, код, использованный во время обсуждения, можно найти на GitHub .