Скаляризация Map.get(...) -- продолжение

...которое было задумано сразу после, но неожиданно задержалось: сложная политическая обстановка, на работе завал, в Москве пробки, гомеопаты атакуют, а в фейсбуке регулярно кто-то не прав — как тут найти время?

После прочтения предыдущего поста возникает депрессиявопрос: можно ли как-то добиться стабильной скаляризации ключей? Краткий ответ: нет. Более полный ответ: нет, стабильной скаляризации в JVM (HotSpot) добиться невозможно. JIT — это рулетка. Смиритесь.

... Но побарахтаться все-таки можно. Ни один из способов ниже я не готов считать "хорошим" — в том смысле, что они не являются примером хорошего кода, и их вряд ли стоит внедрять в свой обычный стиль программирования. Тем не менее, иметь возможность побарахтаться, мне кажется, всегда лучше, чем не иметь :)

Во-первых, можно просто уменьшить размер метода .equals(). Казалось бы, куда уж меньше:

public boolean equals( final Object o ) {
 if( this == o ) {
  return true;
 }
 if( !( o instanceof StringKey ) ) {
  return false;
 }

 final StringKey key = ( StringKey ) o;

 return item1.equals( key.item1 )
   && item2.equals( key.item2 );
}

(Напомню, что этот метод комплируется в 55 байт, что больше 35 — порога вклеивания для не-горячих методов). Оказывается, однако, что меньше можно:

public boolean equals( final Object o ) {
 if( this == o ) {
  return true;
 }
 if( !( o instanceof StringKey ) ) {
  return false;
 }

 final StringKey key = ( StringKey ) o;

 return equals( key );
}

private boolean equals( final StringKey key ) {
 return item1.equals( key.item1 )
   && item2.equals( key.item2 );
}

Первый .equals(Object) комплируется в 27 байт, второй в 34, и тот и другой проходят под порогом. В данном примере такое разбиение имеет самостоятельный смысл: типизированный .equals(StringKey) может быть полезен сам по себе, но вообще-то надо понимать, что мы здесь используем в своих интересах несовершенство эвристики вклеивания — большие методы нужно декомпозировать чтобы код был читабельным и переиспользуемым, а не чтобы переиграть JIT в очко.

Не стоит забывать так же, что увеличивая глубину стека вызовов мы увеличиваем вероятность наступить на порог инлайнинга по глубине (MaxInlineLevel=9) — в изолированном бенчмарке эта вероятность невелика, но в реальной программе она гораздо выше. Кроме того, хотя маленьким методам уже не обязательно быть горячими, но им все равно нужно выполниться хотя бы 250 раз (MinInliningThreshold) чтобы JIT счел их достойными вклеивания.

Ок, в конце-концов можно взять другую реализацию хэш-таблицы. Я пробовал trove THashMap, и guava ImmutableMap. По моим наблюдениям, в обоих случаях ситуация немного лучше, чем с j.u.HashMap, но именно что немного: да, скаляризация случается чаще, но все равно не всегда. Посмотрим, например, на THashMap:

public V get(Object key) {
    int index = index(key);
    return index < 0 ? null : _values[index];
}

protected int index(Object obj) {
    if (obj == null)
        return indexForNull();

    // From here on we know obj to be non-null
    final int hash = hash(obj) & 0x7fffffff;
    int index = hash % _set.length;
    Object cur = _set[index];


    if (cur == FREE) {
        return -1;
    }

    if (cur == obj || equals(obj, cur)) {
        return index;
    }

    return indexRehashed(obj, index, hash, cur);
}

private int indexRehashed(Object obj, int index, int hash, Object cur) {
    final Object[] set = _set;
    final int length = set.length;

    // NOTE: here it has to be REMOVED or FULL (some user-given value)
    // see Knuth, p. 529
    int probe = 1 + (hash % (length - 2));

    final int loopIndex = index;

    do {
        index -= probe;
        if (index < 0) {
            index += length;
        }
        cur = set[index];
        //
        if (cur == FREE)
            return -1;

        //
        if ((cur == obj || equals(obj, cur)))
            return index;
    } while (index != loopIndex);

    return -1;
}

Я наблюдаю два основных сценария, как здесь обламывается скаляризация: во-первых, какой-то из методов index()/indexRehashed() не вклеивается с диагностикой "already compiled into a big method". Например, вот так (size=1024, hit probability=2%):

@ 84   ...THashMap::get (21 bytes)   inline (hot)
   \-> TypeProfile (74492/74492 counts) = gnu/trove/map/hash/THashMap
    @ 2   ...TObjectHash::index (72 bytes)   inline (hot)
      @ 11   ...TObjectHash::hash (5 bytes)   inline (hot)
        @ 1   ...$StringKey::hashCode (5 bytes)   accessor
      @ 54   ...TObjectHash::equals (19 bytes)   inline (hot)
        @ 15   ...$StringKey::equals (55 bytes)   inline (hot)
          @ 29   j.l.String::equals (81 bytes)   (intrinsic)
          @ 43   j.l.String::equals (81 bytes)   (intrinsic)
      @ 68   ...TObjectHash::indexRehashed (80 bytes)   already compiled into a big method

В докладе я разбирал точно такой сценарий на примере LinkedList, напомню вкратце: здесь возникает конфликт между двумя разными эвристиками инлайнинга, и итоговое решение зависит от того, какой из методов скомплируется раньше, а какой позже. А раз порядок компиляции недетерминирован, то и результат тоже: один и тот же код при одинаковых параметрах 5 раз подряд покажет успешную скаляризацию, а на 6-й какой-нибудь посторонний процесс оттянет на себя CPU, слегка изменит соотношение времен исполнения задач компиляции, и все, прощай.

Второй же сценарий провала скаляризации напоминает j.u.HashMap: поиск в THashMap тоже распадается на две ветки (см. выше), одна для прямого попадания, и вторая для разрешения коллизий (indexRehashed), и если одна из этих веток сильно доминирует, то вторая просто не разогреется достаточно сильно, чтобы JIT решил ее вклеить, а порог инлайнинга для не-горячих методов .indexRehashed() явно превышает (диагностика "too big").

(guava ImmutableMap я подробно разбирать не буду: стабильной скаляризации нет и там, хотя метод .get() там чуть ли не самый компактный)