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, и в большинстве случаев скаляризацию удается заставить работать, либо обозначить ключевые причины, почему она в таком коде работать и не будет. Пока, по крайней мере, все выглядит так.

12 комментариев:

  1. А все из какой-то реальной задачи ( упаси господи ) или же "простое" академическое исследование ?

    ОтветитьУдалить
    Ответы
    1. Почему сразу "упаси господи"? У нас в коде испокон веков флаги шли битовой маской, я, конечно, под это дело завел enum, и где можно пользовался EnumSet/EnumMap, потому как очевидно удобнее же. Вот и стало интересно. Конечно, код не ровно так выглядит -- примеры-то я "академические" стараюсь делать.

      Или вы про то, действительно ли это отсутствие скаляризации EnumSet является где-то перфомансной проблемой? Тогда нет, пока я таких примеров, где это является проблемой, у себя не видел.

      Удалить
    2. Как ни странно, мне до сих пор битовая маска часто удобнее, чем EnumSet. Как минимум потому, что она value-type, то есть не надо следить, что утечёт ссылка в недоверенный код и там кто-то мои флаги поменяет. Делать явно копии или оборачивать везде в unmodifiableSet как-то мутно.

      Удалить
  2. Руслан, я давно хотел тебя спросить, не в Word'е ли ты пишешь посты. Но теперь я, кажется, знаю ответ: по-моему, даже Word не растягивает слово "код" на целую строчку

    ОтветитьУдалить
    Ответы
    1. Я пишу прямо в блогспотовском редакторе, и ручками расставляю тэги и длинные тире. Только никому не говори :)

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

      Удалить
    2. Я в IE читаю, только никому не говори :-). Сейчас пришлю скриншот

      Удалить
  3. Не пробовал ли патчить openjdk на тему поведения EA - не исключено, что в некоторых случаях патч не велик будет? Верифицировать и протолкнуть это уже проторенная дорожка Тагиром

    ОтветитьУдалить
    Ответы
    1. В смысле -- патчить OpenJDK? Я не знаю, как починить JDK-8155769 -- даже толком не понимаю, что там сломано. А на уровне джава-кода починить не получится, я же пишу -- здесь-то итератор должен иметь ссылку на EnumSet.

      Удалить
    2. нет, не на уровне java, а на уровне jvm - почему бы не пуститься во все тяжкие...

      Удалить
    3. Это ж на С++ придется писать. Боюсь, потом долго грехи замаливать придется :)

      Морально не готов пока к таким экспериментам над собой.

      Удалить
  4. Общался тут давеча с С++-никами
    У них можно и на стеке аллоцировать и в хипе - просто указав это языку )))
    Ляпота)))
    Сорри за небольшой неконструктив - навеяло )

    ОтветитьУдалить
    Ответы
    1. как нечего делать

      Foo foo(); // on stack

      Foo *foo = new Foo(); // in heap

      и можно еще передавать значения по ссылке, а можно по значению - это значит, что каждый раз на вызов метода будет создан новый объект через copy-constructor

      Удалить