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), и только тогда пытаемся устранить аллокацию в куче. Раз уж мы все равно знаем, что ссылка на объект нам не понадобится — то почему бы не получить заодно бонусы скаляризации?

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

  1. Что происходит с массивом, который распихать по регистрам не получится, но никуда за пределы метода он явно не утекает ?

    ОтветитьУдалить
    Ответы
    1. Если размер массива статически вычислим, то почему бы его и не распихать по регистрам/слотам на стеке? Если же размер массива статически не вычислим, то, конечно, скаляризовать его не получится. Но и в С/С++ же аллоцировать на стеке можно только массивы фиксированного размера (я помню, есть расширение gcc позволяющее аллоцировать на стеке массив размера, вычислимого в момент входа в функцию -- т.е. зависящего только от аргументов)

      Это в теории. На практике, из того, что я пока наблюдаю: если массив фиксированного размера, и ты обращаешься к отдельным ячейкам массива (типа arr[1], arr[5]) -- то массив скаляризуется до length=64. Но стоит тебе сделать что-нибудь типа for( a : arr ) -- и хана скаляризации для length > 1

      Удалить
    2. интересный нюанс про 64 байта, ровно как и про foreach loop - вот тебе и сахарок

      Удалить
    3. Не, сахарок тут ни при чем, обычный цикл по индексу имеет тот же эффект. Важно, что обращение идет не к фиксированным ячейкам, а к "каким-то". Идея понятна: ты можешь легко превратить обращение array[4] в обращение к локальной переменной array$4, но во что превратить обращение array[i]?

      Однако я, изначально, ожидал, что стандартный loop unrolling на 16 итераций должен частично помочь -- то есть цикл <=16 итераций должен раскручиваться компилятором полностью, и дальше уже, казалось бы, скаляризации ничего не мешает. Исходя из этого рассуждения я ожидал, что проблемы со скаляризацией начнутся с length>16. На практике же я вижу, что скаляризация пропадает при length>1.

      Это меня немного удивляет: уж либо вообще любой цикл должен был бы отрубать скаляризацию -- это можно было бы понять так, что раскручивание циклов просто происходит позже скаляризации в списке оптимизаций. Либо length>=16 -- это можно понять так, что раскручивание происходит до скаляризации. А length >=1 -- это хрен знает, как понимать. Возможно, конечно, это какая-то отдельная, специфичная оптимизация, типа "устранение циклов длины 1"...

      Удалить
    4. > Идея понятна: ты можешь легко превратить обращение array[4] в обращение к локальной переменной array$4, но во что превратить обращение array[i]?
      Ну не знаю, а в чем проблема для компилятора, если он знает, что размер массива = 1000, выделить память под эту 1000 элементов на стеке и заменить обращения array[i] на нечто вроде *(&array$0 + i)?
      Нет, идея этого ограничения по-прежнему непонятна.

      Удалить
    5. Когда я писал про array[i] я имел в виду, что прежде чем во что-то это превращать, компилятор должен присвоить индексу конкретное значение. То есть статически "выполнить" цикл. Это совсем не простая задача в общем виде -- вспомните про проверки границ диапазона при доступе к массиву, и про то, что никто не гарантирует, что все индексы будут правильными.

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

      Удалить
    6. Виталик Марин подсказал про такой ключи jvm (в jvm на все есть свой ключ)

      -XX:EliminateAllocationArraySizeLimit=64

      Тут чуть подробнее
      http://stackoverflow.com/questions/18810505/declaring-multiple-arrays-with-64-elements-1000-times-faster-than-declaring-arra

      Удалить
    7. Спасибо. Да, для всего есть свой ключик )

      Удалить
  2. И с векторными операциями над этим массивом

    ОтветитьУдалить
    Ответы
    1. Пока что я наблюдаю, что любое обращение с массивом как с массивом, типа for( a: array) -- кладет толстый болт на скаляризацию. Кроме размера length=1. Подозреваю, что в последнем случае какой-то примитивный loop unrolling успевает отработать до EA

      Удалить
  3. И еще интересно, считается ли escape'ом вызов какого-нибудь String.valueOf(myLocalObject). Есть подозрение, что если JIT заинлайнил String.valueOf(), то никто не помешает ему потом вычислить, что myLocalObject не покидает границ метода.

    ОтветитьУдалить
    Ответы
    1. Конечно, скаляризация и вклеивание -- это как русский с китайцем, братья навек. Без вклеивания скаляризация вообще очень редко где будет отрабатывать, потому что даже new Vector2D(1,2).length() -- это уже убегание, ведь new Vector2D() передается первым неявным аргументом в метод .length(). То есть без вклеивания целями скаляризации останутся разве что структуроподобные классы, без методов и с открытыми полями.

      К счастью, с дефолтной глубиной инлайнинга в 10 уровней у EA есть где развернуться :) И в таком простом случае, как вызов короткого статического метода -- скорее всего, все будет хорошо. Но вообще не случившийся почему-то инлайнинг частая причина облома скаляризации.

      Удалить
  4. Я тут недавно слышал про новый язык "D".
    Говорят там можно отдельно управлять кусками хипа как своего рода зонами.

    Даешь разделение хипа в Java по зонам.

    boolean turn_off_gc=true
    HeapSegment segment = new HeapSegment(turn_off_gc);

    ОтветитьУдалить
    Ответы
    1. В real-time java есть похожая штука. Только RT JVM, по слухам, на порядок медленнее обычной. Не знаю, связаны ли эти вещи :)

      Удалить
    2. Ох уж эти слухи и real-time java.

      Вот честно хочу язык с плюшками Java и без GC
      Одно зло от GC и извраты

      То UNSAFE, то преаллокация.

      Колдовство с бубнами а не программирование

      Удалить
    3. Мне кажется, ты недооцениваешь роль GC в "плюшках" java. На хабре есть цикл статей по реализации concurrent структур данных в С++ -- это адъ и преисподня. В джаве ты даже с ABA редко встречаешься благодаря GC, я уж не говорю о concurrent аллокации/деаллокации.

      Меня лично GC более чем устраивает.

      Удалить
    4. Я сейчас работаю с большими данными
      Ну это когда надо саггрегировать 100ТБ в хипе

      Вот уже где приходится доставать бубен и танцевать
      Ну не работает тут джавовая хешмапа - не работает

      Удалить
    5. Кстати что ты имеешь ввиду под "ABA"
      Видимо квалификации не достает

      Удалить
    6. https://ci.apache.org/projects/flink/flink-docs-master/api/java/org/apache/flink/runtime/memory/MemoryManager.html
      Вот что люди пишут чтобы подружить джаву и большие данные

      На скажи Руслан - разве не изврат ? Сам язык должен предоставлять подобные примитивы - ан нет - народ садится и пишет собственный менеджмент памятью чтоб ГЦ не угробил все приложение

      Удалить
    7. ABA -- это когда CAS не может отличить ситуацию, когда ничего не изменилось, от ситуации, когда что-то изменилось, а потом все вернули взад. В некоторых алгоритмах это разные ситуации, и они должны по-разному обрабатываться, и поэтому приходится вводить дополнительные признаки.

      Что касается менеджера памяти -- сколько процентов приложений на яве используют сотни Гб памяти? Когда их будет хотя бы 10% -- в языке будет решение, я уверен. А пока оракл просто смотрит, что люди придумывают сами. Если оракл будет бежать впереди паровоза, то получится как с EJB 1-2

      Удалить
    8. А как Java разрешает проблему с ABA ?

      Удалить
    9. Универсально никак не решает. Но важный частный случай, это когда ты удалил узел из concurrent структуры данных, память почистил, аллокатор тут же выдал эту память под запрос аллокации следующему клиенту, и клиент этот же кусок памяти в структуру вставил. А ты и не заметил, что царя-то подменили. А в джаве GC тебе не даст переиспользовать память, пока есть хоть одна живая ссылка.

      Удалить
    10. Ну подобный финт ушами можно гарантировать и без ГЦ

      Удалить
    11. Можно. Но дело в том, что без GC его надо именно _делать_ -- причем в таких ситуациях, где проблема совершенно не очевидна, про нее знать надо. А с GC проблемы остаются в тех ситуациях, где они более-менее очевидны. То есть GC добавляет всей системе интуитивности -- он решает проблему именно в тех случаях, когда она наименее очевидна.

      Удалить
  5. Этот комментарий был удален автором.

    ОтветитьУдалить
  6. Про агрегацию 100тб в хипе. Можно чуть подробней - на каком железе эта задача решается? Chronicle и подобные..?

    ОтветитьУдалить
    Ответы
    1. ну 100ТБ это я загнул
      Но 10Г на MacBookPro аггрегирую
      Без HashMap само собой

      Удалить
    2. Да на лабе (Xeon) аггрегирую под 100ГБ
      Дадите 100Т хип и там можно саггрегировать

      Удалить
    3. Я пока до конца так и не понял решаемую задачу и ограничения, в которых вы работаете

      Если начинаются разговоры про большую кучу и чтобы не под jvm gc, то я бы посмотрел на упоминаемый chronicle (http://chronicle.software/products/chronicle-map/) и ему подобные

      Удалить
    4. Тут речь не о поиске готовой либы - а о том как это написать самим
      Зачем не спрашивайте :)

      Удалить
  7. Этот комментарий был удален автором.

    ОтветитьУдалить
  8. "то массив скаляризуется до length=64"
    на самом деле предел 64 очень условный - для byte[64] - да, но вот с double[64] всё интереснее.
    В общем случае, память под массив не должна быть больше (TrackedInitializationLimit * HeapWordSize)

    ОтветитьУдалить
    Ответы
    1. Любопытно -- я не смог найти этого в коде EA. Я вижу, что TrackedInitializationLimit используется для ограничения каких-то других оптимизаций инициализации, вроде обнуления памяти

      Удалить
  9. путь - PhaseMacroExpand::scalar_replacement-> PhaseMacroExpand::value_from_mem-> InitializeNode::find_captured_store-> InitializeNode::captured_store_insertion_point

    ОтветитьУдалить