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, и все-таки оптимизатор оказывается не способен этого сделать...

Комментариев нет:

Отправить комментарий