Самая большая ошибка 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. Однако никто не уведомил нашего друга компилятора о подобных договоренностях и я не вижу твердых планов (и никаких сообщений об их потенциале) в этом направлении.

Но что насчет блокировок, я слышу ваш вопрос. Та же история в основном — вы берете блокировку shared объекта и … ничего не происходит, он все еще shared и только CAS является допустимой операцией. При всей своей сложности система типаов D недостаточно умна, чтобы выучить передачу владения и вставить «умные приведения типов» (как Kotlin) или что-то в этом роде.

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

Обмен сообщениями сам по себе (например библиотека std.concurrency) не решают проблему транзитивности — вы все еще приводите типы на стороне приемника (ведь отправитель должен отпустить этот объект, не правда-ли? Владение — снова не отслеживается и не может быть использовано).

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

Увы, нет, все в целом так же — решение в поисках проблемы. И она создают кучу своих проблем:

1. Копия immutable (T) может передаваться как (неявно) head-mutable, но только если это указатель или слайс. Определяемым пользователем типам не везет и это делает написание общего кода корректного относительно const квалификатора прелестной пыткой.
2. Обобщенный код должен использовать const (T) как надтип T и immutable (T). К сожалению это все еще имеет проблему #1.
3. Шаблоны без радикальной предосторожности и Unqual! T повсюду будут инстанцированны до 3x (!) раз. Это может быть причиной почему время компиляции не лучше на рынке (хотя и среди быстрейших, упущенная возможность прямо здесь).
4. inout. Это. Я был с D с 2010-2018 и это было прекрасное безумное приключение, но. Я. Никогда. Полностью. Не понимал. Как inout может работать за приделами простейших (предусмотренных?) примеров. Также имейте в виду, что это смешивается с проблемой #3.
5. Пожалуй единственные типы хорошо работающие с immutable это указатели и массивы, спасибо #1. И честно говоря, простой оберточный тип запрещающий модификацию легко решает этот сценарий, покрывая 80+% применения immutable «в природе».
6. Сделать свои типы дружелюбными к immutable/const это адская боль в заднице и не пройдет достаточно времени прежде, чем ваши пользователи попробуют const blah = YourType (…); и будут громко жаловаться, что вы не поддерживаете корректность относительно const. Реализовывать сложные типы, которые работают с транзитивным const некрасиво и более того это перекладывает нагрузку не на то место. Пользователи должны подвергаться давлению, чтобы использовать const, но не делая жизнь автора библиотеки значительно труднее.

В отличает от транзитивного const поверхностный const (~ final из Java) тривиально применим к любому определенному пользователем типу, практически без какой-либо дополнительной работы со стороны автора библиотеки. Более того, теперь автор может предоставить типы, которые иммутабельны за счет интерфейса (Коллекции! Строки!).

На конференции 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 байт вне зависимости от размера объекта.

Что смотивировало такой дизайн? У меня две гипотезы. Первая это нежелание резервировать память для недостаточно утилизированных пулов, что не является проблемой из-за того как устроена виртуальная память с ленивым выделением ресурсов. Вторая это опасения выделения слишком большого числа пулов, замедляя выделение памяти и что любопытно фазу mark сборщика мусора. Последнее скорее всего и есть причина, поскольку сборщик мусора делает линейный проход по пулам довольно часто и двоичный поиск для каждого потенциального указателя во время фазы mark.

Это подводит нас ко второй ошибке поиск пула за logP, где P число пулов, что делает mark NlogP задачей. Хештаблица могла бы сэкономить изрядное число циклов.

Завершая наш обзор малых пулов мы также рассмотрим выбор классов размера. Это третья проблема (не ошибка, но спорное решение) в выборе степеней двойки, что гарантирует нам вплоть до 50% внутренней фрагментации. Современные аллокаторы такие как jemalloc предоставляют по одному классы между степенями двоек. Деление на константу не степени двойки немного дороже чем один AND, но все же вполне приемлимы по скорости.

Давайте посмотрим на пулы для больших объектов. Первое, что бросается в глаза это то, что гранулярность одна страница памяти — 4кб для метаданных и аллокаций. Ряды свободных страниц связаны в free list, который сканируется линейно для каждой аллокации. Это четвертая ошибка, то есть с производительностью больших аллокаций решили не заморачиваться. Чтобы обнаружить начало объекта поддерживается отдельная таблица, где для каждой страницы хранится индекс начала относящегося к ней объекта. Эта схема кажется разумной пока мы не задумаемся над большими аллокациями 100+ Mb, поскольку почти наверняка не сможет релоцироваться по месту и создаст новый пул, что израсходует впустую огромный объем памяти на мета данные того, что по сути является одним объектом.

Сборка

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