25 марта 2016 г.

А почему бы не аллоцировать на стеке?

В самом деле: почему? Вот мы прогнали escape analysis на коде метода, обнаружили, что такие-то создаваемые объекты за пределы метода не утекают. Зачем мы их скаляризуем, почему бы нам просто не аллоцировать их на стеке? Ведь скаляризация, на первый взгляд, сложнее аллокации на стеке: отследить, какие операции с полями объектов к именно какому объекту в этот момент относятся, завести под эти поля локальные переменные, преобразовать код, чтобы он обращался к этим переменным, а не к полям объекта, приготовить задел для деоптимизации... Зачем нам весь этот геморрой, когда можно просто выделить кусок памяти на стеке, и впечатать туда объект? И мы получим полноценную ссылку на него, ничем не отличающуюся от ссылки на объект в куче. Ссылку, которую можно запихнуть в любую дырку, куда пролезет обычная ссылка (ну, слишком-то глубоко мы ее не запихаем — мы же знаем, что за пределы метода она не уйдет).

Насколько я понимаю, одного простого ответа на это "почему" нет. Более того, существовали прототипы стековой аллокации — в одной из статей по EA авторы упоминают, что их прототип делал по результатам EA именно стековую аллокацию (правда, тот прототип был на базе IBM JVM).

Но стековая аллокация не так уж проста, когда речь заходит о деталях: JVM (Oracle/Open JDK) знает, сколько памяти выделено ей под кучу — эта информация задается при запуске, и не может быть изменена. И VM этим пользуется: сразу же при старте резервирует у ОС диапазон адресов размером с максимальную кучу (не аллоцирует память, а просто резервирует адреса HEAP_START..HEAP_END = -Xmx реальная же аллокация происходит по необходимости). И с самого первого момента жизни у JVM есть эти два числа [HEAP_START..HEAP_END], между которыми должно лежать значение любого указателя на java-объект, и JVM активно полагается на то, что куча это непрерывный кусок памяти [HEAP_START..HEAP_END]. Например, эти числа можно вклеивать в генерируемый код прямо в виде констант.

Или, например, card marking. Я уже как-то писал о нем в контексте concurrency: generational GC должен как-то отслеживать ссылки между объектами разных поколений. Чтобы собрать молодое поколение, нужно знать, какие ссылки на него существуют в полях объектов старого поколения (они становятся частью root set-а). Разумеется, сканировать старое поколение целиком значит похоронить всю идею generational GC, объем сканирования нужно как-то сузить. Для этого JVM разбивает кучу на блоки-"карты" размером 512 байт, и для каждого такого блока держит однобайтовый признак "была ли в пределах этого блока запись ссылки". Каждая запись ссылки обновляет заодно и card marks: очень грубо, строчка a.f = ref из java-кода превращается примерно в
a.f = ref;
cardMarks[ (addressOf(a.f)-HEAP_START) >> 9 ] = 1
Т.е. мы записали ссылку в поле какого-то объекта, и пометили блок памяти, содержащий этот объект, как модифицированный. (Это относится только к записям ссылок — примитивные типы card marks не обновляют, потому что GC до них нет дела). Перед сборкой молодого поколения GC пройдет все модифицированные блоки, соберет из них ссылки, ведущие в молодое поколение, и добавит их в root set.

Код card marking такой простой потому, что мы заранее знаем начало кучи, какого она размера, и что она непрерывна. Поэтому нам достаточно одного-единственного массива cardMarks, и мы можем уже на старте JVM аллоцировать его нужного размера (= HEAP_SIZE / 512), сразу подо всю, даже еще не аллоцированную, кучу. Очевидно, что если теперь a в коде выше вдруг указывает на объект на стеке, то мы получим выход за границы массива cardMarks, потому что стеки потоков точно никак не попадут в зарезервированный под кучу интервал адресов. Чтобы обрабатывать ссылки на объекты в куче и объекты на стеке одновременно нужно, чтобы код card marking-а был заметно сложнее, скорее всего, содержал какие-то проверки и условные переходы. А это, на минуточку, код записи ссылки — одна из самых базовых операций, из самых часто исполняемых фрагментов кода. Типичная java-программа ссылками оперирует, пожалуй, чаще, чем примитивными типами! Получается, что немного ускорив аллокацию (точнее, де-аллокацию, сборку мусора — аллокация из TLAB в яве и так быстрее некуда) за счет использования стека мы одновременно замедлили один из самых горячих фрагментов кода — запись ссылки. Какой итоговый эффект это окажет на производительность/время отклика приложения в целом — большой и нетривиальный вопрос.

Card marking это только один из примеров того, как неожиданно непросто впихнуть стековые объекты в архитектуру JVM, годами заточенную под манипуляции объектами из кучи. Этот пример простой, но, возможно, уже не самый актуальный — как я понимаю (могу ошибаться), в G1 уже пришлось делить общий массив cardMarks на отдельные массивчики для каждого блока. Возможно, теперь уже не так уж сложно втиснуть в эту схему еще несколько "блоков" для стеков потоков. Но это не единственный такой пример, если судить по переписке в hotspot-dev:

...I tried implementing direct stack allocation in Hotspot a couple of years ago. It was a pain to try to allocate anything outside the heap - there are a lot of checks to make sure that your objects live on the heap. I ended up creating TLAB-like regions in the heap that could hold objects allocated in a stack-like way. It was a lot easier that way, and seemed to give the kinds of performance benefits you would expect. (Jeremy Manson, 01/27/14, @hotspot-dev)

— оказывается, что проще создать свой собственный "стек" с гетерами и панкратионом: откусывать от общей кучи пулы памяти на каждый поток, и использовать их для аллокации неубегающих объектов, на манер стека. И прототип реализации был написан еще два года назад. И где тот стек сейчас?..

...Я сейчас думаю, что, возможно, дело вообще не в сложности технической реализации аллокации на стеке. Дело в том, что непонятно, так ли уж это нужно. В самом деле, чтобы устранить аллокацию в куче нужно а) чтобы алгоритм EA сумел показать, что объект не утекает за границы текущей единицы компиляции б) чтобы алгоритм скаляризации сумел преобразовать все обращения к этому объекту в обращения к его скаляризованной версии. Переход от скаляризации к аллокации на стеке улучшит пункт "б" (сделает его почти 100%-ным). Сейчас, в некоторых случаях, алгоритм скаляризации может спасовать, даже если алгоритм EA и распознал локальность объекта, а с введением аллокации на стеке почти все такие случаи будут обрабатываться. Но вот много ли таких случаев? Точнее: во-первых, в каком проценте случаев скаляризация пасует сейчас, и во-вторых — какой процент от общего числа аллоцированных в программе объектов мы сможем таким образом выиграть? Я экспериментирую сейчас с различными сценариями, и складывается ощущение, что ответ на первый вопрос может быть довольно заметным — ну, скажем, сейчас мы скаляризуем 60-70% объектов, распознанных EA как неубегающие, а будем аллоцировать на стеке все 100%. А вот общий эффект для среднестатистической программы может быть скромным, если вообще заметным.

Вот недавно мне попалась (спасибо твиттеру) свежая статья, про очередной улучшенный алгоритм EA, в конце каковой статьи приведены результаты применения улучшенного алгоритма к разным бенчмаркам из наборов DeCapo и SPECjbb2005. Результат: в среднем устранено примерно ~15% аллокаций в куче. Это довольно продвинутый алгоритм EA, в паре со "стековой" аллокацией — то есть, приблизительно и ориентировочно, можно взять эти 15% аллокаций за оценку сверху возможностей используемого сейчас алгоритма EA. И переход от используемой сейчас скаляризации к какому-нибудь варианту "стековой" аллокации позволит выиграть какую-нибудь треть от этих 15%.

Каким бы совершенным не был "скаляризатор", его поле деятельности ограничено теми не-убегающими аллокациями, которые ему скормит EA. Алгоритм EA в java почти не менялся со времен 1.6. Да и чисто теоретически: возможности EA отыскать не-убегающие аллокации, в свою очередь, тоже ограничены: в пределах одного метода, даже с учетом агрессивного инлайнинга, особо не развернешься, а межпроцедурную оптимизацию JIT сейчас не выполняет. Увеличивать агрессивность инлайнинга? — Неплохой вариант, в основном потому, что дает пинок, наряду со скаляризацией, сразу целому ряду других оптимизаций. И действительно, в 1.8 многие ограничения на инлайнинг ослаблены, и я вижу, как некоторые сценарии, не скаляризовавшиеся в 1.7, в 1.8 начали скаляризоваться. Но особо далеко по этому пути тоже не пройдешь: чрезмерный инлайнинг раздувает код, и с какого-то момента это начинает уже ухудшать производительность. Получается, что существенный прирост можно получить только совершенствуя сразу и скаляризацию, и алгоритм EA, и, по-возможности, увеличивая размер единицы оптимизации, либо подключая межпроцедурную оптимизацию.

В таком рассуждении есть нюанс: когда мы пытаемся оценить профит от улучшений, прогоняя их на существующих уже программах, мы незаметно попадаем в ловушку. Существующие программы написаны с использованием существующих практик написания кода, и в этих практиках — и вообще в опыте разработчиков — уже учтены характерные особенности языка и платформы. Опытные разработчики, сознательно или бессознательно, уже оптимизируют свой код под известные сильные и слабые стороны платформы. Говоря проще: если бы было общеизвестно, что в java есть великолепный EA и скаляризатор, и что редкий временный объект имеет шанс быть аллоцированным в куче — многие программы были бы написаны сильно иначе, чем они написаны сейчас, когда общеизвестно, что да, GC довольно неплохо управляется с короткоживущими объектами, а некоторые объекты даже и скаляризуются, но не всегда, и не все, и вообще как фишка ляжет. В упомянутой выше статье, наряду с набором java-бенчмарков, был взят аналогичный набор Scala-бенчмарков (ScalaDeCapo). И разница очень заметна: (Java)DeCapo от включения EA получает бонус в -5% аллокаций, а ScalaDeCapo — в -15%. Общий прирост производительности (Java)DeCapo: +2.2%, ScalaDeCapo: +9%. В Scala другие наборы best practices, другой компилятор, другая стандартная библиотека...