Попытка заглянуть вглубь
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_ENDObjectSynchronizer::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, собрано из разных источников. Основные из них:
- blogs.oracle.com/dave/entry/biased_locking_in_hotspot
- fuseyism.com/openjdk/cvmi/java2vm.xhtml
- www.dcs.gla.ac.uk/~jsinger/pdfs/sicsa_openjdk/OpenJDKArchitecture.pdf
- www.infoq.com/articles/Introduction-to-HotSpot
- blog.takipi.com/5-things-you-didnt-know-about-synchronization-in-java-and-scala/#comment-1006598967
- www.azulsystems.com/blog/cliff/2010-01-09-biased-locking
- dzone.com/articles/why-should-you-care-about-equals-and-hashcode
- wiki.openjdk.java.net/display/HotSpot/Synchronization
- mechanical-sympathy.blogspot.com.es/2011/11/biased-locking-osr-and-benchmarking-fun.html
Комментарии (51)
nikitasius
07.02.2017 17:15-3Самое большое доказательство того, что String нельзя юзать как key в HashMap.
sleeply4cat
07.02.2017 17:26+3Поясните?
poxvuibr
07.02.2017 18:52+4У стринга плохая хэш функция, к которой легко найти коллизии. Из-за этого до седьмой версии Java, при использовании строк в качестве ключей HashMap, нужно было следить, чтобы все ключи не легли в один и тот же бакет. Заменить хэш функцию на другую было нельзя, так как она описана в стандарте, поэтому в седьмой джаве бакет в HashMap, при появлении в нём более семи объектов, меняет начинку со связного списка на дерево.
Правда, как сказали ниже, у String хэш функция не дефолтная, поэтому что хотел сказать автор комментария действительно не совсем понятно.
vladimir_dolzhenko
07.02.2017 19:14Она описана в javadoc к java.lang.String — менять в рамках одного вендора (и все кто базуируется на OpenJDK) не будут ибо сломают обратную совместимость,
однако у каждого вендора она может быть своя — о том как она должна вычисляться нет в java lang spec.
konsoletyper
08.02.2017 00:03+3Её менять нельзя из-за того, что в java 7 появился switch по строкам. А он как раз реализован через switch (str.hashCode()), и компилятор вставляет предвычисленные хэш-коды прямо в байт-код.
sleeply4cat
08.02.2017 12:04а что происходит в случае коллизии?
konsoletyper
08.02.2017 12:05Внутри case будет цепочка if/else if, где с помощью equals проверяется каждый вариант.
sleeply4cat
08.02.2017 12:09хм.
Тогда что мешает разрешить switch длявсехобъектов, выполняющих некоторый контракт?konsoletyper
08.02.2017 12:11+1Отсутствие в компиляторе знания о том, как именно в этих объектах реализован
hashCode. Отсутствие знания в компиляторе о том, как именно сконструировать экземпляр объекта в compile-time. Для частных случаев (например, строки, enum-ы) это знание есть.sleeply4cat
08.02.2017 12:48зачем вообще это делается на этапе компиляции?
konsoletyper
08.02.2017 12:56Что "делается"? Инстанс объекта создаётся? Нет, ничего не создаётся, но вычисление
hashCodeтребует знания, какое у объекта внутреннее состояния. Без знания логики конструирования объекта о внутреннем состоянии судить нельзя, следовательно невозможно вычислитьhashCode.
Зачем компилятору вычислять
hashCode? А как он сгенерит такое:
switch (str.hashCode()) { case FOO_HASHCODE: if (o.equals("foo")) { ... } else goto default; case BAR_HASHCODE: if (o.equals("bar")) { ... } else goto default; default: { ... } }
Ну хорошо, мы можем и дальше так продолжать играть в вопросы. Давайте так, если есть что предложить — предлагайте (и даже можете кинуть JSR в JCP). Только не в духе "хорошо было бы сделать", а в духе "как ИМЕННО сделать" с учётом разных нюансов. Я уверяю, при попытке сформулировать предложение вы сами всё поймёте.
sleeply4cat
08.02.2017 13:33Окей, как самый простой вариант — пробежать в рантайме все объекты, соответствующие ветвям свитча.
for (Object c: cases) { if (c.hashCode == inp.hashCode) { if (c.equals(inp)) { {...} break; } } }konsoletyper
08.02.2017 13:43Ну а толку-то? По сути, не нужен для этого никакой цикл. Это будет эквивалентно какому-нибудь if..else if… else. На уровне синтаксиса это можно подсахарить. Вон, в Kotlin есть
when, который по сути является сахаром для if..else if. Но чуда не ждите, на рантайме от этого быстрее не станет. Когда в Java 7 вводили switch по строкам, задизайнили фичу так, чтобы её можно было эффективно реализовать.poxvuibr
09.02.2017 10:41Проблема с функцией хэширования строки сильно старше седьмой джавы. Соответственно, когда появилась конструкция switch для строки — проблема уже была и ничего не мешало переопределить String.hashCode одновременно с вводом конструкции. Ничего, кроме спеки.
Основную проблему, связанную с поломкой хэш кода для строк, кстати, зарешали именно в седьмой ждаве, путём внесения изменений в HashMap :)
vladimir_dolzhenko
09.02.2017 13:41+2ломать обратную совместимость — слишком дорогое удовольствие — и ломали её один раз — в 1.2.0 — java bug #4045622
Основную проблему, связанную с поломкой хэш кода для строк, кстати, зарешали именно в седьмой ждаве, путём внесения изменений в HashMap :)
Что именно вы имеете в виду?poxvuibr
09.02.2017 14:23Что именно вы имеете в виду?
Ну, что будет, если в HashMap класть объекты с одинаковым хеш кодом.
vladimir_dolzhenko
09.02.2017 14:46+1в 7ке как был chaining так и остался, в 8ке будет дерево, если превышен порог коллизий
lany
12.02.2017 07:31Спасибо, познавательное чтиво. Особенно это:
I suppose I'd rule out Vo's variant and Weinberger's
function because of their added complexity, albeit minor. Of the remaining
four, I'd probably select P(31), as it's the cheapest to calculate on a RISC
machine (because 31 is the difference of two powers of two). P(33) is
similarly cheap to calculate, but it's performance is marginally worse, and
33 is composite, which makes me a bit nervous.HotSpot JIT-компилятор давно умеет оптимизировать умножение на 31 через сдвиг и вычитание. С множителем 37 было бы хуже, конечно.
apangin
12.02.2017 11:26+2С другой стороны, процессоры тоже давно умеют оптимизировать умножение на аппаратном уровне. Таким образом, strength reduction умножения потеряла первоначальную ценность и теперь, скорее, вредит:
Хотя в исходниках до сих пор можно встретить подобную ручную «оптимизацию», например, в IdentityHashMap.
vladimir_dolzhenko
08.02.2017 13:23+1кстати — вот ещё раз попытался покопаться в java lang spec — и ничего не говорится о том как именно реализован switch(String) — т.е одно дело openjdk (или производный от него) javac создаст класс — а как его потом будут выполнять другие vm?
где-то это должно быть специфицировано, дабы не получить неожиданностей в поведении — может вы нашли это место?konsoletyper
08.02.2017 13:34+1Я так понимаю, это всё-таки не документируется в спеке языка. Т.е. компилятор может реализовывать
switchпо строкам в принципе как ему захочется. А вот в JDK это поведение чётко описано. Просто так особенности реализации в javadoc-ах не описывают, т.е. именно такой способ вычисления String.hashCode — это всё-таки публичный контракт. Учитывая особенности публичного контракта JDK, компилятор может порождать эффективную реализацию (что и делает javac).vladimir_dolzhenko
08.02.2017 13:50String.hashCode — это всё-таки публичный контракт.
String.hashCode описан только в javadoc — в java lang spec его нет, ровно как и нет деталей о том, как компилировать switch(Strings) — формально любой другой вендор имеет право реализовывать свой String.hashCode и вроде как формально он не нарушает спецификацию языка, но как следствие — все либы, которые собраны с другим String.hashCode будут сломаны при использовании switch(String).
Выглядит скорее как дыра в спеке
apangin
08.02.2017 13:56Javadoc к публичным Java SE классам — это часть Java SE спецификации. Не языка Java, а API.
23derevo
14.02.2017 00:18+5Если уж совсем точно, то полная спецификация платформы
- состоит из кучи документов
- имеет конкретную версию
То есть, нет спецификации «Java SE», а есть, например, спецификация «Java SE 8»:
Java SE 8 Platform Specification = JLS 8 + JVMS 8 + Java SE 8 API Specification (aka javadoc 8) + JOSS + Security + Extentions +…
apangin
08.02.2017 13:54+2Всё верно. Алгоритм
String.hashCodeпрописан в спецификации Java SE API, и другие реализации Java SE не вправе его менять. А то, во что switch превращается — отдаётся на откуп компилятору. И javac генерирует код, который на любой Java SE-совместимой реализации будет корректен.vladimir_dolzhenko
08.02.2017 13:58т.е чтобы быть java compatible нужно быть не только следовать java lang spec, но и java se api — и javadoc это вполне себе контракт.
спасибо
Sirikid
07.02.2017 19:15Эта функция используется много где ещё в OpenJDK, например все перегрузки
java.util.Arrays#hashCodeиjava.util.AbstractList.
lany
08.02.2017 17:40поэтому в седьмой джаве бакет в HashMap, при появлении в нём более семи объектов, меняет начинку со связного списка на дерево.
Не в седьмой, а в восьмой.
Ну и константное число запросов к мапке на один запрос к сервису обычно не приводит к эффективной DoS-атаке. А если оно у вас не константное, то частенько вы ССЗБ.
poxvuibr
15.02.2017 09:56Про номер джавы меня уже поправили :).
А вот про константное число запросов — если в бакете оооочень длинный лист, то для эффектиной DoS атаки достаточно просто сделать достаточное количество запросов. По крайней мере я так понял.
poxvuibr
07.02.2017 17:32-5Все бенчмарки прогонялись на Intel Core i5 2,7 ГГц
Это примерно как в 2000 году написать, что все бенчмарки прогонялись на Celeron :).
apangin
07.02.2017 20:23+2А почему в JDK 8 изменили метод генерации identityHashCode, хотя все те же алгоритмы были и раньше?
Maccimo
07.02.2017 20:48+5… задаёт вопрос человек, написавший три года назад статью ;)
Для остальных: http://mail.openjdk.java.net/pipermail/hotspot-runtime-dev/2013-January/005212.html
apangin
07.02.2017 23:02+10Сорри, позволил себе лёгкий троллинг :) Просто зачем автор полез в такие глубины, не разобравшись в более простых вещах? Это ставит под сомнение и всю статью.
I have found no HotSpot flag that allows changing the default generator, so experimenting with other options might need to compile from source.
Как же так? Про-XX:hashCode=Nуже миллион раз писали в блогах, твиттере, на Stack Overflow и пр.
even if there is a single thread interested in the lock, the header word will be contended and require atomic operations to be handled correctly. Which defeats the whole point of biased locking.
Объяснение про несовместимость Biased Lock с identityHashCode вообще жуткое: какие-то диаграммы состояний, перемещение заголовков, бла-бла-бла… Истинная же причина проста: в целях экономии места в заголовок помещается либо признак Biased-блокировки, либо identityHashCode. Только и всего.
TheKnight
07.02.2017 21:23+2Режим Ванги — Шипилёв прочитал вашу статью и подумал — «А чеб и не поменять, раз быстрее?» :)
UPD: Прочитал письмо, вроде похоже на правду.apangin
07.02.2017 22:01+4Ирония в том, что в конечном итоге это изменение было сделано нечаянно. Заветная строчка попала в репозиторий по ошибке вместе с коммитом к совсем другой фиче :)
PhantomGOD
08.02.2017 09:09+1На хабре была статья (как раз недавно ее читал) с названием «Откуда растут ноги у hashCode» . Автору бы не помешало разместить ее в ссылках. Собственно интересовал вопрос адресации памяти выше 4 ГБ, ведь int hashCode().
qwwdfsad
09.02.2017 01:20+1Статья выглядит очень подозрительно с точки зрения осведомленности автора:
Диаграмма состояний и доказательство невозможности выглядит странно, хотя в том же комментарии в oopMark.hpp видно, что в заголовке просто не хватает места на хэшкод и указатель на поток + эпоху.
Когда за блокировку конкурируют два потока, привязанная блокировка отключается в любом случае, так что между двумя методам хеширования не наблюдается значимой разницы.
Это может и правда, но у автора в бенчмарке ошибка копипасты и в обоих случаях он синхронизируется на withoutIdHash
В версиях 6 и 7 это случайно генерируемое число. В версиях 8 и 9 это число, полученное на основании состояния потока
И в переводе, и в оригинале это звучит так, будто в 8 и 9 число уже неслучайное.
Оно все еще случайно, просто seed теперь thread-local (и не один), а сам генератор работает по-другому.
Ну и флаг для смены генератора конечно же есть.
strangeraven
09.02.2017 14:33Если я правильно понял, то все эти танцы с бубнами преследует одну цель: вычислять hashCode лениво, при первом вызове.
Неужели это оправдано? Не проще ли было при создании объекта сразу проинициализировать его адресом или каким-то псевдослучайным числом?
Это выглядит как очень дешевое действие, которое отработает за пару тактов и ни на что особо не повлияет.apangin
09.02.2017 22:04+1Нет, вычислять hashCode лениво вообще не проблема. Вся история о том, где это значение хранить. И в этом смысле инициализация hashCode при создании объекта ничем не поможет.
chabapok
14.02.2017 17:29Где-то на ютуб канале jug Шипилев объяснял, что у них там так исторически сложилось: если позвали хешкод, то отключем навсегда привязанную блокировку этому объекту. Дело в том, что на размер объекта много чего завязано — и решили, что проще сэкономить 1 байт, чем иметь и то и другое.
vlukanichev
17.02.2017 15:32Тоже помню этот доклад. Называется «О чем молчат HeapDump'ы», если кто захочет посмотреть.
breakoffbrain
Спасибо за очередную хорошую статью.)