Таксономия

Иногда чтобы можно было понять, чем схожи те или иные объекты исследования, мы вводим таксономию, классификацию. В этом посте я провожу естественную классификацию языков программирования, в 5 уровней от 0 до 4-го. При этом чем выше уровень, тем дальше язык от машинных кодов.

Уровень 4

Это уровень скриптов, простых программ объединяющих несколько других программ или библиотек. Самыми знаковыми являются тройка из LAMP стека — PHP, Perl, Python. Ruby on Rails приобрела широкую популярность, так же Lua, Groovy.

Уровень 3

Управляемые языки, где в основу положена продуманная виртуальная машина. Цель проста — отсутствие багов связанных с нарушением целостности доступа к памяти. Из средств — сборщик мусора и JIT компилятор. Основные языки — Java (JVM) и C# (CLR). Отдельного внимания заслуживает Beam (Erlang), как распределенная виртуальная машина.

Уровень 2

Системные языки с опциональным сборщиком мусора. Таких совсем немного — D и Go, также Nim. Особенность таких языков большая гибкость применения. Компиляция при это AOT.

Самая большая ошибка D — транзитивные квалификаторы

Не стоит заблуждаться, thread-local по умолчанию это замечательно! Но shared должен был быть квалификатором хранения, а static и простые глобальные переменные остались бы неявно с квалификатором хранения thread-local.

Прояснив этот момент, давайте перейдем к моим причинам для утверждения, что транзитивные квалификаторы являются единственной причиной большинства фундаментальных проблем языка D.

Транзитивные квалификаторы взятые вместе с «wildcard» квалификатором inout являются самым большим ломающим изменением при переходе от D1 к D2 с огромными затратами, которые все еще «оплачиваются» тк они дают стабильный поток багов компилятора, хотя и в основном решенный к настоящему моменту. Побочные эффекты транзитивности не только очевидны в пользовательских базах кода, они так же (если не хуже) проникают в виде изменений в компиляторе.

Продвигаемые как требование для поддержки функционального программирования и гарантий чистых (pure) функций. Что ж, давайте разобьем это утверждение. Во-первых я программировал на Scala, часто используемой как «заменитель» Haskel на JVM, при этом многие идиомы прекрасно переносятся. Смотрите на Cats, Scalaz и связанные проекты для примеров пуристического FP на Scala. Здесь как и в других языках, которые я к сожалению не знаю достаточно хорошо, мутабельность решается очень прагматично:

• val это обозначение тип переменной по умолчанию, означающее неглубокий const (непереприсваиваемое)
• var это мутабельное/переприсваиваемоме обозначение, сильно порицаемое инструментами экосистемы (особенно подсвечивается в редакторах и тд)
• коллекции предоставляют иммутабельность через интерфейс — здесь просто нет write/remove операций в API List-а.
• Мутабельные коллекции предоставляют надмножество иммутабельного API
• Структуры по построению состоят из val или var, но case class-ы повседневная сокращенная нотация для просто данных состоит только из val-ов.

Если мы прибавим к этому явный shared квалификатор, финальный гвоздь в гроб багов concurrency — глобальные переменные в основном будут закрыты. В Scala это было бы очень неудобно ввести shared в основном потому, что ей надо бесшовно интегрироваться с Java/JVM и вводить плохо переводимые квалификаторы хранения / поведения вызвало бы расхождение импеданса. D не ограничен подобными соображениями.

Не полностью уничтожены, но с установленными легкими и корректными умолчаниями, а также с остальным языком и инструментарием подталкивающими в правильном направлении это делает 90% работы без ограничения нишевых случаев. Таких как, например, lock-free программирование, которое очень болезненно писать с транзитивным shared в D — никуда не дется от привидения типов к thread-local мутабельным данным. Проблему легко изложить — многие lock-free алгоритмы держаться на идее получения владения чем-то через операцию CAS (или фиксацию ваших локальных изменений). По самому определению она переводит shared в thread-local. Однако никто не уведомил нашего друга компилятора о подобных договоренностях и я не вижу твердых планов (и никаких сообщений об их потенциале) в этом направлении.

На конференции DConf 2017 в хакатоне я вел группу (из 2 человек) занимающуюся druntime — ковырявшуюся в сборщике мусора D. Спустя пару часов я не мог стряхнуть чувство — черт это все неплохо бы переписать. Так что я решил начать задачу построения лучшего сборщика мусора для D. Первая итерация должна быть более быстрым классическим mark-sweep сборщиком.

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

Пулы, пулы повсюду

Если бы мы проигнорировали некоторую глобальную машинерию то сборщик мусора это просто массив пулов. Каждый пул это кусок mmap-нутой памяти + пачка malloc-нутых метаданных таких как таблицы для mark битов, free битов и так далее. Все аллокации происходят внутри пула, если ни один пул не может аллоцировать память, то создается новый пул. Размер пула определяется арифметической прогрессией по числу пулов или 150% размера аллокации, в зависимости от того, что больше.

Любая маленькая аллокация сперва округляется до одной из степеней 2 (класс размера) — 16, 32, 64, 128,256, 512, 1024, 2048.Затем проверяется глобальный freelist для этих классов размеров, если не удается найти мы ищем маленький пул. Этот маленький пул будет аллоцировать новую страницу связывать ее с free list объектов это класса размеров. И тут видна первая ошибка дизайна — класс размера назначается каждой странице, и следовательно нам нужна таблица, которая отражает страницу пула в класс размер (называемой pagetable).

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