@romychs23 авг 2010 в 21:33

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

4 мин

36K

Java *

+31

Комментарии 78

@standov 23 авг 2010 в 23:29

«Если нам нужны изменяемые строки, разработчики нам предлагают другие классы. Первый, который был в Java изначально — StringBuffer и более новый StringBuilder (появился начиная с версии 1.5). Как пишут в документации, StringBuilder — безопасно применять в многопоточных приложениях, но второй более эффективен.»
сломал мозг

относительно win vs linux — таблицы не соответствуют тексту

@Deepwalker 24 авг 2010 в 00:00

Там именно про класс String — в этой части вполне соответствует.

@ShadowMaster 23 авг 2010 в 23:31

JRockit изначально разрабатывала Appeal Virtual Machines, которую потом купила Bea, которую купила Oracle.

@thevery 24 авг 2010 в 00:09

для полноты картины не хватает сравнения -client/-server, разных Xmx и, возможно, экзотики типа gcj/harmony

@stasikos 24 авг 2010 в 05:47

+ разных CompileThreshold. А возможно тест стоит проводить дважды для одгого инстанса JVM, чтобы увидеть работу JIT в HotSpot.

@opeg 24 авг 2010 в 08:55

Допустим не дважды, а проводить тест существенные промежутки времени тк оптимизация идёт не один раз, а помере накопления статистики.

Сам недавно был удивлён существенному повышению производительности на тесте более 2х часов на простейшем приложении.

Так ~первые сотни запросов шли со скоростью ~100 запросов в сек.
Через 5-10 минут это было 1к-3к запросов в сек.
Через 2-3 часа 2к-5к запросов в сек.
Через 8 часов 8к-12к запросов в сек.

Суть приложения Tomcat + jsp + класс активно работающий со строками, StringBuilder и char[]

@SVlad 24 авг 2010 в 19:39

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

@apangin 24 авг 2010 в 21:50

Как разработчик JVM, уверяю: то, о чем Вы сейчас сказали, к вопросу не относится, и вообще это работает не так. Можно сколь угодно долго работать со строками, и ни в какое «хранилище» они попадать не будут, пока не будет вызван метод intern(). А выделение памяти в JVM — очень дешевая операция, даже быстрее, чем malloc() в C++.

Увеличение производительности со временем — результат именно сбора статистики и рекомпиляции методов.

@Colwin 1 сен 2010 в 08:41

Правильно — объявленные. В предложенном же случае конструкция buff += word + " "; создаст два новых объекта, а старый объект, находящийся в buff, будет удален (за исключением первой итерации, когда в buff лежит объект "", хранящийся в хранилище строк).

@Colwin 1 сен 2010 в 08:42

@romychs 24 авг 2010 в 05:55

Можно было и с разными сборщиками мусора поиграться. Думаю именно со String была бы заметна некоторая разница.

@apangin 24 авг 2010 в 00:27

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

Описка, я так понимаю. StringBuffer — для многопоточности, StringBuilder — для скорости.

@romychs 24 авг 2010 в 05:36

Спасибо, поправил.

@uglock 24 авг 2010 в 00:39

Кстати, конкатенация строк плюсом в цикле — дурной тон, у нас например за это п*здят ногами и лишают премии.
BTW, при конкатенации строк происходит создание объекта StringBuilder, выполнение append-ов всех строк и потом вызов .toString().

@KonstantinSolomatov 24 авг 2010 в 06:55

Мне кажется, это экстремизм. Если понятно, что квадратичному количеству действий браться не от куда, можно и сконкатенировать по-тупому.

@Dimonich 25 авг 2010 в 17:55

Как раз есть откуда. См. Effective Java.

@apangin 24 авг 2010 в 01:18

Все верно: str += word работает в точности как
StringBuilder tmp = new StringBuilder();
tmp.append(str);
tmp.append(word);
str = tmp.toString();
а каждый append() — это вызов System.arraycopy(), вдобавок toString() — еще один arraycopy() на всю длину буфера.
Соответственно, если строка str длиной 100000 символов, а word длиной 5 символов, то str += word должен будет выполнить копирование как минимум 200010 символов, в то время как builder.append(word) скопирует, как правило, только 5 символов. Почувствуйте разницу :) Хороший эксперимент, наглядный результат.

@LuciferOverLondon 24 авг 2010 в 07:58

А разве в циклах оно не оптимизируется? Типа, создается буфер один раз, а не стотыщ?

@apangin 24 авг 2010 в 08:31

Не. Это ж javac так компилирует, а он вообще мало что оптимизирует.

@freeOne 24 авг 2010 в 11:07

Не думаю, что для сложения ДВУХ строк создается StringBuilder.
Уверен, что используется String.concat(String), потому что он заранее создает массив из char нужного объема, копирует туда символы, а затем создает строку, не копируя более массив.

StringBuilder же (даже если компилятор сразу создаст его с буфером нужного размера, а не по умолчанию 16 чаров), в методе toString() копирует свой буфер в новую строку (до 1.5 StringBuffer — не копировал до первого изменения, но видимо посчитали, что синхронизация обходится дороже).

А для конкатенкации больше трех и более строк — согласен, испльзуется StringBuilder.

@ClintEastwood 24 авг 2010 в 11:58

Только что проверил, для 2ух строк тоже используется StringBuilder.

Исходный код

public class Test { /** * @param args */ public static void main(String[] args) { String s1 = "s1"; String s2 = "s2"; String s3 = "s3"; System.out.println("-----------------"); String res1 = s1 + s2; System.out.println(res1); System.out.println("-----------------"); String res2 = s1 + s2 + s3; System.out.println(res2); System.out.println("-----------------"); String res3 = s1; res3 += s2; System.out.println(res3); System.out.println("-----------------"); String res4 = s1; res4 += s2 + s3; System.out.println(res4); } } * This source code was highlighted with Source Code Highlighter.

Декомпилированный код

public class Test { public Test() { } public static void main(String args[]) { String s1 = "s1"; String s2 = "s2"; String s3 = "s3"; System.out.println("-----------------"); String res1 = (new StringBuilder(String.valueOf(s1))).append(s2).toString(); System.out.println(res1); System.out.println("-----------------"); String res2 = (new StringBuilder(String.valueOf(s1))).append(s2).append(s3).toString(); System.out.println(res2); System.out.println("-----------------"); String res3 = s1; res3 = (new StringBuilder(String.valueOf(res3))).append(s2).toString(); System.out.println(res3); System.out.println("-----------------"); String res4 = s1; res4 = (new StringBuilder(String.valueOf(res4))).append(s2).append(s3).toString(); System.out.println(res4); } } * This source code was highlighted with Source Code Highlighter.

@freeOne 24 авг 2010 в 12:17

Спасибо, буду знать.
Хотя мне не понятно, почему сделано так.

НЛО прилетело и опубликовало эту надпись здесь

@vak 24 авг 2010 в 03:33

Нельзя говорить о производительности языка. Можно говорить о производительности реализации языка. То есть нужно делать внятный акцент на то, какую именно реализацию (имплементацию) Java вы тестировали.

P.S. я не Java-программист. Если Java == J2EE и это больше чем язык, то это всё же не меняет сути сказанного выше.

@vak 24 авг 2010 в 03:40

уточню: содержание статьи ОК, комментарий относился лишь к названию.

@romychs 24 авг 2010 в 05:40

Это относится к реализации строк в Java. J2EE это дополнительный набор технологий, но это та же виртуальная машина с той же реализацией строк.

@vak 24 авг 2010 в 03:54

и ещё: в HotSpot вроде важно сколько раз вызывалась функция. Если мало, то эта функция не проходит JIT-компиляцию. А значит в тесте нужно сначала сделать «разогрев».

далее, «в отклонения скрывается дьявол» (с) — то есть, тест для каждой пары (виртуальная машина * тестируемый класс) надо бы запустить несколько раз, скажем 20, чтобы убедиться что отклонение от указанной вами в таблице величины замера не умаляет ваших утверждений. Общепринято указывать отклонения в результатах.

Ах, да, спасибо за статью надо коллеге дать глянуть, он в Java в отличие от меня разбирается :)

@ice9 24 авг 2010 в 06:43

Да ладно вам скромничать, всем бы так в Java не разбираться :)

@red1ynx 24 авг 2010 в 05:21

Возможно, StringBuilder и StringBuffer используют модифицированные алгоритмы соединения большого числа строк, например, как здесь: habrahabr.ru/blogs/algorithm/99373/

@JaoDa 24 авг 2010 в 05:38

можно еще ускорить, задав начальную длину StringBuffer buff = StringBuffer(100000);

а вообще, основные потери производительности идут в момент копирования. И так как String увеличивает свою длину каждый раз на столько насколько это необходимо, то StringBuffer это делает только при недостатке место (сразу на 2*старый размер +2).

вот здесь поподробней описаны все механизмы — www.precisejava.com/javaperf/j2se/StringAndStringBuffer.htm

@romychs 24 авг 2010 в 05:50

Да, хорошая статья, я читал подобную. Просто хотелось показать, что даже с дефолтным конструктором StringBuilder/StringBuffer работают значительно быстрее. Это как с BufferedInputStream/BufferedReader, есть конструктор с помощью которого можно задать размер этого самого буфера. В ряде случаев мы можем подобрать буфер так, чтоб и памяти много не израсходовать и чтение ускорить. Например, когда мы точно знаем размер читаемых объектов (и все объекты в файле одинаковой длины) и создаем буфер, кратный этому размеру.

@barker 24 авг 2010 в 08:02

Просто хотелось показать, что даже с дефолтным конструктором StringBuilder/StringBuffer работают значительно быстрее.

Имхо, это очевидно должно быть даже для джуниоров ) Ну, или хотя бы для тех, кто хотя бы образно представляет, как работаю строки в Java и что из себя представляет конкатенация строк. Выше показали, что работает через StringBuilder. Кстати, именно поэтому всё описанное относится только к конкатенации в цикле и совсем не имеет отношения к линейной конкатенации, типа String s = " bla " + bla() + " bla " + ..., на которой никакого смысла делать через StringBuilder.append нету, ибо оно так и делается, только выглядит короче и писать удобнее.

@oxff 24 авг 2010 в 06:08

А что можно сказать в плане производительности о методе String.concat()? Он тоже реализован с использованием StringBuffer?

@romychs 24 авг 2010 в 07:50

Нет. Создается новый массив символов достаточной длины и в него перегоняются символы из обеих строк. Потом из массива создается новый объект. Вот как он реализован:

    public String concat(String str) {
	int otherLen = str.length();
	if (otherLen == 0) {
	    return this;
	}
	char buf[] = new char[count + otherLen];
	getChars(0, count, buf, 0);
	str.getChars(0, otherLen, buf, count);
	return new String(0, count + otherLen, buf);
    }

@oxff 24 авг 2010 в 07:56

Я сейчас прогнал тест, указанный в данном посте, с использованием String.concat(). Результаты на моем файле (12 тыс. слов) такие:
String += String: 30 сек.
StringBuffer.append(): 25 мсек.
String.concat(): 25 мсек.

@romychs 24 авг 2010 в 08:09

Вот, а если посмотреть StringBuffer.append:

public AbstractStringBuilder append(String str) {
	if (str == null) str = "null";
        int len = str.length();
	if (len == 0) return this;
	int newCount = count + len;
	if (newCount > value.length)
	    expandCapacity(newCount);
	str.getChars(0, len, value, count);
	count = newCount;
	return this;
}

void expandCapacity(int minimumCapacity) {
	int newCapacity = (value.length + 1) * 2;
        if (newCapacity < 0) {
            newCapacity = Integer.MAX_VALUE;
        } else if (minimumCapacity > newCapacity) {
	    newCapacity = minimumCapacity;
	}
        value = Arrays.copyOf(value, newCapacity);
}

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

buff = buff.concat(word).concat(" ");

@oxff 24 авг 2010 в 08:09

Да, именно так и делаю

@u_story 24 авг 2010 в 06:09

А где параметры запуска jvm? Почему jdk не последний? Почему бы не использовать G1 сборщик мусора?

p.s. честно говоря, не очень понял, что вы хотели показать этим тестом. :(

@romychs 24 авг 2010 в 07:53

То, что я хотел показать, я написал во второй строчке поста. А использование последней версии jdk и сборщика мусора не приведет к ускорению конкатенации строк даже в 10 раз, не говоря уже о 1000.

@u_story 24 авг 2010 в 08:09

Разница между 16 и 19 ms это не 10 и не 1000, так что могли бы и получить одинаковые скорости для этих типов.
А вдруг приведут? проверьте. Вы же проверяете вещи, которые и так всем известны из учебников для джуниоров.

@romychs 24 авг 2010 в 09:19

Ну посмотрите исходники

public final class StringBuilder  extends AbstractStringBuilder
...
    public StringBuilder append(String str) {
	super.append(str);
        return this;
    }

public final class StringBuffer  extends AbstractStringBuilder
...
    public synchronized StringBuffer append(String str) {
	super.append(str);
        return this;
    }

Какие опции нужно задать JVM чтобы StringBuffer работал быстрее? Я хотел показать соотношение в скорости работы между String, StringBuffer и StringBuilder. Я не собирался сравнивать JVM между собой, потому, что такое сравнение должно быть комплексным, а не только по скорости работы со строками.

@Absolute 24 авг 2010 в 06:34

«StringBuilder — безопасно применять в многопоточных приложениях»
скорее всего опечатка, на самом деле не так, download.oracle.com/javase/1.5.0/docs/api/java/lang/StringBuilder.html

@Luminal 24 авг 2010 в 06:58

Впечатлила разница между HotSpot и JRockit на линуксе. (StringBuffer/Builder)
Вторая — в 2 раза быстрее.
Неужели ТАК заоптимайзили…

@romychs 24 авг 2010 в 07:37

Ну так получается Оракл не зря хвастается тем, что у него самая быстрая Java-машина, ну точнее — хороший JIT-компилятор :) и GC с прогнозируемым поведением. Но каждой JVM свое место. Например, пользователю не нравится ждать при старте программы в три-четыре раза дольше, пока JIT JRockit-а произведет компиляцию. Я как то сравнивал, время запуска Netbeans-а под HotSpot и JRockit, под первой ~15s, под второй больше 40. Говорят, математика быстро работает в JRockit, сам не проверял…

@whtiger 24 авг 2010 в 15:25

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

@whtiger 24 авг 2010 в 15:32

Или наоборот -client, это было полгода назад, забыл уже =( Но результаты стали практически идентичными.

@KonstantinSolomatov 24 авг 2010 в 07:01

Вы забыли написать о работе со строками как массивами char-ов. Это дало бы наибольшую производительность.

@maxcom 24 авг 2010 в 07:58

почему?

@KonstantinSolomatov 24 авг 2010 в 07:59

Потому что нет дорогих вызовов методов

@maxcom 24 авг 2010 в 08:20

глупость. Тут самая дорогая операция — аллокация нового буфера и дублирование строки.

Вызов методов оптимизирует jit, тем более что все три класса — final

@KonstantinSolomatov 24 авг 2010 в 08:28

А вы попробуйте код напишите и измерте его время работы. В java далеко не все inline-ится.

@KonstantinSolomatov 24 авг 2010 в 09:08

Вот как он jit оптимизируется: habrahabr.ru/blogs/java/102468/#comment_3184048

@ice9 24 авг 2010 в 08:27

А когда вы сами напишете расширяемый массив, там что, совсем не будет методов?

@KonstantinSolomatov 24 авг 2010 в 08:29

Реализация расширяемого массива напрямую вместо использования коллекции в критическом месте, довольно частая и эффективная оптимизация.

@ice9 24 авг 2010 в 08:45

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

@KonstantinSolomatov 24 авг 2010 в 08:47

Ну а что делать, раз JVM не делает таких оптимизаций. Не инлайнится этот масив туда, и все. Поэтому, и приходится переписывать код ручками.

@KonstantinSolomatov 24 авг 2010 в 09:03

Ну вот вам пример кода:

@KonstantinSolomatov 24 авг 2010 в 09:04

Вот вам пример кода:

public class Sandbox {
  static interface Array {
    void append(Object o);
  }

  static class ArrayListArray implements Array {
    List<Object> contents = new ArrayList<Object>();

    @Override
    public void append(Object o) {
      contents.add(o);
    }
  }

  static class SimpleArray implements Array {
    int size = 0;
    Object[] contents = new Object[16];

    @Override
    public void append(Object o) {
      if (contents.length - 1 == size) {
        Object[] newContents = new Object[contents.length * 2];
        System.arraycopy(contents, 0, newContents, 0, contents.length);
        contents = newContents;
      }

      contents[size++] = o;
    }
  }


  private static void measure(Runnable r) {
    long start = System.currentTimeMillis();
    r.run();
    System.out.println("current = " + (System.currentTimeMillis() - start));

  }

  private static void measureArray(final Array a) {
    measure(new Runnable() {
      @Override
      public void run() {
        for (int i = 0; i < 1000000; i++) {
          a.append("aaaa" + i);
        }
      }
    });
  }

  public static void main(String[] args) {    
    measureArray(new ArrayListArray());
    measureArray(new SimpleArray());
  }
}

На моей машине результаты такие: 836 мс, и 510 мс, реализация ручками дает выигрыш почти в два раза.

@ice9 24 авг 2010 в 09:48

А при чем тут коллекция? Речь о том, что внутри буфера и билдера сидит всё тот же массив.
Кстати говоря, у меня(w7, quad) разница в вашем тесте не такая впечатляющая: 575/471.

@apangin 24 авг 2010 в 13:06

А теперь поменяйте местами строчки
measureArray(new SimpleArray());
measureArray(new ArrayListArray());
и померите заново. Ну как? :-)

Забавно, что результат на самом деле зависит не от реализации, а от порядка строк.
Тем не менее, это вполне ожидаемо, если понимать, как работает HotSpot.
Вы только что написали бенчмарку, про которую в свое время Dr. Cliff Click рассказывал в своей презентации «How NOT to write a Microbenchmark».

@w32blaster 24 авг 2010 в 07:08

Спасибо. Интересная статья. В теории я давно знал, что StringBuffer быстрее, но вот только сейчас я узнал насколько он быстрее :)

@vgrichina 24 авг 2010 в 07:19

>Не совсем понятно, почему такая большая разница в работе с объектами класса String под Linux и WinXP.

Почти наверняка изза другого размера кучи по умолчанию. В тестах стоило бы задавать его явно и привести здесь в пример. Чем меньше объем кучи – тем чаще будет сборка мусора в варианте со String.

@LuciferOverLondon 24 авг 2010 в 08:04

Ещё, наверное, может быть разница из-за copy-on-write?

@vgrichina 24 авг 2010 в 08:09

хмм, при чем copy-on-write к объектам String которые неизменимы?

@LuciferOverLondon 24 авг 2010 в 09:08

Хотя сейчас уточнил, к джаве линуксовый copy-on-write не имеет отношения, только к порождению процессов. К тому же не в ту сторону прочитал цифры линукс vs виндоус.

НЛО прилетело и опубликовало эту надпись здесь

@whtiger 24 авг 2010 в 15:28

Ещё небольшая «фича» класса String:

String s = «fjkdsjfjkd… 10 кб текста… ksjdkfjdskjf»;
String s1 = s.substring(1,2);

И объект s1 занимает столько же памяти как и объект s. Понятно, что это сделано для скорости, но всё же =)

@rieder 25 авг 2010 в 13:52

Нет. Результат s.substring(1, 2) использует тот же char[] что и в исходной строке, т.е. дополнительной памяти вообще не потребляет (ну кроме самой String, как враппера над char[]).

@whtiger 26 авг 2010 в 05:00

Чорт! Хотел написать совсем же другое :)

String s = «fjkdsjfjkd… 10 кб текста… ksjdkfjdskjf»;
s = s.substring(1,2);

Вот, получается, что s остаётся здоровенным, хотя использует совсем маленький кусочек.

@apangin 26 авг 2010 в 11:06

Да, но у программиста остается возможность избавиться от ненужного хлама самому, написав
s = new String(s.substring(1, 2));

@whtiger 27 авг 2010 в 04:59

Совершенно верно, но до этого ещё нужно догадаться :) (Как самое простое — залезть в исходники String)

НЛО прилетело и опубликовало эту надпись здесь

@StShadow 24 авг 2010 в 17:49

А! Как-то будучи еще недоджуниором проводили похожие тесты.
У нас при числе итераций >= 8 строки начинали сливать строкостроителям. С тех пор таким правилом и руководствуюсь (чего не скажешь по нашим товарищам по команде из Индии, ага. Жалко, что ну никак не настучать им линейкой по пальцам :( )

@whtiger 25 авг 2010 в 06:54

Посмотрите ещё здесь: www.ibm.com/developerworks/ru/library/j-ropes/
Там есть и сравнение производительности String, StringBuffer, StringBuilder и Ropes for java.

@malkolm 25 авг 2010 в 19:09

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

@Colwin 1 сен 2010 в 08:31

String st = «Маша»;
st += «Саша»;

Создаст новый объект содержащий строку «МашаСаша» а исходные объекты будут уничтожены сборщиком мусора.

Данное высказывание неверно. Новый объект будет создан, но старые при этом не будут удалены, т.к. они находятся в хранилище строк.

@Colwin 1 сен 2010 в 08:35

Если операций конкатенации над одним и тем же строковым объектом производится много, это приводит к интенсивному процессу порождения новых объектов и добавляет работы сборщику мусора.

Опять же, неверное. Если применить конкатенацию к одному и тому же объекту, то будут созданы n объектов, при этом старый объект никуда не денется.

Если же имеется в виду конструкция вида:

for (String t : strList) {
    s += t;
}

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

@javaspecialist 17 мая 2011 в 16:19

Если бы вы запускали тесты на HotSpot JVM для java 6 update 23 или выше, то результаты StringBuilder и StringBuffer скорее всего дали бы идентичные результаты, так как начиная с этой версии по умолчанию включен EscapeAnalysis, который увидел бы что StringBuffer исползуется только одним потоком и не синхронизировал бы код вообще, тем самым превратив его по сути в StringBuilder

Зарегистрируйтесь на Хабре, чтобы оставить комментарий