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 репозитории ее нет.

27 сентября 2015 г.

Joker 2015

Еду в Питер 16-17 октября, на Джокер. Будет Шипилев, Паньгин, будет Мартин Томпсон (это который автор дизраптора и Aeron) — аж с двумя докладами (правда, про Аэрон не будет рассказывать, а жаль). А 18 числа будет University day — тот же Джокер, но для студентов, как я это понял. Но я уже не останусь, годы не те...

20 сентября 2015 г.

Немного тервера


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

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

Такое гадание на кофейной гуще заставляет меня немного кривить лицо, так что в какой-то момент я решил призвать на помощь математику, и прояснить для себя, можно ли сделать оценки не с потолка, и какие. Сколько времени достаточно ждать, чтобы сделать вывод о потере доступности удаленной системы с такой-то степенью достоверности?

Начал я с самой простой (==легко формализуемой) ситуации — когда данные отправляются источником через равные (и известные) интервалы времени. Это соответствует сценарию отправки пульса (heartbeats). Самая первая статистическая модель, которая приходит в голову, выглядит так: с интервалом времени $$T_h$$ к нам в систему отправляют хартбиты. Как всегда, на длинном пути от теории к практике находится большое число разных помех, каждая из которых норовит отклонить реальный период получения от идеального платоновского T. Поэтому приход хартбита мы можем моделировать как случайное событие. Если в момент T=0 мы наблюдали это случайное событие (==получили хартбит), то время возникновения следующего такого события — случайная величина. Как она распределена мы точно не знаем, но в качестве гипотезы первого порядка мы можем принять, что интервал интервал между хартбитами распределен по Гауссу, со средним значением равным $$T_h$$, и какой-то там дисперсией $$\sigma_h$$

Но иногда в системе отправки и доставки хартбитов происходят неисправности. Неисправность — это когда что-то случилось с отправляющей системой, или с сетью, или с нашим сетевым стеком, или еще где — но очередного хартбита нет, и не будет. Неисправности тоже случайные события. Как они распределены во времени нам тоже априори не известно, но в качестве гипотезы первого порядка мы можем принять, что они возникают случайно, независимо и равномерно, в среднем раз в $$T_f$$ — то есть вероятность события неисправности на малом интервале $$[t..t+dt]$$ равна просто $${dt \over T_f}$$.

Тогда, если на принимающей стороне с момента получения последнего хартбита прошло уже время T, а очередного хартбита мы все еще не наблюдаем, то это могло произойти по двум (предположительно, независимым) причинам:
  1. или хартбит еще не пришел (нам просто в этот раз так повезло, и из случайного распределения интервалов между хартбитами нам в этот раз выпало какое-то значение, бОльшее чем T)
  2. или отправляющая система уже сдохла (на отрезке [0..T] произошла неисправность)
Нам нужно как раз понять, с какой вероятностью истинным объяснением задержки будет №2. Несложно видеть, что это будет условная вероятность неисправности при отсутствии хартбита к моменту T: P(неисправность где-то на [0..T] | хартбит не получен в течении T)

$$ = \frac{P(failure \in [0..T])}{P(T_{hb} > T)+P(failure \in [0..T])} = \frac{P(2)}{P(1)+P(2)}$$

То есть нам нужно посчитать две вероятности: вероятность того, что очередной интервал между хартбитами будет >T “сам по себе” (т.е. только из-за случайных задержек), и вероятность того, что на отрезке [0..T] произошла неисправность.

Какова вероятность того, что неисправность случилась на отрезке [0..T]? Проще считать от обратного: вероятность того, что неисправность случилась на отрезке длиной dt равна $$\frac{dt}{T_f}$$. Вероятность того, что неисправность там не случилась $$1 - \frac{dt}{T_f}$$. Вероятность того, что неисправность не случилась нигде на отрезке [0..T] $$ = \left(1-\frac{dt}{T_f}\right)^\frac{T}{dt} \rightarrow e^{-\frac{T}{T_f}}$$, вероятность того, что неисправность случилась хоть где-то на отрезке [0..T] хоть раз $$1 - e^{-\frac{T}{T_f}}$$ (узнавшие пуассоновский процесс эту формулу могли просто вспомнитьподсмотреть в википедии, но я люблю повыпендриваться)

Какова вероятность того, что интервал между хартбитами (нормально распределенная случайная величина $$N_{T_h,\sigma}$$) случайно окажется > T сам по себе? Эта вероятность равна

$$\int\limits_{T}^{\infty}{N_{T_h,\sigma}(t) \, dt = 1-\int\limits_{-\infty}^{T}{ \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(t-T_h)^2}{2\sigma^2}} \, dt} = \frac{1}{2}erfc\left( \frac{T_h-T}{\sqrt{2}\sigma} \right) = Q\left( \frac{T-T_h}{\sigma} \right)$$

($$Q(x)$$ это объем хвоста нормального распределения от x и до беспредельности. В русских источниках я такое обозначение не встречал, но здесь мне оно оказалось очень к месту, поэтому дальше буду им пользоваться) Дальше все просто: формулы подставляем в формулы, и получаем уравнение, в котором P(2) выступает в роли задаваемого параметра (какую степень достоверности определения сбоев желаете: 90%, 95%, 99.99%?), а T — тем самым таймаутом, который позволит обеспечить нужную степень достоверности.

Вот что получается в итоге ($$x = \frac{T-T_h}{\sigma}$$, другими словами — сколько стандартных отклонений от среднего):

$$\frac{1 - \frac{1}{2} erfc\left(-\frac{x}{\sqrt{2}}\right)}{1 - e^{\frac{- (T_h+\sigma\,x)}{T_f}}} = \left(\frac{1}{P}-1\right)$$

На этом месте я несколько застопорился: в элементарных функциях это уравнение не решается, и даже после пары упрощений-приближений не решается все равно. В числах легко решается любой системой компьютерной математики, но хочется же понять сам вид зависимости $$T = f(T_h, T_f, \sigma, P)$$, хотя бы в приближенном, асимптотическом виде. Поигравшись с неделю с численными решениями и графиками я нашел, что с этим можно сделать.

Идея выглядит так: если мы преобразуем это уравнение к виду $$x = f(x)$$, подходящему для метода итераций, то легко показать, что $$f(x)$$ здесь будет иметь очень маленькую производную (при тех значениях параметров, которые нам интересны — $$ T_h, \sigma << T_f$$). А метод простых итераций сходится (если сходится) примерно со скоростью $$|x_n-x| \leq |f(\xi)'|^k|x_0-x| $$. То есть, имея достаточно малую производную $$f(\xi)' < 10^{-3}-10^{-6}$$ можно сделать вообще одну-единственную итерацию, и получить вполне пристойное приближение вида $$x = f(x_0=1)$$. По-сути это формализация примитивного метода последовательных приближений: какова вероятность возникновения неисправности на одном периоде между хартбитами? А насколько должен задержаться хартбит, чтобы вероятность его случайной задержки стала меньше, чем эта вероятность неисправности? — мы могли бы повторить эту процедуру несколько раз, но оказывается, что уже на первом же шаге мы уже почти сойдемся, потому что хвост нормального распределения убывает очень быстро, а распределение Пуассона "набирает вес" гораздо медленнее. Этого все еще недостаточно, потому что $$f(x)$$ здесь все равно получается невыразимая в элементарных функциях, поэтому придется использовать известные асимптотические ограничения на объем хвоста нормального распределения $$Q(x) < e^{-x^2/2}$$. В конечном счете, получается такое приближенное решение:



$$x \simeq \sqrt{ 2\,ln\left( 2\left(\frac{P}{1-P}\right)\frac{T_f}{T_h+\sigma} \right) }$$

Здесь уже достаточно ясно видно, что x зависит от параметров очень слабо — изменение аргументов в пределах 6 порядков изменяет результат в пределах 20-25 процентов (ну еще бы, корень, да из логарифма) При разумных значениях параметров получим x = 4-8. То есть в первом приближении можно просто брать таймаут $$T = T_h + 6..8\sigma$$, и не заморачиваться.

...Еще раз, что у нас получилось: в числителе у нас стоит вес (вероятность) хвоста распределения вероятности последовательных времен прихода данных $$P_{data}(t > T)$$. В знаменателе же "голова" (ну, что у нас с другой стороны от хвоста?) распределения вероятностей времен возникновения неисправностей $$P_f(t < T)$$.

По мере того, как мы двигаем T вправо, голова у нас тяжелеет (вероятность возникновения неисправности на интервале растет по мере роста интервала), и стремится к 1, а хвост тает, и стремится к 0 — поэтому в какой-то момент голова обязательно станет тяжелее хвоста в любое заданное число раз. То есть это уравнение всегда имеет решение. Можно подставлять сюда разные распределения, и смотреть что получится — но вряд ли это будет проще, чем с нормальным распределением.

А вот можем ли мы сказать что-то про решение без предположений о конкретном виде распределения интервалов между данными? Ну, для большого класса распределений с легкими хвостами верна оценка $$P([x-|x|] \geq k*\sigma) \leq exp(-x^2/2)$$ — та самая, которую мы уже использовали для нормального распределения, так что полученный ответ можно считать подходящим и для распределений похожих на нормальное.

С другой стороны, самая общая оценка, верная вообще для любого распределения с конечным средним и дисперсией — это неравенство Чебышева $$P\Big(\frac{x-|x|}{\sigma} \geq k\Big) \leq \frac{1}{k^2}$$

Используя его можно получить такую оценку
$$\frac{1}{x^2} \geq \Big(\frac{1}{P}-1\Big)\frac{T_h + \sigma x}{T_f} \rightarrow x \leq \sqrt{ \frac{P}{1-P} \frac{T_f}{T_h+\sigma x} } \rightarrow x \leq \sqrt{ \frac{P}{1-P} \frac{T_f}{T_h} }$$
Как видно, общий вид зависимости похож (убывающий хвост), но числа здесь уже совсем других порядков: вместо единиц при характерных значениях параметров получаются десятки тысяч (в единицах стандартных отклонений). Ну, неравенство Чебышева это самая общая оценка, которая только возможна в тервере, так что ничего удивительного в его расплывчатости нет. Но, увы, это означает, что хорошую, удобную оценку мы получаем лишь для более-менее периодических сигналов. Если вместо хартбитов мы возьмем какие-то обновления данных, то распределение их по времени легко может оказаться совсем не гауссовским, и иметь тяжелый хвост, и большую дисперсию. И тогда таймаут придется брать весьма не маленьким. Собственно, как я понимаю, это и есть математическое обоснование тому, зачем добавлять в потоки данных еще и хартбиты.

10 августа 2015 г.

Left-Right

Пару лет назад ребята из concurrency freaks опубликовали в c-i описание интересного алгоритма управления конкурентным доступом к произвольной структуре данных. Они назвали этот алгоритм Left-Right, и утверждали, что он позволяет реализовать blocking writes, но зато аж wait-free (population oblivios) reads. При этом писатели не блокируют читателей, хотя читатели блокируют писателей (но не блокируют друг друга). Это довольно-таки неплохой набор свойств, особенно учитывая, что защищаемя структура данных может быть любой. Сценарий с редко обновляемой, зато часто читаемой структурой данных очень типичен, и обычно в нем используется что-то вроде CopyOnWrite — очень простой и надежный алгоритм, но требующий аллокации. Здесь же аллокаций после инициализации нет вообще (в самом алгоритме — если защищаемая структура данных нуждается в аллокациях при выполнении над ней каких-то операций, то эти аллокации, конечно, никуда не исчезнут). Тогда у меня не дошли руки описать их алгоритм, зато дошли сейчас :)

Идея алгоритма (статья в pdf) довольно простая: мы заводим две копии (left & right) нужной нам структуры данных. Одна из копий всегда открыта для чтения, вторая, соответственно, спрятана от читателей. Поток, желающий выполнить операцию чтения должен просто определить, какая из копий открыта, и читать ее. Пишущий же поток захватывает глобальный монитор, и сначала модифицирует скрытую копию. Выполнив запись над скрытой копией писатель делает ее открытой для чтения, а бывшую открытую — скрывает, и повторяет свою запись теперь уже над ней. В итоге одна копия всегда свободна от записей, и ее можно безопасно читать, и одна копия всегда свобода от чтения, и ее можно безопасно модифицировать (под блокировкой, конечно — чтобы не конфликтовать с другими писателями), и после каждой операции записи копии меняются ролями.

Идея простая, но в реализации есть тонкости. Одномоментно сменить открытую копию просто — достаточно обычной volatile ссылки/индекса (и даже не нужно CAS-а, потому что запись и так происходит под блокировкой, и обновлять этот указатель может только один поток в каждый момент времени). Но после того, как мы перенаправили эту ссылку, и бывшая открытая копия стала закрытой — мы пока еще не можем утверждать, что нынешнюю закрытую копию никто не читает, ведь это только новые читатели пойдут по обновленной ссылке, а старые, которые начали чтение до смены ролей, все еще читают копию, которая сейчас уже закрыта. Значит, нам нужен какой-то механизм, позволяющий дождаться, пока все эти старички закончат читать. То есть нужно, чтобы потоки-читатели где-то отмечались “я сейчас читаю копию номер 1”, и чтобы писатель мог спросить “а есть ли хоть кто-то, кто читает копию номер 1?"

Реализация этого механизма регистрации читателей — это ключевая вещь в Left-Right, потому что от его эффективности и progress conditions прямо зависит эффективность и progress condition операций чтения — а неждущие чтения это, пожалуй, основная заявка всего алгоритма. В самом простейшем случае можно просто завести readersCount:AtomicInteger на каждую копию, и каждый читатель будет делать readersCount.incrementAndGet() перед началом чтения, и .decrementAndGet() после окончания, и если readersCount.get() == 0 значит активных читателей не осталось. Этот способ регистрации читателей самый простой, и самый компактный по памяти — но он мягко говоря не очень хорошо масштабируется с увеличением количества читателей, ведь все читатели будут конкурировать за обновление одного участка памяти (true sharing).

Ситуацию можно улучшить, если начать дробить единый счетчик на несколько более мелких: каждый поток-читатель приписан к какому-то суб-счетчику (не обязательно навсегда к одному и тому же, кстати), и инкрементит/декрементит его, а поток-писатель должен тогда будет обойти все суб-счетчики, и просуммировать их значения, чтобы получить итоговую сумму (отдельные суб-счетчики, конечно, нужно хорошенько изолировать друг от друга padding-ом, чтобы не налететь сходу теперь уже на false sharing). В пределе, если на каждый поток-читатель выделить свой собственный суб-счетчик, мы получим полное отсутствие конкуренции за запись (технически нужно еще обеспокоиться еще отсутствием false sharing) — по-сути записи будут чисто локальными для каждого из потоков, и тогда даже CAS/atomicAdd нам не нужно, мы можем обновлять волатильный локальный счетчик обычным инкрементом/декрементом (очень изящную реализацию на базе односвязного списка, слабых ссылок, и thread local-ов можно посмотреть здесь). И значит мы получим-таки заявленное свойство wait-free population oblivios. По цене ~64+ байт на каждый читающий поток (padding + сам счетчик + дополнительные поля — и не забываем, что пишущий поток еще будет обязан все эти локальные счетчики обойти и просуммировать)

(Небезызвестный LongAdder из последних версий jdk использует похожий подход, но он всего лишь lock-free. Почему? Потому что пытается балансировать между скоростью и потреблением памяти — если на каждый поток сразу по 64+ байт выделять — никакого кэша не хватит. Так что LongAdder подстраивает количество счетчиков под реальную нагрузку — он начинает с одного счетчика (общего для всех потоков), который обновляется через CAS. Если неудачных CAS-ов становится много — это значит, что за счетчик идет слишком большая конкуренция, и LongAdder увеличивает количество суб-счетчиков, стараясь равномерно распределять потоки между ними. Покуда неудачных CAS-ов все еще много — количество счетчиков еще увеличивается, пока их не окажется столько, чтобы за каждый конкретный счетчик конкуренция была ниже некого предела. Очень изящное, эффективное, и гораздо более универсальное решение — но вся эта машинерия динамической перестройки, увы, уже не вписывается в wait-free)

(Любопытная деталь: чтобы получить конкурентный алгоритм с наиболее “хорошими” свойствами для читателей, в ущерб писателям, нам оказывается нужен, в качестве строительного блока, алгоритм счетчика с наиболее “хорошими” свойствами для писателей, в ущерб читателям)

Довольно очевидно, что алгоритм близок идейно к CopyOnWrite, только в CoW количество копий не ограничено, а за количеством читателей следит GC — пока на какую-то из копий хоть из одного потока есть ссылка, эта копия считается занятой, как только ни одной ссылки не остается — копию подбирает GC, и ее память заново можно использовать для аллокации. За эту простоту приходится платить — алгоритмы определения достижимости у GC обходятся гораздо дороже по CPU, чем смена читаемой копии в LR, да к тому же теряется детерминированность. Плюс вместо дублирования одной конкретной записи мы вынуждены при реаллокации копировать все содержимое структуры данных целиком.

Что в алгоритме LR еще интересного? Интересно то, что его основной недостаток — блокировка для писателей — не актуален, если писатель у нас один. Поскольку блокировка нужна только для разруливания конфликтов между писателями, то в случае одного писателя ее можно просто выкинуть. И мы получаем алгоритм с wait-free писателем, и wait-free (или lock-free если мы пожадничаем на память для счетчиков) читателями. Хотя стоп, писателю же все равно придется ждать завершения всех чтений? Да, никакого wait-free не получится, писатель все равно остается блокирующимся, просто монитор захватывать в этом случае не нужно.

Второй интересный аспект это пакетная запись. Если нам не принципиально предоставлять читателям свежую версию максимально быстро — мы можем переключать копии между открытой на закрытой не после каждой записи, а, скажем, после какого-то их числа, или по явной команде, типа commit/flush. И тогда высокая стоимость записей может быть амортизирована на всю пачку. В том числе и блокировку можно брать лишь однажды и на всю пачку (или вообще не брать — если писатель один-единственный). От необходимости выполнять каждую запись дважды это нас не избавит, но все остальные накладные расходы можно сильно размазать.

Третья идея — а что, если копий сделать больше одной? В пределе неограниченного количества копий мы приходим к классическому CopyOnWrite + GC, но что если копий все-таки ограниченное количество? В оригинальной статье этот вариант не рассматривается, но насколько я вижу, это вполне можно реализовать. Здесь есть интересный вариант: мы можем, как и в оригинальном LR применять каждую запись N раз, к каждой копии. А можем вместо этого при модификации копировать все содержимое самой свежей копии (текущей читаемой) в самую старую (будущую читаемую), и применять текущую запись уже поверх. (Очевидно, что при большом N этот способ рано или поздно станет более эффективным).

То, что у нас здесь получится — это натуральный CopyOnWrite, только без аллокации и GC, и с ограниченным набором копий. В чем его потенциальные преимущества? По сравнению с обычным CoW нет постоянной реаллокации (но все же есть копирование). А вот по сравнению с LR преимущество в том, что для выполнения записи нам не нужно дожидаться завершения всех чтений над только-что-переставшей-быть-открытой копией — потому что сейчас нам в нее ничего писать не нужно. Пишем (копируем свежее состояние + применяем текущую запись) мы в самую последнюю (самую дальнюю от текущей) копию, и именно она должна быть свободна от читателей. Но поскольку эта дальняя копия была открытой для чтения уже довольно давно, то вероятность, что ее все еще кто-то читает (т.е. есть кого ждать) довольно мала, и ее можно уменьшать далее увеличивая количество копий.

Мы получаем такую версионную структуру данных, которая одновременно содержит черты CoW, кольцевого буфера (ну, потому что копии организованы натурально в виде кольцевого буфера), и LR. Без аллокаций, с wait-free чтением (если не жалко по 64+ байт кэша на каждый читающий поток потратить), и с блокирующейся записью — но при этом вероятность ожидания на записи можно регулировать увеличивая количество копий. Интересная штука, правда, очень сложно поверить, что эту структуру данных еще никто не придумал :)

14 марта 2014 г.

JPoint 2014

Кстати, если кто еще не в курсе: jpoint 2014 будет в Москве. 18 апреля в Radisson Славянская. В этом году я там как участник, а не докладчик, но там и без меня хорошо: Роман будет рассказывать теорию моделей памяти, а Глеб распускать кишки HotSpot и показывать как оно там все реализовано. Из остальных уже заявленных докладов я лично собираюсь послушать Паньгина (про расследование heap dump он уже не первый раз рассказывает, но я не попадал), Бреслава про дизайн языков программирования, и Дударева про уязвимости нулевого дня. (Не так давно на хабре была переводная статья, где автор жаловался, что никто из джава-экспертов не умеет валить JVM -- надеюсь, Михаил меня научит, а то стыдно как-то). Ну, там еще расписание смотреть надо будет...

4 февраля 2014 г.

How fast the logger could be?

В начале декабря у нас тут случилась своя маленькая и уютненькая внутренняя конференция, на которой я рассказывал про быстрое логгирование. Поскольку конференция внутренняя, часть информации под NDA, так что просто выложить презентацию я не могу, но общие моменты попробую описать.

Задача взялась вполне себе из практики: есть приложение, которое зарабатывает бабло наносит пользу человечеству. У этого приложения есть legacy-версия, которая уж сколько-то лет в работе, и есть новая, с 0 переписанная (в основном мной) версия, которая сейчас готовится ее сменить на боевом посту. Разумеется, возникает масса вопросов вида "а почему вот в новой версии у этой транзакции результат чуть не такой, как в старой?". И приходится много времени шароебиться по логам, выясняя, как и что происходило. И, конечно, регулярно думаешь, что вот если бы еще здесь, здесь, и вот здесь дополнительно ключевые параметры сбрасывать в лог, то расследование было бы в разы быстрее и проще.

Казалось бы, в чем проблема-то? Проблема в том, что заказанное среднее время обработки транзакции в приложении <100us (мы пока до него не дотягиваем, но стараемся). В этих условиях приходится быть довольно экономным. Примерная стоимость вызова log4j.info() в асинхронном режиме где-то 5мкс — особо не разбежишься. Новая версия приложения давно уже использует gflogger как основной инструмент для логгирования, но даже здесь стоимость вызова примерно 1мкс, что, конечно, гораздо лучше, но все-таки еще многовато. Хочется же уместить 30-100 вызовов логгера в <10us (т.е. <10% целевого времени ответа). Другими словами, мне нужно решение для логгирования, которое требует 100-300нс/запись. Так вот, вопрос — можно ли так сделать?

В принципе, примерный маршрут виден: многие вещи уже обкатаны Володей при разработке gflogger-а. Garbage-free API, GC-free реализация с преаллоцированными буферами — все это себя вполне хорошо зарекомендовало. Но gflogger все-таки делался по принципу "возьмем log4j, отрежем весь явно лишний функционал, а так же еще что под руку попадется, и реализуем остальное". Большое преимущество такого подхода "сверху вниз" — короткий путь "до рынка": тот же gflogger начали использовать уже через пару месяцев после начала его разработки. Недостаток же в том, что в большой системе с обширным функционалом довольно сложно понять, кто какой вклад в производительность вносит. Просто-напросто слишком много вариантов того, что можно убрать/добавить/сделать иначе. Поэтому лично я предпочитаю вести ОКР в обратном направлении, снизу вверх — от примитивов, шаг за шагом собирая нужный мне комплект функционала, с постоянным бенчмаркингом. Чудеса случаются и здесь, но в целом, мне кажется, такой маршрут дает гораздо более понятную картину.

Собственно, так я здесь и сделал: поставил себе задачу собрать асинхронный логгер с gflogger-like API, на базе кольцевого буфера, с записью в один-единственный файл. Вообще-то, до записи как раз руки и не дошли, потому что меня больше интересовала не пропускная способность (по всем прикидкам она более чем достаточна для моих целей), а накладные расходы рабочих потоков, т.е. время вызова log.message(...).

Что получилось: удалось добиться ~150ns/message в 4-х поточном случае.

Что использовал и на какие компромиссы пришлось пойти:
  • Multi-threaded claiming: я рассказывал про это еще полтора года назад на jug-е: можно сильно улучшить масштабирование, и, что еще важнее, уменьшить простои потоков (т.е. приблизить к wait-free) если вместо общего на всех курсора publishedSequence использовать флаг в каждой конкретной записи.
  • Только примитивные аргументы. Во-первых это в целом упростило API. Во-вторых с примитивными аргументами можно заранее вычислить нужный размер записи. Без этого пришлось бы либо выделять по-максимуму, с запасом, либо сначала писать все во временный буфер, а потом копировать в основной.
  • Компактное представление записи: я не форматирую сообщение прямо в рабочем потоке, я пишу в буфер непосредственно messageId+arguments Во-первых, это гораздо компактнее, чем готовое сообщение (чаще всего, но не всегда — нашел у себя в проекте пару изощренных контрпримеров), а размер сообщения сильно влияет на время записи. А во-вторых, снимает с рабочих потоков задачу форматирования. Разумеется, это так легко и эффективно получилось только вкупе с предыдущим пунктом — если добавлять кроме примитивов хотя бы даже строки, подозреваю, эффективность заметно упадет.
  • Вариабельный размер записи. Это интересная тема, про которую меня регулярно спрашивали в контексте дизраптора и кольцевых буферов вообще. На пальцах казалось, что ничего принципиально сложного нет, но случая проверить до сих пор не выпадало. На первый взгляд непонятно, зачем это здесь, но я прицеливался в то, чтобы на каком-то этапе в будущем можно было использовать в качестве буфера memory-mapped file, и тогда оставлять много пустых мест кажется плохой идеей. Исходя из этой задумки я и решил, что вот он мой шанс наконец-то попробовать. Реализовывать эту штуку было очень интересно, но возникает много тонкостей. В целом мой вывод: для себя интересно, но если нет реальной необходимости, на работе лучше не заморачиваться и использовать записи фиксированного размера, гораздо проще выходит

На чем в основном тратим время? Вполне предсказуемо: где-то 2/3 времени примерно поровну делят между собой addAndGet на выделении записи и собственно запись данных в буфер. Остальная треть приходится на все остальное, типа thread local-ов и прочих накладных расходов. В принципе, у меня есть идея как несколько ускорить выделение записей, но надо еще думать.

Проект лежит здесь вместе со всеми бенчмарками. На всякий случай еще раз уточняю: это не рабочий код, и даже не альфа-версия, это экспериментальный код с бенчмарками. В лучшем случае тянет на прототип.

19 июля 2013 г.

Data races is pure evil

Nondeterminism is unavoidable, but data races are pure evil (by Hans Boehm) -- любопытная статья, которая висит у меня в закладках несколько месяцев.

Ханс пишет про то, что многие люди пытаются уйти от синхронизации к data race based протоколам во имя увеличения масштабируемости (scalability). И это совершенно не оправдано — мало того, что код с гонками получается ошибочным в 9 случаях из 10, так еще и надежды на масштабируемость — это, по большей части, лишь фантазии. Ханс обращает внимание на важную вещь: синхронизация это (вообще говоря) локальная операция. То есть, в идеальном мире, она вносит только локальные задержки, но не уменьшает масштабируемость.

...Некоторое время назад, когда наткнулся на идею weak caches, я был очень вдохновлен идеей отказа от синхронизации для улучшения производительности. Дополнительным аргументом было то, что в распределенных системах как раз много внимания уделялось eventually-consistent алгоритмам и структурам данных, и мне казалось очевидным, что и многопоточное программирование должно двигаться туда же. Ведь в чем принципиальная разница между синхронизацией двух ядер в многоядерной машине, и синхронизацией двух узлов кластера, расположенных на разных континентах?

Как оказывается, разница-то, конечно, есть. Синхронизация в распределенных системах, и инструкции синхронизации в shared memory multithreading — это разные вещи. Когда говорят про синхронизацию в распределенных системах, то подразумевают непосредственно пересылку данных — flush. Потому что именно это является основным источником проблем — и задержек, и нестабильности. Когда типичное время обработки транзакции в хорошо оптимизированном коде измеряется десятками/сотнями микросекунд, а время пересылки измеряется десятками миллисекунд, то очевидно, кто тут слабое звено, и вокруг чего будет весь сыр-бор.

В контексте же многопоточного программирования с разделяемой памятью, синхронизация — это совсем про другое (и для многих этот факт является большим сюрпризом). Здесь инструкции синхронизации означают всего лишь локальный запрет на переупорядочивания операций. Как я уже не раз писал, если я выдаю барьер памяти — это не означает, что я требую немедленно синхронизироваться с основной памятью, или кэшами соседних процессоров, это всего лишь означает, что я требую, чтобы эта синхронизация, когда бы она не произошла — выполнялась в определенном порядке. И это не какая-то там теория, все так на практике и есть: когда, на x86, вы выдаете lock add %esp, 0 — никакой глобальной синхронизации не происходит, процессор просто сбрасывает свой store buffer в свой же локальный кэш. Ни в основную память, ни в кэши соседних процессоров эти данные никто немедленно отправлять не будет (разумеется, на архитектурах без аппаратной кэш-когерентности, типа ARM-ов, этот процесс может выглядеть иначе — я точно не знаю, как).

Таким образом взаимодействие потоков посредством разделяемой памяти состоит из двух частей: непосредственно передача данных между ядрами, и структурирование этой передачи — дабы данные не передавались в абы каком порядке. И вот вторая часть это вотчина инструкций синхронизации, а первая вообще происходит под ковром — но все-таки происходит, про это надо помнить.

Так вот, в дискуссиях вокруг многопоточного программирования часто возникают спекуляции на тему дороговизны этих самых инструкций синхронизации. И важно понимать следующее: да, в начале "эры multicore" инструкции синхронизации стоили довольно дорого. Еще несколько лет назад на x86 CAS стоил под 100нс. Но все эти годы инженеры не лаптем щи хлебали -- на Core i7 uncontended CAS стоит всего ~3ns! Это примерно 6-8 "средних" инструкций (К этим бенчмаркам стоит относиться с осторожностью — слишком они искусственные. В более реальных условиях я бы ожидал цифры в 2-3 раза больше -- но это все равно не так уж страшно). И это не предел — нет никаких фундаментальных причин, почему бы инструкциям синхронизации не стоить как обычным инструкциям.

А вот для скорости работы шины InterConnect-а фундаментальные ограничения есть — скорость света, как минимум. И из общих соображений понятно, что скорость обмена данными с соседними ядрами скорее всего всегда будет оставаться в разы, а то и в десятки раз меньше, чем скорость обмена данными внутри ядра. И отсюда уже становится очевидным, что полная стоимость обмена данными между процессорами (упорядочивание + физическая передача) упирается прежде всего в стоимость передачи данных по шине, и лишь во вторую очередь в стоимость инструкций синхронизации.

Поэтому-то идея как-то радикально ускориться отказавшись от упорядочивания и перейдя к алгоритмам с гонками — она изначально ущербна. Сэкономив на стоимости инструкций синхронизации нам все равно придется платить за передачу данных по шине.

Но это еще не все. Ведь как организованы алгоритмы с гонками? В алгоритмах без гонок мы упорядочиваем передачу данных release/acquire барьерами. В алгоритмах с гонками мы никак передачу не упорядочиваем, но на принимающей стороне мы вынуждены строить такую логику, которая сумеет разобраться с приходящими данными, в каком бы порядке они не появились. И это значит, что на принимающей стороне должна быть какая-то дополнительная логика, умеющая разбирать, образуют ли видимые сейчас данные что-то согласованное, что уже можно использовать, или надо еще подождать, пока придут недостающие кусочки. Говоря совсем просто — это будет цепочка условных переходов, spin-loop-ов на наборе ожидаемых полей.

А теперь, зная, что современные процессоры не любят условные переходы, особенно слабопредсказуемые (а spin-loop на 3-4 полях, с барьером компилятора, с backoff-ом — будет, как мне кажется, довольно сложным для предсказания), и зная, что инструкции синхронизации стоят всего-то ~10-20 обычных инструкций — есть ли основания полагать, что алгоритм с гонками будет хоть чуть-чуть быстрее нормального, корректно синхронизированного кода? Ну, я думаю, есть такие основания — для самых простейших случаев, вроде упомянутого String.hashCode(). Но вряд ли таких случаев много. И более того, перспективность этого направления близка к нулю, потому что инструкции синхронизации будут еще больше дешеветь, и смысла от их устранения будет все меньше.

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

То есть eventually-consistent алгоритмы — это совсем иное, чем data race. Цель EC в уменьшении количества обменов данными, и в разработке алгоритмов, которые остаются рабочими (а структуры данных — в некотором роде согласованными) даже если какие-то данные сильно запоздали. В этом смысле ближайшая аналогия, мне кажется, это wait-free алгоритмы, где каждый поток может прогрессировать вне зависимости от других потоков, поддерживая структуру данных внутренне согласованной.

С точки же зрения же оптимизации — в многопоточных программах (точно так же, как и в распределенных системах) фокус должен быть на уменьшении трафика между потоками, а вовсе не на уменьшении количества инструкций синхронизации. Производительность хорошо написанного многопоточного кода упирается чаще всего именно в шину. Проблема здесь в том, что инструкции синхронизации — они вот, прямо в коде написаны, бери да вычеркивай. А физический обмен данными скрыт где-то под ковром, и возможности прямо на него влиять — нет. И чтобы хотя бы примерно видеть, когда и как этот обмен происходит в вашем конкретном алгоритме нужно неплохо представлять как работает JIT, процессор, и протоколы кэш-когерентности.


P.S. Надо, конечно, помнить, что в реальной жизни всегда есть ньюансы. Например, теоретически-то инструкции синхронизации являются локальными. Но на практике HotSpot для реализации volatile на x86 использует lock xadd, который на короткое время блокирует шину глобально. Почему? Потому что mfence который вроде бы и есть полный двусторонний барьер, и специально для этого и предназначен (и не блокирует шину) в каких-то деталях не совместим с тем, что требует JMM, и приходится пользоваться тем, что попалось под руку.

Кроме того, бывают ситуации, где вы вынуждены использовать слишком сильный примитив синхронизации, просто потому, что более слабого в вашем распоряжении нет. Например, в JMM нет инструкции синхронизации, обеспечивающей только двусторонний барьер чтения (без записи). Это не позволяло реализовать очень эффективный версионный ReadLock. (Пока не пришел Даг Ли, и не создал такую инструкцию как раз под этот случай — но на все случаи Дагов не напасешься ведь)

27 февраля 2013 г.

А почему компилятор не синхронизирует код за меня?

Основная гарантия, которую дает программисту JMM, это что программы без гонок (data race free) выполняются так, как будто они sequentially consistent. Гонки (data race), напомню, это пара чтение/запись или запись/запись одной переменной, когда операции в этой паре не упорядочены через happens-before. И чтобы их упорядочить, если они еще не, нужно добавить каких-то действий синхронизации.

...Но если это так, то почему бы компилятору самому не находить конфликтующие доступы к данным, и не расставлять бы самому в нужных местах упорядочивающие их барьеры? Да, мы потеряем возможность писать программы с гонками. Ну, проживем без эффективного String.hashCode(), да ленивых кэшей, уж перетопчимся как-нибудь. Зато сколько геммороя сразу пропадет! Большинство разработчиков рассуждают о своем коде исключительно в рамках неявно предполагаемой sequential consistency, хотя вообще-то чтобы так рассуждать, нужно сначала сделать программу корректно синхронизированной. Какое счастье и благолепие настало бы, если бы за этой магией следил бы компилятор, а?

Я давно об этом думал, а вот сегодня прямо явно наткнулся (выделение мое):

In fact, Shasha and Snir show that non-sequentially consistent results can only occur when there is a cycle in the graph of happens-before and conflict edges (if two accesses conflict, there is a conflict edge between them). Therefore, detecting where to place memory barriers is a matter of detecting these cycles, and placing memory barriers accordingly.
...Lee and Padua developed a similar compiler analysis, and showed that minimizing the number of memory barriers using their technique was NP-complete.
[Manson, Pugh, Adve]

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

Мораль цитаты в том, что она отвечает на вопрос почему весь этот геморрой с синхронизацией вообще свалился на программиста — да просто компилятор с ним не справляется, вот и приходится привлекать могучий человеческий разум на помощь кремниевому арифмометру. Компилятор с программистом традиционно делят ответственность по-братски: компилятору что может, программисту все оставшееся.