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-полная.

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

26 февраля 2013 г.

Нет никакой ложки...

...и нет никаких реордерингов. Reordering — это поэтическая метафора. Процессоры вовсе не переставляют инструкции. Процессоры просто выполняют код хуй знает какиначе, чем он написан. Как именно? — да как считают нужным, не нравится — не покупайте. Компиляторы — сюрприз — тоже не переставляют инструкции. Компиляторы делают с вашим кодом что-то противоестественноекакую-то неведомую и непонятную херню. Не верите — выведите дизасм достаточно длинного метода на яве, и попробуйте точно объяснить смысл хотя бы пары дюжин подряд идущих инструкций. Там есть комментарии, но вряд ли это вам поможет. Не нравится — пишите свой, с перестановками и циклами причинности.

В формальной части JMM нет никаких перестановок. Можете перечитать JLS-17.*, термин reordering там используется исключительно в разделах "пояснения и обсуждение", чтобы человеческим языком (ну, тем, что авторы считают человеческим языком) объяснить смысл сформулированных определений.

На этом уровне — на уровне метафоры, наглядного образного объяснения, и существуют разные эвристики, вроде "обычную запись можно переставлять до волатильной, но нельзя после нее". Надо четко понимать, что это именно эвристические правила, а не строгие утверждения. Нигде в JMM вы не найдете утверждения, в каком направлении обычные записи можно или нельзя переставлять с волатильными.

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

Вот что я имею в виду по расплывчатостью понятия reordering. Именно от всего этого пытается абстрагировать программиста JMM. JMM просто-напросто (да, я издеваюсь) дает возможность для каждой инструкции чтения в программе ответить на вопрос "какую инструкцию записи это чтение может увидеть?" И это именно то, что интересует меня, как программиста.

Проблема в том, что "просто-напросто", к сожалению, совсем не так просто. Это "просто-напросто" в некоторых местах настолько непросто, что даже его создатели ухитрились с ним кое-где накосячить. И поэтому даже расплывчатое и дырявое понятие реордерингов для большинства является более понятным и приемлемым, чем формальная спецификация.

Очень похожая картина, как мне кажется, существует вокруг мифического spurious wakeup. Всем впадлу объяснять очередному поколению программистов тонкую смысловую разницу между "ожиданием определенного состояния (выполнения некого условия)" и "ожиданием извещения" — гораздо проще помянуть про легендарное ВНЕЗАПНО, и заставить писать проверку в цикле. Кажется, если бы spurious wakeup не существовал, его стоило бы придумать хотя бы ради экономии времени.

Точно так же очередное поколение java-программистов поднимает руки перед мистическим семнадцатым разделом JLS, и остается на полумифическом уровне рассуждений о возможных перестановках.


О автор, ты не мудри, ты пальцем покажипрости мне мою глупость, но я так и не понял, может ли великолепная Виртуальная Машина Явы переставлять обычную запись с волатильной?
Позвольте я переформулирую ваш вопрос для наших читателей:


volatile int va = 0;
int a = 0;
a = 42;
va = 1;
if( va == 1 ){
   print a;
}

volatile int va = 0;
int a = 0;
va = 1;
a = 42;
if( a == 42 ){
   print va;
}

Благоволит ли Аллах такому чуду, чтобы код в первом примере выведет 0? И достанет ли ли Его доброты, чтобы и второй код еще раз явил миру ноль — красивейшее из чисел?

Согласно сутре Пророка, в первом примере, для случая well-formed executions это неугодно Аллаху. Во втором примере, в общем случае это возможно (т.е. доказать невозможность в общем случае нельзя), но в частных случаях это тоже может оказаться противным воле Всевышнего (см. пример из предыдущего поста). В обоих случаях все может измениться от воли Его, и более широкого контекста — от кода, который окружает эти инструкции. Так восславим же Аллаха за его доброту!

P.S. Точности ради: говоря о реордерингах, надо упомянуть еще другой уровень — уровень разработчиков JVM. Уровень людей, которым нужно прописать в JIT-е для конкретной архитектуры процессора конкретные правила преобразования кода, правила допустимости или недопустимости каких-то оптимизаций в каком-то контексте, правила расстановки барьеров памяти. Для них как раз актуальна задача "что может, и что должна делать с кодом JVM, чтобы результат выполнения не противоречил гарантиям, предоставляемым JMM?" И здесь reordering обретает конкретный смысл, потому что для известной архитектуры процессора наблюдаемые эффекты от перестановки двух известных инструкций можно узнать из его спецификации. И эти эффекты можно сравнить с тем, что требует JMM, и решить, подходят ли они нам.

15 февраля 2013 г.

Квест по внутренностям JMM: solution

Студентка Люся выучила все билеты по логике и стала мужиком.

Хорошо, давайте разберем предыдущий пост. Для доказательства нам понадобится всего ничего: волос с головы Путина, менструальная кровь девственницыJMM в мягком переплете, и мозг со способностями к математической логике.
Замечание 0:
В JMM есть понятие частичного порядка happens-before. Немного математики: что такое вообще частичный порядок на множестве A? Неформально: частичный порядок означает, что на множестве A задан способ упорядочивания элементов a1 < a2, но упорядочить можно не все элементы множества: есть такие пары (an, am) что для них порядок не определен: не верно ни что (an < am), ни что (am < an). В противовес этому полный порядок, как можно догадаться, это когда все пары сравнимы: для любых элементов множества A всегда либо am < an, либо an < am, третьего не дано.
Замечание 1:
Если у нас есть события записи и чтения одной переменной W: sharedVar = X, R: localVar = sharedVar, то какие значения может прочитать (увидеть) чтение? Согласно JMM, варианта три:
  1. Если W hb R, то R наверняка прочитает (увидит) X (если нет других записей в ту же переменную)
  2. Если !(W hb R), то R может прочитать X, а может и не прочитать -- как звезды лягут (этот случай как раз называется чтением через data race)
  3. Если R hb W, то R никак не может прочитать X (опять же, если нет других записей). Это самый важный для дальнейшего пункт
Замечание 2:
Synchronized actions (к которым принадлежат vstore и vload) образуют total synchronization order, SO. Важно здесь, что это именно полный порядок. То есть для любых двух SA1, SA2 всегда либо SA1 so SA2, либо SA2 so SA1.

Наше оружие — слово божье, и математический аппарат

Код из предыдущего примера, чуть приглаженый и пронумерованный:
(0) AI sharedRef = null; //write default value

Thread 1

Thread 2

(1) localRef = allocate(sizeOf(AI));
(2) localRef.value = 42;
(3) sharedRef = localRef;

(4) localRef2 = sharedRef;
(5) if(localRef2 != null ){
(6)   localValue = localRef2.value;   
    }

Рассмотрим множество трасс над этим кодом, в которых чтение (6) происходит, и видит значение 0:
  1. Чтобы прочитать что угодно из localRef в (6), нужно чтобы чтение (4) вернуло не null (иначе мы не попадем в эту ветку)
  2. Поскольку 0 это не 42, то не верно, что (2) hb (6).
  3. Раз не верно, что (2) hb (6), то не верно и что (2) sw (6), потому что synchronization order вложен в (согласован с) happens-before.
  4. Поскольку (2) и (6) — synchronized actions, то из ![ (2) sw (6) ] => [(6) sw (2) ] => [(6) hb (2)]. Это ключевой, самый нетривиальный пункт — дальше все просто
  5. (4) hb (6) согласно program order (который тоже вложен/согласован с hb)
  6. (2) hb (3) аналогично
  7. По транзитивности: [(4) hb (6)] + [(6) hb (2)] + [(2) hb (3)] => [(4) hb (3)]
  8. Но раз [(4) hb (3)], то чтение (4) никак не может увидеть значение, записанное (3). Значит (4) может прочитать только значение, записанное в (0), то есть null.
  9. А это противоречит первому пункту.
Получается, что предполагаемые нами трассы не могут существовать в рамках ограничений, накладываемых на исполнение кода моделью памяти java.

Dixi


P.S. Да, совсем забыл -- я могу и ошибаться :)

13 февраля 2013 г.

Квест по внутренностям JMM



class AtomicInteger { 
    private volatile int value;
    public AtomicInteger(final int value) {
        this.value = value;
    }
....
}

AtomicInteger sharedRef;

Thread 1

Thread 2

sharedRef = new AtomicInteger(42);

if( sharedRef != null ) {
    System.out.println(sharedRef.get());
}

  1. Может ли этот код вывести 0?
  2. ...Если может — то как? Сможете ли вы теперь теми же глазами смотреть на AtomicInteger?
  3. ...Если нет — то почему?

P.S. Я, если честно, точного ответа не знаю. Хотя пара правдоподобных вариантов у меня есть.

4 февраля 2013 г.

Задача с собеседования: продолжение

Поскольку в комментариях ответ нашли аж несколько раз, то сознаюсь — да, идея в том, что второй процессор это не только дополнительные 600 баксов стоимости и 70Вт энергопотребления, но еще и лишние 32Кб L1 кэша данных (а в Sandy Bridge так и лишние 256Кб L2, потому что там L2 тоже на каждое ядро). Так что, хотя в общем случае логично ожидать, что однопроцессорная версия будет быстрее (потому что не надо тратиться на синхронизацию), но если задача достаточно memory intensive (т.е. мы упираемся в скорость доступа к данным), причем фазы P1 и P2 оперируют разными данными, то в двухпроцессорном варианте данные фазы 1 будут горячими в кэше CPU1, а данные фазы 2 горячими в кэше CPU2. Получим эффективный размер L1 в 64Кб. И эффект от такого "увеличения" кэша может оказаться доминирующим, и оправдать даже расходы на синхронизацию.

Но мне стало интересно, смогу ли я этот эффект поймать в реальности. Реальность, как обычно, оказалась чуть сложнее теории, но в поединке мозга и компьютера мозг опять победил: вот этот код при базовых (тщательно подобранных) настройках дает в синхронном режиме (-Dasync=false) (690 +/- 1%) нс/сообщение, а в асинхронном (560 +/- 8%) нс/сообщение.

Хотелось бы в общих чертах понять, о чем говорит иностранецчто там происходит?

Нужно подобрать некоторую условную memory intensive задачу, и разбить ее на две фазы, каждая из которых обращается к своему куску данных. Я взял кусок данных в виде достаточно большого (сопоставимого с размером L1) массива double[]. Сама "фаза обработки сообщения" состоит из нескольких чтений/записей в ячейки этого массива. "Несколько" выбрано равным 128, и эти 128 ячеек выбираются из всего массива по псевдослучайному алгоритму (типа ЛКГ: I = (A*I) mod C). Сначала первая фаза делает это над своим массивом, потом вторая фаза делает ровно то же самое над своим — и так для каждого сообщения, коих легион 1 000 000 в каждом заходе. Да чего я код надиктовываю:
int index = message.index;
for( int i = 0; i < OPS_PER_MESSAGE; i++ ) {
  index = Math.abs( index * offset ) % DATA_SIZE;
  array[index] += amount;
}

Интересный вопрос №1: если псевдослучайное скакание по массиву заменить на проходку с фиксированным шагом, то разница в производительности практически пропадает. Скорее даже, с небольшим перевесом, почти на грани погрешности, начинает выигрывать синхронный вариант. Почему так? Интересный вопрос №2: если отставить в сторону рассмотренный вариант — какие еще эффекты могут обеспечить преимущество "распараллеленному" варианту последовательного кода? P.S. Да, кстати — мы (Дойче банк) набираем людей. Кажется, 3-4 вакансии у нас сейчас открыты. Можно прямо мне и писать — а то у меня еще много интересных идей для собеседования есть :)

31 января 2013 г.

Задача с собеседования

...Пусть у нас есть некоторая процедура обработки сообщений. Процедура состоит из двух фаз: P1 и P2. Фазы строго последовательны — P2 не может начаться, пока не закончилась P1. У нас есть датацентр, в датацентре — стойка, в стойке — сервер, в сервере — 2 процессора.

Есть два варианта организации процесса обработки:
Дизайн 1 (тривиальный)
Мы просто задействуем одно-единственное ядро, которое последовательно для каждого сообщения выполняет P1 и P2. Второе ядро курит бамбук.
Дизайн 2
P1 вешаем на ядро 1, P2 на ядро 2, между ними организуем какой-то протокол передачи сообщений.
Вопрос — какой вариант будет быстрее? (== меньше времени на обработку одного сообщения, от начала P1 до конца P2)


...те же грабли, но вид сбоку: теперь нас интересует не скорость, а пропускная способность. У нас есть входящий поток сообщений, которые надо разгребать. Опять же, два варианта:
Дизайн 1 (тривиальный)
Каждое ядро обрабатывает половину входящих сообщений, при этом каждое ядро для доставшихся ему сообщений выполняет обе фазы обработки последовательно.
Дизайн 2
Все сообщения идут сначала на ядро 1, которое выполняет фазу P1, потом пересылаются на ядро 2, которое выполняет для них фазу P2

Вопрос — в каком варианте можно достичь бОльшей пропускной способности? (== количество сообщений, обрабатываемых за единицу времени)


Подсказка: правильно заданный вопрос, как обычно, содержит половину ответа. Правильно заданный вопрос, в данном случае, будет "какой дизайн и при каких условиях даст лучший результат?"

UPD: Я упустил отметить, что по замыслу объемы (сложности) фаз примерно равны. Т.е. среднее время выполнения P1 равно среднему времени выполнения P2.

UPD2: В комментариях уже есть хороший ответ, так что не подглядывайте!

28 января 2013 г.

А что мы измеряем, когда измеряем "производительность CAS-а"?

Очередная статья Мартина — продолжение одного из его уже довольно старых экспериментов. Там у него получилось, что простейший бенчмарк скорости выполнения intcementAndGet (==lock xadd) показывает лучшие результаты на процессорах архитектуры Nehalem, нежели на процессорах более свежей (и, вообще говоря, почти везде более производительной) архитектуры Sandy Bridge. Бенчмарк был совершенно тривиальный — сколько-то потоков, тупо делающих __sync_add_and_fetch() одному счетчику — поэтому результаты, конечно, выглядели странно. И вот, больше чем через год, наконец-то странность объяснилась, и объяснение очень интересное — я не могу удержаться, и не разобрать его.

Преамбула

(Для понимания дальнейшего полезно прочитать мой незаконченный цикл про протоколы кэш-когерентности здесь)

Начнем с того, что Read-Modify-Write (RMW) инструкции в кэш-когерентных системах выполняются примерно так:
  1. Посылаем системе управления кэшом запрос на кэш-строку, содержащую нужную ячейку памяти в состоянии не ниже E(xclusive).
  2. Запрос удовлетворяется немедленно, если текущее ядро уже является эксклюзивным владельцем строки (т.е. строка уже в нашем кэше либо в состоянии E, либо в M(odified)
  3. Если владелец строки кто-то другой, или владельца вообще нет (еще никто ее не загрузил из основной памяти) — инициируем транзакцию на шине InterConnect с целью таки заполучить нужное. Это называется request for ownership, RFO
  4. Убедившись, что текущее ядро является эксклюзивным владельцем нужной строки кэша, мы временно блокируем InterConnect для дальнейших запросов (тем самым не даем никому отобрать у нас только что полученное право собственности)
  5. Выполняем Read-Modify-Write как отдельные инструкции — точно так же, как если бы не было никакого atomic. Атомарность будет гарантирована за счет блокировки шины.
  6. Убираем сигнал #LOCK с шины

Самой (потенциально) тяжелой частью является пункт 3. Если нужной нам строки ни у кого нет — нам как минимум придется ждать основную память или L2-кэш, которые в разы медленнее L1-кэша. Если же у строки уже есть владелец — все еще гемморойнее, потому что запрос к основной памяти будет этим владельцем прерван, и будет инициирован некий протокол арбитрации — переговоров между ядрами на тему "кто кому и когда эту строку будет передавать".

Если эта часть не нужна (т.е. строка уже у нас в кэше в нужном состоянии) то atomic RWM выполняется не сильно медленнее обычной последовательности RMW. Такой удачный вариант (fast path), не требующий межпроцессорной арбитрации, часто называется "локальным RMW" (вы можете встретить выражения типа "local CAS", например), в противовес "глобальному RMW", который эту арбитрацию включает, и может оказаться в чуть ли не в сотню раз медленнее "локального".

Ближе к сути

Что же случилось с бенчмарком Мартина?

Вот есть у нас 2 потока на разных ядрах, вертящих в цикле getAndAdd. Пусть первое ядро захапало себе нужную строку кэша в E, и делает над ней всякие непотребстваload, add, store. Это будет локальный getAndAdd — строка-то наша. Как долго будет продолжаться это право первой ночи? — Да до тех пор, пока второе ядро у нас строку не отберет. А чтобы ее у нас отобрать, нужно инициировать и пройти до конца всю процедуру арбитрации. Таким образом можно заметить, что чем дольше длятся переговоры, тем больше локальных (быстрых!) getAndAdd успеет сделать ядро. Скажем, если арбитрация стоит 50нс, а локальный getAndAdd — 5нс, то мы успеем сделать 10 локальных операций пока у нас строку не отберут.

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

То есть после каждых 10 локальных операций, стоимостью в 5нс, мы прерываемся на 10(на пересылку "туда")+ 50(на арбитрацию)+10(на пересылку "назад")=70нс — и в это время соседнее ядро делает свои 10 локальных операций. Средняя стоимость одной операции (10*5 + 70) / 10 = 12нс.

А теперь внезапно Sandy Bridge, и гениальные инженеры Интела, заработав седину на висках, заоптимизировали арбитрацию. И теперь арбитрация стоит 10нс (не зря седину заработали, да). И за время этой арбитрации мы успеваем сделать только 2 локальных операции. И теперь после каждых 2х локальных операций по 5нс будет одна пауза в (10 + 10 + 10) = 30нс. Среднее время выполнения getAndAdd (2*5 + 30)/2 = 20нс.

Черт побери. Как-то неаккуратненько вышло.

Особенно любопытно что: легко видеть, что каждый конкретный getAndAdd на Sandy Bridge выполняется не медленнее, чем на Nehalem (а часто и быстрее). Но вот количество "медленных" (глобальных) getAndAdd-ов на Sandy Bridge стало в разы больше, чем было на Nehalem. И именно потому, что каждый конкретный глобальный getAndAdd стал быстрее.

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

Мораль

Это очень красивый эффект, возникающий в некоторых системах, когда оптимизация slow path может ухудшить общую производительность системы, потому что после оптимизации увеличится доля объектов, обрабатываемых по slow path. Очень похожий по сути Парадокс Брайеса существует в транспортных сетях. На еще более похожую ситуацию я сам натыкался, когда анализировал Disrupor — до сих пор бьюсь в экстазе, когда вспоминаю.

Важно, что для возникновения такой парадоксальной ситуации нужно, чтобы система некоторым образом "тупо" саморегулировалась. В парадоксе Брайеса нужно, чтобы водители сами эгоистично выбирали себе маршрут (если ввести внешнее регулирование парадокс пропадает). В случае Disruptor-а важно, чтобы скорость накладаторов/разгребаторов определялась только самим Disruptor-ом, а не, скажем, бизнес-логикой. В случае Мартиновских бенчмарков то же самое — важно, чтобы оба потока фигачили свои getAndAdd так часто, как только можно, а не так часто, как нужно по логике. Т.е. система в режиме насыщения, и каждый тянет одеяло на себя. Если как-то нагрузку упорядочить — ввести Backoff, или какую-то полезную нагрузку — мы получим искомое ускорение, как и ожидалось.