4 декабря 2016 г.

Так что насчет производительности?..

Значительная часть моих историй про скаляризацию состоит из описания того, как все весело разваливается, чуть что-нибудь где-нибудь недозаинлайнилось. После чего у некоторых читателей возникает ощущение "да ну его в жопу, я лучше сам все закэширую, и все гарантированно будет быстро, и не важно, что там как инлайнится". Честно говоря, мне и самому стало интересно, насколько оно все будет быстро, если плохо заинлайнится, поэтому я написал такой несложный бенчмарк:
public class GCCostBenchmark {


 @Param( { "32", "64", "128", "256", "1024" } )
 public static int SIZE = 128;

 ArrayList<Integer> list = new ArrayList<>();

 @Setup
 public void setup() {
  final ThreadLocalRandom rnd = ThreadLocalRandom.current();
  for( int i = 0; i < SIZE; i++ ) {
   list.add( rnd.nextInt() );
  }
 }


 @Benchmark
 public long sumWithIterator() {
  long sum = 0;
  for( final Integer n : list ) {
   sum += n;
  }
  return sum;
 }

 @Benchmark
 public long sumWithIndex() {
  long sum = 0;
  for( int i = 0; i < list.size(); i++ ) {
   final Integer n = list.get( i );
   sum += n;
  }
  return sum;
 }
}
Просто создаем ArrayList разных размеров, заполняем его случайными числами, и в цикле суммируем. И смотрим на два разных варианта организации цикла: через итератор, и старперский, через индекс.
Benchmark               (SIZE)   Mode  Cnt   Score    Error   Units
sumWithIndex                32  thrpt    5  27.195 ±  3.476  ops/us
sumWithIndex                64  thrpt    5  15.362 ±  0.443  ops/us
sumWithIndex               128  thrpt    5   8.359 ±  0.775  ops/us
sumWithIndex               256  thrpt    5   4.243 ±  0.268  ops/us
sumWithIndex              1024  thrpt    5   1.115 ±  0.029  ops/us
sumWithIterator             32  thrpt    5  24.300 ±  0.244  ops/us
sumWithIterator             64  thrpt    5  12.973 ±  0.056  ops/us
sumWithIterator            128  thrpt    5   7.415 ±  0.035  ops/us
sumWithIterator            256  thrpt    5   4.023 ±  0.392  ops/us
sumWithIterator           1024  thrpt    5   1.138 ±  0.012  ops/us
Видно, что на моей JDK 1.8.0_102 они идут ноздря в ноздрю: вариант с индексом слегка обходит итератор, но различие в пределах погрешностей. Ок, это будет наша реперная точка. Теперь мы запускаем тот же бенчмарк, но с флагом -XX:-EliminateAllocations. В у бенчмарка с итератором, разумеется, появляются строчки gc-profiler-а gc.alloc.rate.norm=32.000±0.001 B/op, но меня интересуют другие цифры:
Benchmark                (SIZE)   Mode  Cnt    Score    Error   Units
sumWithIndex                 32  thrpt    5   27.063 ±  1.527  ops/us
sumWithIndex                 64  thrpt    5   15.571 ±  0.243  ops/us
sumWithIndex                128  thrpt    5    7.795 ±  0.066  ops/us
sumWithIndex                256  thrpt    5    4.213 ±  0.022  ops/us
sumWithIndex               1024  thrpt    5    1.120 ±  0.011  ops/us
sumWithIterator              32  thrpt    5   21.022 ±  1.452  ops/us
sumWithIterator              64  thrpt    5   11.295 ±  2.082  ops/us
sumWithIterator             128  thrpt    5    6.145 ±  0.273  ops/us
sumWithIterator             256  thrpt    5    3.359 ±  0.035  ops/us
sumWithIterator            1024  thrpt    5    0.905 ±  0.032  ops/us
Как и можно было бы ожидать, итерация с индексом почти никак не отреагировала на этот флаг, а итератор стал медленнее, примерно на ~15-20%. Но это я волевым решением отрезал скаляризацию. А давайте сэмулируем отсутствие инлайнинга (и как следствие — скаляризации):
-XX:CompileCommand="dontinline,java.util.AbstractList::*"
-XX:CompileCommand="dontinline,java.util.ArrayList::*"
— я отключаю инлайнинг для всех методов ArrayList/AbstractList (ну, чтобы уж с надежностью):
Benchmark                (SIZE)   Mode  Cnt    Score    Error   Units
sumWithIndex                 32  thrpt    5    2.767 ±  0.033  ops/us
sumWithIndex                 64  thrpt    5    1.410 ±  0.012  ops/us
sumWithIndex                128  thrpt    5    0.709 ±  0.003  ops/us
sumWithIndex                256  thrpt    5    0.357 ±  0.003  ops/us
sumWithIndex               1024  thrpt    5    0.093 ±  0.003  ops/us
sumWithIterator              32  thrpt    5    3.528 ±  0.055  ops/us
sumWithIterator              64  thrpt    5    1.821 ±  0.029  ops/us
sumWithIterator             128  thrpt    5    0.933 ±  0.015  ops/us
sumWithIterator             256  thrpt    5    0.464 ±  0.020  ops/us
sumWithIterator            1024  thrpt    5    0.119 ±  0.003  ops/us
Без инлайнинга производительность цикла просела в 10 раз! (кстати, теперь версия с итератором работает быстрее :)

Пример немного искусственный: уж больно много разных loop optimizations отваливается без инлайнинга. Для кода более общего вида настолько радикального падения производительности не будет. Но в целом, мораль истории такова: если у вас где-то в горячем коде не сработал инлайнинг — у вас скорее всего уже достаточно серьезные проблемы с производительностью в этом месте. Не скаляризованные аллокации добавят сюда лишь какие-то крохи.

29 ноября 2016 г.

Видео с jug-ekb

Сентябрьский доклад на jug-ekb. Спасибо организаторам:

25 ноября 2016 г.

Скаляризация 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() там чуть ли не самый компактный)

8 октября 2016 г.

Скаляризация Map.get(new CompositeKey(key1, key2, ...))

Один из самых интересных примеров из моего последнего доклада на jug-ekb (на JPoint этот пример не влез) это скаляризация композитных ключей в поиске по словарю:
final Map<CompositeKey, V> map = ...;

...
    final CompositeKey key = new CompositeKey( key1, key2, ... );
    final V value = map.get( key );
...
Это весьма частый паттерн: нам нужно отображение вида [key1, key2, key3...] -> value. Наиболее простой и очевидный способ это сделать: как раз таки использовать композитный ключ (кортеж из ключей). Решение отличное по всем показателям, кроме одного: для каждого поиска в словаре придется создавать новый объект.

Иногда хочется этого избежать. Тогда приходится организовывать иерархические словари-словарей-словарей... — я видел много таких примеров (поиск по текущему проекту находит аж 5 различных реализаций чего-то вроде TwoKeyMap/ThreeKeyMap). Это решение мне самому не нравится (хотя 2 из 5 упомянутых реализаций — мои). Например, словарь-словарей это совсем другой тип, нежели словарь-словарей-словарей — расширение ключа на одну позицию не является прозрачным, окружающий код специализирован под конкретное число ключей. У этого решения, как правило, хуже производительность: во-первых, потому что приходится делать 2-3-4... поиска вместо одного, а во-вторых потому, что соответствующие словари обычно получаются очень неравномерно заполненными. Скажем, key1 может иметь всего 3-4 разных значения, а лежать они будут в таблице размером по-умолчанию (16). При этом, скажем, ключей вида ("A", *) всего 2, а вида ("B", *) — 10000. То есть часто образуется много сильно недозаполненных таблиц, вперемешку с несколькими нормальными. Будь все эти ключи в одной таблице — все эти неоднородности сильно сгладились бы.

В общем, хотелось бы и чтобы все было хорошо, и за это не приходилось бы ничего платить. Может ли JIT сам скаляризовать аллокацию ключа в сценарии типа map.get( new CompositeKey( key1, key2, ... ) )?

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

Как выглядит сам бенчмарк: я генерирую пул строк, из них образую парные композитные ключи (StringKey), которыми наполняю хэш-таблицу. Внутри главного цикла бенчмарка я создаю ключи таким образом, чтобы они присутствовали или отсутствовали в словаре с какой-то вероятностью (hit probability — один из параметров сценария), и запрашиваю у словаря соответствующие значения.

private final Pool<String> keys = poolOf( randomUniqueStrings( 2 * SIZE ) );

private final Pool<String> nonExistentKeys = poolOf( randomUniqueStrings( 2 * SIZE ) );

//...

public long run() {
 final boolean successful = ( rnd.nextDouble() <= SUCCESSFUL_LOOKUPS_PROBABILITY );
 
 final String key1;
 final String key2;
 if( successful ) {
  key1 = keys.next();
  key2 = keys.next();
 } else {
  key1 = nonExistentKeys.next();
  key2 = nonExistentKeys.next();
 }

 final String value = map.get( new StringKey( key1, key2 ) );

 if( value == null ) {
  return 0;
 } else {
  return 1;
 }
}

Что получается на выходе: иногда ключи скаляризуются почти стабильно, для целого спектра размеров таблицы (1,2,4...65) и спектра hit probability=(0%, 50%, 100%). А иногда — почти стабильно не скаляризуются. А иногда вообще какая-то ересь получается: сценарий аллоцирует что-то вроде 120 байт на вызов, вместо обычных 24-х — что уже вообще ни в какие ворота. Поведение меняется от небольших изменений в коде, и от того, использую ли я в качестве ключей свой собственный класс StringKey, или заменяю его на ImmutablePair из apache commons.

Дальше я буду идти от теории к практике — порассуждаю про код, и подтвержу свои рассуждения примерами. В реальности все происходило ровно наоборот: я сначала поставил много экспериментов, результаты которых были довольно запутывающими, а потом уже построил модель, что и как происходит. Такая история, конечно, гораздо увлекательнее, но пересказывать ее уж очень долго выходит.

Начнем с кода HashMap.get(). В 1.8.0_102 он выглядит так:

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
Что мы можем здесь увидеть — помимо того, что автору неплохо бы пересмотреть свой стиль именования переменных? Мы можем увидеть, что здесь две ветки — "прямое попадание", и процедура разрешения коллизий, и внутри второй ветки — еще две ветки (поиск в связном списке или дереве). Чтобы скаляризация имела шанс сработать, нам необходимо (но не достаточно), чтобы заинлайнились все методы, в которые уходит интересующий нас объект (key), до самого низа. В данном случае, как минимум, должны заинлайниться hashCode(), оба вызова .equals() и .getTreeNode().

А что нужно, чтобы метод заинлайнился? О, это большая тема :) Инлайнинг — одна из самых потенциально эффективных оптимизаций в JIT-ах, так что эвристик у нее немало. К счастью, все они нам обычно не нужны, достаточно сильно сокращенной версии:
  1. Если метод-кандидат виртуальный — он должен быть девиртуализован. Для девиртуализации необходимо либо чтобы CHA показал, что сейчас в JVM в принципе загружена только одна реализация, либо чтобы профиль, собранный во время исполнения (TypeProfile) показал, что в данном конкретном месте (вероятно) вызывается не более двух реализаций виртуального метода.
  2. Если метод-кандидат достаточно горячий (горячесть вычисляется как по абсолютному количеству вызовов, так и по тому, насколько часто метод-кандидат вызывается из того метода, в который мы его собираемся вклеивать), то его размер в байт-кодах должен быть не больше FreqInlineSize(=325), и размер в машинных кодах (если он уже был скомпилирован изолированно) не больше SmallInlineSize(=2000).
  3. Если метод недостаточно горячий, то, возможно, он хотя бы маленький (< MaxInlineSize(=35))? Но, при этом, он должен все-таки выполниться хоть сколько-то: как минимум, MinInliningThreshold(=250) раз. А иначе какой смысл вклеивать?
  4. ...Но если какая-то ветка не выполнилась вообще ни разу (за время профилирования), то C2 выкинет ее код вообще, а на случай "а вдруг" поставит вместо нее т.н. uncommon trap: перезапуск выполнения метода в режиме интерпретатора. Эта часть уже не является частью политики инлайнинга, это отдельная, и очень мощная спекулятивная оптимизация, но она очень помогает скаляризации: ведь если весь код ветки выброшен, то он не анализируется на предмет убегания ссылок.
(Обычному java-программисту непривычно думать о размере метода в байт-кодах, поэтому цифры типа 325 и 35 могут выглядеть довольно абстрактно. Точного соотношения между размером джава-кода и размером байт-кода, разумеется, нет, но по порядку величины можно сказать так: 325 байт это довольно большой метод, примерно на полстраницы-страницу, а 35 байт это коротенький метод, на 3-4 строчки)

...Итак, у нас есть код поиска ключа в хэш-таблице, который состоит из нескольких этапов (веток): поиск нужной корзинки (bucket), сравнение (по хэш-коду и по .equals()), поиск по списку коллизий (по хэш-коду и по .equals()) или поиск по дереву коллизий (там вообще мрак и ужас). И поиск может завершиться на любом этапе, но вся идея хэш-таблицы как структуры данных в том, что как правило у нас списки коллизий короткие, или отсутствуют вовсе. То есть, если раскладка данных в хэш-таблице достаточно равномерная (==хэш-функция хорошая), то вероятность завершить поиск на первом же этапе довольно высока, вероятность попасть в ветку разрешения коллизий — заметно меньше, а вероятность наткнуться на список коллизий настолько длинный, чтобы он конвертировался в дерево — совсем маленькая. Более точно, можно выделить такие сценарии:

  1. Попали в пустую корзинку: этот сценарий довольно часто (с вероятностью = 1 - load factor = 25%..60%) будет реализовываться, когда мы будем искать несуществующие в таблице ключи (hit probability << 100%). Здесь вызывается только key.hashCode(), ни один из 2х .equals(), ни .getTreeNode() не вызывается вообще
  2. Попали в корзинку с единственной парой ключ-значение: этих сценариев будет большинство среди тех, когда мы вообще что-то найдем (==ключ присутствует в таблице). В этом случае мы дернем key.hashCode(), и первый .equals(), а второй .equals() и .getTreeNode() все так же не выполняются
  3. Попали в корзинку с несколькими парами ключ-значение, но нашли нужный нам ключ с первой же попытки — наш маршрут через код совпадает с предыдущим
  4. Наконец, мы попали в корзинку с несколькими парами, и нашли нужный ключ не с первой попытки, либо вообще его не нашли, просмотрев весь список коллизий. В этом случае мы успеем дернуть key.hashCode(), и оба .equals(), (.getTreeNode()все так же не у дел)
  5. Для редкостных неудачников: мы попали в корзинку с >8 парами ключ-значение, при общем размере таблицы >64, и обнаружили, что корзинка сконвертирована в TreeBin — тут, наконец, мы заглянем во врата ада.getTreeNode()
Из всего этого уже можно начать рисовать различные сценарии "что может пойти не так с инлайнингом (и, как следствие, скаляризацией)".

Во-первых, очевидно, у нас могут доминировать сценарии №1. В этом варианте может оказаться, что ни один из двух .equals() не набрал достаточного количества вызовов, чтобы оказаться горячим, и тогда код .equals() должен быть ну очень коротким, чтобы пролезть под порогом инлайнинга для не горячих методов (35 байт). Например, такой вот, стандартный

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 байт, и не пролезает.

Как я уже упоминал, на этот сценарий реальнее всего попасть когда большинство искомых ключей в таблице отсутствуют. В самом деле, запуская сценарий с (HashMap.size=64, hit probability=0%) мы получаем грустную историю дискриминации толстяков:

@ 84   j.u.HashMap::get (23 bytes)   inline (hot)
 \-> TypeProfile (11045/11045 counts) = java/util/HashMap
  @ 2   j.u.HashMap::hash (20 bytes)   inline (hot)
    @ 9   ...StringKey::hashCode (19 bytes)   inline (hot)
      @ 4     j.l.String::hashCode (55 bytes)   inline (hot)
      @ 14    j.l.String::hashCode (55 bytes)   inline (hot)
  @ 6   j.u.HashMap::getNode (148 bytes)   inline (hot)
    @ 59   ...StringKey::equals (55 bytes)   too big       <--- 
    @ 126  ...StringKey::equals (55 bytes)   too big       <--- 
Видно, что ни один из двух .equals() не вклеился. too big это лишь один из вариантов, я наблюдал так же и executed < MinInliningThreshold

Если мы начнем увеличивать hit probability, то очень быстро "разогреем" первый .equals(): (size=64, hit probability=1%, 2%, ... )

@ 84   j.u.HashMap::get (23 bytes)   inline (hot)
 \-> TypeProfile (11045/11045 counts) = java/util/HashMap
  @ 2   j.u.HashMap::hash (20 bytes)   inline (hot)
    @ 9   ...StringKey::hashCode (19 bytes)   inline (hot)
      @ 4     j.l.String::hashCode (55 bytes)   inline (hot)
      @ 14    j.l.String::hashCode (55 bytes)   inline (hot)
  @ 6   j.u.HashMap::getNode (148 bytes)   inline (hot)
    @ 59   ...StringKey::equals (55 bytes)   inline (hot)    <---
      @ 29     j.l.String::equals (81 bytes)   (intrinsic)
      @ 43     j.l.String::equals (81 bytes)   (intrinsic)
    @ 126  ...StringKey::equals (55 bytes)   too big         <---
Увеличивая hit probability дальше, мы в какой-то момент разогреем и второй .equals(). Точный момент указать сложно, потому что ключи каждый раз генерируются заново, и раскладка по корзинкам получается в каждом запуске немного другая (а она зависит еще и от размера таблицы...), да и сбор профиля внутри JVM — тоже не детерминированный процесс. Вот сейчас у меня получилось достичь этого при hit probability=5%:
...
@ 84   j.u.HashMap::get (23 bytes)   inline (hot)
 \-> TypeProfile (112592/112592 counts) = java/util/HashMap
  @ 2   j.u.HashMap::hash (20 bytes)   inline (hot)
    @ 9   ...StringKey::hashCode (19 bytes)   inline (hot)
      @ 4     j.l.String::hashCode (55 bytes)   inline (hot)
      @ 14    j.l.String::hashCode (55 bytes)   inline (hot)
  @ 6   j.u.HashMap::getNode (148 bytes)   inline (hot)
    @ 59   ...StringKey::equals (55 bytes)   inline (hot)   <---
      @ 29     j.l.String::equals (81 bytes)   (intrinsic)
      @ 43     j.l.String::equals (81 bytes)   (intrinsic)
    @ 126  ...StringKey::equals (55 bytes)   inline (hot)   <---
      @ 29     j.l.String::equals (81 bytes)   (intrinsic)
      @ 43     j.l.String::equals (81 bytes)   (intrinsic)
...
И да — бинго! — в этом сценарии ключи начали скаляризоваться, код больше ничего не аллоцирует.

Среди прочего, интересно заметить, что в логе компиляции .getTreeNode() вообще не упоминается. Это все потому, что соответствующая ветка вообще не используется, и JIT заменил ее на uncommon trap — большая любезность с его стороны, а то у нас были бы околонулевые шансы добиться скаляризации в этом примере хоть когда-нибудь.

До сих пор все просто и логично. Вот только я точно помню, что в каких-то старых вариантах бенчмарка наблюдал стабильную скаляризацию для всего спектра hit probability, в том числе и = 0. Как такое могло происходить?

Оказывается (это "оказывается" стоило мне нескольких часов недосыпа), я неаккуратно генерировал ключи. В генерации пула "несуществующих" ключей была ошибка, из-за которой с некоторой заметной вероятностью такие ключи все же находились в словаре — а как мы видели, достаточно небольшой примеси "найденных" ключей, чтобы разогреть холодные ветки. Но этого мало, у меня еще и сами ключи генерировались с очень плохим распределением. Точнее, отдельные-то ключи имели вполне равномерное распределение, но в пары они собирались по порядку, и вот тут-то хэш-код становился буквально кратным 32-м. Это, конечно, создавало очень неравномерное распределение по корзинкам, и длинные списки коллизий, а длинные списки коллизий еще сильнее ускоряли разогрев соответствующей ветки.

Эти же длинные списки коллизий сыграли при переходе на ключи ImmutablePair из apache commons. С ImmutablePair я наблюдал аллокацию аж 120 байт на вызов, которым, вроде, совсем неоткуда там было взяться. А все дело в том, что, в отличие от простого и дубового StringKey, навороченный ImmutablePair implements Comparable, и при превращении цепочки коллизий в дерево, HashMap это пытается использовать, чтобы сделать дерево более красивым. И вот такой код, где-то внутри .getTreeNode():

static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        if ((ts = c.getGenericInterfaces()) != null) {   // <---- 
            for (int i = 0; i < ts.length; ++i) {
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
        }
    }
    return null;
}
что он делает? Дело в том, что даже если key1 instanceof Comparable && key2 instanceof Comparable, нельзя так просто взять, и вызвать key1.compareTo(key2). Нельзя потому, что, возможно, эти Comparable промеж собой не совместимы: может, один из них Comparable<A>, а другой Comparable<B>. Процитированный код как раз пытается понять, чем конкретно параметризован этот Comparable. И вот вызов c.getGenericInterfaces() как раз и порождает загадочные 120 байт

Что получается в итоге? Получается, что успех или неуспех скаляризации зависит от раскладки ключей в хэш-таблице. Интересно что: чем ближе раскладка к идеальной (с точки зрения производительности) "один ключ на одну корзину", тем более вероятно, что ветка разрешения коллизий окажется холодной, и скаляризация не произойдет. Более того, профилирование происходит в начале исполнения кода, и после окончательной компиляции (C2) без веских причин перепрофилирования не будет, а это значит, что версия, скомпилированная по "неудачному" профилю, собранному в начале исполнения, так и будет исполняться дальше, уже независимо от актуального профиля.

P.S. Первопричина многих подобных нестабильностей в том, эвристики инлайнинга жестко заточены на производительность: мы стараемся вклеивать те методы, от вклеивания которых ожидается наибольший прирост скорости исполнения, и не рвемся вклеивать те, от которых заметного прироста не ожидаем. Это не совсем то, что нужно для скаляризации: скаляризация-то срабатывает по принципу "все или ничего": все маршруты конкретного объекта должны быть доступны для анализа, и если хотя бы один, пусть и редкий, маршрут уходит за горизонт (в невклеенный метод), то скаляризации не сможет работать. С точки зрения производительности же вклеивать редкий метод нет смысла: прирост производительности минимальный, а код раздувается. Скаляризация выступает тут бедным родственником, который вынужден довольствоваться тем, что дают: иначе было бы логично явно учитывать и ее интересы в эвристиках инлайнинга (такой EA-guided inlining предлагался, кажется, еще в Choi99).

12 августа 2016 г.

EnumSet scalarization

В эфире очередной выпуск блогопередачи "скаляризуй меня полностью". На этот раз под мою горячую руку попался EnumSet. Первое, что мне про него было интересно — это, конечно, скаляризация итератора. Ну, потому что по любой коллекции очень удобно ходить циклом foreach, но не всегда хочется за это удобство платить, пусть даже и не дорого:
public static enum Enum3 {
 FIRST,
 SECOND,
 THIRD
}

...

final EnumSet set = EnumSet.allOf( Enum3.class );

...

//benchmark start
long sum = 0;
for( final Enum e : set ) {
   sum += e.ordinal();
}
return sum;
//benchmark end
... JIT меня здесь не подвел: как и в большинстве коллекций, которые я до сих пор исследовал, итератор успешно скаляризуется. По-крайней мере, пока количество элементов в перечислении не превышает 64-х. Я не сумел сходу понять, что там такого в JumboEnumSet.EnumSetIterator-е, что смущает скаляризацию, а копать глубже мне немного лениво, потому что ДА ГОСПОДИ ИИСУСЕ КТО Ж ДЕЛАЕТ ПЕРЕЧИСЛЕНИЯ ПО 64+ ЭЛЕМЕНТОВ? Да таких случаев один на 1000, хрен с ней тогда, со скаляризацией, тут о вечном думать пора...

А вот более практичный вопрос: скаляризуется ли сам EnumSet в примере выше? То есть: если внести создание EnumSet.allOf(...) в бенчмарк — сумеет ли JIT спроецировать этот EnumSet в простой скалярный long?

Простой тест показывает, что нет. Но, конечно, гораздо интереснее понять — почему. По первости я грешил на вот этот метод:
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
   Enum[] universe = getUniverse(elementType);
   if (universe == null)
      throw new ClassCastException(elementType + " not an enum");

   if (universe.length <= 64)
      return new RegularEnumSet<>(elementType, universe);
   else
      return new JumboEnumSet<>(elementType, universe);
}
мне казалось довольно логичным, что статически предсказать ветку RegularEnumSet/JumboEnumSet невозможно, и получается уже известный сценарий с merge points. Чтобы это проверить я скопировал весь исходный код EnumSet/RegularEnumSet/JumboEnumSet из java.util к себе, и закомментировал ветку с JumboEnumSet. На удивление, это не помогло, и я пошел копать дальше. После какого-то количества промежуточных экспериментов (я уже, было, начал писать свой собственный SimpleEnumSet — чтобы, начав с крайне простого кода, потом добавлять понемногу функционал, пока скаляризация не сломается) поиск сошелся вот на чем: RegularEnumSet.EnumSetIterator это не-статический внутренний класс. В этом, казалось бы, нет ничего плохого — если только вы не слушали мой доклад на JPoint, где я уже разбирал ровно такой же случай, только на примере Arrays.asList(..)

...Оказывается, из-за загадочного бага в JIT-е, скаляризация ломается (не всегда, но часто), если на потенциально скаляризуемый объект ссылается уже скаляризованный объект. То есть EnumSetIterator успешно скаляризуется, но одно из его полей — неявная ссылка на объект родительского класса, на RegularEnumSet — застревает костью в горле у алгоритма скаляризации, когда этот алгоритм пытается скаляризовать сам RegularEnumSet. Другими словами, вот такой код
...
final EnumSet<Enum3> set = EnumSet.allOf( Enum3.class );
final boolean b = set.contains( Enum3.SECOND );
...
(без итератора) вполне успешно скаляризуется. Как и код с итератором (но без аллокации EnumSet) в самом начале статьи. Проблемы возникают когда мы эти два куска объединяем: когда мы хотим, чтобы одновременно и итератор, и сам RegularEnumSet скаляризовались. Тут нас ждет облом.

К сожалению, ситуация с EnumSet несколько хуже, чем с Arrays.asList(). В последнем случае итератор был не-статическим классом просто по недосмотру — раньше это никого не волновало. Сделать его не статическим ничего особо не стоило, никакой функциональности это не мешало. Благодаря усилиям Тагира Валеева это изменение даже было принято патчем в OpenJDK, так что в 9-ке, вероятно, Arrays.asList() будет скаляризоваться без проблем. А вот с EnumSet такое простое решение не пройдет, итератор здесь не-статический не случайно: доступ к родительскому объекту ему необходим для реализации метода remove(). Остается надеяться только на то, что JDK-8155769 когда-нибудь починят.

P.S. Удивительный факт, который остался немного за кадром: в этом коде
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
   Enum[] universe = getUniverse(elementType);
   if (universe == null)
      throw new ClassCastException(elementType + " not an enum");

   if (universe.length <= 64)
      return new RegularEnumSet<>(elementType, universe);
   else
      return new JumboEnumSet<>(elementType, universe);
}
JIT ухитряется как-то протащить реальный класс перечисления через getUniverse(..), и статически вычислить условие (universe.length <= 64)! Да они там совсем укурились в своем hotspot-dev!


P.P.S. Что меня в теме скаляризации вдохновляет сейчас: когда я начинал ее смотреть, я был готов к сценарию, что тут кромешный адъ и тьма египетская, и без знания наизусть всех кишок компилятора разобраться, или предсказать, или починить скаляризацию невозможно. А оказалось, что странности есть, но пока что все они умещаются в очень небольшой список шаблонов. То есть достаточно помнить по пальцам считанное число граблей (пусть даже не про все из них понятно, откуда они взялись), да знать ключики типа -XX:+PrintCompilation/-XX:+PrintInlining, и в большинстве случаев скаляризацию удается заставить работать, либо обозначить ключевые причины, почему она в таком коде работать и не будет. Пока, по крайней мере, все выглядит так.

30 июня 2016 г.

Tricky scalar replacement: больше-меньше

В предыдущей серии я уже писал, что такой код:
private double allocateConditionally( final ThreadLocalRandom rnd ) {
 final Vector2D v;
 if( rnd.nextBoolean() ) {
  v = new Vector2D( 1, rnd.nextDouble() );
 } else {
  v = new Vector2D( rnd.nextDouble(), 1 );
 }

 return v.length();
}
не скаляризуется — хотя интуитивно кажется, что скаляризация здесь должна быть тривиальной.

А что если немного добавить аллокаций?
private double allocateConditionally2( final ThreadLocalRandom rnd ) {
 final Vector2D result = new Vector2D();

 if( rnd.nextBoolean() ) {
  final Vector2D v = new Vector2D( 1, rnd.nextDouble() );
  result.copyFrom(v);
 } else {
  final Vector2D v = new Vector2D( rnd.nextDouble(), 1 );
  result.copyFrom(v);
 }

 return result.length();
}
В этом коде на одну точку аллокации больше — но все эти аллокации успешно скаляризуются. В общем-то, ничего особо удивительного: здесь каждая ссылочная переменная в любых сценариях исполнения всегда адресует один-единственный объект, поэтому никаких сложностей у скаляризации не возникает :)

21 июня 2016 г.

Escape Analysis & Scalarization (видео с jpoint)

Наконец-то выложили финальное обработанные записи докладов с JPoint. Среди прочих и мой доклад про Escape Analysis и скаляризацию. Кажется, получилось неплохо :)

25 марта 2016 г.

А почему бы не аллоцировать на стеке?

В самом деле: почему? Вот мы прогнали escape analysis на коде метода, обнаружили, что такие-то создаваемые объекты за пределы метода не утекают. Зачем мы их скаляризуем, почему бы нам просто не аллоцировать их на стеке? Ведь скаляризация, на первый взгляд, сложнее аллокации на стеке: отследить, какие операции с полями объектов к именно какому объекту в этот момент относятся, завести под эти поля локальные переменные, преобразовать код, чтобы он обращался к этим переменным, а не к полям объекта, приготовить задел для деоптимизации... Зачем нам весь этот геморрой, когда можно просто выделить кусок памяти на стеке, и впечатать туда объект? И мы получим полноценную ссылку на него, ничем не отличающуюся от ссылки на объект в куче. Ссылку, которую можно запихнуть в любую дырку, куда пролезет обычная ссылка (ну, слишком-то глубоко мы ее не запихаем — мы же знаем, что за пределы метода она не уйдет).

Насколько я понимаю, одного простого ответа на это "почему" нет. Более того, существовали прототипы стековой аллокации — в одной из статей по EA авторы упоминают, что их прототип делал по результатам EA именно стековую аллокацию (правда, тот прототип был на базе IBM JVM).

Но стековая аллокация не так уж проста, когда речь заходит о деталях: JVM (Oracle/Open JDK) знает, сколько памяти выделено ей под кучу — эта информация задается при запуске, и не может быть изменена. И VM этим пользуется: сразу же при старте резервирует у ОС диапазон адресов размером с максимальную кучу (не аллоцирует память, а просто резервирует адреса HEAP_START..HEAP_END = -Xmx реальная же аллокация происходит по необходимости). И с самого первого момента жизни у JVM есть эти два числа [HEAP_START..HEAP_END], между которыми должно лежать значение любого указателя на java-объект, и JVM активно полагается на то, что куча это непрерывный кусок памяти [HEAP_START..HEAP_END]. Например, эти числа можно вклеивать в генерируемый код прямо в виде констант.

Или, например, card marking. Я уже как-то писал о нем в контексте concurrency: generational GC должен как-то отслеживать ссылки между объектами разных поколений. Чтобы собрать молодое поколение, нужно знать, какие ссылки на него существуют в полях объектов старого поколения (они становятся частью root set-а). Разумеется, сканировать старое поколение целиком значит похоронить всю идею generational GC, объем сканирования нужно как-то сузить. Для этого JVM разбивает кучу на блоки-"карты" размером 512 байт, и для каждого такого блока держит однобайтовый признак "была ли в пределах этого блока запись ссылки". Каждая запись ссылки обновляет заодно и card marks: очень грубо, строчка a.f = ref из java-кода превращается примерно в
a.f = ref;
cardMarks[ (addressOf(a.f)-HEAP_START) >> 9 ] = 1
Т.е. мы записали ссылку в поле какого-то объекта, и пометили блок памяти, содержащий этот объект, как модифицированный. (Это относится только к записям ссылок — примитивные типы card marks не обновляют, потому что GC до них нет дела). Перед сборкой молодого поколения GC пройдет все модифицированные блоки, соберет из них ссылки, ведущие в молодое поколение, и добавит их в root set.

Код card marking такой простой потому, что мы заранее знаем начало кучи, какого она размера, и что она непрерывна. Поэтому нам достаточно одного-единственного массива cardMarks, и мы можем уже на старте JVM аллоцировать его нужного размера (= HEAP_SIZE / 512), сразу подо всю, даже еще не аллоцированную, кучу. Очевидно, что если теперь a в коде выше вдруг указывает на объект на стеке, то мы получим выход за границы массива cardMarks, потому что стеки потоков точно никак не попадут в зарезервированный под кучу интервал адресов. Чтобы обрабатывать ссылки на объекты в куче и объекты на стеке одновременно нужно, чтобы код card marking-а был заметно сложнее, скорее всего, содержал какие-то проверки и условные переходы. А это, на минуточку, код записи ссылки — одна из самых базовых операций, из самых часто исполняемых фрагментов кода. Типичная java-программа ссылками оперирует, пожалуй, чаще, чем примитивными типами! Получается, что немного ускорив аллокацию (точнее, де-аллокацию, сборку мусора — аллокация из TLAB в яве и так быстрее некуда) за счет использования стека мы одновременно замедлили один из самых горячих фрагментов кода — запись ссылки. Какой итоговый эффект это окажет на производительность/время отклика приложения в целом — большой и нетривиальный вопрос.

Card marking это только один из примеров того, как неожиданно непросто впихнуть стековые объекты в архитектуру JVM, годами заточенную под манипуляции объектами из кучи. Этот пример простой, но, возможно, уже не самый актуальный — как я понимаю (могу ошибаться), в G1 уже пришлось делить общий массив cardMarks на отдельные массивчики для каждого блока. Возможно, теперь уже не так уж сложно втиснуть в эту схему еще несколько "блоков" для стеков потоков. Но это не единственный такой пример, если судить по переписке в hotspot-dev:

...I tried implementing direct stack allocation in Hotspot a couple of years ago. It was a pain to try to allocate anything outside the heap - there are a lot of checks to make sure that your objects live on the heap. I ended up creating TLAB-like regions in the heap that could hold objects allocated in a stack-like way. It was a lot easier that way, and seemed to give the kinds of performance benefits you would expect. (Jeremy Manson, 01/27/14, @hotspot-dev)

— оказывается, что проще создать свой собственный "стек" с гетерами и панкратионом: откусывать от общей кучи пулы памяти на каждый поток, и использовать их для аллокации неубегающих объектов, на манер стека. И прототип реализации был написан еще два года назад. И где тот стек сейчас?..

...Я сейчас думаю, что, возможно, дело вообще не в сложности технической реализации аллокации на стеке. Дело в том, что непонятно, так ли уж это нужно. В самом деле, чтобы устранить аллокацию в куче нужно а) чтобы алгоритм EA сумел показать, что объект не утекает за границы текущей единицы компиляции б) чтобы алгоритм скаляризации сумел преобразовать все обращения к этому объекту в обращения к его скаляризованной версии. Переход от скаляризации к аллокации на стеке улучшит пункт "б" (сделает его почти 100%-ным). Сейчас, в некоторых случаях, алгоритм скаляризации может спасовать, даже если алгоритм EA и распознал локальность объекта, а с введением аллокации на стеке почти все такие случаи будут обрабатываться. Но вот много ли таких случаев? Точнее: во-первых, в каком проценте случаев скаляризация пасует сейчас, и во-вторых — какой процент от общего числа аллоцированных в программе объектов мы сможем таким образом выиграть? Я экспериментирую сейчас с различными сценариями, и складывается ощущение, что ответ на первый вопрос может быть довольно заметным — ну, скажем, сейчас мы скаляризуем 60-70% объектов, распознанных EA как неубегающие, а будем аллоцировать на стеке все 100%. А вот общий эффект для среднестатистической программы может быть скромным, если вообще заметным.

Вот недавно мне попалась (спасибо твиттеру) свежая статья, про очередной улучшенный алгоритм EA, в конце каковой статьи приведены результаты применения улучшенного алгоритма к разным бенчмаркам из наборов DeCapo и SPECjbb2005. Результат: в среднем устранено примерно ~15% аллокаций в куче. Это довольно продвинутый алгоритм EA, в паре со "стековой" аллокацией — то есть, приблизительно и ориентировочно, можно взять эти 15% аллокаций за оценку сверху возможностей используемого сейчас алгоритма EA. И переход от используемой сейчас скаляризации к какому-нибудь варианту "стековой" аллокации позволит выиграть какую-нибудь треть от этих 15%.

Каким бы совершенным не был "скаляризатор", его поле деятельности ограничено теми не-убегающими аллокациями, которые ему скормит EA. Алгоритм EA в java почти не менялся со времен 1.6. Да и чисто теоретически: возможности EA отыскать не-убегающие аллокации, в свою очередь, тоже ограничены: в пределах одного метода, даже с учетом агрессивного инлайнинга, особо не развернешься, а межпроцедурную оптимизацию JIT сейчас не выполняет. Увеличивать агрессивность инлайнинга? — Неплохой вариант, в основном потому, что дает пинок, наряду со скаляризацией, сразу целому ряду других оптимизаций. И действительно, в 1.8 многие ограничения на инлайнинг ослаблены, и я вижу, как некоторые сценарии, не скаляризовавшиеся в 1.7, в 1.8 начали скаляризоваться. Но особо далеко по этому пути тоже не пройдешь: чрезмерный инлайнинг раздувает код, и с какого-то момента это начинает уже ухудшать производительность. Получается, что существенный прирост можно получить только совершенствуя сразу и скаляризацию, и алгоритм EA, и, по-возможности, увеличивая размер единицы оптимизации, либо подключая межпроцедурную оптимизацию.

В таком рассуждении есть нюанс: когда мы пытаемся оценить профит от улучшений, прогоняя их на существующих уже программах, мы незаметно попадаем в ловушку. Существующие программы написаны с использованием существующих практик написания кода, и в этих практиках — и вообще в опыте разработчиков — уже учтены характерные особенности языка и платформы. Опытные разработчики, сознательно или бессознательно, уже оптимизируют свой код под известные сильные и слабые стороны платформы. Говоря проще: если бы было общеизвестно, что в java есть великолепный EA и скаляризатор, и что редкий временный объект имеет шанс быть аллоцированным в куче — многие программы были бы написаны сильно иначе, чем они написаны сейчас, когда общеизвестно, что да, GC довольно неплохо управляется с короткоживущими объектами, а некоторые объекты даже и скаляризуются, но не всегда, и не все, и вообще как фишка ляжет. В упомянутой выше статье, наряду с набором java-бенчмарков, был взят аналогичный набор Scala-бенчмарков (ScalaDeCapo). И разница очень заметна: (Java)DeCapo от включения EA получает бонус в -5% аллокаций, а ScalaDeCapo — в -15%. Общий прирост производительности (Java)DeCapo: +2.2%, ScalaDeCapo: +9%. В Scala другие наборы best practices, другой компилятор, другая стандартная библиотека...

22 февраля 2016 г.

Tricky scalar replacement

...Однако, насяльника, код сильно сложный, синтаксический дерево большой, корень толстый, ссылка туда гоняй, сюда гоняй, одну присвояй, другую присовояй, моя не понимать...
Допустим, у нас есть класс Vector2D, типа такого:
public static final class Vector2D {
 private double x;
 private double y;

 public Vector2D( final double x,
                  final double y ) {
  this.x = x;
  this.y = y;
 }

 public Vector2D add( final Vector2D other ) {
  return new Vector2D(
    x + other.x,
    y + other.y
  );
 }

 public void addAccumulate( final Vector2D other ) {
  x = x + other.x;
  y = y + other.y;
 }

 public double dot( final Vector2D other ) {
  return x * other.x + y * other.y;
 }

 public double length() {
  return Math.sqrt( this.dot( this ) );
 }
}
(Конкретные детали не важны, нужен класс без сложной логики и коллекций внутри)

...И мы пишем такой код:
private double allocateOnce( final ThreadLocalRandom rnd ) {
 return new Vector2D( rnd.nextDouble(), 3.8 )
  .add( new Vector2D( 1.5, 3.4 ) )
  .dot( new Vector2D( 1.9, 14.3 ) );
}
Скаляризует ли JIT эти 3 объекта?
Ответ: да, скаляризует (по крайней мере, на тестируемых мной jdk 1.7.0_25 и 1.8.0_73).

Это ожидаемо, но слишком просто. Давайте добавим немного жизни:
private double allocateInLoop( final ThreadLocalRandom rnd ) {
 final Vector2D v = new Vector2D(
  rnd.nextDouble(),
  rnd.nextDouble()
 );
 for( int i = 0; i < SIZE; i++ ) {
  final Vector2D addition = new Vector2D( i, i * 2 );
  v.addAccumulate( addition );
 }
 return v.length();
}
Здесь создается SIZE+1 объектов, SIZE из которых в теле цикла, и один проходит через цикл как аккумулятор. Что произойдет здесь?

Ответ: все эти SIZE+1 объектов успешно скаляризуются. Это уже менее ожидаемо (я лично не был уверен), и поэтому особенно приятно.

Однако это еще далеко не все, что способен измыслить опытный программист:

private double replaceInLoop( final ThreadLocalRandom rnd ) {
 Vector2D v = new Vector2D(
  rnd.nextDouble(),
  rnd.nextDouble()
 );
 for( int i = 0; i < SIZE; i++ ) {
  v = v.add( new Vector2D( 1, 2 ) );
 }
 return ( long ) v.length();
}
Здесь все так же создается 2*SIZE+1 объектов, 2*SIZE из которых в теле цикла, и один входит в цикл как начальное значение. И этот код — не скаляризуется. (Точнее, для SIZE = 1 все-таки скаляризуется — как я уже упоминал, циклы размера 1 EA как-то ухитряется разворачивать. Для SIZE > 1 аллокации скаляризуются частично: new Vector2D( 1, 2 ) в цикле скаляризуется, а вот остальные SIZE+1 аллокаций — нет.)

Это уже не очень приятно, хотя, пожалуй, ожидаемо. Не то, чтобы я ожидал такого поведения именно в этом случае, но интуитивно понятно, что чем сложнее код, тем больше шансов запутать EA.

Однако это еще не конец. Давайте уберем цикл:

private double allocateConditionally( final ThreadLocalRandom rnd ) {
 final Vector2D v;
 if( rnd.nextBoolean() ) {
  v = new Vector2D(
   1,
   rnd.nextDouble()
  );
 } else {
  v = new Vector2D(
   rnd.nextDouble(),
   1
  );
 }

 return v.length();
}
Вопрос: скаляризуется ли этот простой код? Ответ: неожиданно, но нет. Почему?

Причина вырисовывается чуть яснее, если заметить, что вот такой код

private double allocateUnConditionally( final ThreadLocalRandom rnd ) {
 final double x;
 final double y;
 if( rnd.nextBoolean() ) {
  x = 1;
  y = rnd.nextDouble();
 } else {
  x = rnd.nextDouble();
  y = 1;
 }
 final Vector2D v = new Vector2D( x, y );

 return v.length();
}
...успешно скаляризуется, ровно как и вот такой:
private double allocateUnConditionally2( final ThreadLocalRandom rnd ) {
 if( rnd.nextBoolean() ) {
  final Vector2D v = new Vector2D(
   1,
   rnd.nextDouble()
  );
  return v.length();
 } else {
  final Vector2D v = new Vector2D(
   rnd.nextDouble(),
   1
  );
  return v.length();
 }
}
Как я уже писал, после скаляризации ссылки на объект уже не остается. И поэтому алгоритм скаляризации весьма не любит, когда ссылками на потенциально скаляризуемый объект начинают жонглировать — ему приходится отслеживать, какой объект через какую ссылку в итоге окажется доступен, а это задача непростая. Однако allocateConditionally довольно тривиально преобразуется в allocateUnConditionally2, и все-таки оптимизатор оказывается не способен этого сделать...

17 февраля 2016 г.

Stack allocation vs scalar replacement

Самурай без меча подобен самураю с мечом, только без меча

Когда мы говорим об аллокации в java, регулярно всплывает тема аллокации объектов в куче против аллокации объектов на стеке. Начиная с jdk 1.6 Sun (а потом уже и Oracle) заявляет, что JIT умеет анализировать область жизни создаваемых объектов (escape analysis — "анализ убегания" как-то не очень звучит по-русски) и не выделять память в куче под те объекты, которые не покидают границ метода. Неформально об этом часто упоминают как "JIT умеет аллоцировать объекты на стеке". Официально же документация не говорит об аллокации на стеке, она говорит о скаляризации (scalar replacement). В чем разница?

Разница существенная. Объект, аллоцированный на стеке — это ровно такой же объект, как и объект, аллоцированный в куче, только на стеке. Порядок полей, выравнивание, системные поля, типа _vtable в C++ или object header в яве — все это должно быть одинаковым в обоих вариантах аллокации, иметь один и тот же размер и смещения. Почему? Потому что если мы возьмем ссылку/указатель на объект на стеке, и такой же объект в куче, то доступ к полям объекта через эти ссылки не должен зависеть от того, где объект аллоцирован. Или необходимо будет вводить признак "где объект расположен", и каждый доступ к каждому полю объекта будет тогда идти через дополнительные проверки типа расположения, и выбор соответствующего смещения.

Это аллокация на стеке. Которой в джаве нет — ни явной, ни автоматической. А есть (автоматическая) скаляризация. Скаляризация (scalar replacement) — это превращение объекта в набор полей (т.е. скалярных значений), которые раскладываются в локальные переменные текущего метода. Вместо того, чтобы выделять на стеке память под v = Vector2D(double x, double y) — мы просто добавляем в список локальных переменных метода double v$x, double v$y, и все обращения к v.x/v.y перенаправляем к ним. Объект как целое исчезает, появляется россыпь независимых полей, спроецированных на локальные переменные.

Чем это круче? Тем, что компилятору не нужно соблюдать порядок полей. Скаляризованные поля объекта уже не обязаны идти подряд, в фиксированном порядке — компилятор может разложить их в свободные слоты на стеке как ему удобно. Может использовать один слот под несколько переменных, если их области использования не пересекаются. Если у компилятора достаточно свободных регистров — он может вообще не выделять под эти поля слоты на стеке. Более того, компилятор может вообще выкинуть какие-то поля, если обнаружит, что в данном методе они не используются. (Если у Vector2D есть поле для хранения hashCode, на манер String, но в данном методе никто у вектора хэшкод не спрашивает, то и поле создавать не нужно). Короче говоря, весь спектр оптимизаций, применимых к компоновке локальных переменных, теперь применим и к скаляризованным полям.

Недостаток же у скаляризации один: раз объекта больше нет, то и ссылку на него тоже не получишь, а значит никуда за пределы текущего метода объект по ссылке передать не получится. То есть скаляризация работает если объект достижим исключительно в пределах одного метода. Поэтому в джаве напрашивается именно скаляризация: ведь мы начинаем с того, что доказываем, что ссылка на объект никуда за пределы метода не уходит (escape analysis), и только тогда пытаемся устранить аллокацию в куче. Раз уж мы все равно знаем, что ссылка на объект нам не понадобится — то почему бы не получить заодно бонусы скаляризации?

2 февраля 2016 г.

Массовые расстрелы и духовная практика смирения


— Микола, ты слыхал как профессиональные программисты тм наш newValue кличут?
— Не, а как?
— "о"!
— Да ну! Вот же ж нелюди, поубивал бы гадов!

Разбирался сегодня в одном из наших сервисов, который использует довольно старую версию trove (2.1.0)

Цитата из THashMap.Entry.setValue():
public V setValue(V o) {
    if (_values[index] != val) {
        throw new ConcurrentModificationException();
    }
    _values[index] = o;
    o = val; // need to return previous value
    val = o; // update this entry's value, in case setValue is called again
 
    return o;
}
Возьмите себе минуту времени на то, чтобы найти в нем ошибку.

Нашли?

Теперь так (o -> newValue):
public V setValue(V newValue) {
    if (_values[index] != val) {
        throw new ConcurrentModificationException();
    }
    _values[index] = newValue;
    newValue = val; // need to return previous value
    val = newValue; // update this entry's value, in case setValue is called again
 
    return newValue;
}
Стало очевиднее?

Возможно, что нет.

Тогда еще одна попытка (+final):
public V setValue(final V newValue) {
    if (_values[index] != val) {
        throw new ConcurrentModificationException();
    }
    _values[index] = newValue;
    newValue = val; // need to return previous value
    val = newValue; // update this entry's value, in case setValue is called again
 
    return newValue;
}
... упс, так написать нельзя – будет ошибка компиляции при присвоении значения
final переменной. Придется завести еще одну переменную (внимательный читатель
заметил, что заодно мы уже вынуждены исправить одну из ошибок – в .val
записывалось ее же старое значение, вместо нового):

public V setValue(final V newValue) {
    if (_values[index] != val) {
        throw new ConcurrentModificationException();
    }
    _values[index] = newValue;
    final V oldValue = val; // need to return previous value
    val = newValue; // update this entry's value, in case setValue is called again
 
    return newValue;
}
...Странно: мы хотим вернуть из метода старое значение, а возвращаем – новое.
Что-то здесь не так. Исправим:
public V setValue(final V newValue) {
    if (_values[index] != val) {
        throw new ConcurrentModificationException();
    }
    _values[index] = newValue;
    final V oldValue = val; // need to return previous value
    val = newValue; // update this entry's value, in case setValue is called again
 
    return oldValue;
}
Итого: 2 ошибки (!) в коде из 7 строчек. Совсем не очевидные в исходном варианте (я лично потратил несколько минут).

А чтобы эти ошибки стали очевидны (и, скорее всего, даже и не попали бы в репозиторий) достаточно было бы:
  1. объявить все локальные переменные и аргументы методов final
  2. назвать переменные своими именами
  3. не переиспользовать локальные переменные, а заводить новые (смотри так же пункт 2)
тогда на одну из этих ошибок укажет компилятор, а вторая становится достаточно очевидной глазу (Куда уж очевиднее: " – Что мы хотим сделать? – Вернуть старое значение. – А что написано? – return newValue")

Конечно, после драки завсегда легко кулаками помахать. Мне-то на исходную ошибку вообще указал findbugs (справедливости ради, я и не собирался ревьювить код trove). Однако в моей практике я регулярно сталкиваюсь с тем, что достаточно выполнить эти 3 пункта, и запутанные методы становятся понятными, а глупые ошибки начинают бросаться в глаза. Почему люди так не делают? Это третий величайший вопрос на свете после "откуда пыль берется" и "куда деньги деваются".


Когда я сталкиваюсь с подобными сценариями, у меня создается твердое ощущение, что многие программисты всерьез считают свой мозг самым крутым компьютером на свете. Типа – раз я управляю этим примитивным кремниевым i7, значит я умнее его. И поэтому я даже не буду предполагать, что мой мозг может запутаться в 7 строчках кода с 3 переменными – да ну, это невозможно, я же профессионал, я в такой ерунде не ошибаюсь. И зачем я буду помогать себе, выбирая осмысленные имена для переменных? Это для слабаков, настоящие профессионалы не нуждаются в таких костылях.

...Человеческий мозг может быть и превосходит по мощности – формально – любой существующий суперкомпьютер. Вот только у любого вычислителя есть сильные и слабые стороны, и слабенький DSP умножает матрицы в сотню раз быстрее, чем человеческий мозг. Математика, логика, синтаксический разбор, анализ потоков данных и синтаксических деревьев, программирование (в том виде, в котором мы его сейчас знаем) – не относятся к сильным сторонам человеческого мозга. Даже близко не относятся. То, что мы можем (лет за 5-10-20 ежедневного опыта) научить свой мозг как-то все это делать – вовсе не означает, что мозг делает это хорошо. Мозг не делает это хорошо, и никогда не будет, просто (пока) никто не делает это лучше, поэтому мы вынуждены решать эти задачи используя такой неподходящий биологический компьютер. Я, может, неожиданную мысль скажу, но никто в мире не программирует хорошо. Хорошо работает компилятор: javac на моем компьютере распарсит и скомпилирует несколько тысяч файлов за пару десятков секунд без единой ошибки – вот это хорошая работа. Кто может похвастаться, что превратил несколько тысяч страниц бизнес-спецификации в код без единой ошибки хотя бы за неделю? Хоть раз в жизни? Никто таким не может похвастаться, нет таких людей. Никто из нас не программирует хорошо, по 5-бальной шкале мы все в пределах тысячных долей от нуля. Мы занимаемся этим только и исключительно потому, что компилятора не формализованных бизнес-спецификаций пока не придумали.

К чему это я? К тому, что, раз уж эта работа для мозга сложная, то необходимо использовать любые способы помочь мозгу делать эту сложную работу, к которой он совершенно не подготовлен эволюционно. Любые способы как-то подключить сильные стороны мозга к решению столь непрофильных задач. Давая же бессмысленные имена переменным, переиспользуя их где ни попадя – я усложняю мозгу и без того сложную задачу.


...Только массовые расстрелы регулярная практика смирения спасет IT-отрасль. Ежеутренняя получасовая медитация, прямо перед стэндапом: "Я обычный человек, мой мозг слаб, грешен, и подвержен ошибкам. Мой мозг не способен надежно оперировать более чем 3-4 единицами информации одновременно. Мой мозг нуждается в подсказках. Никто не способен писать код без ошибок, и я тоже не способен. Даже если очень стараюсь – в моем коде есть ошибки. Моя задача – сделать мои ошибки очевидными любому, кто читает мой код..."

P.S. На всякий случай: в какой-то версии trove старше 2.1.0 эта ошибка была исправлена. Я не смог отследить, в какой именно: в старом CVS репозитории ошибка присутствует везде, в "новом" SVN репозитории ее нет.