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

Вступление

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

ВАЖНО: 17 апдейт 7 версии Java не содержит изменений, описанных в этой статье.

Разделение массива символов 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 строки изначально были не персистентными. Вот ссылка на интересную статью Эрика Липперта, в которой он подробно объяснил, почему это именно так.

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