Таинственный FrontCache

Всё началось с того, что я в очередной раз ковырял в Eclipse Memory Analyzer дамп памяти Java-приложения и увидел такую интересную вещь:

С кодом HashMap я знаком весьма неплохо, но вложенного класса FrontCache никогда там не видел. Может, с последним обновлением JDK мне прислали обновлённый HashMap? Я заглянул в исходники, но слова «front» там не обнаружилось. Стало интересно, откуда же этот класс берётся и что он делает.

Порывшись в JRE (у меня 1.7u10, но и в последних 1.6 тоже это есть), я нашёл любопытный джарик: alt-rt.jar, в котором и обнаружился HashMap$FrontCache.class, а также несколько других классов (LinkedHashMap, TreeMap, BigDecimal, BigInteger, MutableBigInteger и их вложенные классы). Обычно эти классы подключаются из rt.jar. Почему же они стали грузиться из этого загадочного джарика?

Я вспомнил, что недавно экспериментировал с опциями Java-машины и, в частности, включил -XX:+AggressiveOpts. На сайте Оракла про этот ключ написано скупо:

Turn on point performance compiler optimizations that are expected to be default in upcoming releases.

На Хабре была попытка объяснить эту опцию подробнее, мол, это комбинация других ключиков. Порывшись в исходниках OpenJDK 7-й версии я понял, что ключиками дело не ограничивается. Вот что мы видим в hotspot/src/share/vm/runtime/arguments.cpp:

jint Arguments::parse_vm_init_args(const JavaVMInitArgs* args) { ...   if (AggressiveOpts) {     // Insert alt-rt.jar between user-specified bootclasspath     // prefix and the default bootclasspath.  os::set_boot_path()     // uses meta_index_dir as the default bootclasspath directory.     const char* altclasses_jar = "alt-rt.jar";     size_t altclasses_path_len = strlen(get_meta_index_dir()) + 1 +                                  strlen(altclasses_jar);     char* altclasses_path = NEW_C_HEAP_ARRAY(char, altclasses_path_len);     strcpy(altclasses_path, get_meta_index_dir());     strcat(altclasses_path, altclasses_jar);     scp.add_suffix_to_prefix(altclasses_path);     scp_assembly_required = true;     FREE_C_HEAP_ARRAY(char, altclasses_path);   } 

Ага! С этой опцией действительно помимо всего прочего добавляется alt-rt.jar. В этом можно убедиться и из своего приложения, воспользовавшись System.getProperty("sun.boot.class.path"). Таким образом, для упомянутых классов при включенных AggressiveOpts реализация меняется.

Но в чём различие в реализации HashMap? Я стал искать изменённый исходник, но тут меня постигла неудача. Выяснилось, что этот jar собирается с помощью jdk/make/altclasses/Makefile, а каталог с исходниками обозначен как

ALTCLASSES_SRCDIR = $(CLOSED_SRC)/share/altclasses

Это запахло не очень хорошо, и файл jdk/make/common/Defs.gmk подтвердил мои опасения:

# Files that cannot be included in the OpenJDK distribution are # collected under a parent directory which contains just those files. ifndef CLOSED_SRC   CLOSED_SRC  = $(BUILDDIR)/../src/closed endif

Разумеется, указанного каталога в комплекте не идёт. На всякий случай я выкачал JDK 8, но там ситуация была не лучше. Oracle прячет альтернативный HashMap.

Порывшись в интернете, я напоролся на проект, который обнадёжил меня, но напрасно. На главной написано, что там есть исходники классов из jre\lib\alt-rt.jar, по факту же там стандартная реализация HashMap и остальных классов. Видимо, автор не разобрался, что есть два варианта.

Остался один способ — дизассемблировать байткод (javap -c -private) и почитать его так. Чтобы было проще, я дизассемблировал обычный и альтернативный HashMap, парой регекспов выкинул несущественные вещи и сравнил diff’ом. Сперва всё выглядело довольно страшно, но потом я догадался, что код обычного и альтернативного HashMap эволюционировали независимо, поэтому сравнивать альтернативный HashMap надо с общим предком, коим оказался HashMap из последних апдейтов 6-й JDK. Тут картина стала гораздо понятней, не потребовалось даже специальных инструментов для декомпиляции в Java-код. В HashMap действительно появилось HashMap.FrontCache frontCache, которое инициализируется в конструкторе. Конструктор FrontCache принимает capacity — количество элементов в основной хэш-таблице. В метод get(Object key) добавлен примерно такой код:

if(frontCache != null) { 	V value = frontCache.get(key); 	if(value != null) return value; }

В метод put(K key, V value) добавлено следующее:

if(frontCache != null) { 	frontCache.put(key, value); }

Есть технические изменения и в других методах, но суть здесь. Ясно, что frontCache — какое-то альтернативное (видимо, более быстрое) хранилище данных. При запросе элемента он в первую очередь ищется в frontCache, а при занесении нового заносится и в frontCache, и в обычную хэш-таблицу. Что же такого ускоряет класс FrontCache? Вот как выглядят самые важные методы из него:

private class FrontCache { 	private Object[] cache; 	private int bitMask; 	 	public FrontCache(int capacity) { 		this.cache = new Object[capacity]; 		this.bitMask = makeBitMask(capacity); 	}  	public int makeBitMask(int capacity) { 		return -1 << (32 - Integer.numberOfLeadingZeros(capacity - 1)); 	} 	 	public boolean inRange(int value) { 		return (value & bitMask) == 0; 	} 	 	public V get(Object key) { 		if(key instanceof Integer) { 			int intKey = ((Integer)key).intValue(); 			if(inRange(intKey)) { 				return (V) cache[intKey]; 			} 		} 		return null; 	} 	 	private void put(K key, V value) { 		if(key instanceof Integer) { 			int intKey = ((Integer)key).intValue(); 			if(inRange(intKey)) { 				cache[intKey] = value; 			} 		} 	} }

Прочие методы служат для удаления элементов, изменения размера кэша и т. д. Но идея из приведённого кода понятна: если ключ — Integer и он попадает в диапазон от 0 до capacity-1 (проверка оригинально соптимизирована), то значение просто заносится в массив по индексу с соответствующим порядковым номером без всяких преобразований и хэш-функций.

Если же ключи не являются целыми числами, то FrontCache просто бесполезен. Однако массив всё равно выделяется и проверки делаются при каждой операции с HashMap.

На самом деле теряется даже больше памяти, так как HashMap.Entry имеет метод setValue, который теперь должен обновлять и значение в FrontCache при необходимости. Поэтому в каждый Entry добавлена ссылка на сам HashMap, что может добавлять до 8 лишних байт на запись.

Открытие несколько шокировало меня. Последнее время мы во славу Trove почти не пользуемся ключами вроде Integer, поэтому получилось, что оптимизация только напрасно ест время и память. В общем, я решил, что AggressiveOpts лучше отключить. Конечно, я не разбирался, что там изменилось в TreeMap и математических классах (в LinkedHashMap изменения косметические, связанные как раз с изменениями в HashMap.Entry для поддержки FrontCache). Будьте осторожнее и не используйте опций, смысла которых вы до конца не понимаете.