Таинственный 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). Будьте осторожнее и не используйте опций, смысла которых вы до конца не понимаете.