JEP 192: String Deduplication in G1

Аннотация

Уменьшить объём живых данных в куче Java за счёт доработки сборщика мусора G1: дублирующиеся экземпляры String будут автоматически и непрерывно дедуплицироваться.

Что не является целью

Реализация этой возможности для сборщиков мусора, отличных от G1, не является целью.

Мотивация

Многие крупные Java-приложения сейчас упираются в память. Измерения показали, что примерно 25 % живых данных в куче Java в приложениях такого типа занимают объекты String. Более того, примерно половина этих объектов String — дубликаты, где под дубликатами понимается, что string1.equals(string2) истинно. Хранение дублирующихся объектов String в куче — по сути, просто пустая трата памяти. В рамках этого проекта в сборщике мусора G1 будет реализована автоматическая и непрерывная дедупликация String, чтобы не тратить память впустую и уменьшить объём занимаемой памяти.

Описание

Дедупликация строк

У класса String два поля:

private final char[] value
private int hash

Поле value зависит от реализации и не наблюдаемо извне самого класса String. Класс String не изменяет содержимое массива char[] и не синхронизируется на самом объекте массива. Это значит, что массив можно безопасно и прозрачно использовать одновременно в нескольких экземплярах String.

Концептуально дедупликация объекта String — это просто повторное присваивание поля value, т. е. aString.value = anotherString.value. Однако само присваивание выполняет VM, поэтому свойство final поля value на практике проблемой не является.

На самом деле мы дедуплицируем не сами объекты String, а только массивы символов, в которых хранятся их данные. Безопасно дедуплицировать сами объекты String нельзя, поскольку такое изменение было бы наблюдаемо из Java-приложения и могло бы вызвать проблемы, если бы, например, приложение использовало этот объект для синхронизации или иным образом полагалось на Identity (идентичность объекта) этого объекта.

Дедупликация строк не потребует никаких изменений в библиотеке классов JDK или в любом другом существующем коде на Java.

Ожидаемая польза

Измерения на большом числе Java-приложений (больших и маленьких) показали следующее:

• Средняя доля живых данных в куче, занимаемая объектами String, — 25 %

• Средняя доля живых данных в куче, занимаемая дублирующимися объектами String, — 13,5 %

• Средняя длина String — 45 символов

Поскольку мы дедуплицируем только массивы символов, накладные расходы на сами объекты String (заголовок объекта, поля и выравнивание) сохраняются. Эти накладные расходы зависят от платформы и конфигурации и составляют от 24 до 32 байт. Тем не менее при средней длине String в 45 символов (90 байт + заголовок массива) выигрыш всё равно значительный.

С учётом сказанного выше фактическая ожидаемая польза составляет около 10 % уменьшения кучи. Обратите внимание, что это число — расчётное среднее по широкому кругу приложений. Уменьшение кучи для конкретного приложения может значительно отличаться как в большую, так и в меньшую сторону.

Реализация

Обзор

Во время сборки мусора обходятся живые объекты в куче. Для каждого посещённого объекта выполняется проверка, является ли он кандидатом на дедупликацию строк. Если проверка показывает, что это кандидат, ссылка на объект помещается в очередь для последующей обработки. Поток дедупликации работает в фоне и обрабатывает очередь. Обработка элемента очереди означает его удаление из очереди и попытку дедуплицировать объект String, на который он ссылается. Для учёта всех уникальных массивов символов, используемых объектами String, применяется хеш-таблица. При дедупликации в этой таблице выполняется поиск, чтобы проверить, нет ли уже где-то в куче идентичного массива символов. Если есть, объект String перенастраивается так, чтобы указывать на этот массив символов, и ссылка на исходный массив освобождается, что позволяет со временем удалить его при сборке мусора. Если поиск неудачен, массив символов вместо этого добавляется в хеш-таблицу, чтобы в будущем этот массив можно было использовать совместно.

Выбор кандидатов

Выбор кандидатов выполняется во время young/mixed-сборок и полных сборок. Эта операция чувствительна к производительности, поскольку применяется ко всем посещаемым объектам. Объект считается кандидатом на дедупликацию, если выполнены все следующие условия:

• Объект является экземпляром String,

• Объект эвакуируется из молодого региона кучи, и

• Объект эвакуируется в регион кучи young/survivor и возраст объекта равен возрастному порогу дедупликации, или объект эвакуируется в старый регион кучи и возраст объекта меньше возрастного порога дедупликации.

Как только объект String переведён в старый регион или его возраст превысил возрастной порог дедупликации, он больше никогда не станет кандидатом. Такой подход позволяет не делать один и тот же объект кандидатом более одного раза.

Интернированные строки — особый случай. Они явно дедуплицируются перед помещением в StringTable (почему — подробно описано ниже). Позже они тоже могут стать кандидатами на дедупликацию, если достигнут возрастного порога дедупликации или будут эвакуированы в старый регион кучи. Вторая попытка дедуплицировать такие строки будет напрасной, но быстрого способа отфильтровать их у нас нет. Как показала практика, это не проблема, поскольку число интернированных строк обычно ничтожно по сравнению с числом обычных (неинтернированных) строк.

Возрастной порог дедупликации

Предполагается, что объекты String живут либо очень недолго, либо долго. Дедупликация объектов, которые скоро умрут, — просто пустая трата ресурсов процессора и памяти. Чтобы не дедуплицировать строки слишком рано, возрастной порог дедупликации определяет, насколько старым должен быть объект String, прежде чем он будет рассматриваться как кандидат на дедупликацию. У этого порога будет разумное значение по умолчанию, но его также можно будет настроить с помощью опции VM.

Очередь дедупликации

На самом деле очередь дедупликации состоит из нескольких очередей — по одной на каждый рабочий поток GC. Благодаря этому рабочие потоки GC могут добавлять элементы в очередь без блокировок и с эффективным использованием кэша. Это важно, поскольку эти операции выполняются во время фазы stop-the-world.

Хеш-таблица дедупликации

Хеш-таблица дедупликации используется для учёта всех уникальных массивов символов (привязанных к объектам String), найденных в куче. При обработке кандидата на дедупликацию в хеш-таблице выполняется поиск, чтобы проверить, существует ли уже идентичный массив символов. Если поиск успешен, поле value объекта String обновляется так, чтобы указывать на массив символов, найденный в хеш-таблице, что позволяет сборщику мусора со временем удалить исходный массив. Если поиск неудачен, массив символов вместо этого добавляется в хеш-таблицу, чтобы в будущем этот массив можно было использовать совместно. Массив символов удаляется из хеш-таблицы, когда он удаляется при сборке мусора, т. е. когда все ссылающиеся на него объекты String становятся недостижимыми.

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

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

Для нагрузок, которые создают большое число уникальных строк и дают мало возможностей для дедупликации, хеш-таблица может потреблять больше памяти, чем освобождает дедупликация. В таких случаях дедупликацию строк включать не следует. Статистика дедупликации, выводимая в журнал GC, поможет принять такое решение.

Поток дедупликации

Поток дедупликации — внутренний поток VM, который работает параллельно с Java-приложением. Именно в этом потоке выполняется собственно работа по дедупликации. Он ожидает появления ссылок на объекты String в очереди дедупликации и начинает извлекать их по одной. Для каждой извлечённой String он вычисляет хеш-код строки (при необходимости), ищет её в хеш-таблице дедупликации и, возможно, дедуплицирует строку. Поток дедупликации ведёт статистику дедупликации (число проверенных кандидатов, число дедуплицированных строк и т. д.), которую может выводить в журнал GC.

Интернированные строки

Когда String интернируется (вызывается String.intern()), она дедуплицируется перед помещением в StringTable. Это гарантирует, что после интернирования String больше никогда не будет дедуплицироваться. Как показала практика, дедуплицировать String после интернирования — плохая идея, поскольку это сводит на нет оптимизации компилятора для строковых литералов. Некоторые оптимизации предполагают (и вполне обоснованно), что поле String.value никогда не меняется так, чтобы указывать на другой массив. Зная это, компилятор может генерировать код, в котором адрес массива символов записан как непосредственное значение. Эта оптимизация позволяет, например, String.equals() выполнять на быстром пути простое сравнение указателей. Если GC перемещает массив, адрес в таких блоках кода корректируется соответствующим образом. Однако если String.value выполняется вне GC, оптимизация незаметно перестанет срабатывать и произойдёт откат к обычному (более медленному) посимвольному сравнению.

Влияние на время пауз GC

На время пауз GC могут влиять или будут влиять следующие факторы:

• Выбор кандидатов выполняется на горячем пути маркировки (полные сборки) и эвакуации (young/mixed-сборки).

• И очередь дедупликации, и хеш-таблица хранят oop, которые с точки зрения GC считаются слабыми ссылками. Это значит, что GC должен обходить обе структуры, чтобы корректировать или удалять ссылки на объекты, которые были перемещены или удалены при сборке мусора. Обход очереди и хеш-таблицы — самая критичная для производительности часть этой возможности. Обход выполняется параллельно всеми рабочими потоками GC.

Предполагается, что достаточно высокая доля успешной дедупликации компенсирует большую часть этого влияния или всё влияние, поскольку дедупликация может уменьшить объём работы в других фазах паузы GC (например, за счёт меньшего числа объектов для эвакуации), а также снизить частоту GC (за счёт меньшей нагрузки на кучу).

Опции командной строки

Будут доступны следующие новые опции командной строки:

• UseStringDeduplication (bool) — включает дедупликацию строк

• PrintStringDeduplicationStatistics (bool) — выводит подробную статистику дедупликации

• StringDeduplicationAgeThreshold (uintx) — объекты String, достигшие этого возраста, будут считаться кандидатами на дедупликацию

Альтернативы

Существует множество других способов дедуплицировать объекты String.

• Дедупликация при создании String

  Проблема этого подхода в том, что многие или большинство объектов String умирают молодыми, а накладные расходы на вычисление хеш-кода и поиск существующего равного массива символов немалые.

• Явное использование String.intern() в коде

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

  Одна из проблем в том, что String.intern() возвращает один и тот же объект String для всех равных строк. Если не соблюдать крайнюю осторожность, возможны функциональные регрессии, например в случаях, когда объекты String используются для синхронизации.

  Другая проблема в том, что во многих случаях разработчики не знают, в каких местах кода им следует использовать String.intern(). Бывает даже трудно найти сам код и/или людей, отвечающих за него, чтобы вообще добиться его изменения.

  Наконец, текущая реализация String.intern() плохо масштабируется, поэтому эта операция может быть очень дорогой.

• Профилирование и внедрение эквивалента вызовов String.intern()

  Можно также профилировать существующие приложения, выяснять, где обычно хранятся дублирующиеся объекты String, и с помощью фреймворков вроде java.lang.instrument внедрять вызовы String.intern() в подходящих местах. Преимущество этого способа в том, что не нужно менять сам исходный код: байт-код изменяется динамически под реальную нагрузку. Одна из проблем такого подхода в том, что не так просто понять, насколько часто обновляются поля, поэтому если вызовы intern() внедрены в горячие пути, это может значительно повлиять на производительность. Кроме того, при изменении исходного кода профилирование, возможно, придётся проводить заново, а это может быть затратной и отчасти ручной работой.

• Дедупликация в String.equals() и String.compareTo()

  Когда два объекта String сравниваются и результат показывает, что они равны, эти методы перед возвратом результата могли бы изменить одну из строк так, чтобы она использовала символьный массив другой строки. Был реализован прототип этого подхода, и он работал достаточно хорошо. Главное преимущество этого подхода в нулевых накладных расходах памяти, поскольку не нужно хранить хэш-таблицу дедупликации.

  Однако у этого подхода есть несколько очевидных ограничений. Во-первых, чтобы произошла дедупликация, два объекта String должны быть сравнены. Это значит, что значительная часть кандидатов на дедупликацию упускается, так как сравниваются не все строки. Кроме того, у VM есть интринсики компилятора для этих методов, что усложняет реализацию, поскольку дело не ограничивается изменениями в самом классе String. Есть и несколько других технических проблем, которые в совокупности делают этот подход менее привлекательным.

• Однократная дедупликация

  Вместо того чтобы выполнять дедупликацию непрерывно, её можно выполнять и как однократную операцию. Вкратце это можно реализовать так: найти все объекты String в куче, на лету построить хэш-таблицу дедупликации, выполнить дедупликацию объектов String там, где это нужно, а затем освободить хэш-таблицу и другие временные структуры данных. Это значительно проще реализовать, чем непрерывную дедупликацию, и к тому же такой способ не увеличивает потребление памяти, когда дедупликация не выполняется. Можно также представить, что при необходимости такие однократные операции дедупликации можно запускать время от времени по расписанию, делая дедупликацию полунепрерывной.

  Был разработан прототип этого подхода, который использовал JVMTI для поиска объектов String в куче. Возникло несколько проблем. Во-первых, результаты на крупной нагрузке типа Java EE показали, что дедупликацию выгодно выполнять непрерывно, а не лишь время от времени. Если же выполнять эту операцию часто, то накладные расходы на сканирование всей кучи и перестроение хэш-таблицы каждый раз становятся значительными. Кроме того, выполнять такую работу с помощью JVMTI слишком негибко, когда нужно выбирать, какие объекты String и когда подвергать дедупликации.

Тестирование

Будут добавлены тесты jtreg, чтобы убедиться, что дедупликация работает как ожидается. Для оценки сокращения набора живых данных в куче Java и регрессий/улучшений производительности нужны системные тесты и тесты производительности.

Риски и допущения

• Предполагается, что добавление проверки «включена ли дедупликация» в горячий путь логики маркировки/копирования сборщика мусора не вносит значительных накладных расходов. Это необходимо проверить.

• Обычно объект String и соответствующий ему символьный массив размещаются в памяти рядом, что обеспечивает хорошую локальность кэша. После дедупликации объекта String его символьный массив окажется дальше, что может немного снизить производительность. Однако первоначальные измерения показали, что это, по-видимому, не является проблемой. Более того, после дедупликации общий объём памяти, к которой происходит обращение, уменьшается, что обычно повышает долю попаданий в кэш.

Влияние

• Производительность/масштабируемость: изменения могут повлиять на время пауз GC и на долю попаданий в кэш при обращении к символьному массиву объектов String. Нам потребуется провести тесты, чтобы оценить влияние на производительность.