Изменения внутреннего представления строк в Java

http://java-performance.info/changes-to-string-java-1-7-0_06/
  • Перевод

Вступление


Это мой первый перевод статьи. Решил посвятить его Java, как ни странно. В статье рассказывается об изменениях строкового типа данных, которые произошли в Java.

ВАЖНО: В 17 апдейте Java 7 по-прежнему ничего не поменялось в отношении статьи.

Разделение массива символов char[]

В настоящей реализации класса String имеется 4 экземплярных поля: массив символов char[] value — содержащий символы строки, int offset — индекс первого используемого символа в массиве value, int count — количество используемых символов и int hash — кэшированное значение вычисленного хеш кода для данной строки. Как вы могли заметить, в большинстве случаев строка будет иметь значения offset = 0 и count = value.length. Единственное исключение из этого правила, возможно, когда строка создается путем вызова метода viaString.substring или любым методом, который использует данный метод (например, split).

String.substring создает строку, которая разделяет внутренний массив символов char[] с оригинальной строкой, что позволяет:
  1. Сохранить память, используя ее совместно;
  2. Сделать время выполнение метода String.substring константным (O(1)).

В то же время, при такой реализация возможна утечка памяти: если вы извлекаете маленькую подстроку из большой строки и большая строка вам больше не нужна, у вас все равно останется ссылка на большой массив символов исходной строки. Единственный способ этого избежать — вызвать конструктор new String(String), что заставит создать копию массива символов, то есть отсоединит вашу маленькую строку от большого «родителя».

В Java 1.7.0_06 поля offset и count были удалены из класса String. Это означает, что мы теперь не можем совместно использовать массив символов. Теперь мы можем забыть об утечках памяти описанных выше и больше никогда не использовать конструктор new String(String). Как недостаток, вы должны всегда помнить, что метод String.substring сейчас имеет линейную сложность в отличие от константой, которая была раньше.

Изменения в логике хеширования

Другое изменение, введенное в класс String в этом же апдейте: новый алгоритм хеширования. Oracle говорит, что новый алгоритм дает лучшее распределение хеш кодов, что должно улучшить производительность некоторых основанных на хешировании коллекций: HashMap, Hashtable, HashSet, LinkedHashSet, WeakHashMap и ConcurentHashMap. В отличие от изменений, описанных в начале статьи, эти изменения являются экспериментальными и выключены по умолчанию.

Как вы наверно заметили, данные изменения верны только для случая, когда ключами коллекций являются строки. Если вы хотите включить эти изменения, вы должны установить значение системного свойства jdk.map.althashing.threshold в неотрицательное значение (по умолчанию оно равно -1). Это значение является порогом размера коллекции, после которого будет использоваться новый алгоритм хеширования. Маленькая поправка: алгоритм хеширования будет изменен только при нехватке памяти. Если коллекция была перераспределена при размере size = 160 и jdk.map.althashing.threshold = 200, то метод хеширования будет сменен только, когда размер коллекции вырастит до 320.

У класса String сейчас есть метод hash32(), результат которого кэшируется в поле int hash32. Результат метода hash32() для одинаковых строк может быть разным для различных запусков JVM (на самом деле оно будет разным практически всегда, потому что использует System.currentTimeMillis() и два вызова System.nanoTime для начальной инициализации). Как результат, итерация по одной и той же коллекции может быть разной при разных запусках программы. На самом деле, я был немного удивлен данным методом. Зачем он нам, если настоящая реализация метода hashCode работает достаточно хорошо? Я решил проверить, сколько коллизий будет получено при использовании метода hash32(). Метод String.hash32() не является публичным, но я посмотрел на реализацию класса HashMap, чтобы определить, как он его вызывает. Ответ: sun.misc.Hashing.stringHash32(String). На тесте, содержащем один миллион строк, метод выдал 304 коллизии, в сравнении с не одной коллизией используя метод String.hashCode. Я думаю, мы должны подождать дальнейших улучшений.

Новая логика хеширования может серьезно повлиять на многопоточный код

Oracle допустил ошибку при реализации хеширования в следующих классах: HashMap, Hashtable, HashSet, LinkedHashSet, WeakHashMap. Только ConcurentHashMap не содержит данной ошибки. Проблема заключается в том, что все не параллельные классы теперь имеют поле:

/**
 * Случайное значение связанное с этим экземпляром для того чтобы осложнить поиск коллизий.
 */
transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);


Это означает, что при каждом создании вышеуказанных коллекций будет вызываться метод sun.misc.Hashing.randomHashSeed. В свою очередь, метод randomHashSeed вызывает метод java.util.Random.nextInt. Как известно, класс Random не очень дружелюбен с многопоточностью: он содержит поле private final AtomicLong seed. Atomics работают неплохо при средней нагрузке, но плохо при большой нагрузке.

Как результат, многие высоконагруженные веб-приложения обрабатывающие HTTP/JSON/XML могут быть затронуты этой ошибкой, потому что почти все известные парсеры (анализаторы) используют хотя бы один из затронутых классов. Все эти парсеры могут создавать вложенные map коллекции, что увеличит число созданных map коллекций в секунду.

Как решить эту проблему?

1. Путь ConcurrentHashMap: вызвать метод randomHashSeed только, когда определено системное свойство jdk.map.althashing.threshold. Однако это доступно только для разработчиков JDK ядра.

/**
 * Случайное значение связанное с этим экземпляром для того чтобы осложнить поиск коллизий.
 */
private transient final int hashSeed = randomHashSeed(this);
 
private static int randomHashSeed(ConcurrentHashMap instance) {
    if (sun.misc.VM.isBooted() && Holder.ALTERNATIVE_HASHING) {
        return sun.misc.Hashing.randomHashSeed(instance);
    } 
    return 0;
}


2. Хакерский путь: изменить класс sun.misc.Hashing. Крайне не рекомендуется. Если вы все-таки решили это сделать, то можно поступить так: класс java.util.Random не является финальным. Вы можете расширить его и переопределить его метод nextInt, возвращая, например, константное значение. Затем необходимо изменить поле sun.misc.Hashing.Holder.SEED_MAKER установив его в ваш класс, унаследованный от Random. Не переживайте, что это поле является приватным, статичным и финальным — рефлексия поможет вам.

Резюме

  • Начиная с Java 1.7.0_06 метод String.substring всегда создает новый массив символов char[] для каждой созданной им строки. Это означает, что теперь этот метод имеет линейную сложность в сравнении с константной как в предыдущих версиях. В результате такого изменения строка занимает на 4 байта меньше чем раньше, и гарантированно исключаются утечки памяти, вызванные методом String.substring.
  • Начиная с этого же апдейта, в классе String появился второй метод для хеширования, который называется hash32. Этот метод не публичный и может быть доступен без рефлексии только через вызов метода sun.misc.Hashing.stringHash32(String). Этот метод используется в JDK 7 коллекциями, основанными на хешировании, если их размер превысит значение системного свойства jdk.map.althashing.threshold. Это экспериментальный метод, и я не рекомендую использовать его в своем коде.
  • Начиная с Java 1.7.0_06, все стандартные не многопоточные коллекции имеют нежелательный побочный эффект, вызванный новым алгоритмом хеширования. Это ошибка проявляется только в многопоточных приложениях создающих множество map коллекций в секунду.

От себя

Тот факт, что строки в Java разделяли массив символов, говорит о том, что они являлись персистентными. Как известно персистентными называют структуры, которые сохраняют все свои предыдущие версии при изменении. Это было сделано явно, как оптимизация для уменьшения количества используемой памяти + сделать время работы метода substring константным. Однако, польза от данной оптимизации не столь большая, именно поэтому от этой идеи отказались в 7 версии Java.

В .NET строки изначально были не персистентными. Вот ссылка на интересную статью Эрика Липперта, в которой он подробно объяснил, почему это именно так.

Спасибо, что прочли.
Надеюсь, статья оказалась полезной.
Поделиться публикацией

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

    +2
    IMPORTANT: Java 7 update 17 still has no changes in the subject of this article.
    ВАЖНО: 17 апдейт 7 версии Java не содержит изменений, описанных в этой статье.
    По-моему, смысл перевода получился диаметрально противоположным.
      0
      Переводчик погорячился конечно сильно
        0
        Спасибо за то, что не поленились проверить оригинал, а то моему возмущению не было предела касательно этого пункта.
        +1
        Единственный способ этого избежать — вызвать конструктор new String(String), что заставит создать копию массива символов, то есть отсоединит вашу маленькую строку от большого «родителя».

        Не единственный, еще можно intern() вызвать
          0
          Замечательное решение что бы убить приложение.
            0
            почему?
              0
              Потому что строки, полученные методом intern() попадают в PermGen
        0
        Я понял, что изменения вступили в силу только начиная с Java 1.7.0_06, а в Java 1.7.0 их нет.
          0
          Подскажите, кто разбирается в вопросе, то как реализован класс java.lang.String является частью какого-либо JSR и соответственно можно рассчитывать на единую реализацию, независимо от используемых JDK и JVM или это отдается на откуп вендорам и, например, для реализации от IBM, то о чем написано в статье может оказаться не актуальным?
            +1
            Спецификация: docs.oracle.com/javase/7/docs/api/java/lang/String.html
            Всё, что не является частью спецификации класса String — отдаётся на откуп вендорам. То есть они вольны использовать любую имплементацию: с оффсетами и без, с одними хэшкодами и с другими и т.п. Более того, они могут оптимизировать работу со строками под свои нужды. Не удивлюсь, если IBM тюнит в своей J9, которая идёт в составе WebSphere, работу со строками именно под типичные паттерны работы WebSphere.
              0
              Ради интереса посмотрел jdk 7 от IBM — там реализация String осталась прежней
                0
                Вероятно это потому, что их Java сделана на базе OpenJDK, а в релизе OpenJDK 7 летом 2011 года была именно прежняя имплементация. Думаю, если принципиальная схема работы IBM с OpenJDK за год кардинально не изменится, то этот фикс со строками попадёт к ним в восьмёрку.
                  0
                  ага, я буду следить и отпишусь сюда. А то различия в скорости String.substring в пределах одного вендора — как-то это меня парит.
            0
            Как я понял эти изменения касаются именно реализации от Oracle. Про реализацию от IBM без понятия…
              +1
              > разделяет внутренний массив символов

              по-русски было бы «использует совместно», а так смысл «разделяет» звучит как «split» и непонятно, какого фига оно пытается что-то разделить, а на самом деле имеется в виду «share». Это понятно из следующего текста, но… переводить тоже надо со смыслом, а не просто слова.
                +1
                А что их вынудило поменять поведения Стринга? Откровенный даунгрейд, на первый взгляд.
                  +2
                  да ладно))) Вы меряли производительность? Результаты в студию!

                  К тому же, не совсем ясно, что является настоящей проблемой под нагрузкой —
                  1.копирование массивов чаров или
                  2. GC, который вынужден как-то постоянно обрабатывать накапливающиеся и накапливающиеся строки.

                  Есть мнение, что в некоторых случаях второй эффект может так загрузить GC, что копирование строк покажется детским лепетом.
                    0
                    Есть хорошая вероятность, что все эти ваши строки очень хорошо соберутся в стадии concurrent-mark и concurrent-sweep, при условии что мы их выкидываем, а если постоянно держим, то опять же, висят и висят, никого не трогают
                      0
                      Я не знаю, честно говоря, есть ли какая-то зависимлость работы CMS от размера собираемых объектов. Но полагаю, что с фрагментацией в старой Java проблемы сильнее при любом GC.
                      0
                      Дело может быть не только в производительности, но и в объёмах памяти. Если вы храните множество не очень длинных строк на протяжении работы всей программы, то раньше их можно было посадить на один массив, а теперь массивов много — для каждой строки добавляется оверхед на объект массива и выравнивание.
                        0
                        Другой юзкейс: читается какая-то длинная строка из потока (100500 символов), потом берётся какой-то её substring длиною 10, после чего сама строка нам не нужна, а массив чаров остаётся лежать огромный. Разница мложет составлять порядки

                        Короче говоря, зависит от паттерна использования. Видимо, описанный Вами паттерн не очень распространён.
                          0
                          Извините, это не юзкейс, а неумение пользоваться инструментом, который вам дали. Напишите new String(src.substring(1,10)) и всё.
                            0
                            так мы далеко зайти можем.
                    0
                    Дело в том, что пользы от данной оптимизации не так уж много, поэтому они решили от нее избавится.
                      +1
                      Как известно, класс Random не очень дружелюбен с многопоточностью: он содержит поле private final AtomicLong seed. Atomics работают неплохо при средней нагрузке, но плохо при большой нагрузке.
                      Во-первых, с чего это Atomic* — это «не очень дружелюбен с многопоточностью».
                      Во-вторых, атомики работают плохо при рейс кондишне, и, я не знаю что нужно делать, что бы созданием таких объектов как мапы забить cas до состояния, когда на нем просядет производительность.

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

                      Самое читаемое