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