Лингвофорум

Часть 8. Простейший escape analysis.

Одна из основных нагрузок на сборщик мусора -- это простые иммутабельные наборы скалярных величин вроде векторов или матриц, оные обычно реализуются в динамических языках через понятие tuple:

class Vector3f { public final int x, y, z; }

В силу их иммутабельности, одна простая операция может порождать десятки однотипных объектов. Несмотря на наличие в сборщике младшего поколения, легко отсеивающего 99% промежуточных объектов, сборка мусора имеет достаточно весомый оверхед: чем больше потоков создаёт объекты, тем чаще происходит малая сборка; а даже малая сборка требует остановки всех потоков, при этом следует трейсить мегабайты дайнных и обновлять ссылки.

Когда автор физического движка JBullet занимался портированием с C++, он столкнулся с проблемой (тогда Java 5 была последней версией): при расчёте физических функций миллионы создаваемых векторов и матриц запускали сборку мусора так часто, что нормальное функционирование физического движка было просто невозможно. Автор решил эту проблемом хаком на уровне перекомпиляции скомпилированного байткода.

В C# это решили введением в виртуальную машину нового подтипа: value type objects, что значительно усложнило реализацию VM.

Чтобы превратить heap allocation в stack allocation, мы должны анализировать, в какие дали утекает ссылка на созданный объект. Если ссылка на объект не утекает дальше текущего метода/потока -- то есть в конечном счёте не может быть потенциально shared между разными потоками -- то объект можно без проблем очень быстро создать в стеке, и при выходе из метода просто "забыть" его. Чтобы анализатор не думал слишком долго -- глубина анализа не должна превышать два метода (текущий и вызываемый из текущего):

1) если из текущего метода (где создан объект) объект утекает в иной метод, то следует анализировать такой иной метод -- но дальше рекурсивно не идти (глубина = 2) и ежли что консервативно помечать "утекшим"
2) если в одном из анализируемых методов на объект используются операции вроде setstaticfield, setobjectfield, throw то объект считается безвозратно "утекшим"
3) если объект утекает в virtual-метод, то объект считается безвозратно "утекшим". Дело в том, что виртуальный метод может быть overriden в подклассе, и его реализация может быть совершенно не предсказуемая -- объект может утекать, а может не утекать -- наш статический анализатор не может предсказать.
4) если ни одно из указанных выше условий не оправдалось, то объект можно выделить "в стеке".

Так вот, мой простейший подход заключается в том, что автор иммутабельных классов должен следовать определённому контракту. Во-первых, чтобы сократить время анализа, анализатор ВООБЩЕ будет игнорировать классы, в которых есть хотя бы одно нескалярное поле. Во-вторых, критичные методы иммутабельного класса должны быть помечены как final и не переопределять родительских методов (т.е. не быть virtual). Поэтому автор иммутабельных классов должен иметь эти условия в виду: если хотя бы одно условие не выполнено, объект будет создаваться не в стеке, а в куче.
Эти условия легко выполнимы для критичных объектов вроде Vector3f или Matrix4f.

Пример объекта, выделяемого в стеке:
class Vector3f {
  public final int x, y, z;
  public final Vector3f add(Vector3f o) { return new Vector3f(x + o.x, y + o.y, z + o.z); }
  /* .. */
}

Проблема возникает при возврате объекта из функции. С одной стороны, объект утекает непонятно куда. С другой стороны, этот метод может быть псевдо-вложен (псевдо-заинлайнен) в родительский метод и желательно было бы иметь возможность возвращать объект через стек.
Что делать? Нужно делать копию тела метода. Если возвращаемый объект доселе был неутекшим, и мы вот-вот его собираемся возвратить -- в таком случае мы должны породить два варианта тела метода: в одном варианте (общий вариант) объект в самом начале выделяется в куче, в другом варианте (частный) он передается в стеке. Линкуем тот или иной вариант, в зависимости от контекста. В примере выше для метода Vector3f.add будет сгенерировано два варианта.

Цитата: Python от февраля 23, 2012, 03:25
сли файл с байт-кодом изменился после последней компиляция, производится повторная компиляция байт-кода в машинный код.

Я же говорю про deployment, то есть конечный продукт, подаваемый пользователю. Там не предполагается, что байткод будет изменяться. JIT по идее нужен только в динамических сценариях, когда невозможно узнать заранее, какие типы будут использоваться (в C# это generic types и System.Reflection.Emit).

ЦитироватьПолная прекомпиляция.

Я бы предпочел не прекомпиляцию при установке (тем более, не всегда есть необходимость в этом ритуале), а JIT-компиляцию с кешированием результатов (кеш хранится на диске, программа, один раз откомпилированная, в следующий раз подгружается из него. Если файл с байт-кодом изменился после последней компиляция, производится повторная компиляция байт-кода в машинный код. Также кеш можно очистить вручную).

Часть 7. Deployment.

User-end виртуальная машина не должна быть system-wide-компонентом, она должна быть настолько менее intrusive, насколько это возможно. Это исключает dll hell, свистопляски с CLASS_PATH и очень переносимо; если по какой-то причине VM сломалась (некорректная версия, баг и т.д.), то перестают работать не все приложения, а только одно. Если ставить на компактность и расширяемость, в таком случае копия виртуальной машины на каждую программу -- не беда, тем более что сейчас не 1996 год и память не проблема. Разумеется, JVM и .NET весят под десятки мегабайт, где громоздкие bloated-библиотеки связаны между собой в большую нераспутываемую гирлянду -- и там такое решение не прокатит. Но если иметь изначально компактный дизайн, то такое возможно -- вспомним, например, Visual Basic -- в нём вся виртуальная машина весила под мегабайт и могла распространяться одним простым dll в папке программы. Лучше и не придумаешь.
(Разумеется, девелоперская версия должна быть system wide.)

Поэтому я бы выделил три стандартных способа deployment:

1. Локальные виртуальные машины -- как описано выше: по виртуальной машине на каждую папку/программу; байткод-библиотеки желательно пострипены от неиспользуемых классов. Но этим мы не ограничиваемся: вводится понятие контейнеров. В Java единственный простой способ запустить программу -- это использовать консоль/ярлык с вызовом программы java.exe, что не совсем красиво (неправильно отображается в списке процессов). В C# используется куда лучший механизм, но он опирается на стандарты Windows, и под Unix всё равно приходится использовать ручной вызов. Так вот, контейнер -- это исполняемый stub-файл целевой платформы (под Windows -- *.exe), который распаковывает байткод и запускает виртуальную машину -- причём и виртуальная машина, и весь байткод могут быть как запакованы внутри контейнера, так и находится вне его.

2. Полная прекомпиляция. Большинство серьёзных программ устанавливаются через installer, и в таком случае не очень понятно, зачем вообще нужен JIT (кроме generic types в C#). Write once, run everywhere легко работает и без JIT'а: во время инсталяции можно делать не только распаковку байткода, но и полную компиляцию в машинный код. Далее байткод нужен только для метаданных; startup программ всегда мгновенный. В gentoo так и делают: при установке компилируют из исходников. И никто особо не нуждается в JIT-компиляции, а один и тот же си-код работает на разных платформах. Единственно что если поменялся процессор, то программа может сломаться. (В таком случае можно проверять процессор и ежли что просить переустановить программу?)

3. API-интерфейс для эмбеддинга в качестве скриптового языка.

Часть 6. Память. Сборка мусора.

По идее, на VM не ставится никаких условий по реализации аллокатора и сборщика мусора. Тем не менее, текущий простенький stop-the-world прототип использует следующий алгоритм:

1. Первоначально, все объекты создаются в малой куче/младшем поколении, с помощью простого bump pointer allocation. Когда поколение переполняется, то происходит малая сборка: сборщик рекурсивно маркирует достижимые объекты (от корней, статических полей, GC references, intergenerational cards и данных стека) и эвакирует достижимые объекты в старшее поколение, попутно обновляя ссылки на них.

Само поколение поделено на два подпространства: память выделяется в одном подпространстве, а при малой сборке эвакуируется в противоположном (и затем они меняются местами) -- это позволяет эвакуировать только те объекты, что пережили хотя бы две малых сборки.

На данный момент используется глобальный мьютекс, что не есть хорошо В будущем надо реализовать как-нибудь lock-free TLAB'ы.

2. Итак, после того, как объект пережил две сборки в малой куче, он эвакуируется в большую кучу/старшее поколение -- до тех пор, пока сама большая куча не будет переполнена, в таком случае происходит уже большая сборка. В отличие от малой, большая куча допускает фрагментацию, так как для увеличения скорости она никогда не будет компактироваться (ну что такое менять указатели в 1 гигабайте?). Здесь пока я в раздумьях насчёт конкретной реализации, пока что не реализовал -- главное тут уметь быстро эвакуировать, чтобы сократить время малых сборок.

3. Есть также системная память VM. Здесь хранятся внутренние структуры VM и GC, классы, тела методов. Проще говоря: здесь хранятся объекты C++, выделенные с помощью new. Здесь не надо заморачиваться.

4. Память под fixed-объекты и Очень Большие Объекты (LOH). Зависит от реализации менеджера памяти. Так как в моей реализации старшее поколение не является moving, то и fixed/LOH мы можем выделять сразу прямиком в старшем поколении.

Объекты из старшего поколения могут быть корнями для объектов из младшего поколения, но при малой сборке контр-продуктивно трейсить всю большую кучу. Поэтому VM использует понятие intergenerational-ссылок. При каждом store/load поля объекта, а так же при эвакуации, VM вставляет read/write-барьеры, которые проверяют условие: стал ли текущий объект ссылаться извне своего поколения? Если условие верно, то тогда используется схема под названием card marking. Старшее поколение имеет ещё дополнительный битмап: interGenBitmap. Каждые 1024 (например) байтов  индексируются одним байтом (не битом -- для скорости). Если существует intergenerational-ссылка в данном сегменте, то байт поставлен в 1, и наоборот. При малой сборке мусора данные сегменты целиком регистрируются как корни, что гораздо уменьшает диапазон поиска по сравнению с трейсингом всей кучи.

Часть 5. Safepoints, native access и fixed-объекты.

Сборщик мусора пока что находится в стадии прототипирования, о нём потом. Здесь я поговорю о safepoints. Safepoint это состояние потока, когда он может быть безопасно остановлен. Если реализовать SovietVM через интерпретацию, то вставка safepoints проста -- например, через каждые N инструкций поток сигнализирует о том, что он находится в safepoint.

Зачем они нужны? Чтобы сборщик мусора мог безопасно остановить все VM-потоки перед самой сборкой. Когда VM соображает, что памяти тю-тю, она устанавливает глобальное событие stopThreads. Каждый поток через каждые N инструкций проверяет сие событие и сам себя приостанавливает, если флаг события равен true. Сам же поток, вызвавший сборку мусора, сидит и ждёт, пока все VM-потоки не перейдут в режим suspended.

Такой подход гарантирует целостность состояния в том смысле, что при остановке каждый поток находится между двумя байткод-инструкциями, а не посередине их исполнения, т.е. любой отдельно взятый объект на куче целостен.

Проблема возникает с native access. Если поток в данный момент находится в native call, то вставить safepoint уже не получится. Что если native-вызов - блокирующий, например Thread.sleep? Сборщик мусора не может ждать несколько секунд. Решение такое: если поток находится в native, то мы должны проигнорировать его, с условием что по выходу из native call поток должен сразу перейти в safepoint.

Но из такого решения вылазит ещё одна проблема. Если разрешить native-потоку трогать VM-кучу, то нативный мутатор может оставить кучу в нестабильном состоянии, а сам native-код будет крашиться, потому что все указатели вдруг переместились (после сборки). Что делать? Разумное и простое решение, которое я пока вижу: ввести в VM специальное понятие fixed-объектов. Эти объекты выделяются вне куч, гарантируются быть непередвигаемыми и т.д. В C# эту проблему решили с помощью object pinning, но оно фрагментирует кучу (даже nursery!) и усложняет сборку. А в Java классы вроде direct buffers итак выделяются вне обычной кучи и не двигаются.

Но в отличие от Java, мы вводим это понятие в само ядро VM -- объект любого класса может выделен как moving или как fixed, а также конвертирован туда-обратно. В C# подобное тоже делается во время маршалинга (например, строк), однако оно почти никак не контролируется и спрятано от программиста, а также мы не можем кешировать результаты/буферы, из-за чего память для одного объекта может выделяться и конвертироватся туда-сюда по N раз, что есть плохо.

Native call'ы должны принимать в качестве аргументов только fixed-объекты; в ином случае -- автоматически конвертировать non-fixed-объект в fixed-объект.

Язык, целиком и полностью поддерживающий SovietVM, должен располагать синтаксисом вроде new fixed int[10].

Я думаю, чтобы радикально упростить сборку мусора, мы можем запретить fixed-объектам иметь какие-либо by-reference-поля. Пусть это лучше будет intptr, с ручным маршалингом через что-то вроде vm.Object vm.Native.ptrToObject(intptr, vm.Class). В таком случае сборщику мусора можно не сканировать fixed-объекты вообще.

Если же надо реализовать (в low level VM-расширениях) какие-то более заковыристые случаи, то рекомендуется использовать glue-библиотеку. API уже имеет немного функционала. Напр. само по себе GCReference даёт нам WeakReference, а GCReference + GC::registerRoot позволяет нам хранить, изменять и проч. moving-объекты даже изнутри С-кода.

Часть 4. Атрибуты.

Атрибуты эта метаинформация, embedded в определения классов, полей, методов.
Атрибуты в первую очередь служат в помощь компилятору целевого языка, они в целом игнорируются ядром. Но по сравнению с C#/Java, мы значительно расширяем их узус.

Конструкторы. С точки зрения VM, конструктор это рядовая функция инициализации, которая вызывается аккурат после выделения памяти под объект. Чтобы VM-язык мог отличить конструктор от рядовой функции, функция инициализации помечается специальным атрибутом. Этот маркер используется только компилятором, а сама виртуальная машина не делает никаких рантайм-проверок и ничего не знает ни о каких "конструкторах":

@Constructor
public void init() { }


Все подобные атрибуты выведены за пределы ядра.

Generics. VM не поддерживает generics напрямую (в отличие от C#), ибо полноценная реализация generics находилась бы в противоречии с системой типов и заявленным минимализмом. Однако целевой язык волен делать проверки типов в compile-time (как в Java). Атрибуты в данном контексте мы можем использовать, чтобы явно пометить type parameters в интерфейсе (чтобы красиво было видно в API reference).

Свойства. Свойства это всего лишь getter- и setter-методы с няшным синтаксисом. Поэтому нет смысла добавлять их поддержку напрямую в VM (как сделали в CLR) -- пусть это будет просто атрибут, compiler hint:


@PropertyGetter("x")
public int getX() { return x; }


Сюда же: события, throws clause и т.д.

Под сомнением, должны ли поддерживаться напрямую или быть атрибутами: access modifiers (public, private, etc.), final (== sealed || const) ?

By-value типы. С помощью атрибутов можно эмулировать by-value-типы в C#. Напр., реализация C# вольна помечать такие классы атрибутом @Struct. Store/load объектов всех классов, помеченных этим атрибутом, компилятор C# тогда будет осуществлять, напр., с помощью метода obj.clone(). Если VM реализует escape analysis вкупе с inlining, то оверхед будет не сильно большой.

И что самое здесь прекрасное, так это то, что языки, которые напр. не поддерживают свойства, могут просто игнорировать эти атрибуты и искренне думать, что свойство это очередной метод.

Цитата: Python от февраля 14, 2012, 00:14
Я бы вынес абстракцию знака за пределы базовых примитивных типов, просто добавив отдельные операции для знакового и беззнакового сравнения и некоторые другие действия. Разграничение типов по знаковости — забота не VM, а языка. Так же, как и разграничение символов и чисел.

Согласен, так и предполагается в моей VM, однако минималистическая VM типа моей не должна иметь специальных unsigned-операций. Вы правильно сказали, что это забота языка, поэтому именно язык, поддерживающий unsigned-значения, должен эмулировать unsigned-поведение (имеющимся ограниченным набором байткод-инструкций), а не VM должна иметь особые add.unsigned и add.signed.

Да, это непроизводительно, но это проблема JIT'а (или интерпретатора), он должен быть настроен так, чтобы находить такие паттерны и замечательно их оптимизировать.

Цитата: Python от февраля 14, 2012, 00:08
В сишнике как-то обходились без.

Потому что си слабо типизированный. В современном языке использовать всё что угодно в качестве boolean logic — моветон. Байткод и метаданные должны иметь чётко определённые логические операции и интерфейсы, для простоты и изящества. Мне так кажется. Если у вас есть серьёзные аргументы против, то всегда можно использовать typedef'ы (уже вне ядра, правда будет проблема с ExtendedTypes )

Цитата: Python от февраля 14, 2012, 00:10
Тяжеловато получится, мне кажется.

Да не очень. В Java, например, все вызовы ByteBuffer.put/ByteBuffer.get суть intrinsic и компилируются в простые машинные инструкции чтения/записи в память. Правда, у меня такого не получится (ByteBuffer живёт вне ядра и недосягаем для таких оптимизаций), но для современных систем не беда заинлайнить подобные вызовы: ведь что такое ByteBuffer.get? Это просто нахождение нужного int и немного bit shuffling-магии.

Самый главный предполагаемый вами оверхед - это маршаллинг между VM и нативным кодом (теми самыми си-функциями fread/fwrite, что реально читают из файла, например), так тут наоборот просто идиллия: можно скармливать си-коду сразу внутренний int[] (по ссылке), и это прокатит, ведь для нативного кода нет разницы: int* или byte*. Для него это просто последовательный набор байтов.

ЦитироватьБолее того, в Java тип byte - знаковый, что является полным маразмом и дискредитацией наличия этого типа в системе типов.

Я бы вынес абстракцию знака за пределы базовых примитивных типов, просто добавив отдельные операции для знакового и беззнакового сравнения и некоторые другие действия. Разграничение типов по знаковости — забота не VM, а языка. Так же, как и разграничение символов и чисел.