Конкатенация строк и производительность
Содержание
1 Введение
2 Разница в "+" и StringBuffer
3 Поясняющий пример
4 Расшифровка результатов
5 Ссылки
Введение
Советы от 5 февраля 2002 "Запись методов toString" (источник и перевод на JavaGu.ru) включали следующее предложение:
Обратите внимание, что использование "+" в toString для построения возвращаемого значения не всегда является самым эффективным подходом. Возможно, вы захотите использовать вместо этого StringBuffer.
Читатель технических советов отметил, что в документации по Java говорится о том, что для фактической реализации оператора + применяется StringBuffer. Поэтому возникает вопрос, какой выигрыш в производительности, если он существует, вы получите при явном использовании StringBuffer в ваших программах? В этой статье делается попытка ответить на этот вопрос.
Для начала рассмотрим пример, в котором строка формируется путем повторения одного и того же символа:
class MyTimer {
private final long start;
public MyTimer() {
start = System.currentTimeMillis();
}
public long getElapsed() {
return System.currentTimeMillis() - start;
}
}
public class AppDemo1 {
static final int N = 47500;
public static void main(String args[]) {
// создать строку при помощи оператора +
MyTimer mt = new MyTimer();
String str1 = "";
for (int i = 1; i <= N; i++) {
str1 = str1 + "*";
}
System.out.println("elapsed time #1 = " + mt.getElapsed());
// создать строку при помощи StringBuffer
mt = new MyTimer();
StringBuffer sb = new StringBuffer();
for (int i = 1; i <= N; i++) {
sb.append("*");
}
String str2 = sb.toString();
System.out.println("elapsed time #2 = " + mt.getElapsed());
// проверка на равенство
if (!str1.equals(str2)) {
System.out.println("str1/str2 mismatch");
}
}
}После выполнения этой программы вы должны получить примерно следующий результат:
elapsed time #1 = 61890
elapsed time #2 = 16Подход №2 явно использует StringBuffer, тогда как подход №1 использует его неявно, как часть реализации оператора +. Вы можете исследовать байт-коды, использующиеся для реализации первого подхода при помощи команды:
javap -c -classpath . AppDemo1Разница в "+" и StringBuffer
Откуда такая огромная разница между этими двумя подходами? Во втором подходе символы добавляются в StringBuffer, что довольно эффективно. А в первом подходе не используется этот метод? На самом деле нет. Выражение:
str1 = str1 + "*";не добавляет символы к строке str1. Это происходит из-за того, что Java-строки постоянны, они не изменяются после создания. Вот что происходит в действительности:
StringBuffer создается
str1 копируется в него
"*" добавляется в буфер
Результат преобразуется в строку
Ссылка str1 меняется для указания на эту строку
Старая строка, на которую ранее ссылалась переменная
str1, делается доступной для сборщика мусора.
Цикл проходит через N итераций, и на каждой итерации содержимое str1 (содержащей N-1 символов) должно быть скопировано в буфер. Такое поведение подразумевает, что первый подход имеет квадратичную или худшую производительность. "Квадратичная" означает, что время выполнения пропорционально квадрату N. Есть вероятность эффективно заморозить приложение при применении такого типа цикла.
В примере AppDemo1 демонстрируется ситуация, когда периодически присоединяется одна строка к другой, так что обе строки должны быть скопированы во временную область (StringBuffer), создана новая строка и, затем, ссылка на оригинальную строку заменяется ссылкой на новую строку.
Но что если вы не выполняете этот тип операции, а вместо этого, просто имеете некоторый код, похожий на следующий:
public String toString() {
return "X=" + x + " Y=" + y;
}Здесь нет цикла или повторений и нет строки, которая становится все длиннее и длиннее. Есть какой-либо вред от применения + вместо StringBuffer в этом примере?
Поясняющий пример
В примере AppDemo1 демонстрируется ситуация, когда периодически присоединяется одна строка к другой, так что обе строки должны быть скопированы во временную область (StringBuffer), создана новая строка и, затем, ссылка на оригинальную строку заменяется ссылкой на новую строку.
Но что если вы не выполняете этот тип операции, а вместо этого, просто имеете некоторый код, похожий на следующий:
public String toString() {
return "X=" + x + " Y=" + y;
}Здесь нет цикла или повторений и нет строки, которая становится все длиннее и длиннее. Есть какой-либо вред от применения + вместо StringBuffer в этом примере?
Для ответа на этот вопрос рассмотрим дополнительный код:
class MyPoint {
private final int x, y;
private final String cache;
public MyPoint(int x, int y) {
this.x = x;
this.y = y;
cache = "X=" + x + " Y=" + y;
}
public String toString1() {
return "X=" + x + " Y=" + y;
}
public String toString2() {
StringBuffer sb = new StringBuffer();
sb.append("X=");
sb.append(x);
sb.append(" Y=");
sb.append(y);
return sb.toString();
}
public String toString3() {
String s = "";
s = s + "X=";
s = s + x;
s = s + " Y=";
s = s + y;
return s;
}
public String toString4() {
return cache;
}
}
class MyTimer {
private final long start;
public MyTimer() {
start = System.currentTimeMillis();
}
public long getElapsed() {
return System.currentTimeMillis() - start;
}
}
public class AppDemo2 {
static final int N = 1000000;
public static void main(String args[]) {
MyPoint mp = new MyPoint(37, 47);
String s1 = null;
String s2 = null;
String s3 = null;
String s4 = null;
// toString1
MyTimer mt = new MyTimer();
for (int i = 1; i <= N; i++) {
s1 = mp.toString1();
}
System.out.println("toString1 " + mt.getElapsed());
// toString2
mt = new MyTimer();
for (int i = 1; i <= N; i++) {
s2 = mp.toString2();
}
System.out.println("toString2 " + mt.getElapsed());
// toString3
mt = new MyTimer();
for (int i = 1; i <= N; i++) {
s3 = mp.toString3();
}
System.out.println("toString3 " + mt.getElapsed());
// toString4
mt = new MyTimer();
for (int i = 1; i <= N; i++) {
s4 = mp.toString4();
}
System.out.println("toString4 " + mt.getElapsed());
// проверка исправности для того, чтобы убедиться,
// что результаты, возвращенные из каждого метода toString идентичны
if (!s1.equals(s2) || !s2.equals(s3) || !s3.equals(s4)) {
System.out.println("check error");
}
}
}В этой программе создается класс MyPoint, который используется для представления точек X,Y. В ней реализуются различные методы toString для класса. Результат выполнения программы может выглядеть примерно так:
toString1 2797
toString2 2703
toString3 5656
toString4 32Расшифровка результатов
Первые два способа, использующие + и StringBuffer, имеют примерно одинаковую производительность. Поэтому вы можете сделать вывод, что эти два способа фактически идентичны. Генерируемый для toString1 байт-код указывает, что создается StringBuffer, а затем различные строки просто добавляются к нему. Полученный код очень похож на toString2.
Но не все так просто. Первая проблема в том, что вы не всегда сможете сформулировать возвращаемое из toString значение в виде отдельного выражения. toString3 и toString1 показывают идентичные результаты. Но время работы toString3 в два раза больше по причине, описанной в примере AppDemo1. Пример AppDemo2 демонстрирует ситуацию, когда надо создать возвращаемое значение за один раз. В этом случае toString2, использующий явно StringBuffer, является более хорошим выбором.
Другая проблема касается высказывания, найденного в "Спецификации по языку программирования Java" в разделе 15.18.1.2, в котором говорится:
Реализация может выполнить преобразование и конкатенацию за один шаг, чтобы избежать создания и удаления промежуточного объекта String. Для увеличения производительности повторных конкатенаций строки компилятор Java может использовать класс StringBuffer или аналогичную технику для уменьшения количества промежуточных объектов String, создающихся при вычислении выражения.
Это утверждение говорит о том, что компилятор Java не обязательно оптимизирует такое выражение как:
str1 + str2 + str3 + ...как это сделано для метода toString1, а может вместо этого создать промежуточные строковые объекты.
Поэтому будьте осторожны при использовании оператора +, особенно для длинных строк или в циклах.
Отметим, что существует даже более быстрый способ реализации toString для этого примера. MyPoint является постоянным классом. Это означает, что его экземпляры не могут быть модифицированы после создания. Учитывая это, возвращаемое из toString значение всегда будет одним и тем же. Поскольку значения одинаковы, оно может быть вычислено один раз в конструкторе MyPoint и затем просто возвращено из toString4.
Такой вид кэширования часто очень полезен, но есть и отрицательные стороны. Если класс является изменяемым, то кэширование может не иметь смысла. Тоже самое можно сказать и для ситуаций, когда вычисление значения кэша трудоемко, когда кэш занимает много памяти, или когда метод toString вызывается нечасто.
Ссылки
Дополнительная информация по этой теме находится в разделе 15.18.1 "Оператор конкатенации строк +" в "Спецификации по языку программирования Java, второе издание (http://java.sun.com/docs/books/jls/), и в разделе 5 "Строки" книги "Настройка производительности Java" Jack Shirazi.