AloneCoder Feb 7 2017 at 15:59

Как работает hashCode() по умолчанию?

12 min

128K

VK corporate blogJava*System Analysis and Design*Debugging*Concurrent computing*

Translation

Попытка заглянуть вглубь hashCode() привела к спелеологическому путешествию по исходному коду JVM, с рассмотрением структуры объектов и привязанной блокировки (biased locking), а также удивительных последствий для производительности, связанных с использованием hashCode() по умолчанию.

Тривиальная загадка

Недавно в рабочем проекте я внёс в класс тривиальное изменение: реализацию toString(), чтобы от логов была польза. К моему удивлению, это привело примерно к 5-процентному уменьшению покрытия (coverage drop) класса. Я знал, что весь новый код покрывался уже имевшимися модульными тестами, так в чём же дело? При анализе отчётов о покрытии мой коллега заметил, что реализация hashCode() покрывалась только до внесения изменений, а не после. Причина была понятна: по умолчанию toString() вызывает hashCode():

public String toString() {
    return getClass().getName() + "@" + Integer.toHexString(hashCode());
}

После корректирования toString() наш кастомный hashCode() перестал вызываться. Мы пропустили тест.

Все знали, что собой представляет реализация по умолчанию toString(), но…

Чем является реализация по умолчанию hashCode()?

Реализация по умолчанию hashCode() возвращает значение, которое называется идентификационный хеш (identity hash code). Я и дальше буду использовать это значение, чтобы отличать его от хешей, генерируемых переопределёнными реализациями hashCode(). Для сведения: даже если класс переопределяет hashCode(), вы всегда можете получить идентификационный хеш объекта o с помощью вызова System.identityHashCode(o).

Здравый смысл подсказывает, что идентификационный хеш использует целочисленное представление адреса памяти. Об этом свидетельствует документация J2SE на Object.hashCode():

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

Однако с этим связаны проблемы, поскольку контракт метода (method contract) требует:

При применении к одному и тому же объекту более одного раза в ходе выполнения Java-приложения метод hashCode должен в обязательном порядке возвращать одно и то же целочисленное значение.

Учитывая, что JVM будет перемещать объекты (например, при сборке мусора в ходе продвижения или уплотнения), после вычисления идентификационного хеша объекта мы должны сделать так, чтобы он как-то отслеживал местоположение самого объекта.

Например, можно взять текущую позицию объекта в памяти при первом вызове hashCode() и сохранить её где-нибудь, например в заголовке объекта. Тогда при перемещении объекта в другое место с ним переедет и исходный хеш. Недостаток способа: два объекта могут иметь одинаковый хеш, но это разрешено спецификацией.

Лучшим подтверждением будет посмотреть в исходный код. К сожалению, дефолтная java.lang.Object::hashCode() является нативной функцией:

public native int hashCode();

Надеть каски!

Настоящий hashCode()

Обратите внимание, что идентификационная реализация hashCode() зависит от JVM. Я буду рассматривать только исходный код OpenJDK, помните об этом при каждом дальнейшем упоминании JVM. Все ссылки относятся к набору изменений 5934:87ee5ee27509 дерева Hotspot, и полагаю, что большинство из них применимы и к Oracle JVM, но в других машинах есть свои нюансы.

OpenJDK определяет входную точку hashCode() в src/share/vm/prims/jvm.h и src/share/vm/prims/jvm.cpp. Последняя содержит:

JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle))
  JVMWrapper("JVM_IHashCode");
// как реализовано в классической виртуальной машине; возвращает 0, если объект NULL
  return handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ;
JVM_END

ObjectSynchronizer::FastHashCode() также вызывается из identity_hash_value_for, который используется и несколькими другими точками вызова (например, System.identityHashCode())

intptr_t ObjectSynchronizer::identity_hash_value_for(Handle obj) {
  return FastHashCode (Thread::current(), obj()) ;
}

Можно наивно ожидать, что ObjectSynchronizer::FastHashCode() делает что-то вроде:

if (obj.hash() == 0) {
    obj.set_hash(generate_new_hash());
}
return obj.hash();

Но оказывается, что там функция на сотню строк. А это куда сложнее. По крайней мере, мы можем отметить пару блоков «если-не-существует-то-генерировать»:

mark = monitor->header();
...
hash = mark->hash();
if (hash == 0) {
  hash = get_next_hash(Self, obj);
...
}
...
return hash;

Это подтверждает нашу гипотезу. Пока что проигнорируем monitor и удовлетворимся получением заголовка объекта. Он хранится в mark, указателе на экземпляр markOop, который представляет слово mark, принадлежащее младшим битам заголовка объекта. Итак, попытаемся засунуть хеш в слово mark. Если он отсутствует, то сгенерируем с помощью get_next_hash, сохраним и вернём.

Реальное генерирование идентификационного хеша

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

0. Случайно сгенерированное число.
1. Функция адреса объекта в памяти.
2. Жёстко запрограммированное значение 1 (используется при тестировании на чувствительность (sensitivity testing)).
3. Последовательность.
4. Адрес объекта в памяти, приведённый к целочисленному значению.
5. Состояние потока, объединённое с xorshift (https://en.wikipedia.org/wiki/Xorshift)

Какой метод используется по умолчанию? Согласно globals.hpp, в OpenJDK 8 это метод 5:

product(intx, hashCode, 5,
         "(Unstable) select hashCode generation algorithm")

То же самое и в OpenJDK 9. В OpenJDK 7 и OpenJDK 6 используется первый метод, генератор случайных чисел.

Так что, если я не ошибаюсь, как минимум с шестой версии реализация по умолчанию hashCode в OpenJDK не имеет ничего общего с адресом памяти.

Заголовки объектов и синхронизация

Вернёмся немного и рассмотрим пару пропущенных моментов. Во-первых, функция ObjectSynchronizer::FastHashCode() выглядит слишком сложной, в ней используется больше 100 строк кода для выполнения того, что мы считали тривиальной операцией «получить-или-сгенерировать». Во-вторых, что это вообще такое – monitor – и почему у него есть заголовки нашего объекта?

Структура слова mark — хорошее место для начала изысканий. В OpenJDK она выглядит так:

// markOop описывает заголовок объекта.
//
// Обратите внимание, что mark — это не настоящий oop, а просто слово.
// Оно находится в иерархии oop по историческим причинам.
//
// Бит-формат заголовка объекта (сначала самые важные, дальше по убыванию):
//
//  32 битные:
//  --------
//             hash:25 ------------>| age:4    biased_lock:1 lock:2 (нормальный объект)
//             JavaThread*:23 epoch:2 age:4    biased_lock:1 lock:2 (привязанный (biased) объект)
//             size:32 ------------------------------------------>| (блок без CMS (CMS free block))
//             PromotedObject*:29 ---------->| promo_bits:3 ----->| (объект, продвигаемый (promoted) CMS)
//
//  64 bits:
//  --------
//  unused:25 hash:31 -->| unused:1   age:4    biased_lock:1 lock:2 (нормальный объект)
//  JavaThread*:54 epoch:2 unused:1   age:4    biased_lock:1 lock:2 (привязанный объект)
//  PromotedObject*:61 --------------------->| promo_bits:3 ----->| (объект, продвигаемый CMS)
//  size:64 ----------------------------------------------------->| (блок без CMS)
//
//  unused:25 hash:31 -->| cms_free:1 age:4    biased_lock:1 lock:2 (COOPы && нормальный объект)
//  JavaThread*:54 epoch:2 cms_free:1 age:4    biased_lock:1 lock:2 (COOPы && привязанный объект)
//  narrowOop:32 unused:24 cms_free:1 unused:4 promo_bits:3 ----->| (COOPы && объект, продвигаемый CMS)
//  unused:21 size:35 -->| cms_free:1 unused:7 ------------------>| (COOPы && блок без CMS)

Для 32 и 64 битов формат несколько различается. Во втором случае могут быть два варианта, в зависимости от того, включены ли указатели сжатых объектов (Compressed Object Pointers). В Oracle и OpenJDK 8 по умолчанию они включены.

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

Но в других состояниях указатель связан с JavaThread или PromotedObject. Дело усложняется: если поместить идентификационный хеш в «нормальный объект», то извлечёт ли его кто-нибудь? И куда? Если объект привязан (biased), то куда мы можем поместить хеш? Что такое привязанный объект?

Попробуем ответить на все эти вопросы.

Привязанная блокировка (biased locking)

Привязанные объекты — это результат привязанной блокировки. Это запатентованный механизм, по умолчанию используемый начиная с HotSpot 6. Он пытается снизить стоимость блокирования объектов. Подобные операции дороги, поскольку ради безопасной обработки запросов блокировки/разблокировки объекта от разных потоков их реализации часто опираются на атомарные процессорные инструкции (сравнение с обменом). Но подмечено, что во многих реализациях большинство объектов когда-либо блокируются лишь одним потоком, так что использование атомарных операций зачастую расточительно. Чтобы этого избежать, JVM’ы с привязанной блокировкой позволяют потокам попытаться самостоятельно «привязать» объект. Когда потоку это удаётся, он может блокировать/разблокировать объект без использования атомарных инструкций. А раз у нас нет потоков, борющихся за один и тот же объект, то мы получаем прирост производительности.

Бит biased_lock в заголовке обозначает, привязан ли объект к потоку, указанному в JavaThread*. Биты lock обозначают, заблокирован ли объект.

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

Начнём с FastHashCode. Первое, что мы обнаруживаем:

intptr_t ObjectSynchronizer::FastHashCode (Thread * Self, oop obj) {
  if (UseBiasedLocking) {
    if (obj->mark()->has_bias_pattern()) {
      ...
      BiasedLocking::revoke_and_rebias(hobj, false, JavaThread::current());
      ...
      assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");
    }
  }

Погодите. Здесь просто отменяются привязка и привязанная блокировка объекта (метод false означает «не пытайся снова привязать»). Несколькими строками ниже это остаётся действительно неизменным:

// объект должен оставаться недоступным для привязанной блокировки
assert (!mark->has_bias_pattern(), "invariant") ;

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

Чёрт возьми.

Почему сохранение состояния привязанной блокировки конфликтует с сохранением идентификационного хеша?

Для ответа на этот вопрос мы должны понять, где может находиться слово mark (содержащее идентификационный хеш) в зависимости от состояния блокировки объекта. Ниже показаны возможные переходы:

Моё (возможно, ошибочное) мнение таково.

Для четырёх состояний в верхней части схемы OpenJDK сможет использовать представления thin-блокировок. В простейшем случае (без блокировок) это означает хранение идентификационного хеша и других данных прямо в пространстве слова mark в объекте:

unused:25 hash:31 -->| unused:1   age:4    biased_lock:1 lock:2 (нормальный объект)

В более сложных случаях это пространство используется для хранения указателя на «запись о блокировке». Тогда слово mark будет «перемещено» в другое место.

Поскольку заблокировать объект у нас только пытается один поток, этот указатель фактически ссылается на область памяти в собственном стеке потока. Это хорошо по двум причинам:

скорость (отсутствие разногласий или координации доступа к области памяти),
этого достаточно, чтобы поток знал о том, что он владеет блокировкой (область памяти ссылается на его собственный стек).

Но это будет работать не всегда. Если у нас есть соперничающие объекты (например, объекты, используемые в синхронизированных выражениях, на которых пересекается несколько потоков), то нам нужна более сложная структура, подходящая не только для копирования заголовков объектов (опять же «перемещённых»), но и для списка ожидания. Подобный список потребуется и в том случае, если поток исполняет object.wait().

Нашим нуждам удовлетворяет структура ObjectMonitor, которая на схеме называется «тяжёлый монитор». Оставшееся в заголовке объекта значение указывает не на «перемещённое слово mark», а на реальный объект (монитор). Теперь для доступа к идентификационному хешу требуется «получить монитор» (inflating the monitor): сделать указатель на объект и считывать/изменять в зависимости от поля, содержащего перемещённое слово mark. Это дороже и требует координации.

Есть работа и для FastHashCode.

В строках с L640 по L680 выполняется поиск заголовка и проверка на наличие закешированного идентификационного хеша. Я считаю, что это быстрый способ проверки случаев, когда нам не нужно получить монитор.

Начиная с L682 придётся стиснуть зубы:

// Получаем монитор для сохранения хеша
monitor = ObjectSynchronizer::inflate(Self, obj);

// Загружаем перемещённый заголовок и проверяем на наличие хеша
mark = monitor->header();
...
hash = mark->hash();

Если тут есть id. hash (hash != 0), то JVM может его вернуть. В противном случае мы можем получить его от get_next_hash и спокойно сохранить в перемещённом заголовке, который содержится в ObjectMonitor.

Это даёт разумное объяснение, почему вызов hashCode() применительно к объекту класса, который не переопределяет реализацию по умолчанию, делает объекты недоступными для привязанной блокировки:

Чтобы сохранять консистентность идентификационного кеша после перемещения, нам нужно хранить хеш в заголовке объекта.
Потоки, запрашивающие идентификационный хеш, могут вообще не заморачиваться блокировкой объекта. Но на практике они будут совместно использовать структуры данных, применяемые механизмом блокировки. Это очень сложная система, поскольку она может не только менять, но и перемещать содержимое заголовков.
Привязанная блокировка помогает выполнять операции блокирования/разблокирования без использования атомарных операций. Это эффективно до тех пор, пока объект блокируется лишь одним потоком, потому что нам нужно хранить состояние блокировки в слове mark. Я не совсем уверен, но, как я понял, поскольку другие потоки могут запрашивать идентификационный хеш, даже если блокировка нужна лишь одному потоку, слово header будет конкурентным и для корректной обработки потребуется использовать атомарные операции. Что лишает смысла привязанную блокировку.

Промежуточные итоги

Реализация по умолчанию hashCode() (идентификационного хеша) не имеет отношения к адресу памяти объекта, как минимум в OpenJDK. В версиях 6 и 7 это случайно генерируемое число. В версиях 8 и 9 это число, полученное на основании состояния потока. Здесь проведён тест, который привёл к такому же выводу.
- Доказательство предупреждений «зависит от реализации» не для эстетики: Azul’s Zing действительно генерирует идентификационный хеш на основании адреса памяти объекта.
В HotSpot идентификационный хеш генерируется лишь раз, а затем кешируется в слове mark в заголовке объекта.
- В Zing для сохранения консистентности при перемещениях используется механизм задержки сохранения id.hash до тех пор, пока объект не переместится. В данном случае хеш хранится в «предзаголовке».
В HotSpot вызов дефолтного hashCode() или System.identityHashCode() приводит к недоступности объекта для привязанной блокировки.
- Это означает, что при синхронизации объектов, не имеющих разногласий, вам лучше переопределить реализацию по умолчанию hashCode(), иначе вы не сможете воспользоваться оптимизациями JVM.
В HotSpot можно для каждого объекта в отдельности отключать привязанную блокировку.
- Это очень полезная возможность. Мне встречались приложения, в которых очень часто возникают разногласия между очередями создания/потребления; привязанная блокировка больше мешала, чем помогала, так что приходилось её отключать. Мы делали это только для конкретных объектов/классов, просто вызывая применительно к ним System.identityHashCode().
Я не нашёл в HotSpot флага, позволяющего менять генератор по умолчанию, так что эксперименты с другими опциями могут потребовать компилирования из исходников.

Бенчмарки

Для проверки своих умозаключений я написал простой тест JMH.

Бенчмарк (исходник) делает нечто вроде этого:

object.hashCode();
while(true) {
    synchronized(object) {
        counter++;
    }
}

Одна конфигурация (withIdHash) синхронизирует объект, который использует идентификационный хеш, так что можно ожидать, что привязанная блокировка будет отключена при вызове hashCode(). Вторая конфигурация (withoutIdHash) реализует кастомный хеш, при котором привязанная блокировка не отключается. Каждая конфигурация сначала прогоняется с одним потоком, затем с двумя (они получают суффикс Contended).

Кстати, необходимо включить -XX:BiasedLockingStartupDelay=0, а иначе JVM понадобится четыре секунды на запуск оптимизации, что исказит результат.

Первый запуск:

Benchmark                                       Mode  Cnt       Score      Error   Units
BiasedLockingBenchmark.withIdHash              thrpt  100   35168,021 ±  230,252  ops/ms
BiasedLockingBenchmark.withoutIdHash           thrpt  100  173742,468 ± 4364,491  ops/ms
BiasedLockingBenchmark.withIdHashContended     thrpt  100   22478,109 ± 1650,649  ops/ms
BiasedLockingBenchmark.withoutIdHashContended  thrpt  100   20061,973 ±  786,021  ops/ms

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

При втором запуске привязанная блокировка отключается (-XX:-UseBiasedLocking) во всех конфигурациях.

Benchmark                                       Mode  Cnt      Score      Error   Units
BiasedLockingBenchmark.withIdHash              thrpt  100  37374,774 ±  204,795  ops/ms
BiasedLockingBenchmark.withoutIdHash           thrpt  100  36961,826 ±  214,083  ops/ms
BiasedLockingBenchmark.withIdHashContended     thrpt  100  18349,906 ± 1246,372  ops/ms
BiasedLockingBenchmark.withoutIdHashContended  thrpt  100  18262,290 ± 1371,588  ops/ms

Метод хеширования больше не влияет на результат, и withoutIdHash теряет своё преимущество.

Все бенчмарки прогонялись на Intel Core i5 2,7 ГГц.

Ссылки

Всё, что не является дикими спекуляциями и моими слабыми рассуждениями в попытке осмыслить исходные коды JVM, собрано из разных источников. Основные из них:

Tags:

Hubs: