Содержание

понедельник, 16 мая 2011 г.

java.lang.String: вы уверены, что знаете про строки все?

Казалось бы, что может быть непонятно о таком часто используемом объекте как строки? Я тоже так думал долгие годы, однако, если почитать документацию и копнуть поглубже о некоторых свойствах строк, то можно найти много интересного. Например, я только недавно узнал, что время операции intern зависит от размера пула, что, на самом деле, созданную строку можно поменять стандартными средствами java, а в версии JVM 1.4 использование String, строго говоря, не является потокобезопасным.


Класс java.lang.String состоит из трех final полей: массив символов, длина строки и сдвиг в массиве, с помощью которого реализуется метод substring. Так же в этом классе есть поле, в котором хранится посчитанный хэшкод, после первого вызова метода hashCode.

Свойство Immutable и потокобезопасность
Так как все логические поля класса являются final, то модель памяти java 5.0 гарантирует, что после вызова конструктора все потоки, которые видят ссылку на экземпляр этого класса, увидят и все final поля. Однако до java 5 этого никто не гарантировал, поэтому поток, который данную строку не создавал, вполне мог получить ссылку на инконсистентный (с его точки зрения) объект.

Постойте, но, ведь, значение строки можно поменять через reflection:
Таким образом, получается, что строку можно поменять, а другой поток этих изменений и не увидит? Неправда - видимость измененных final полей через reflection тоже гарантируется моделью памяти java 5.0.

Методы, над реализацией которых, мало кто задумывается
Как я уже упоминал вначале, метод substring(int beginIndex, int endIndex) не копирует содержимое массива символов, а использует ссылку на оригинальный массив и выставляет соответствующим образом поля длины строки и сдвига. Таким образом, если вы считали большой файл в строку, потом взяли из него подстроку и удалили ссылку на первый объект, то память у вас нисколько не освободиться. Так же если вы сериализуете полученную подстроку стандартными средствами и передаете её по сети, то опять же ничего хорошего не выйдет, так как будет сериализован весь оригинальный массив и количество передаваемых байтов по сети вас неприятно удивит. Если это ваш случай, то после нахождения подстроки вы можете воспользоваться конструктором String(String original), который скопирует только реально используемую часть массива. Кстати, если этот конструктор вызывать на стоке длиной равной длине массива символов, то копирования в этом случае происходить не будет, а будет использоваться ссылка на оригинальный массив.

Методы String(byte[] bytes) и getBytes() кодируют и декодируют строку в байты и наоборот, используя кодировку по умолчанию, которую можно переопределить запустив JVM с параметром "Dfile.encoding=". Если вы кодировку не переопределяете, то используется UTF-8. Если её не присутствует в системе, то - ISO-8859-1. Если нет и её, то JVM завершается с кодом -1. Но когда я пытался выставить "Dfile.encoding=" в java 1.4, то она у меня не подцеплялась. Погуглив немного, я выяснил, что с данной проблемой сталкивался не только я, правда, почему этот параметр не хочет работать, я так и не нашел.

Важно не путать вышеупомянутые методы с String(byte[] ascii, int hibyte), String(byte[] ascii, int hibyte, int offset, int count) и getBytes(int srcBegin, int srcEnd, byte[] dst, int dstBegin), которые могут некорректно преобразовать символы в байты и обратно.

Переопределение операции "+"

Здесь важно понимать, что данный оператор переопределяется не на уровне байткода, а еще на этапе компиляции java файла в байткод. Если вы декомпилируете байткод, то уже не увидите никакого сложения,а вместо операции
вы уже увидите что-то похожее на
Т.е. смысла засорять ваш код и вместо простого знака "+" городить громоздкий и плохо читаемый код из StringBuilder смысла никакого нет. Даже скажу больше, те кто в java 1.4. вместо плюсов писали StringBuffer, то их код в пятой джаве теперь может работать даже медленнее, так как StringBuffer работает не быстрее чем StringBuilder.
Еще в последних версиях JVM появился замечательный оптимизационный флаг -XX:+OptimizeStringConcat, который при вызове метода StringBuilder.toString() не будет копировать внутренний массив StringBuilder в новый String, а будет использовать тот же массив, таким образом операция конкатенации будет проходить вообще без копирования массивов.

Однако стоить заметить, что в циклах JVM вам может и не заменить операцию "+" на StringBuilder. Вернее она может заменить её на создание нового StringBuilder на каждом шаге цикла, т.е. код
может быть скомпилирован в
Да, раз уж начал об этом писать, то, наверное, стоить упомянуть, что код String a = "b" + "c" скомпилируется в String a = "bc"
Сколько же String занимает места в памяти?
Казалось, бы чего тут сложного - строка это объект с тремя полями int и массивом char'ов, т.е. 

[8 bytes (заголовок объекта) + 3*4(int) + 4 (ссылка на массив)]{выравнивание по 8 байтам} + [8 bytes (заголовок объекта массива) + 4(int длины массива) + 2(char)*длина_строки]{выравнивание по 8 байтам} = 24 + [12 + 2*length]{выравнивание по 8 байтам} = [36 + 2*length]{выравнивание по 8 байтам}

Получается пустая строка в сумме будет весить 40 байтов.

Теперь посмотрим во что это обернется на 64 битной jvm:

[16 bytes (заголовок объекта) + 3*4(int) + 8 (ссылка на массив)]{выравнивание по 8 байтам} + [24 bytes (заголовок массива) + 2(char)*длина_строки]{выравнивание по 8 байтам} = 40 + [24 + 2*length]{выравнивание по 8 байтам} = 64 + 2*length{выравнивание по 8 байтам}
Таким образом пустая строка уже вести 64 байта.

Если же у нас включена опция (-XX:+UseCompressedOops), которая в последних JVM уже работает по умолчанию для куч размером меньше 32 гигов, то имеем следующую арифметику:

[16 bytes (заголовок объекта) + 3*4(int) + 4 (ссылка на массив)]{выравнивание по 8 байтам} + [16 bytes (заголовок массива) + 2(char)*длина_строки]{выравнивание по 8 байтам} = 32 + [16 + 2*length]{выравнивание по 8 байтам} = 48 + 2*length{выравнивание по 8 байтам}

Значит для пустой строки в этом случае нам надо 48 байтов.

Так же не стоит забывать о существовании параметра -XX:+UseCompressedStrings, при использовании которого, ANSII строки будут содержать внутри массив байтов, а не символов. Таким образом в формулах выше нужно длину строки умножать на один, а не на два. Т.е. данная опция может сократить размер строк до двух раз.
Пул строк
Как вы уже знаете в java есть пул строк. Туда неявно попадают все литералы (строки в коде оформленные через двойные кавычки "literal"). Так же есть возможность положить строку в пул явно с помощью метода intern(). Например, классы java reflection интенсивно используют этот метод, и все имена полей и методов класса попадают в пул. Соответственно, то же самое происходит при использовании стандартной java сериализации, которая неявно использует reflection. Так же обычно библиотеки работающие с XML кладут в пул названия элементов и атрибутов документов.

Пул располагается в PermGen и хранит строки с помощью слабых ссылок. Таким образом при вызове Full GC, если ваша куча больше не ссылается на строки, находящиеся в пуле, то сборщик мусора их очищает. Однако не стоит увлекаться складыванием всего попало в пул: чем больше в вашем пуле находится строк, тем дольше будет операция на проверку находится ли строка уже там или нет. Мои замеры показали, что зависимость примерно прямо пропорциональна (О(n)) и при размере пула 1 миллион строк, каждая такая операция у меня уже занимала несколько микросекунд.

Говоря о пуле строк, не могу не упомянуть почему некоторые библиотеки при объявлении констант используют вышеописанный метод intern:
Данная конструкция может показаться абсурдной не искушенному программисту. И правда, зачем класть эту строку в пул, если она и так константа и присутствует в единственном экземпляре. И вообще, это же литерал, он и так должен неявно попадать в пул. Однако цель, с которой это делается в библиотеках - совсем не пулинг. Дело в том, что если бы эта константа была объявлена в библиотеке просто как
и вы бы использовали её в своем коде, то при компилировании в байткод эта строка заинлайнилась. И если бы вы потом подложили jar с новой версией библиотеки, и не перекомпилировали ваши исходники, то ваш код изменения в данной константе просто бы не заметил.

19 комментариев:

  1. "SOME_VALUE".intern() как способ запретить встраивание -- это любопытно.

    ОтветитьУдалить
  2. Анонимный17 мая 2011 г., 11:08

    Эмм.... Немного впал в ступор по поводу StringBuffer, так как сломалось моё мировозрение :) Тогда где использовать сейчас StringBuffer? И почему в этой статье результаты указывают на эффективность оных - http://habrahabr.ru/blogs/java/102468/ ? Спасибо.

    ОтветитьУдалить
  3. самое больше и шокирующее открытие для меня - это то, что reflection позволяет модифицировать final свойства - всегда думал, что он бросит IllegalAccessException не смотря ни на что.

    что-то сильно сомневаюсь, что поиск в пуле строк имеет сложность O(n) - в своё время смотрел в исходный код openjdk jvm и по-сути intern это поиск в hash таблице - т.е O(1) + коллизии.

    т.е, что касается производительности (при обычных условиях string pool'а)
    s1.equals("literalValue") и s1.intern() == "literalValue" разницы почти никакой нет из-за финального сравнения поиска в hash таблице на equals

    ОтветитьУдалить
  4. IllegalAccessException бросится, если не выставишь f.setAccessible(true)

    про O(n) - я тоже не поверил, прочитав впервые про это тут http://blog.griddynamics.com/2010/01/java-tricks-reducing-memory-consumption.html, но потом сам написал пару тестов и вижу, что это действительно происходит так. Я как домой из командировки вернусь - тебе на почту свой тест скину, ты его проревьюшиь на адекватность и я тогда могу здесь запостить в качестве пруфа

    По поводу openjdk - реализвация в HotSpot на самом деле может отличаться, надо попробовать запустить тест на openjdk чтоле...

    ОтветитьУдалить
  5. w32blaster, в статье на хабре приведен пример работы с конкатенацией в цикле, я же предлагаю его не использовать вне циклов, так что никакого противоречия нет. StringBuffer - используете когда вы конкатинируете строку в нескольких потоках параллельно.

    ОтветитьУдалить
  6. openjdk всё же очень близка к sun jdk - ибо изначально была опубликована именно sun jdk и постоянно делаются почти параллельные commit'ы в обе ветки - закрытую, и open. В openjdk есть и G1 и прочие up-to-date плюшки.

    берём openjdk7
    http://www.java.net/download/openjdk/jdk7/promoted/b142/openjdk-7-ea-src-b142-12_may_2011.zip

    в итоге intern сваливается до

    openjdk/hotspot/src/share/vm/classfile/symbolTable.cpp

    oop StringTable::intern(Handle string_or_null, jchar* name,
    int len, TRAPS) {
    unsigned int hashValue = java_lang_String::hash_string(name, len);
    int index = the_table()->hash_to_index(hashValue);
    oop string = the_table()->lookup(index, name, len, hashValue);

    // Found
    if (string != NULL) return string;

    // Otherwise, add to symbol to table
    return the_table()->basic_add(index, string_or_null, name, len,
    hashValue, CHECK_NULL);
    }

    the_table() возращает
    static SymbolTable* _the_table;

    SymbolTable наследутся от Hashtable.

    Т.е выглядит всё очень даже O(1). Другой вопрос, который остаётся - это цена overhead'а и потенциальные коллиции на больших объёмах.

    Откуда было придумано O(N) я так и не могу понять.

    По ссылке ходил, но Алексей говорит о сложности intern'а без каких-либо ссылок подтверждающих его высказывание.

    ОтветитьУдалить
  7. Читать код, надо тоже уметь, но, порой его надо более детально:
    почему страдает java.util.String intern

    ОтветитьУдалить
  8. Вобщем результат проверки моего микробенчмарка Володя описал в своем блоге, на который дал ссылку в комменте выле. Если кратко, то хештаблица для пулов представляет собой таблицу фиксированной длины (сейчас 1009), так что на больших объемах время поиска по ней сильно деградирует. Свою статью я по такому случаю скоро отмодерирую, а эти комментарии поудаляю.

    ОтветитьУдалить
  9. Я вот чего не могу понять насчёт intern в библиотеках. Зачем захламлять пул строк своими константами, если можно с тем же успехом написать
    SOME_CONSTANT = "SOME_VALUE".toString();
    ?

    ОтветитьУдалить
  10. @Сергей
    java.lang.String.toString() {return this;}

    константа и так всегда оказывается в пуле строк на этапе загрузки класса - для данного use case'а разницы между intern и toString нет

    ОтветитьУдалить
  11. "и хранит строки с помощью слабых ссылок. Таким образом при вызове Full GC, если ваша куча больше не ссылается на строки, находящиеся в пуле, то сборщик мусора их очищает"

    Приведите пожалуйста ссылку на обоснование(JVM spec/oracle site...)

    ОтветитьУдалить
  12. Я сделал этот вывод, запуская тест: я запихивал очень много строк в пул, потом я убирал все ссылки и фреймов на эти строки, и после запуска GC PermGen освобождался.

    ОтветитьУдалить
  13. @jroom36 jvm spec не формализует вообще intern - ни его сложность, ни тем более реализацию (как например, схожей деградации intern не замечено у gcj, в отличии от sun jdk / open jdk)

    о том, что объекты в пуле действительно храняться как "некоторые" weak refs можно понять из исходных кодов jvm (см. реализацию openjdk)

    ОтветитьУдалить
  14. Идея простая, создаём объекты(бесконечный цикл) в пуле строк(interned String, permgen), если GC пул не чистит мы получим OutOfMemoryError.

    import java.util.Random;

    public class InternedStringGCed {
    public static void main(String[] args) {
    Random r = new Random();
    while (true) String.valueOf(r.nextLong()).intern();}}

    Программа благополучно работает. Визуально можно посмотреть, как постепенно наполняется, а после и освобождается permgen в VisualVM/VisualGC.

    //алгоритм сборки SerialGC, компилятор клиентский(C1), vm HotSpot, jdk 1.6.0_24

    ОтветитьУдалить
  15. Теперь понятно :) Я просто из вашего изначального поста подумал, что вы сомневаетесь про то, что PermGen чиститься и приводите программу в качестве аргумента, где очистка PermGen не происходит.

    Просто у моего одного знакомого он как раз не чистился нифига, оказалось, что у него был алгоритм GC, который не чистит PermGen. Больше подробностей правда не помню.

    ОтветитьУдалить
  16. Все-же магическое превращение конкатенации строк через "+" в подобие StringBuilder.append().append() вызывает огромные сомнения. Сами Sun, а в последствии Oracle пишут, что каждая конкатенация через "+" создает новый экземпляр строки (благодаря иммутабельности строк) и если нужно много данных сконкатенировать в одну строку, то лучше использовать StringBuilder, который и работает быстрее и не наплодит ссылок на объекты строк (ссылок на эти строки мы не получим, а строковый пул заполнять начнем).

    Например:
    String str1 = "one"; //str1 - строка №1
    String str2 = str1 + "two"; //"two" - строка №2, ссылку теряем; str2 - строка №3 ("onetwo")
    str1 += "three"; //"three" - строка №4, ссылку теряем; str1 - строка №5 (onethree), также теряем ссылку на "one"

    В результате у нас было создано 5 объектов строк (если я корректно подсчитал) из которых мы имеем только 2 с живыми ссылками.

    В то же самое время, использование серии append() из StringBuilder выльется, по вышеприведенному примеру в два объекта строк:
    StringBuilder str1 = new StringBuilder("one");
    StringBuilder str2 = new StringBuilder(str1);
    str2.append("two");
    str1.append("three");

    ОтветитьУдалить
  17. Возможно следует уточнить, что начиная с версии 7 u6 substring всегда выполняет копирование массива, и никаких offset в классе уже нет.

    ОтветитьУдалить
  18. Этот комментарий был удален автором.

    ОтветитьУдалить