Самурай без меча подобен самураю с мечом, только без меча
Когда мы говорим об аллокации в 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), и только тогда пытаемся устранить аллокацию в куче. Раз уж мы все равно знаем, что ссылка на объект нам не понадобится — то почему бы не получить заодно бонусы скаляризации?
Что происходит с массивом, который распихать по регистрам не получится, но никуда за пределы метода он явно не утекает ?
ОтветитьУдалитьЕсли размер массива статически вычислим, то почему бы его и не распихать по регистрам/слотам на стеке? Если же размер массива статически не вычислим, то, конечно, скаляризовать его не получится. Но и в С/С++ же аллоцировать на стеке можно только массивы фиксированного размера (я помню, есть расширение gcc позволяющее аллоцировать на стеке массив размера, вычислимого в момент входа в функцию -- т.е. зависящего только от аргументов)
УдалитьЭто в теории. На практике, из того, что я пока наблюдаю: если массив фиксированного размера, и ты обращаешься к отдельным ячейкам массива (типа arr[1], arr[5]) -- то массив скаляризуется до length=64. Но стоит тебе сделать что-нибудь типа for( a : arr ) -- и хана скаляризации для length > 1
интересный нюанс про 64 байта, ровно как и про foreach loop - вот тебе и сахарок
УдалитьНе, сахарок тут ни при чем, обычный цикл по индексу имеет тот же эффект. Важно, что обращение идет не к фиксированным ячейкам, а к "каким-то". Идея понятна: ты можешь легко превратить обращение array[4] в обращение к локальной переменной array$4, но во что превратить обращение array[i]?
УдалитьОднако я, изначально, ожидал, что стандартный loop unrolling на 16 итераций должен частично помочь -- то есть цикл <=16 итераций должен раскручиваться компилятором полностью, и дальше уже, казалось бы, скаляризации ничего не мешает. Исходя из этого рассуждения я ожидал, что проблемы со скаляризацией начнутся с length>16. На практике же я вижу, что скаляризация пропадает при length>1.
Это меня немного удивляет: уж либо вообще любой цикл должен был бы отрубать скаляризацию -- это можно было бы понять так, что раскручивание циклов просто происходит позже скаляризации в списке оптимизаций. Либо length>=16 -- это можно понять так, что раскручивание происходит до скаляризации. А length >=1 -- это хрен знает, как понимать. Возможно, конечно, это какая-то отдельная, специфичная оптимизация, типа "устранение циклов длины 1"...
> Идея понятна: ты можешь легко превратить обращение array[4] в обращение к локальной переменной array$4, но во что превратить обращение array[i]?
УдалитьНу не знаю, а в чем проблема для компилятора, если он знает, что размер массива = 1000, выделить память под эту 1000 элементов на стеке и заменить обращения array[i] на нечто вроде *(&array$0 + i)?
Нет, идея этого ограничения по-прежнему непонятна.
Когда я писал про array[i] я имел в виду, что прежде чем во что-то это превращать, компилятор должен присвоить индексу конкретное значение. То есть статически "выполнить" цикл. Это совсем не простая задача в общем виде -- вспомните про проверки границ диапазона при доступе к массиву, и про то, что никто не гарантирует, что все индексы будут правильными.
УдалитьДругое дело, что эта задача и так уже частично решается -- JIT умеет во многих случаях разматывать цикл, пусть и частично, и доказывать отсутствие выхода за границы массива (скорее, сводить все проверки к небольшому их количеству). И странно, что эти оптимизации не "суммируются"
Понял, согласен.
УдалитьВиталик Марин подсказал про такой ключи jvm (в jvm на все есть свой ключ)
Удалить-XX:EliminateAllocationArraySizeLimit=64
Тут чуть подробнее
http://stackoverflow.com/questions/18810505/declaring-multiple-arrays-with-64-elements-1000-times-faster-than-declaring-arra
Спасибо. Да, для всего есть свой ключик )
УдалитьИ с векторными операциями над этим массивом
ОтветитьУдалитьПока что я наблюдаю, что любое обращение с массивом как с массивом, типа for( a: array) -- кладет толстый болт на скаляризацию. Кроме размера length=1. Подозреваю, что в последнем случае какой-то примитивный loop unrolling успевает отработать до EA
УдалитьИ еще интересно, считается ли escape'ом вызов какого-нибудь String.valueOf(myLocalObject). Есть подозрение, что если JIT заинлайнил String.valueOf(), то никто не помешает ему потом вычислить, что myLocalObject не покидает границ метода.
ОтветитьУдалитьКонечно, скаляризация и вклеивание -- это как русский с китайцем, братья навек. Без вклеивания скаляризация вообще очень редко где будет отрабатывать, потому что даже new Vector2D(1,2).length() -- это уже убегание, ведь new Vector2D() передается первым неявным аргументом в метод .length(). То есть без вклеивания целями скаляризации останутся разве что структуроподобные классы, без методов и с открытыми полями.
УдалитьК счастью, с дефолтной глубиной инлайнинга в 10 уровней у EA есть где развернуться :) И в таком простом случае, как вызов короткого статического метода -- скорее всего, все будет хорошо. Но вообще не случившийся почему-то инлайнинг частая причина облома скаляризации.
Я тут недавно слышал про новый язык "D".
ОтветитьУдалитьГоворят там можно отдельно управлять кусками хипа как своего рода зонами.
Даешь разделение хипа в Java по зонам.
boolean turn_off_gc=true
HeapSegment segment = new HeapSegment(turn_off_gc);
В real-time java есть похожая штука. Только RT JVM, по слухам, на порядок медленнее обычной. Не знаю, связаны ли эти вещи :)
УдалитьОх уж эти слухи и real-time java.
УдалитьВот честно хочу язык с плюшками Java и без GC
Одно зло от GC и извраты
То UNSAFE, то преаллокация.
Колдовство с бубнами а не программирование
Мне кажется, ты недооцениваешь роль GC в "плюшках" java. На хабре есть цикл статей по реализации concurrent структур данных в С++ -- это адъ и преисподня. В джаве ты даже с ABA редко встречаешься благодаря GC, я уж не говорю о concurrent аллокации/деаллокации.
УдалитьМеня лично GC более чем устраивает.
Я сейчас работаю с большими данными
УдалитьНу это когда надо саггрегировать 100ТБ в хипе
Вот уже где приходится доставать бубен и танцевать
Ну не работает тут джавовая хешмапа - не работает
Кстати что ты имеешь ввиду под "ABA"
УдалитьВидимо квалификации не достает
https://ci.apache.org/projects/flink/flink-docs-master/api/java/org/apache/flink/runtime/memory/MemoryManager.html
УдалитьВот что люди пишут чтобы подружить джаву и большие данные
На скажи Руслан - разве не изврат ? Сам язык должен предоставлять подобные примитивы - ан нет - народ садится и пишет собственный менеджмент памятью чтоб ГЦ не угробил все приложение
ABA -- это когда CAS не может отличить ситуацию, когда ничего не изменилось, от ситуации, когда что-то изменилось, а потом все вернули взад. В некоторых алгоритмах это разные ситуации, и они должны по-разному обрабатываться, и поэтому приходится вводить дополнительные признаки.
УдалитьЧто касается менеджера памяти -- сколько процентов приложений на яве используют сотни Гб памяти? Когда их будет хотя бы 10% -- в языке будет решение, я уверен. А пока оракл просто смотрит, что люди придумывают сами. Если оракл будет бежать впереди паровоза, то получится как с EJB 1-2
А как Java разрешает проблему с ABA ?
УдалитьУниверсально никак не решает. Но важный частный случай, это когда ты удалил узел из concurrent структуры данных, память почистил, аллокатор тут же выдал эту память под запрос аллокации следующему клиенту, и клиент этот же кусок памяти в структуру вставил. А ты и не заметил, что царя-то подменили. А в джаве GC тебе не даст переиспользовать память, пока есть хоть одна живая ссылка.
УдалитьНу подобный финт ушами можно гарантировать и без ГЦ
УдалитьМожно. Но дело в том, что без GC его надо именно _делать_ -- причем в таких ситуациях, где проблема совершенно не очевидна, про нее знать надо. А с GC проблемы остаются в тех ситуациях, где они более-менее очевидны. То есть GC добавляет всей системе интуитивности -- он решает проблему именно в тех случаях, когда она наименее очевидна.
УдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьПро агрегацию 100тб в хипе. Можно чуть подробней - на каком железе эта задача решается? Chronicle и подобные..?
ОтветитьУдалитьну 100ТБ это я загнул
УдалитьНо 10Г на MacBookPro аггрегирую
Без HashMap само собой
Да на лабе (Xeon) аггрегирую под 100ГБ
УдалитьДадите 100Т хип и там можно саггрегировать
Я пока до конца так и не понял решаемую задачу и ограничения, в которых вы работаете
УдалитьЕсли начинаются разговоры про большую кучу и чтобы не под jvm gc, то я бы посмотрел на упоминаемый chronicle (http://chronicle.software/products/chronicle-map/) и ему подобные
Тут речь не о поиске готовой либы - а о том как это написать самим
УдалитьЗачем не спрашивайте :)
Этот комментарий был удален автором.
ОтветитьУдалить"то массив скаляризуется до length=64"
ОтветитьУдалитьна самом деле предел 64 очень условный - для byte[64] - да, но вот с double[64] всё интереснее.
В общем случае, память под массив не должна быть больше (TrackedInitializationLimit * HeapWordSize)
Любопытно -- я не смог найти этого в коде EA. Я вижу, что TrackedInitializationLimit используется для ограничения каких-то других оптимизаций инициализации, вроде обнуления памяти
Удалитьпуть - PhaseMacroExpand::scalar_replacement-> PhaseMacroExpand::value_from_mem-> InitializeNode::find_captured_store-> InitializeNode::captured_store_insertion_point
ОтветитьУдалитьСпасибо, прослежу.
Удалить