США, Техас, Остин, клуб Continental
Воскресенье, 5 января 1987 г.

Спасибо за приглашение, мистер Ломуто. Скоро я возвращаюсь в Англию, так что это было очень вовремя.

Спасибо, что согласились со мной встретиться, мистер сэр Чарльз Энтони Ричард Хоар. Это большая честь для меня. Я даже не знаю, как к вам обращаться. У вас есть рыцарский титул?

Зовите меня Тони, и если вы позволите, я буду называть вас Нико.

На первый взгляд обычная картина: два человека наслаждаются виски. Однако внимательному наблюдателю открываются интригующие подробности. Прежде всего напряжение, которое можно было резать ножом.

Одетый в безупречно подогнанный костюм-тройку с нарочитой небрежностью, на какую способен только англичанин, Тони Хоар был таким же воплощением Британии, как и чашка чая. Смиренное выражение лица, с которым он попивал из своего стакана, без всяких слов выражало его мнение в споре между бурбоном и скотчем. Сидевший напротив Нико Ломуто представлял полную ему противоположность: одетый в джинсы программист, мешавший виски с колой (что для Тони было настолько возмутительно, что он сразу решил подчёркнуто это игнорировать как резкий запах пота или оскорбительную татуировку), в состоянии расслабленного трепета перед гигантом информатики, с которым он только что познакомился лично.

Послушайте, Тони, сказал Нико после того, как иссякли темы для обычной лёгкой беседы. По поводу того алгоритма разбиения. Я даже не собирался его публиковать...

Что? Ах да, алгоритм разбиения, Тони поднял брови в притворном изумлении, словно забыв, что каждая статья или книга о быстрой сортировке за последние пять лет упоминала их имена вместе. Очевидно, что именно это связывало этих двух людей и было причиной этой встречи, но Тони, как безупречный джентльмен, мог бы часами говорить о погоде, если бы собеседник не упомянул о стоящем в комнате розовом слоне.

Да, тот самый алгоритм разбиения, который постоянно вспоминают в связи с вашим, продолжал Нико. Я не большой теоретик в области алгоритмов. Я работаю над Ada, и всю эту штуку с разбиением придумал только для развлечения. Но что меня беспокоит, говорил Нико непринуждённым тоном человека, которому нечего скрывать, что этот алгоритм ничем не лучше. Моя схема разбиения всегда делает столько же сравнений и по крайней мере столько же обменов, сколько и ваша. В худшем случае мой алгоритм делает n дополнительных обменов n! Я не понимаю, почему его продолжают вспоминать. Я уже ничего не могу с этим сделать. Я не знаю, какие каким алгоритмам стоит учить студентов. Это как сортировка пузырьком. Каждый раз, когда кто-то упоминает быструю сортировку, в аудитории обязательно оказывается какой-то пустоголовый (или пузырькоголовый?) болван, который скажет: а я ещё слышал про сортировку пузырьком. У меня от этого кровь вскипает.

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

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

Я понимаю, Нико. Но подумайте вот о чём. Ваш алгоритм прост и постоянен, двигается в одном направлении и делает по крайней мере один обмен каждый шаг. Возможно, в будущем появятся машины, которые...

Неважно, какая машина: меньшее количество обменов всегда лучше, чем большее. Это просто здравый смысл, категорически возразил Нико.

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

Согласен. Хорошее место. Скоро должна начаться живая музыка в стиле кантри.

Прелестно, к собственному изумлению Тони выдавил вежливую улыбку.

США, Массачусетс, Честнат-Хилл
Наши дни

Многие годы я живу с тщательно скрываемой зависимостью от проблем сортировки. Скрыть её было нетрудно: нездоровый интерес к вопросам сортировки социально приемлемая форма профессиональной деформации. Уверен, что немало программистов потратили одну или две бессонных ночи, чтобы попробовать ещё одну идею сортировки, которая уж точно окажется лучше всех остальных. Потому никто не повёл бровью, когда ещё в 2002 году я написал о сортировке. (Слышали про fit pivot? Конечно же не слышали). Никто не стал вмешиваться, когда я разработал функцию std.sort в D, которая, как оказалось, в некоторых случаях выдавала квадратичную сложность (с тех пор это, к счастью, исправлено). Никто не поднял шума даже когда я написал научную статью о задаче выбора (которая рука об руку идёт с задачей сортировки), будучи независимым участником конференции, чем впечатлил даже организаторов. И даже мой доклад о сортировке на CppCon 2019 не вызвал публичного скандала. Программисты свои люди, они всё понимают.

Я стараюсь соблюдать воздержание. Как там говорят, жить по одному дню? Но всё же я почувствовал внутри себя волнение, когда увидел заголовок одной недавней статьи: Ошибки в предсказании переходов не затрагивают сортировку слиянием (Branch Mispredictions Dont Affect Mergesort). Какое заманчивое название. Для начала: а что, ошибки в предсказании переходов должны были затрагивать сортировку слиянием? Я понятия не имел, главным образом потому что все вплоть до вашей бабушки используют быструю сортировку, так что сортировка слиянием никогда не попадала в поле моего внимания. Но слушайте, мне об этом даже не нужно волноваться, потому что заголовок говорит, что проблема, о существовании о которой я даже не знал, вовсе не является проблемой. Так что в этом смысле заголовок сам себя отменяет. Но я всё же прочитал статью (и вам тоже советую), и помимо многих других интересных вещей кое-что особенно зацепило моё внимание: схема разбиения Ломуто рассматривалась как серьёзный соперник повсеместно используемому разбиению Хоара с точки зрения эффективности. Эффективности!

Оказывается, современные компьютерные архитектуры иногда действительно идут наперекор здравому смыслу.

Разбить, быть может, отсортировать

Давайте быстро пройдёмся по двум схемам разбиения. Разить массив значит организовать элементы так, чтобы все элементы, меньшие или равные опорному элементу, были слева от него, а элементы, большие или равные ему, справа. Окончательная позиция опорного элемента должна быть на границе разбиений. (Если есть несколько равных опорных элементов, то окончательная позиция может разниться, из чего вытекают практические последствия, но в данной дискуссии можно принять, что все значения в массиве уникальны).

Схема разбиения Ломуто проходится по массиву слева направо, сохраняя индексы чтения и записи, начинающиеся 0. Каждый считываемый элемент сравнивается с опорным: если он больше, то он пропускается (позиция чтения переходит на шаг вперёд). В противном случае значение под индексом чтения меняется местами со значением под индексом записи, и оба индекса передвигаются на шаг вперёд. Когда чтение закончено, индекс записи определяет место разбиения. В качестве иллюстрации анимация ниже (сделано пользователем Википедии под ником Mastremo, используется без изменений согласно лицензии CC-BY-SA 3.0).

Проблема с разбиением Ломуто в том, что оно может делать ненужные обмены. Возьмём экстремальный случай, когда только самый первый слева элемент больше опорного. Каждая итерация алгоритма будет неуклюже перемещать этот элемент на одну позицию вправо, подобно, эм, сортировке пузырьком.

Схема разбиения Хоара элегантно решает эту проблему, итерируя массив с двух сторон двумя парами индексов чтения и записи. Алгоритм пропускает элементы, которые уже находятся в положенных местах (слева меньше, справа больше) и меняет местами только меньший элемент слева с большим элементом справа. Когда индексы встречаются, массив разбит вокруг места встречи. Большинство современных реализаций быстрой сортировки используют разбиение Хоара, по очевидным причинам: оно делает столько же сравнений, что и разбиение Ломуто, и меньше обменов.

Учитывая, что разбиение Хоара очевидно делает меньше работы, чем разбиение Ломуто, возникает вопрос, зачем тогда вообще учить студентов последнему. Александр Степанов создатель STL написал отличную статью о разбиении и привёл аргумент об обобщённости: для разбиения Ломуто достаточно итерирования в одну сторону, тогда как разбиение Хоара требует двунаправленного итерирования. Это ценная мысль, хотя её практическая ценность невелика: да, вы можете использовать разбиение Ломуто на односвязных списках, но обычно разбиение делают ради быстрой сортировки, а для односвязных списков быстрая сортировка плохой выбор, здесь лучше подойдёт сортировка слиянием.

И всё же существует очень практичный и очень неожиданный довод в пользу разбиения Ломуто, и в нём заключается гвоздь всей статьи: если реализовать разбиение Ломуто без ветвления, то на случайных данных оно становится намного быстрее разбиения Хоара. Учитывая, что быстрая сортировка большую часть времени тратит на разбиение, то это сулит нам солидный выигрыш в производительности быстрой сортировки (да, я говорю об индустриальных реализациях в стандартных библиотеках в C++ и D), если мы заменим алгоритм разбиения на тот, который буквально делает больше работы.

Вы всё правильно прочитали.

Время расчехлить код

Давайте посмотрим на аккуратную реализацию разбиения Хоара. Чтобы исключить все лишние подробности, код в этой статье написан для типа long в качестве элемента и использует простые указатели. Он компилируется и работает одинаково что в C++, что в D. Код в этой статье останется универсальным для обоих языков, поскольку исследовательская литература часто использует в качестве стандарта std::sort из C++.

/**Partition using the minimum of the first and last element as pivot.Returns: a pointer to the final position of the pivot.*/long* hoare_partition(long* first, long* last) {    assert(first <= last);    if (last - first < 2)        return first; // nothing interesting to do    --last;    if (*first > *last)        swap(*first, *last);    auto pivot_pos = first;    auto pivot = *pivot_pos;    for (;;) {        ++first;        auto f = *first;        while (f < pivot)            f = *++first;        auto l = *last;        while (pivot < l)            l = *--last;        if (first >= last)            break;        *first = l;        *last = f;        --last;    }    --first;    swap(*first, *pivot_pos);    return first;}

Возможно, выбор опорного элемента покажется вам странным, но не волнуйтесь: обычно используется более сложная схема (например, медиана трёх значений), но для основного цикла важно лишь, чтобы опорный элемент не было самым большим элементом массива. Это позволит основному циклу опустить некоторые проверки без риска выйти за пределы массива.

Эффективность этой реализации заслуживает многих похвал (и вероятно, именно такой код, с минимальными отличиями, вы увидите в стандартных библиотеках C++ и D). По этому коду видно, что его написали люди, которые ничего в своей жизни не делают просто так. Люди, которые аккуратно стригут ногти, приходят когда обещают прийти и регулярно звонят маме. Они делают упражнения ушу каждое утро и не дают ни одному циклу компьютера уйти впустую. В этом коде нет ни одной торчащей нитки. Генерируемый ассемблер исключительно ёмок и почти одинаков для C++ и D. Отличия есть только между бэкендами: LLVM (clang и ldc) показывает небольшое преимущество по размеру перед gcc (g++ и gdc).

Изначальная реализация разбиения Ломуто, показанная выше, хорошо подходит для объяснения, но с точки зрения эффективности слишком небрежна:

/**Choose the pivot as the first element, then partition.Returns: a pointer to the final position of the pivot. */long* lomuto_partition_naive(long* first, long* last) {    assert(first <= last);    if (last - first < 2)        return first; // nothing interesting to do    auto pivot_pos = first;    auto pivot = *first;    ++first;    for (auto read = first; read < last; ++read) {        if (*read < pivot) {            swap(*read, *first);            ++first;        }    }    --first;    swap(*first, *pivot_pos);    return first;}

Начать с того, что этот код будет делать слишком много бессмысленных обменов (обменов элемента массива с самим собой), если несколько элементов слева окажутся больше опорного элемента. Всё это время first будет равно write, и менять местами *first с *write будет пустой тратой времени. Давайте исправим это, добавив предварительный цикл, который будет пропускать неинтересное начало массива:

/**Partition using the minimum of the first and last element as pivot. Returns: a pointer to the final position of the pivot.*/long* lomuto_partition(long* first, long* last) {    assert(first <= last);    if (last - first < 2)        return first; // nothing interesting to do    --last;    if (*first > *last)        swap(*first, *last);    auto pivot_pos = first;    auto pivot = *first;    // Prelude: position first (the write head) on the first element    // larger than the pivot.    do {        ++first;    } while (*first < pivot);    assert(first <= last);    // Main course.    for (auto read = first + 1; read < last; ++read) {        auto x = *read;        if (x < pivot) {            *read = *first;            *first = x;            ++first;        }    }    // Put the pivot where it belongs.    assert(*first >= pivot);    --first;    *pivot_pos = *first;    *first = pivot;    return first;}

Теперь функция выбирает в качестве опорного меньший из первого и последнего элементов, прямо как hoare_partition. Я также сделал ещё одно небольшое изменение: вместо функции swap будем использовать явное присваивание. Оптимизатор позаботится обо всём автоматически, зато мы более чётко увидим сравнительно дорогие операции над элементами массива. Теперь к интересной части. Сфокусируемся на основном цикле:

for (auto read = first + 1; read < last; ++read) {    auto x = *read;    if (x < pivot) {        *read = *first;        *first = x;        ++first;    }}

Подумаем о статистике. В этом цикле две проверки условия: read < last и x < pivot. Насколько они предсказуемы? Что ж, первая из них чрезвычайно предсказуема: можно с надёжностью предсказать, что результат всегда будет истинным, и мы ошибёмся только один раз вне зависимости от размера массива. Разработчики компиляторов и проектировщики железа об этом знают и планируют самый быстрый путь, исходя из предположения, что цикл будет продолжаться. (Идея подарка для вашего друга инженера из Intel: дверной коврик с надписью Переход назад всегда будет выполнен). Процессор начнёт выполнять следующую итерацию цикла ещё до того, как определит, должен ли цикл продолжаться. Лишняя работа будет выброшена только один раз в конце цикла. В этом заключается магия спекулятивного выполнения.

Со второй проверкой x < pivot всё не так радужно. Со случайными данными и случайно выбранным опорным элементом результат может быть любым с равной вероятностью. Это значит, что спекулятивное выполнение здесь не поможет, что очень плохо для производительности. Насколько плохо? В архитектурах с многоступенчатыми конвейерами (а на сегодняшний день они все такие) ошибка предсказания означает, что работу, проделанную несколькими стадиями конвейера, придётся выбросить, и этим мы запустим пузырёк бесполезности через весь конвейер (представьте пузырьки воздуха в садовом шланге). Если этих пузырьков станет слишком много, цикл будет выдавать только часть от достижимой производительности. Как покажут измерения, одно лишнее предсказание забирает около 30% потенциальной скорости.

Как нам исправить эту проблему? Вот идея: вместо того, чтобы принимать решения, контролирующие ход выполнения, мы напишем код прямолинейно и оформим решения как целые числа, которые будут направлять данные при помощи аккуратной индексации. Готовьтесь: нам придётся делать глупые вещи. Например, каждую итерацию вместо того, чтобы в зависимости от условия делать либо две записи, либо ноль, мы будем делать ровно две записи независимо ни от чего. Если записи не требуются, мы будем перезаписывать данные в памяти их собственными значениями (я говорил про глупые вещи?). Чтобы подготовить к этому код, перепишем его следующим образом:

for (auto read = first + 1; read < last; ++read) {    auto x = *read;    if (x < pivot) {        *read = *first;        *first = x;        first += 1;     } else {        *read = x;        *first = *first;        first += 0;     }}

Теперь обе ветви в цикле практически одинаковы, не считая данных. Код всё ещё корректен (хоть он и странный), потому что ветвь else впустую переписывает *read и *first самими собой. Как нам объединить две ветви? Чтобы сделать это эффективно, придётся немного подумать и поэкспериментировать. Увеличить first на единицу в зависимости от условия несложно: first += x < pivot. Проще простого. Справиться с двумя записями в память уже труднее, но основная идея в том, чтобы взять разницу между указателями и использовать индексацию. Вот получившийся код. Потратьте минуту, чтобы его осмыслить:

for (; read < last; ++read) {    auto x = *read;    auto smaller = -int(x < pivot);    auto delta = smaller & (read - first);    first[delta] = *first;    read[-delta] = x;    first -= smaller;}

Перефразируя крылатое латинское выражение, explanatio longa, codex brevis est. Краток код, объяснение длинно. Инициализация smaller через -int(x < pivot) выглядит странно, но для неё есть хорошая причина: smaller можно использовать и как целое (0 или 1) для обычной арифметики, и как маску со значением 0x0 или 0xFFFFFFFF (то есть все биты выставлены либо на 0, либо на 1) для побитовых операций. Мы будем использовать эту маску, чтобы пропустить или не пропустить другое целое при вычислении delta. Если x < pivot, то smaller это все единицы, и delta инициализируется как read - first. Далее delta используется в first[delta] и read[-delta] на самом это деле просто синтаксический сахар для *(first + delta) и *(read - delta). Если заменить delta в этих выражениях, получим соответственно *(first + (read - first)) и *(read - (read - first)).

Последняя строчка first -= smaller тривиальна: если x < pivot, то отнять от first 1, что то же самое, что и увеличить first на 1. В противном случае отнять от first 0, что не окажет никакого эффекта.

Если заменить x < pivot на 1, то вот что происходит в теле цикла:

auto x = *read;int smaller = -1;auto delta = -1 & (read - first);*(first + (read - first)) = *first;*(read - (read - first)) = x;first -= -1;

Почти по волшебству две операции над указателями упрощаются до *read и *first, так что два присваивания складываются в обмен (не забывайте, что x только что инициализировали значением *read). Это именно то, что мы делали в ветви if в первоначальной версии!

Если x < pivot ложь, то delta инициализируется нулём, и тело цикла работает так:

auto x = *read;int smaller = 0;auto delta = 0 & (read - first);*(first + 0) = *first;*(read - 0) = x;first -= 0;

На этот раз всё проще: *first и *read переписывается самими собой, а с first ничего не происходит. Весь этот код ничего не делает, и это как раз то, что нам было нужно.

Теперь посмотрим на всю функцию:

long* lomuto_partition_branchfree(long* first, long* last) {    assert(first <= last);    if (last - first < 2)        return first; // nothing interesting to do    --last;    if (*first > *last)        swap(*first, *last);    auto pivot_pos = first;    auto pivot = *first;    do {        ++first;        assert(first <= last);    } while (*first < pivot);    for (auto read = first + 1; read < last; ++read) {        auto x = *read;        auto smaller = -int(x < pivot);        auto delta = smaller & (read - first);        first[delta] = *first;        read[-delta] = x;        first -= smaller;    }    assert(*first >= pivot);    --first;    *pivot_pos = *first;    *first = pivot;    return first;}

Красиво, правда? Ещё более красив сгенерированный код: взгляните на clang/ldc и g++/gdc. Опять же, между бэкендами наблюдается небольшая разница.

Эксперименты и результаты

Весь код доступен здесь: https://github.com/andralex/lomuto.

Чтобы устроить честное сравнение двух схем разбиения, я написал реализацию быстрой сортировки, поскольку именно для неё чаще всего используется разбиение. Для простоты я опустил некоторые детали, присутствующие в индустриальных имплементациях быстрой сортировки, нужные для данных с разными характеристиками (частично отсортированные в прямом или обратном порядке, с локальными паттернами, со множеством дубликатов). Библиотечные реализации тщательно выбирают опорный элемент, обычно из 39 элементов, иногда с рандомизацией. Они умеют определять проблемные вводные данные и избегать их, обычно с помощью интроспективной сортировки.

Наш бенчмарк для простоты проводит тест только на случайных данных, и опорный элемент выбирается просто как меньшее значение из первого и последнего элементов. Репрезентативность при этом не страдает: более качественный выбор опорного элемента и добавление интроспекции делаются одинаково вне зависимости от метода разбиения. Наш главный интерес сравнить производительность Хоара, Ломуто и версии Ломуто без ветвления.

Графики ниже показывают время, затраченное на одну сортировку в зависимости от объёма входных данных. Используемая машина: Intel i7-4790 на частоте 3600МГц с иеархией кэша 256Кб / 1Мб / 8Мб, работающий под Ubuntu20.04. Все билды были настроены на максимальную скорость (-O3, без проверок assert и проверок границ массивов в D). Входные данные псевдослучайная последовательность значений типа long с одинаковым зерном для всех языков и платформ. Для устранения шума были взяты минимальные значения за несколько эпох.

Ниже показаны результаты для языка D, включая std.sort из стандартной библиотеки в качестве базовой величины.

Ниже показаны результаты для C++. Опять же, для сравнения взята функция std::sort из стандартной библиотеки.

Важная метрика эффективность использования CPU, которую Intel VTune показывает в виде диаграммы-воронки. VTune выдаёт очень подробные отчёты, но диаграмма-воронка наглядно показывает, на что уходит работа. Чем уже выход (справа), тем медленнее выполняется программа по сравнению с её возможным потенциалом.

Диаграммы ниже соответствуют разбиению Хоара, разбиению Ломуто (в традиционной реализации) и разбиению Ломуто без ветвления. Первые два выбрасывают примерно 30% всей работы из-за ошибок предсказания. По сравнению с ними версия разбиения Ломуто без ветвления почти ничего не выбрасывает, что позволяет ей быть эффективнее несмотря на большее количество записей в память.

Диаграмма-воронка для разбиения Хоара. Значительная часть работы проделана впустую из-за ошибок предсказания переходов.

Диаграмма-воронка для традиционной реализации разбиения Ломуто. Примерно столько же ошибок предсказания переходов, что и в разбиении Хоара.

Диаграмма-воронка для реализации разбиения Ломуто без ветвления. Практически ничего не уходит впустую из-за ошибок предсказания переходов, что даёт гораздо большую эффективность.

Обсуждение

Четыре версии (два языка помноженные на два бэкенда) показывают слабые отличия из-за различиях в реализации стандартных библиотек и в бэкендах. Не вызывает удивления, что незначительные различия в генерируемом коде могут создавать измеряемую разницу в скорости выполнения.

Как и ожидалось, обычная версия разбиения Ломута показывает себя хуже, чем разбиение Хоара, особенно на большом объёме входных данных. И то, и то, находятся в одной лиге, когда идёт речь о реализации функции сортировки в стандартной библиотеке. Однако версия разбиения Ломуто без ветвления побеждает с большим отрывом вне зависимости от платформы, бэкенда и объёма входных данных.

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

Что касается сортировки, то Ломуто определённо возвращается, и его стоит принимать в расчёт тем, кто разрабатывает индустриальные реализации быстрой сортировки на архитектурах со спекулятивным выполнением.

Благодарности

Большое спасибо Amr Elmasry, Jyrki Katajainen и Max Stenmark за их вдохновляющую статью. Мне пока не удалось написать реализацию сортировки слиянием (основной результат их статьи), который мог бы поспорить с описанной здесь быстрой сортировкой, но я над этим работаю. (Да простит меня Общество анонимных сортировщиков Я опять сорвался). Также хочу поблагодарить Майкла Паркера и всех авторов комментариев к оригинальной публикации за то, что исправили многие мои языковые косяки английский для меня не родной. (Как обычно говорят: pretend not to notice или pretend to not notice? Каждый раз забываю). И конечно, основная заслуга принадлежит Нико Ломуто, который придумал алгоритм, который не просто прошёл проверку временем он его опередил.

Уолтер Брайт великодушный пожизненный диктатор языка программирования D и основатель Digital Mars. За его плечами не один десяток лет опыта в разработке компиляторов и интерпретаторов для нескольких языков, в числе которых Zortech C++ первый нативный компилятор C++. Он также создатель игры Empire, послужившей основным источником вдохновения для Sid Meiers Civilization. Данная публикация первая в серии статей о режиме Better C в языке D.

Язык D был с самого начала спроектирован так, чтобы легко и напрямую обращаться к C и, в меньшей степени, C++. Благодаря этому в нём доступны бесчисленные C-библиотеки, стандартная библиотека C и конечно же системные API, которые как правило построены на API языка C.

Но C это не только библиотеки. На C написаны многие большие и неоценимо полезные программы, такие как операционная система Linux и значительная часть программ для неё. И хотя программы на D могут обращаться к библиотекам на C, обратное неверно. Программы на C не могут обращаться к коду на D. Невозможно (или по крайней мере очень сложно) скомпилировать несколько файлов на D и слинковать их в программу на C. Проблема в том, что скомпированные файлы на D могут обращаться к чему-то, что существует только в рантайме D, а добавлять его в линковку обычно оказывается непрактично (рантайм довольно объёмный).

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

Так было до тех пор, пока не появился Better C.

Это всё уже было, идея не новая. Бьёрн Страуструп в 1988 году написал статью под названием A Better C. Его ранний компилятор C++ мог компилировать код на C почти без изменений, и можно было начать использовать возможности C++ тут и там, где это имело смысл не жертвуя существующими наработками на C. Это была блестящая стратегия, обеспечившая ранний успех C++.

Более современный пример Kotlin, в котором использовался другой подход. Синтаксически Kotlin не совместим с Java, однако он обеспечивает двустороннее взаимодействие с существующими Java-библиотеками, что позволяет постепенно мигрировать с Java на Kotlin. Kotlin действительно улучшенная Java, и его успех говорит за себя.

D как улучшенный C

D использует кардинально другой подход для создания улучшенного C. Это не надстройка над C, не надмножество С, и он не тащит за собой давние проблемы C (такие как препроцессор, переполнение массивов и т.д.). Решение D это создание подмножества языка D, из которого убраны возможности, требующие инициализирующего кода и рантайма. И сводится оно к опции компилятору -betterC.

Остаётся ли урезанная версия D языком D? На это не так просто ответить, и на самом деле это лишь вопрос личных предпочтений. Основная часть языка остаётся на месте. Однозначно остаются все свойства, аналогичные C. В результате мы получаем язык, промежуточный между C и D.

Что убрано

Очевидно, что убран сборщик мусора, а вместе с ним возможности, которые от него зависят. Память всё ещё можно выделять точно так же, как и в C: при помощи malloc или собственного аллокатора.

Классы C++ и COMвсё ещё будут работать, но полиморфные классы D нет, поскольку они полагаются на сборщик мусора.

Исключения, typeid, статические конструкторы и деструкторы модулей, RAII и юниттесты убраны. Но возможно, мы придумаем, как их вернуть.

На сегодняшний день в Better C уже стали доступны RAII и юниттесты. (прим. пер.)

Проверки assert изменены, чтобы использовать библиотеку C вместо рантайма D.

(Это неполный список, см. спецификацию Better C).

Что осталось

Гораздо более важно, что может предложить Better C по сравнению C?

Программистов на C в первую очередь могут заинтересовать безопасность доступа к памяти в виде проверок границ массивов, запрет на утечку указателей из области видимости и гарантированная инициализация локальных переменных. Далее следуют возможности, которые ожидаются от современного языка: модульность, перегрузка функций, конструкторы, методы, Юникод, вложенные функции, замыкания, выполнение функций на стадии компиляции (Compile Time Function Execution, CTFE), генератор документации, продвинутое метапрограммирование и проектирование через интроспекцию (Design by Introspection, DbI).

Генерируемый код

Возьмём следующую программу на С:

#include <stdio.h>int main(int argc, char** argv) {    printf("hello world\n");    return 0;}

Она скомпилируется в:

_main:push EAXmov [ESP],offset FLAT:_DATAcall near ptr _printfxor EAX,EAXpop ECXret

Размер исполняемого файла 23068 байт.

Перенесём её на D:

import core.stdc.stdio;extern (C) int main(int argc, char** argv) {    printf("hello world\n");    return 0;}

Размер исполняемого файла тот же самый: 23068 байт. Это неудивительно, потому что и компилятор C, и компилятор D генерируют один и тот же код, поскольку используют один и тот же генератор кода. (Эквивалентная программа на полноценном D занимала бы 194 Кб). Другими словами, вы ничего не платите за использование D вместо C при аналогичном коде.

Но Hello World это слишком просто. Возьмём что-то посложнее: пресловутый бенчмарк на основе решета Эратосфена:

#include <stdio.h>/* Eratosthenes Sieve prime number calculation. */#define true    1#define false   0#define size    8190#define sizepl  8191char flags[sizepl];int main() {    int i, prime, k, count, iter;    printf ("10 iterations\n");    for (iter = 1; iter <= 10; iter++) {        count = 0;        for (i = 0; i <= size; i++)            flags[i] = true;        for (i = 0; i <= size; i++) {            if (flags[i]) {                prime = i + i + 3;                k = i + prime;                while (k <= size) {                    flags[k] = false;                    k += prime;                }                count += 1;            }        }    }    printf ("\n%d primes", count);    return 0;}

Перепишем на Better C:

import core.stdc.stdio;extern (C):__gshared bool[8191] flags;int main() {    int count;    printf("10 iterations\n");    foreach (iter; 1 .. 11) {        count = 0;        flags[] = true;        foreach (i; 0 .. flags.length) {            if (flags[i]) {                const prime = i + i + 3;                auto k = i + prime;                while (k < flags.length) {                    flags[k] = false;                    k += prime;                }                count += 1;            }        }    }    printf("%d primes\n", count);    return 0;}

Выглядит почти так же, но кое-что следует отметить:

• Приписка extern(C) означает использование соглашения о вызове из языка C.
• D обычно хранит статические данные в локальном хранилище потока (thread-local storage, TLS). C же хранит их в глобальном хранилище. Аналогичного поведения мы достигаем при помощи __gshared.
• Инструкция foreach более простой способ пройтись циклом по известному промежутку.
• Использование const даёт знать читателю, что prime никогда не изменится после инициализации.
• Типы iter, i, prime и k выводятся автоматически, уберегая от ошибок с непредвиденным приведением типов.
• За количество элементов в flags отвечает flags.length, а не какая-то независимая переменная.

Последний пункт ведёт к скрытому, но очень важному преимуществу: при обращении к массиву flags происходит проверка его границ. Больше никаких ошибок из-за выхода за границы массива! И нам для этого даже не нужно было ничего делать.

И это только верхушка айсберга всех возможностей Better C, которые позволят вам улучшить выразительность, читабельность и безопасность ваших программ на C. К примеру, в D есть вложенные функции, и по моему опыту, они практически не оставляют мне поводов прибегать к запретной технике goto.

От себя лично могу сказать, что с тех пор, как появилась опция -betterC, я начал переводить на D многие мои старые, но всё ещё используемые программы по одной функции за раз. Работая по одной функции и запуская набор тестов после каждого изменения я постоянно сохраняю программу в рабочем состоянии. Если что-то сломалось, мне нужно проверить только одну функцию, чтобы найти причину. Мне не очень интересно дальше поддерживать свои программы на C, и с появлением Better C для этого больше нет причин.

Уолтер Брайт великодушный пожизненный диктатор языка программирования D и основатель Digital Mars. За его плечами не один десяток лет опыта в разработке компиляторов и интерпретаторов для нескольких языков, в числе которых Zortech C++ первый нативный компилятор C++. Он также создатель игры Empire, послужившей основным источником вдохновения для Sid Meiers Civilization. Данная публикация первая в серии статей о режиме Better C в языке D.

Вы устали от багов, которые легко сделать и трудно найти, которые часто не всплывают во время тестирования и уничтожают так тщательно построенный вами замок после того, как код ушёл в производство? Снова и снова они стоят вам много времени и денег. Ах, если бы только вы были по-настоящему хорошим программистом, то этого бы не происходило, верно?

А может, дело не в вас? Я покажу вам, что эти ошибки не ваша вина: это вина инструментов, и если только улучшить инструменты, то ваш замок будет в безопасности.

И вам даже не придётся идти ни на какие компромисы.

Выход за границы массива

Возьмём обычную программу для подсчёта суммы значений массива:

#include <stdio.h>#define MAX 10int sumArray(int* p) {    int sum = 0;    int i;    for (i = 0; i <= MAX; ++i)        sum += p[i];    return sum;}int main() {    static int values[MAX] = { 7,10,58,62,93,100,8,17,77,17 };    printf("sum = %d\n", sumArray(values));    return 0;}

Программа должна напечатать:

sum = 449

И именно это она и делает на моей машине с Ubuntu Linux: и в gcc, clang, и даже с флагом -Wall. Уверен, вы уже догадались, в чём ошибка:

for (i = 0; i <= MAX; ++i)              ^^

Это классическая ошибка на единицу. Цикл выполняется 11 раз вместо 10. Должно быть так:

for (i = 0; i < MAX; ++i)

Обратите внимание, что несмотря на баг, программа всё равно вывела правильный результат! Во всяком случае, на моей машине. И я бы не обнаружил этой ошибки. А вот на машине пользователя она бы загадочно всплыла, и я бы столкнулся с багом Гейзенберга на удалённой машине. Я уже съёживаюсь в предвкушении того, сколько времени и денег мне это будет стоить.

Это настолько мерзкий баг, что за годы я перепрограммировал свой мозг на то, чтобы:

1. никогда-никогда не использовать промежутки, включающие верхнюю границу;
2. никогда-никогда не использовать <= в проверке цикла.

Став лучшим программистом, я решил проблему! Или нет? На самом деле нет. Давайте посмотрим на этот код с точки зрения бедняги, которому придётся его проверять. Он хочет убедиться, что sumArray работает корректно. Для этого он должен:

1. Найти все функции, вызывающие sumArray, и проверить, что за указатель они передают.
2. Убедиться, что указатель действительно указывает на массив.
3. Убедиться, что размер массива действительно MAX.

И хотя в этой тривиальной программе это сделать просто, такой подход плохо масштабируется с возрастанием сложности программы. Чем больше функций обращаются к sumArray и чем более сложными становятся структуры данных, тем труднее делать, по сути, целый анализ потока данных у себя в уме, чтобы убедиться, что всё работает правильно.

Даже если вы не ошибётесь насколько вы можете быть уверены, что всё будет нормально? Если кто-то другой внесёт изменения, то ошибок всё ещё не будет? Хотите заново делать весь этот анализ? Уверен, вам и так есть чем заняться. Это дело инструментов.

Фундаментальная проблема состоит в том, что массивы в С преобразуются в указатели, когда используются как аргумент функции, даже если параметр функции определён как массив. Этой проблемы никак не избежать. И её никак не обнаружить. (По крайней мере, ни gcc, ни clang не умеют обнаруживать эту проблему, но может, кто-то разработал анализатор, который умеет это делать).

Инструмент, который решает эту проблему это компилятор D с опцией -betterC. В D есть такое понятие, как динамический массив, который на самом деле просто толстый указатель, который определён примерно вот так:

struct DynamicArray {    T* ptr;    size_t length;}

Он объявляется вот так:

int[] a;

И наш пример становится таким:

import core.stdc.stdio;extern (C):   // use C ABI for declarationsenum MAX = 10;int sumArray(int[] a) {    int sum = 0;    for (int i = 0; i <= MAX; ++i)        sum += a[i];    return sum;}int main() {    __gshared int[MAX] values = [ 7,10,58,62,93,100,8,17,77,17 ];    printf("sum = %d\n", sumArray(values));    return 0;}

Компилируем:

dmd -betterC sum.d

Запускаем:

./sumAssertion failure: 'array overflow' on line 11 in file 'sum.d'

Так-то лучше. Заменяем <= на < и получаем:

./sumsum = 449

Что здесь произошло? В динамическом массиве a хранится его длина, и компилятор вставляет проверки выхода за границы массива.

Но подождите, это ещё не всё.

Ещё там есть вот это вот досадное MAX. Поскольку массив a знает свою длину, то вместо этого можно написать так:

for (int i = 0; i < a.length; ++i)

Это настолько частая идиома, что в D для неё имеется специальный синтаксис:

foreach (value; a)    sum += value;

Теперь вся функция sumArray выглядит вот так:

int sumArray(int[] a) {    int sum = 0;    foreach (value; a)        sum += value;    return sum;}

и теперь sumArray можно рассматривать отдельно от всей остальной программы. Вы сделали большее за меньшее время и с большей надёжностью, и теперь можете рассчитывать на повышение зарплаты. Или по крайне мере вам не придётся приезжать на срочный вызов в свой выходной, чтобы исправить ошибку.

Протестую! скажете вы. Передача массива a в sumArray требует двух проталкиваний в стек, тогда как указатель p требовал только одного. Ты обещал, что не придётся идти на компромиссы, но здесь я жертвую скоростью.

Это правда в случае, если MAX является константой, а не передаётся в функцию, как здесь:

int sumArray(int *p, size_t length);

Но я же обещал, что не придётся идти ни на какие компромиссы. D позволяет предавать параметры по ссылке, в том числе и массивы фиксированной длины.

int sumArray(ref int[MAX] a) {    int sum = 0;    foreach (value; a)        sum += value;    return sum;}

Что здесь происходит? Массив a, будучи параметром с аттрибутом ref, во время выполнения становится всего лишь указателем. Однако он типизирован как указатель на массив из MAX элементов, что позволяет при обращении к нему делать проверки границ. Вам не придётся проверять функции, вызывающие sumArray, потому что система типов гарантируют, что они могут передавать только массивы правильного размера.

Протестую! скажете вы. D поддерживает указатели. Разве я не могу написать так же, как было? Что меня остановит? Я думал, что речь идёт о механических гарантиях!

Да, вы можете написать вот так:

import core.stdc.stdio;extern (C):   // use C ABI for declarationsenum MAX = 10;int sumArray(int* p) {    int sum = 0;    for (int i = 0; i <= MAX; ++i)        sum += p[i];    return sum;}int main() {    __gshared int[MAX] values = [ 7,10,58,62,93,100,8,17,77,17 ];    printf("sum = %d\n", sumArray(&values[0]));    return 0;}

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

sum = 39479

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

Как можно гарантировать, что этого не произойдёт? Добавить в код аттрибут @safe:

import core.stdc.stdio;extern (C):   // use C ABI for declarationsenum MAX = 10;@safe int sumArray(int* p) {    int sum = 0;    for (int i = 0; i <= MAX; ++i)        sum += p[i];    return sum;}int main() {    __gshared int[MAX] values = [ 7,10,58,62,93,100,8,17,77,17 ];    printf("sum = %d\n", sumArray(&values[0]));    return 0;}

Попытка скомпилировать выдаст следующее:

sum.d(10): Error: safe function 'sum.sumArray' cannot index pointer 'p'

Конечно, во время код-ревью надо будет будет сделать grep, чтобы удостовериться, что используется @safe, но на этом всё.

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

Уолтер Брайт великодушный пожизненный диктатор языка программирования D и основатель Digital Mars. За его плечами не один десяток лет опыта в разработке компиляторов и интерпретаторов для нескольких языков, в числе которых Zortech C++ первый нативный компилятор C++. Он также создатель игры Empire, послужившей основным источником вдохновения для Sid Meiers Civilization.

Better C это способ перенести существующие проекты на языке C на язык D в последовательной манере. В этой статье показан пошаговый процесс конвертации нетривиального проекта из C в D и показывает частые проблемы, которые при этом возникают.

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

Мне пришла на ум старая make-программа, которую я написал для компилятора C Datalight в начале 1980-х. Это реальная имплементация классической программы make, которая постоянно использовалась с начала 80-х. Она написана на C ещё до его стандартизации, была портирована из одной системы в другую и укладывается всего в 1961 строчку кода, включая комментарии. Она до сих пор регулярно используется.

Вот документация и исходный код. Размер исполняемого файла make.exe 49692 байта, и последнее изменение было 19августа2012 г.

Наш Злобный план:

1. Свести к минимуму diffы между C- и D-версиями. Таким образом, если поведение программ будет различаться, проще будет найти источник различия.
2. Во время переноса не будет предпринято попыток исправить или улучшить код на C. Это делается во исполнение пункта 1.
3. Не будет предпринято попыток рефакторинга кода. Опять же, см. пункт 1.
4. Воспроизвести поведение программы на C насколько это возможно, со всеми багами.
5. Сделать всё, что необходимо ради исполнения пункта 4.

Только когда мы закончим, можно будет приступить к исправления, рефакторингу, подчистке и т.д.

Спойлеры!

Законченный перенос с C на D. Размер исполняемого файла 52252 байт (сравнимо с оригиналом 49692 байт). Я не анализировал увеличение в размере, но вероятно, оно взялось из-за экземпляров шаблона NEWOBJ (в C-версии это макрос) и изменений в рантайме DMC после 2012 года.

Шаг за шагом

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

Включение файлов через #include заменено на импортирование соответствующих модулей D: например, #include <stdio.h> заменено на import core.stdc.stdio;. К сожалению, некоторые из включаемых файлов специфичны для Digital Mars C, и для них не существует версий на D (это надо исправить). Чтобы не останавливаться на этом, я просто вставил соответствующие объявления с 29-й строки по 64-ю. (См. документацию по объявлению import).

Конструкция #if _WIN32 заменена на version (Windows). (См. документацию по условной компиляции версий и список предопределённых версий).

Объявление extern(C): помечает последующие объявления в файле как совместимые с C. (См. документацию по аттрибуту линковки).

При помощи глобального поиска и замены макросы debug1, debug2 и debug3 заменены на debug prinf. В целом, директивы препроцессора #ifdef DEBUG заменены на условную компиляцию при помощи debug. (См. документацию по выражению debug).

/* Delete these old C macro definitions...#ifdef DEBUG-#define debug1(a)       printf(a)-#define debug2(a,b)     printf(a,b)-#define debug3(a,b,c)   printf(a,b,c)-#else-#define debug1(a)-#define debug2(a,b)-#define debug3(a,b,c)-#endif*/// And replace their usage with the debug statement// debug2("Returning x%lx\n",datetime);debug printf("Returning x%lx\n",datetime);

Макросы TRUE, FALSE и NULL при помощи поиска и замены заменены на true, false и null.

Макрос ESC заменён константой времени компиляции. (См. документацию по константам).

// #define ESC     '!'enum ESC =      '!';

Макрос NEWOBJ заменён шаблонной функцией.

// #define NEWOBJ(type)    ((type *) mem_calloc(sizeof(type)))type* NEWOBJ(type)() { return cast(type*) mem_calloc(type.sizeof); }

Макрос filenamecmp заменён функцией.

Убрана поддержка устаревших платформ.

Глобальные переменные в D по умолчанию помещаются в локальное хранилище потока (thread-local storage, TLS). Но поскольку make однопоточная программа, их можно поместить в глобальное хранилище при помощи класса хранилища __gshared. (См. документацию по атрибуту __gshared).

// int CMDLINELEN;__gshared int CMDLINELEN

В D нет отдельного пространства имён для структур, так что в typedef нет необходимости. Вместо этого можно использовать alias. (См. документацию по объявлению alias). Кроме того, из объявлений переменных убрано слово struct.

/*typedef struct FILENODE        {       char            *name,genext[EXTMAX+1];                char            dblcln;                char            expanding;                time_t          time;                filelist        *dep;                struct RULE     *frule;                struct FILENODE *next;        } filenode;*/struct FILENODE{        char            *name;        char[EXTMAX1]  genext;        char            dblcln;        char            expanding;        time_t          time;        filelist        *dep;        RULE            *frule;        FILENODE        *next;}alias filenode = FILENODE;

В языке D macro это ключевое слово, поэтому вместо этого будем использовать MACRO.

В отличие от C, в языке D звёздочка в объявлении указателя является частью типа, поэтому при объявлении нескольких указателей звёздочка применяется к каждому символу:

// char *name,*text;// In D, the * is part of the type and // applies to each symbol in the declaration.char* name, text;

Объявления массивов в стиле C преобразованы в объявления в стиле D. (См. документацию по синтаксису объявлений в D).

Слово static на уровне модуля в D ничего не значит. В C статические глобальные переменные эквивалентны приватным переменным уровня модуля в D, но это неважно, если модуль никогда не импортируется. Их всё ещё нужно обозначить как __gshared, и этот можно сделать целым блоком. (См. документацию по атрибуту static).

/*static ignore_errors = FALSE;static execute = TRUE;static gag = FALSE;static touchem = FALSE;static debug = FALSE;static list_lines = FALSE;static usebuiltin = TRUE;static print = FALSE;...*/__gshared{    bool ignore_errors = false;    bool execute = true;    bool gag = false;    bool touchem = false;    bool xdebug = false;    bool list_lines = false;    bool usebuiltin = true;    bool print = false;    ...}

Предварительные объявления функций в языке D не нужны. Функцию, определённую на уровне модуля, можно вызывать из любого места в этом модуле, даже до её определения.

В расширении символов подстановки в make-программе нет большого смысла.

Параметры функций, определённые с синтаксисом массивов, на самом деле являются указателями, и в D объявляются как указатели.

// int cdecl main(int argc,char *argv[])int main(int argc,char** argv)

Макрос mem_init() ни во что не расширяется, и до этого мы его убрали.

В C можно грязно играть с аргументами, но D требует, чтобы они соответствовали прототипу функции.

void cmderr(const char* format, const char* arg) {...}// cmderr("can't expand response file\n");cmderr("can't expand response file\n", null);

При помощи глобального поиска и замены оператор-стрелка (->) языка C заменён на точку (.), поскольку в D доступ к членам осуществляется одинаково.

Директивы условной компиляции заменены на version.

/* #if TERMCODE    ... #endif*/    version (TERMCODE)    {        ...    }

Отсутствие прототипов функций свидетельствует о древности этого кода. D требует полноценных прототипов.

// doswitch(p)// char *p;void doswitch(char* p)

В языке D слово debug зарезервировано. Переименуем в xdebug.

Многострочные литералы в C требуют \n\ в конце каждой строки. В D этого не требуется.

Неиспользуемый код закомментирован при помощи вложенного блока комментариев /+ +/. (См. документацию по строчным, блочным и вложенным комментариям).

Выражение static if может во многих случаях заменить #if. (См. документацию по static if).

Массивы в D не сводятся к указателю автоматически, следует использовать .ptr.

// utime(name,timep);utime(name,timep.ptr);

Использование const для строк в стиле C проистекает из строковых литералов в D, поскольку D не позволяет брать изменяемые указатели на строковые литералы. (См. документацию по const и immutable).

// linelist **readmakefile(char *makefile,linelist **rl)linelist **readmakefile(const char *makefile,linelist **rl)

Преобразование void* в char* в D должно быть явным.

// buf = mem_realloc(buf,bufmax);buf = cast(char*)mem_realloc(buf,bufmax);

Тип unsigned заменён на uint.

Атрибут inout можно использовать, чтобы передать константность аргумента функции на возвращаемый тип. Если параметр обозначен как const, то таким же будет возвращаемое значение, и наоборот. (См. документацию по inout-функциям).

// char *skipspace(p) {...}inout(char) *skipspace(inout(char)* p) {...}

Макрос arraysize можно заменить на свойство .length. (См. документацию по свойствам массивов).

// useCOMMAND  |= inarray(p,builtin,arraysize(builtin));useCOMMAND  |= inarray(p,builtin.ptr,builtin.length)

Строковые литералы неизменяемы (immutable), поэтому изменяемые строки необходимо заменить на массивы, выделенные на стеке. (См. документацию по строковым литералам).

// static char envname[] = "@_CMDLINE";char[10] envname = "@_CMDLINE";

Свойство .sizeof служит заменой оператору sizeof() из C. (См. документацию по .sizeof).

// q = (char *) mem_calloc(sizeof(envname) + len);q = cast(char *) mem_calloc(envname.sizeof + len)

Старые версии Windows нас не интересуют.

Доисторическое применение char * заменено на void*.

И вот и все изменения! Как видите, не так уж плохо. Я не выставлял таймер, но сомневаюсь, что всё это заняло у меня больше часа включая исправление нескольких ошибок, которые я сделал в процессе.

У нас остаётся только файл man.c, который был нужен, чтобы открывать в браузере документацию по make при запуске с опцией -man. К счастью, он уже портирован на D, так что я могу просто скопировать код.

Собрать make так просто, что для этого даже не требуется make-файл:

\dmd2.079\windows\bin\dmd make.d dman.d -O -release -betterC -I. -I\dmd2.079\src\druntime\import\ shell32.lib

Резюме

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

Проблемы, с которыми мы столкнулись, типичны и легко решаются следующими способами:

• замена #include на import;
• замена отсутствующих D-версий включаемых файлов;
• глобальный поиск и замена вещей вроде ->;
• замена макросов препроцессора на:
  
  • константы времени компиляции,
  • простые шаблоны,
  • функции,
  • спецификаторы версий,
  • спецификаторы отладки;
• замена зарезервированных слов;
• изменение объявлений массивов и указателей;
• удаление ненужных прототипов функций;
• более строгое соблюдение типов;
• использование свойств массивов;
• замена типов C типами D.

Не потребовалось ничего из следующего:

• реорганизация кода,
• изменения в структурах данных,
• изменение хода выполнения программы,
• изменения в работе программы,
• изменение управления памятью.

Будущее

Теперь, когда у нас есть Better C, нам доступны многие современные возможности, которые позволят нам улучшить наш код:

• модули!
• безопасное обращение к памяти (включая проверку переполнения буфера),
• метапрограммирование,
• RAII,
• Юникод,
• вложенные функции,
• методы,
• перегрузка операторов,
• генератор документации,
• функциональное программирование,
• выполнение функций во время компиляции (CTFE),
• и многое другое.

К действию

Если вы знаете английский, заходите на форум D и расскажите нам, как продвигается ваш проект на Better C!

Введение

Кажется, стоит вам отвернуться, и появляется новый язык программирования, нацеленный на решение некоторого специфического набора задач. Увеличение количества языков программирования и данных глубоко взаимосвязано, и растущий спрос на вычисления в области Data Science является связанным феноменом. В области научных вычислений языки программирования Chapel, D и Julia являются весьма релевантными. Они возникли в связи с различными потребностями и ориентированы на различные группы проблем: Chapel фокусируется на параллелизме данных на отдельных многоядерных машинах и больших кластерах; D изначально разрабатывался как более продуктивная и безопасная альтернатива C++; Julia разрабатывалась для технических и научных вычислений и была нацелена на освоение преимуществ обоих миров высокой производительности и безопасности статических языков программирования и гибкости динамических языков программирования. Тем не менее, все они подчеркивают производительность как отличительную особенность. В этой статье мы рассмотрим, как различается их производительность при вычислении ядра матрицы, и представим подходы к оптимизации производительности и другие особенности языков, связанные с удобством использования.

Вычисление ядра матрицы формирует основу методов в приложениях машинного обучения. Задача достаточно плохо масштабируется -O(m n^2), где n количество векторов, а m количество элементов в каждом векторе. В наших упражнениях m будет постоянным и мы будем смотреть на время выполнения в каждой реализации по мере увеличения n. Здесь m = 784 и n = 1k, 5k, 10k, 20k, 30k, каждое вычисление выполняется три раза и берется среднее значение. Мы запрещаем любое использование BLAS и допускаем использование только пакетов или модулей из стандартной библиотеки каждого языка, хотя в случае D эталон еще сравнивается с вычислениями, использующими Mir, библиотеку для работы с многомерными массивами, чтобы убедиться, что моя реализация матрицы отражает истинную производительность D. Подробности вычисления ядра матрицы и основных функций приведены здесь.

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

С точки зрения предвзятости, в начале работы, я был гораздо лучше знаком с D и Julia, чем с Chapel. Тем не менее, для получения наилучшей производительности от каждого языка требовалось взаимодействие с сообществами каждого языка, и я делал всё возможное, чтобы осознавать мои предубеждения и исправлять их там, где это было необходимо.

Бенчмарки языков программирования на задаче вычисления ядра матрицы

Приведенная выше диаграмма (сгенерированная с помощью ggplot2 на R с помощью скрипта) показывает время выполнения для количества элементов n для Chapel, D, и Julia, для девяти вычислений ядра. D лучше всего работает в пяти из девяти случаев, Julia лучше в двух из девяти, а в двух задачах (Dot и Gaussian) картинка смешанная. Chapel был самым медленным для всех рассмотренных задач.
Стоит отметить, что математические функции, используемые в D, были взяты из math API языка C, доступного в D через core.stdc.math, так как математические функции в стандартной библиотеке std.math языка D бывают достаточно медленными. Использованные математические функции приведены здесь. Для сравнения рассмотрим скрипт mathdemo.d, сравнивающий C-функцию логарифма с D-функцией из std.math:

$ ldc2 -O --boundscheck=off --ffast-math --mcpu=native --boundscheck=off mathdemo.d && ./mathdemoTime taken for c log: 0.324789 seconds.Time taken for d log: 2.30737 seconds.

Объект Matrix, используемый в бенчмарке D, был реализован специально из-за запрета на использование модулей вне стандартных языковых библиотек. Чтобы удостовериться, что эта реализация конкурентоспособна, т.е. не представляет собой плохую реализацию на D, я ее сравниваю с библиотекой Mir's ndslice, тоже написанной на D. На диаграмме ниже показано время вычисления матрицы минус время реализации ndslice; отрицательное значение означает, что ndslice работает медленнее, что указывает на то, что используемая здесь реализация не представляет собой негативную оценку производительности D.

Условия тестирования

Код был выполнен на компьютере с операционной системой Ubuntu 20.04, 32 ГБ памяти и процессором Intel Core i9-8950HK @ 2.90GHz с 6-ю ядрами и 12-ю потоками.

$ julia --versionjulia version 1.4.1$ dmd --versionDMD64 D Compiler v2.090.1$ ldc2 --versionLDC - the LLVM D compiler (1.18.0):  based on DMD v2.088.1 and LLVM 9.0.0$ chpl --versionchpl version 1.22.0

Компиляция

Chapel:

chpl script.chpl kernelmatrix.chpl --fast && ./script

D:

ldc2 script.d kernelmatrix.d arrays.d -O5 --boundscheck=off --ffast-math -mcpu=native && ./script

Julia (компиляция не требуется, но может быть запущена из командной строки):

julia script.jl

Реализации

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

• Чтобы читатель после установки языковой среды мог легко скопировать и запустить код. Необходимость установки внешних библиотек может быть немного неудачной.
• Пакеты, не относящиеся к стандартным библиотекам, могут исчезнуть, поэтому отказ от внешних библиотек сохраняет актуальность статьи и кода.
• Статья полностью прозрачна и показывает, как работает каждый из языков.

Chapel

Chapel использует цикл forall для распараллеливания по потокам. Также используется C-указатели на каждый элемент, а не стандартное обращение к массивам, и применяется guided итерация по индексам:

proc calculateKernelMatrix(K, data: [?D] ?T){  var n = D.dim(0).last;  var p = D.dim(1).last;  var E: domain(2) = {D.dim(0), D.dim(0)};  var mat: [E] T;  var rowPointers: [1..n] c_ptr(T) =    forall i in 1..n do c_ptrTo(data[i, 1]);  forall j in guided(1..n by -1) {    for i in j..n {      mat[i, j] = K.kernel(rowPointers[i], rowPointers[j], p);      mat[j, i] = mat[i, j];    }  }  return mat;}

Код на Chapel был самым трудным для оптимизации по производительности и потребовал наибольшего количества изменений кода.

D

Для распараллеливания кода D используется taskPool потоков из пакета std.parallel. Код на D претерпел наименьшее количество изменений для оптимизации производительности большая польза от использования специфического компилятора и выбранных ключей компиляции (обсуждается далее). Моя реализация Matrix позволяет отобрать столбцы по ссылке с помощью refColumnSelect.

auto calculateKernelMatrix(alias K, T)(K!(T) kernel, Matrix!(T) data){  long n = data.ncol;  auto mat = Matrix!(T)(n, n);  foreach(j; taskPool.parallel(iota(n)))  {    auto arrj = data.refColumnSelect(j).array;    foreach(long i; j..n)    {      mat[i, j] = kernel(data.refColumnSelect(i).array, arrj);      mat[j, i] = mat[i, j];    }  }  return mat;}

Julia

Код Julia использует макрос threads для распараллеливания кода и макрос views для ссылок на массивы. Единственное, что сбивает с толку с массивами в Julia это их ссылочный статус. Иногда, как и в этом случае, массивы будут вести себя как объекты-значения, и на них нужно ссылаться с помощью макроса views, иначе они будут генерировать копии. В других случаях они ведут себя как ссылочные объекты, например, при передаче их в функцию. С этим может быть немного сложно разобраться, потому что вы не всегда знаете, какой набор операций сгенерирует копию, но там, где это происходит, views обеспечивает хорошее решение.
Тип Symmetric позволяет сэкономить немного дополнительной работы, необходимой для отражения в матрице.

function calculateKernelMatrix(Kernel::K, data::Array{T}) where {K <: AbstractKernel,T <: AbstractFloat}  n = size(data)[2]  mat = zeros(T, n, n)  @threads for j in 1:n      @views for i in j:n          mat[i,j] = kernel(Kernel, data[:, i], data[:, j])      end  end  return Symmetric(mat, :L)end

Макросы @ bounds и @ simd в основных функциях использовались для отключения проверки границ и применения оптимизации SIMD к вычислениям:

struct DotProduct <: AbstractKernel end@inline function kernel(K::DotProduct, x::AbstractArray{T, N}, y::AbstractArray{T, N}) where {T,N}  ret = zero(T)  m = length(x)  @inbounds @simd for k in 1:m      ret += x[k] * y[k]  end  return retend

Эти оптимизации достаточно заметны, но очень просты в применении.

Использование памяти

Суммарное время для каждого бенчмарка и общая используемая память была собрана с помощью команды /usr/bin/time -v. Вывод для каждого из языков приведен ниже.

Chapel занял наибольшее общее время, но использовал наименьший объем памяти (почти 6 Гб оперативной памяти):

Command being timed: "./script"User time (seconds): 113190.32System time (seconds): 6.57Percent of CPU this job got: 1196%Elapsed (wall clock) time (h:mm:ss or m:ss): 2:37:39Average shared text size (kbytes): 0Average unshared data size (kbytes): 0Average stack size (kbytes): 0Average total size (kbytes): 0Maximum resident set size (kbytes): 5761116Average resident set size (kbytes): 0Major (requiring I/O) page faults: 0Minor (reclaiming a frame) page faults: 1439306Voluntary context switches: 653Involuntary context switches: 1374820Swaps: 0File system inputs: 0File system outputs: 8Socket messages sent: 0Socket messages received: 0Signals delivered: 0Page size (bytes): 4096Exit status: 0

D расходует наибольший объем памяти (около 20 ГБ оперативной памяти на пике), но занимает меньше общего времени, чем Chapel для выполнения:

Command being timed: "./script"User time (seconds): 106065.71System time (seconds): 58.56Percent of CPU this job got: 1191%Elapsed (wall clock) time (h:mm:ss or m:ss): 2:28:29Average shared text size (kbytes): 0Average unshared data size (kbytes): 0Average stack size (kbytes): 0Average total size (kbytes): 0Maximum resident set size (kbytes): 20578840Average resident set size (kbytes): 0Major (requiring I/O) page faults: 0Minor (reclaiming a frame) page faults: 18249033Voluntary context switches: 3833Involuntary context switches: 1782832Swaps: 0File system inputs: 0File system outputs: 8Socket messages sent: 0Socket messages received: 0Signals delivered: 0Page size (bytes): 4096Exit status: 0

Julia потратила умеренный объем памяти (около 7,5 Гб пиковой памяти), но выполнялась быстрее всех, вероятно, потому что ее генератор случайных чисел является самым быстрым:

Command being timed: "julia script.jl"User time (seconds): 49794.85System time (seconds): 30.58Percent of CPU this job got: 726%Elapsed (wall clock) time (h:mm:ss or m:ss): 1:54:18Average shared text size (kbytes): 0Average unshared data size (kbytes): 0Average stack size (kbytes): 0Average total size (kbytes): 0Maximum resident set size (kbytes): 7496184Average resident set size (kbytes): 0Major (requiring I/O) page faults: 794Minor (reclaiming a frame) page faults: 38019472Voluntary context switches: 2629Involuntary context switches: 523063Swaps: 0File system inputs: 368360File system outputs: 8Socket messages sent: 0Socket messages received: 0Signals delivered: 0Page size (bytes): 4096Exit status: 0

Оптимизация производительности

Процесс оптимизации производительности на всех трех языках был очень разным, и все три сообщества были очень полезны в этом процессе. Но были и общие моменты.

• Статическая диспетчеризация функций ядра вместо использования полиморфизма. Это означает, что при передаче функции ядра используется параметрический (времени компиляции) полиморфизм, а не динамический (времени исполнения), при котором диспетчеризация с виртуальными функциями влечет за собой накладные расходы.
• Использование представлений/ссылок, вместо копирования данных в многопоточном режиме, имеет большое значение.
• Распараллеливание вычислений имеет огромное значение.
• Знание того, что массив является основным для строки/столбца, и использование этого в вычислениях имеет огромное значение.
• Проверки границ и оптимизации компилятора дают огромную разницу, особенно в Chapel и D.
• Включение SIMD в D и Julia внесло свой вклад в производительность. В D это было сделано с помощью флага -mcpu=native, а в Julia это было сделано с помощью макроса @ simd.

С точки зрения специфики языка, наиболее сложным был переход к производительному коду в Chapel, и код в Chapel больше всего изменился: от простых для чтения операций с массивами до использования указателей и управляемых итераций. Но со стороны компилятора было относительно легко добавить --fast и получить большой прирост производительности.

Код на D изменился очень мало, и большая часть производительности была получена за счет выбора компилятора и его флагов оптимизации. Компилятор LDC богат возможностями оптимизации производительности. Он имеет 8 -O уровней оптимизации, но некоторые из них повторяются. Например, -O, -O3 и -O5 идентичны, а других флагов, влияющих на производительность, бесчисленное множество. В данном случае использовались флаги -O5 --boundscheck=off -ffast-math, представляющие собой агрессивные оптимизации компилятора, проверку границ, и LLVM's fast-math, и -mcpu=native для включения инструкций векторизации.

В Julia макросы в рассмотренных ранее изменениях заметно улучшили производительность, но они не были слишком запутанными. Я попробовал изменить уровень оптимизации -O, но это не улучшило производительность.

Качество жизни

В этом разделе рассматриваются относительные плюсы и минусы, связанные с удобством и простотой использования каждого языка. Люди недооценивают усилия, затрачиваемые на повседневное использование языка; необходима значительная поддержка и инфраструктура, поэтому стоит сравнить различные аспекты каждого языка. Читателям, стремящимся избежать TLDR, следует прокрутить до конца данного раздела до таблицы, в которой сравниваются обсуждаемые здесь особенности языка. Было сделано все возможное, чтобы быть как можно более объективным, но сравнение языков программирования является сложным, предвзятым и спорным, поэтому читайте этот раздел с учетом этого. Некоторые рассматриваемые элементы, такие как массивы, рассматриваются с точки зрения Data Science/технических/научных вычислений, а другие являются более общими.

Интерактивность

Программистам нужен быстрый цикл кодирования/компиляции/результата во время разработки, чтобы быстро наблюдать за результатами и выводами для того, чтобы двигаться вперёд либо вносить необходимые изменения. Интерпретатор Julia самый лучший для этого и предлагает гладкую и многофункциональную разработку, а D близок к этому. Этот цикл кодирования/компиляции/результата может быть медленным даже при компиляции небольшого кода. В D есть три компилятора: стандартный компилятор DMD, LLVM-компилятор LDC и GCC-компилятор GDC. В этом процессе разработки использовались компиляторы DMD и LDC. DMD компилирует очень быстро, что очень удобно для разработки. А LDC отлично справляется с созданием быстрого кода. Компилятор Chapel очень медленный по сравнению с ним. В качестве примера запустим Linux time для компилятора DMD и для Chapel для нашего кода матрицы без оптимизаций. Это дает нам для D:

real0m0.545suser0m0.447ssys0m0.101s

Сравним с Chapel:

real0m5.980suser0m5.787ssys0m0.206s

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

Стоит однако отметить, что при разработке пакетов в Julia время компиляции может быть очень долгим, и пользователи отмечают, что при загрузке нескольких пакетов время компиляции может растягиваться. Поэтому практика цикла разработки в Julia может варьироваться, но в данном конкретном случае процесс был безупречным.

Документация и примеры

Один из способов сравнить документацию на разных языках это сравнить их все с официальной документацией Python, которая является золотым стандартом для языков программирования. Она сочетает примеры с формальными определениями и инструкциями в простом и удобном для пользователя виде. Поскольку многие программисты знакомы с документацией на Python, такой подход даёт представление о том, как они сравнивают.

Документация Julia наиболее близка по качеству к документации на Python и даёт пользователю очень плавный, детальный и относительно безболезненный переход на язык. Она также имеет богатую экосистему блогов, и темы по многим аспектам языка легкодоступны. Официальная документация D не так хороша и может быть сложной и разочаровывающей, однако существует очень хорошая бесплатная книга Программирование на D, которая является отличным введением в язык, но ни одна единичная книга не может охватить язык программирования целиком и не так много исходных текстов примеров для продвинутых тем. Документация Chapel достаточно хороша для того, чтобы сделать что-то, хотя представленные примеры различаются по наличию и качеству. Часто программисту требуется знать, где искать. Хорошая тема для сравнения библиотеки файлового ввода/вывода в Chapel, D и Julia. Библиотека ввода/вывода Chapel содержит слишком мало примеров, но относительно ясна и проста; ввод/вывод D распределён по нескольким модулям, и документации более сложно следовать; документация по вводу/выводу Julia содержит много примеров, и она ясна и проста для понимания.

Возможно, одним из факторов, влияющих на принятие Chapel, является отсутствие примеров поскольку массивы имеют нестандартный интерфейс, пользователю приходится потрудиться, чтобы их узнать. Несмотря на то, что документация в D может быть не так хороша местами, язык имеет много сходств с Си и Си++, потому ему сходит с рук более скудная документация.

Поддержка многомерных массивов

Массивы здесь относятся не к массивам в стиле С и С++, доступным в D, а к математическим массивам. Julia и Chapel поставляются с поддержкой массивов, а D нет, но у него есть библиотека Мир, которая содержит многомерные массивы (ndslice). В реализации расчета ядра матрицы я написал свой объект матрицы в D, что несложно, если понимать принцип, но это не то, что хочет делать пользователь. Тем не менее, в D есть линейная библиотека алгебры Lubeck, которая обладает впечатляющими характеристиками производительности и интерфейсами со всеми обычными реализациями BLAS. Массивы Julia, безусловно, самые простые и знакомые. Массивы Chapel сложнее для начального уровня, чем массивы Julia, но они спроектированы для запуска на одноядерных, многоядерных системах и компьютерных кластерах с использованием единого или очень похожего кода, что является хорошей уникальной точкой притяжения.

Мощность языка

Поскольку Julia это динамический язык программирования, некоторые могут сказать: Ну, Julia это динамический язык, который гораздо более разрешительный, чем статические языки программирования, поэтому дебаты закончены, но все гораздо сложнее. В статических системах типов есть свое могущество. У Julia есть система типов, похожая по своей природе на системы типов из статических языков, так что вы можете писать код так, как если бы вы использовали статический язык, но вы можете делать вещи, зарезервированные только для динамических языков. Она имеет высокоразвитый синтаксис общего и мета-программирования, а также мощные макросы. Она также имеет очень гибкую объектную систему и множественную диспетчеризацию. Это сочетание возможностей делает Julia самым мощным языком из трех.

D был задуман как замена C++ и взял очень много от C++ (а также заимствовал из Java), но делает шаблонное программирование и вычисления времени компиляции (CTFE) намного более удобными для пользователя, чем в C++. Это язык с одиночной диспетчеризацией (хотя есть пакет с мультиметодами). Вместо макросов в D есть mixin для строк и шаблонов, которые служат аналогичной цели.

Chapel имеет поддержку дженериков и зарождающуюся поддержку для ООП с одиночной диспетчеризацией, в нем нет поддержки макросов, и в этих вопросах он ещё не так зрел, как D или Julia.

Конкурентность и параллельное программирование

В настоящее время новые языки изначально поддерживают конкурентность с ее популярным подмножеством параллелизмом, но детали сильно варьируются в зависимости от языка. Параллелизм более актуален в этом примере, и все три языка предоставляют его. Написать параллельные циклы просто во всех трех языках.

В модели параллелизма Chapel гораздо больше внимания уделяется параллелизму данных, но есть инструменты для параллелизма задач и предоставляется поддержка параллелизма на основе кластеров.

Julia имеет хорошую поддержку как конкурентности, так и параллелизма.

D имеет промышленно- сильную поддержку конкурентности и параллелизма, хотя его поддержка многопоточности гораздо менее хорошо документирована примерами.

Стандартная библиотека

Насколько хороша стандартная библиотека всех трех языков в целом? Какие задачи она позволяют пользователям легко выполнять? Это сложный вопрос, потому что при этом учитываются качество библиотеки и фактор документирования. Все три языка имеют очень хорошие стандартные библиотеки. В D самая полная стандартная библиотека, но Julia отличная вторая, потом Chapel, но все никогда не бывает так просто. Например, пользователь, желающий написать бинарный ввод/вывод, может найти Julia самой простой для начинающего; она имеет самый простой, понятный интерфейс и документацию, за ней следует Chapel, а затем D. Хотя в моей реализации программы для чтения IDX-файлов, ввод/вывод D был самым быстрым, но зато код Julia было легко написать для случаев, недоступных на двух других языках.

Менеджеры и экосистема пакетов

С точки зрения документации, использования и возможностей, менеджер пакетов D Dub является наиболее полным. D также имеет богатую экосистему пакетов на веб-сайте Dub, зато менеджер пакетов Julia тесно интегрирован с GitHub и является хорошей пакетной системой с хорошей документацией. У Chapel есть менеджер пакетов, но нет высокоразвитой экосистемы.

Интеграция с Cи

Cи- интероперабельность проста в использовании на всех трех языках; Chapel имеет хорошую документацию, но не так популярен, как другие. Документация на языке D лучше, а документация на языке Julia самая полная. Однако, как ни странно, ни в одной документации по языкам нет команд, необходимых для компиляции вашего собственного кода на C и его интеграции с языком, что является недосмотром, особенно когда дело касается новичков. Тем не менее, в D и Julia легко искать и найти примеры процесса компиляции.

Сообщество

Для всех трех языков есть удобные места, где пользователи могут задавать вопросы. Для Chapel, самое простое место это Gitter, для Julia это Discourse (хотя есть и Julia Gitter), а для D это официальный форум сайта. Julia сообщество является наиболее активным, а затем D, а затем Chapel. Я обнаружил, что вы получите хорошие ответы от всех трех сообществ, но вы, вероятно, получите более быстрые ответы по D и Julia.
Таблица характеристик качества жизни для Chapel, D & Julia

Резюме

Если вы начинающий программист, пишущий числовые алгоритмы и выполняющий научные вычисления, и хотите быстрого и простого в использовании языка, Julia это ваш лучший выбор. Если вы опытный программист, работающий в той же области, Julia все еще является отличным вариантом. Если вы хотите более традиционный, промышленный, статически скомпилированный, высокопроизводительный язык со всеми свистоперделками, но хотите что-то более продуктивное, безопасное и менее болезненное, чем C++, то D это ваш лучший вариант. Вы можете написать что угодно в D и получить отличную производительность благодаря его компиляторам. Если вам нужно, чтобы вычисления массивов происходили на кластерах, то Chapel, наверное, самое удобное решение.

С точки зрения грубой производительности в этой задаче, D был победителем, явно демонстрируя лучшую производительность в 5 из 9 эталонных задач. Исследование показало, что ярлык Julia как высокопроизводительного языка это нечто большее, чем просто шумиха он обладает собственными достоинствами в сравнении с высококонкурентными языками. Было сложнее, чем ожидалось, получить конкурентоспособную производительность от Chapel команде Chapel потребовалось много исследований, чтобы придумать текущее решение. Тем не менее, по мере того, как язык Chapel взрослеет, мы сможем увидеть дальнейшее улучшение.

D, как и многие активно используемые сегодня языки, поставляется со сборщиком мусора (Garbage Collector, GC). Многие виды ПО можно разрабатывать, вообще не задумываясь о GC, в полной мере пользуясь его преимуществами. Однако у GC есть свои изъяны, и в некоторых сценариях сборка мусора нежелательна. Для таких случаев язык позволяет временно отключить сборщик мусора или даже совсем обойтись без него.

Чтобы получить максимальное преимущество от сборщика мусора и свести недостатки к минимуму, необходимо хорошо понимать, как работает GC в языке D. Хорошим началом будет страничка Garbage Collection на dlang.org, которая подводит обоснование под GC в языке D и даёт несколько советов о том, как с ним работать. Это первая из серии статей, которая призвана более подробно осветить тему.

В этот раз мы коснёмся только самых основ, сосредоточившись на функциях языка, которые могут вызвать выделение памяти через GC. Будущие статьи представят способы отключить GC при необходимости, а также идиомы, помогающие справляться с его недетерминированностью (например, управление ресурсами в деструкторах объектов, находящихся под контролем GC).

Самая первая вещь, которую нужно уяснить: сборщик мусора в D запускается только во время выделения памяти и только в том случае, если нет памяти, которую можно выделить. Он не сидит в фоне, периодически сканируя кучу и собирая мусор. Это необходимо понимать, чтобы писать код, эффективно использующий память под контролем GC. Рассмотрим следующий пример:

void main() {    int[] ints;    foreach(i; 0..100) {        ints ~= i;    }}

Эта программа создаёт динамический массив значений типа int, а затем при помощи имеющегося в D оператора присоединения добавляет в него числа от 0 до 99 в цикле foreach. Что неочевидно неопытному глазу, так это то, что оператор присоединения выделяет память для добавляемых значений через сборщик мусора.

Реализация динамического массива в рантайме D вовсе не тупая. В нашем примере не произойдёт сотни выделений памяти, по одному на каждое значение. Когда требуется больше памяти, массив выделяет больше памяти, чем запрашивается. Мы можем определить, сколько на самом деле будет выделений памяти, задействовав свойство capacity. Это свойство возвращает количество элементов, которые можно поместить в массив, прежде чем потребуется выделение памяти.

void main() {    import std.stdio : writefln;    int[] ints;    size_t before, after;    foreach(i; 0..100) {        before = ints.capacity;        ints ~= i;        after = ints.capacity;        if(before != after) {            writefln("Before: %s After: %s",                before, after);        }    }}

Скомпилировав этот код в DMD 2.073.2 и выполнив, мы увидим шесть сообщений шесть выделений памяти через GC. Это означает, что у GC шесть раз была возможность собрать мусор. В этом маленьком примере это вряд ли произошло. Если бы этот цикл был частью большой программы, использующей GC, то это вполне могло бы произойти.

Кроме того, любопытно взглянуть на значения before и after. Программа выдаёт последовательность: 0, 3, 7, 15, 31, 63, и 127. После выполнения цикла массив ints содержит 100 значений, и в нём есть место под ещё 27 значений, прежде чем произойдёт следующее выделение памяти, которое увеличит объём массива до 255, экстраполируя предыдущие значения. Это, однако, уже детали реализации рантайма D, и в будущих релизах всё может поменяться. Чтобы узнать больше о том, как GC контролирует массивы и срезы, взгляните на прекрасную статью Стива Швайхоффера (Steve Schveighoffer) на эту тему.

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

Даже когда речь идёт о языках без встроенного сборщика мусора, таких как C и C++, большинство программистов рано или поздно узнают, что для общей производительности лучше заранее выделить как можно больше ресурсов и свести к минимуму выделение памяти во внутренних циклах. Это одна из многих преждевременных оптимизаций, которые не является корнем всех зол то, что мы называем лучшими практиками. Учитывая, что GC в языке D запускается только когда происходит выделение памяти, ту же самую стратегию можно применять как простой способ минимизировать его влияние на производительность. Вот как можно переписать пример:

void main() {    int[] ints = new int[](100);    foreach(i; 0..100) {        ints[i] = i;    }}

Мы сократили шесть выделений памяти до одного. Единственная возможность для GC запуститься перед внутренним циклом. Этот код выделяет место для по крайней мере 100 элементов и инициализирует их значением нулями перед входом в цикл. После new длина массива будет 100, но в нём почти наверняка будет дополнительная ёмкость.

Есть также другой способ: функция reserve:

void main() {    int[] ints;    ints.reserve(100);    foreach(i; 0..100) {        ints ~= i;    }}

Это выделит память под по крайней мере 100 значений, но массив всё ещё будет пустым (его свойство length будет возвращать 0), так что ничего не будет инициализировано значениями по умолчанию. Учитывая, что цикл добавляет только 100 значений, гарантируется, что выделения памяти не произойдёт.

Помимо new и reserve, можно также выделять память явным образом, напрямую вызывая GC.malloc.

import core.memory;void* intsPtr = GC.malloc(int.sizeof * 100);auto ints = (cast(int*)intsPtr)[0 .. 100];

Литералы массивов обычно выделяет память.

auto ints = [0, 1, 2];

Это верно также в том случае, когда литерал массива используется в enum.

enum intsLiteral = [0, 1, 2];auto ints1 = intsLiteral;auto ints2 = intsLiteral;

Значение типа enum существует только во время компиляции и не имеет адреса в памяти. Его имя синоним его значения. Где бы вы его не использовали, это будет как если бы вы скопировали и вставили его значение на месте его имени. И inst1, и inst2 вызовут выделение памяти, как если бы мы определили их вот так:

auto ints1 = [0, 1, 2];auto ints2 = [0, 1, 2];

Литералы массивов не выделяют память, если целью является статический массив. Кроме того, строковые литералы (строки в D это массивы) исключение из общего правила и также не выделяют память.

int[3] noAlloc1 = [0, 1, 2];auto noAlloc2 = "No Allocation!";

Оператор конкатенации всегда выделяет память:

auto a1 = [0, 1, 2];auto a2 = [3, 4, 5];auto a3 = a1 ~ a2;

У ассоциативных массивов в D своя стратегия выделения памяти, но можно ожидать, что они будут выделять память при добавлении элементов и при их удалении. Также они реализуют два свойства: keys и values, которые выделяют память под массив и заполняют его копиями соответствующих элементов. Когда ассоциативный массив нужно изменять во время того, как вы по нему итерируете, или если нужно отсортировать элементы или ещё каким-то образом обработать их в отрыве от массива, эти свойства то что доктор прописал. В других случаях это лишь лишнее выделение памяти, чрезмерно нагружающее GC.

Когда сборка мусора всё-таки запускается, время, которое она займёт, будет зависеть от объёма сканируемой памяти. Чем меньше, тем лучше. Никогда не будет лишним избегать ненужных выделений памяти, и это ещё один хороший способ минимизировать влияние сборщика мусора на производительность. Как раз для этого у ассоциативных массивов в D есть три свойства: byKey, byValue и byKeyValue. Каждое из них возвращает диапазон, который можно итерировать ленивым образом. Они не выделяют память, поскольку напрямую обращаются к элементам массива, поэтому не следует его изменять во время итерирования. Более подробно о диапазонах можно прочитать в главах Ranges и More Range из книги Али Чехрели (Ali ehreli) Programming in D.

Замыкания делегаты или функции, которые должны нести в себе указатель на фрейм стека также выделяют память. Последняя возможность языка, упомянутая на страничке Garbage Collection выражение assert. Если проверка проваливается, выражение assert выделяет память, чтобы породить AssertError, которое является частью иерархии исключений языка D, основанной на классах (в будущих статьях мы рассмотрим, как классы взаимодействуют с GC).

И наконец, есть Phobos стандартная библиотека D. Когда-то давным-давно большая часть Phobosа была реализована без особой заботы о выделении памяти через GC, отчего его трудно было использовать в ситуациях, когда это было нежелательно. Однако потом было приложено много усилий, чтобы сделать его более сдержанным в обращении с GC. Некоторые функции были переделаны, чтобы они могли работать с ленивыми диапазонами, другие были переписаны, чтобы они принимали буфер, а некоторые были переработаны, чтобы избежать лишних выделений памяти внутри себя. В результате стандартная библиотека стала гораздо более пригодной для написания кода, свободного от GC (хотя, возможно, ещё остаются места, которые ещё предстоит обновить пулл-реквесты всегда приветствуются).

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

Спасибо Гийому Пьола (Guillaume Piolat) и Стиву Швайхофферу за их помощь в подготовке этой статьи.

В первой из серии статей о GC я представил сборщик мусора в языке D и возможности языка, которые его используют. Два ключевых момента, которые я пытался донести:

1. GC запускается только тогда, когда вы запрашиваете выделение памяти. Вопреки расхожему заблуждению, GC языка D не может просто взять и поставить на паузу ваш клон Майнкрафта посреди игрового цикла. Он запускается только когда вы запрашиваете память через него и только тогда, когда это необходимо.

   
   

2. Простые стратегии выделения памяти в стиле C и C++ позволяют уменьшить нагрузку на GC. Не выделяйте память внутри циклов вместо этого как можно больше ресурсов выделяйте заранее или используйте стек. Сведите к минимуму общее число выделений памяти через GC. Эти стратегии работают благодаря пункту 1. Разработчик может диктовать, когда допустимо запустить сборку мусора, грамотно используя выделение памяти из кучи, управляемой GC.

   
   

Стратегии из пункта 2 подходят для кода, который программист пишет сам, но они не особенно помогут, когда речь идёт о сторонних библиотеках. В этих случаях при помощи механизмов языка D и его рантайма можно гарантировать, что в критических местах кода никакого выделения памяти не произойдёт. Также есть параметры командной строки, которые помогают убедиться, что GC не встанет на вашем пути.

Давайте представим, что вы пишете программу на D и по тем или иным причинам решили полностью исключить сборку мусора. У вас есть два очевидных решения.

Таблетка от жадности

Первое решение вызвать GC.disable при запуске программы. Выделение памяти через GC всё ещё будет работать, но сборка мусора остановится. Вся сборка мусора, включая ту, что могла произойти в других потоках.

void main() {    import core.memory;    import std.stdio;    GC.disable;    writeln("Goodbye, GC!");}

Вывод:

Goodbye, GC!

Преимущество этого способа в том, что все возможности языка, использующие GC, продолжат работать, как и ожидалось. Но если учесть, что будет происходить выделение памяти без всякой очистки, то по здравому размышлению вы поймёте, что такое решение может выйти вам боком. Если всё время бесконтрольно выделять память, то рано или поздно какое-то из звеньев цепи сдаст. Из документации:

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

Насколько это плохо, зависит от конкретного случая. Если для вас такое ограничение приемлемо, то есть ещё кое-какие инструменты, которые помогут держать всё под контролем. Вы можете по необходимости вызывать GC.enable и GC.collect. Такая стратегия позволяет контролировать циклы освобождения ресурсов лучше, чем простые техники из C и C++.

Антимусоросборочная стена

Когда запуск сборщика мусора абсолютно неприемлем, вы можете обратиться к атрибуту @nogc. Повесь его на main, и минует тебя сборка мусора.

@nogcvoid main() { ... }

Это окончательное решение вопроса GC. Атрибут @nogc, применённый к main, гарантирует, что сборщик мусора не запустится никогда и нигде на всём протяжении стека вызовов. Больше никаких подводных камней если это необходимо для дальнейшей корректной работы программы.

Не первый взгляд такое решение кажется гораздо лучшим, чем GC.disable. Давайте попробуем.

@nogcvoid main() {    import std.stdio;    writeln("GC be gone!");}

На этот раз мы не продвинемся дальше компиляции:

Error: @nogc function 'D main' cannot call non-@nogc function 'std.stdio.writeln!string.writeln'(Ошибка: @nogc-функция 'D main' не может вызвать не-@nogcфункцию 'std.stdio.writeln!string.writeln')

Сила атрибута @nogc в том, что компилятор не позволяет его обойти. Он работает очень прямолинейно. Если функция обозначена как @nogc, то любая функция, которую вы вызываете внутри неё, также должна быть обозначена как @nogc. Очевидно, что writeln это требование не выполняет.

И это ещё не всё:

@nogc void main() {    auto ints = new int[](100);}

Компилятор не спустит вам с рук и этого:

Error: cannot use 'new' in @nogc function 'D main'(Ошибка: нельзя использовать 'new' в @nogc-функции 'D main')

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

При таком подходе вам придётся прибегнуть к различным обходным путям, чтобы обойтись без несовместимых с @nogc возможностей языка и библиотечных функций, включая некоторые функции из стандартной библиотеки. Некоторые из них тривиальны, другие сложнее, а что-то и вовсе нельзя обойти (мы подробно всё это рассмотрим в будущих статьях). Неочевидный пример одной из таких вещей исключения. Идиоматический способ породить исключение такой:

throw new Exception("Blah");

Из-за того, что здесь есть new, в @nogc-функции так написать нельзя. Чтобы обойти это ограничение, требуется заранее выделить место под все исключения, которые могут быть выброшены, а для этого требуется потом как-то освобождать эту память, из чего проистекают идеи об использовании для механизма исключений подсчёта ссылок или о выделении памяти на стеке Короче говоря, это большой клубок проблем. Сейчас появилось предложение по улучшению D Уолтера Брайта, которое призвано распутать этот клубок и сделать так, чтобы throw new Exception работало без GC, когда это необходимо.

К сожалению, проблема использования исключений в @nogc-коде не решена до сих пор. (прим. пер.)

Справиться с ограничениями @nogc main вполне выполнимая задача, она просто потребует немного мотивации и дисциплины.

Ещё одна вещь, которую стоит отметить: даже @nogc main не исключает GC из программы полностью. D поддерживает статические конструкторы и деструкторы. Первые срабатывают перед входом в main, а последние после выхода из неё. Если они есть в коде и не обозначены как @nogc, то, технически, выделение памяти через GC и сборка мусора могут происходить даже в @nogc-программе. Тем не менее, атрибут @nogc, применённый к main, означает, что на протяжение работы main сборка мусора запускаться не будет, так что по сути это то же самое, что не иметь никакого GC.

Добиваемся хорошего результата

Здесь я выскажу мнение. Существует широких спектр программ, которые можно написать на D, не отключая GC на время и не отказываясь от него полностью. Очень много можно добиться, минимизируя выделение памяти через GC и исключая его из горячих точек кода и именно так и следует делать. Я не устаю это повторять, потому что часто неправильно понимают, как происходит сборка мусора в языке D: она может запуститься только когда программист выделяет память через GC и только когда это нужно. Используйте это знание с пользой, выделяя мало, редко и за пределами внутренних циклов.

В тех программах, где действительно нужен полный контроль, возможно, нет необходимости полностью отказываться от GC. Рассудительное использование @nogc и/или API core.memory.GC зачастую позволяет избежать любых проблем с производительностью. Не вешайте атрибут @nogc на main, повесьте его на функции, где точно нужно запретить выделение памяти через GC. Не вызывайте GC.disable в начале программы. Вызывайте её перед критическим местом, а после него вызывайте GC.enable. Сделайте так, чтобы GC собирал мусор в стратегических точках (например, между уровнями игры), при помощи GC.collect.

Как и всегда в оптимизации производительности при разработке ПО, чем полнее вы понимаете, что происходит под капотом, тем лучше. Необдуманное использование API core.memory.GC может заставить GC выполнять лишнюю работу или не оказать никакого эффекта. Для лучшего понимания внутренних процессов вы можете использовать тулчейн D.

В скомпилированную программу (не компилятор!) можно передать параметр рантайма D --DRT-gcopt=profile:1, который поможет вам в тонкой настройке. Вы получите полезную информацию от профилировщика GC, такую как суммарное количество сборок мусора и суммарное время, затраченное на них.

В качестве примера: gcstat.d добавляет двадцать значений в динамический массив целых чисел.

void main() {    import std.stdio;    int[] ints;    foreach(i; 0 .. 20) {        ints ~= i;    }    writeln(ints);}

Компиляция и запуск с параметром профилировщика GC:

dmd gcstat.dgcstat --DRT-gcopt=profile:1[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]        Number of collections:  1        Total GC prep time:  0 milliseconds        Total mark time:  0 milliseconds        Total sweep time:  0 milliseconds        Total page recovery time:  0 milliseconds        Max Pause Time:  0 milliseconds        Grand total GC time:  0 millisecondsGC summary:    1 MB,    1 GC    0 ms, Pauses    0 ms <    0 ms

Отчёт сообщает об одной сборке мусора, которая, по всей вероятности, произошла во время выхода из программы. Рантайм D завершает работу GC на выходе, что (в текущей реализации) обычно вызовет сборку мусора. Это делается главным образом для того, чтобы запустить деструкторы собранных объектов, хотя D и не требует, чтобы деструкторы объектов под контролем GC когда-либо вызывались (это тема для одной из следующих статей).

DMD поддерживает параметр командной строки -vgc, который отобразит каждое выделение памяти через GC в вашей программе включая те, что спрятаны за возможностями языка, такими как оператор присоединения ~=.

В качестве примера: взгляните на inner.d.

void printInts(int[] delegate() dg){    import std.stdio;    foreach(i; dg()) writeln(i);} void main() {    int[] ints;    auto makeInts() {        foreach(i; 0 .. 20) {            ints ~= i;        }        return ints;    }    printInts(&makeInts);}

Здесь makeInts внутренняя функция. Указатель на нестатическую внутреннюю функцию является не указателем на функцию, а делегатом, то есть парным указателем на функцию/контекст (если внутренняя функция обозначена как static, то вместо типа delegate вы получаете тип function). В этом конкретном случае делегат обращается к переменной в родительской области видимости.

Вот вывод компилятора с опцией -vgc:

dmd -vgc inner.dinner.d(11): vgc: operator ~= may cause GC allocationinner.d(7): vgc: using closure causes GC allocation(inner.d(11): vgc: оператор ~= может вызвать выделение памяти через GC)(inner.d(7): vgc: использование замыкания может вызвать выделение памяти через GC)

Здесь мы видим, что нужно выделить память, чтобы делегат мог нести в себе состояние ints, что делает его замыканием (которое не является отдельным типом тип по-прежнему delegate). Переместите объявление ints внутрь области видимости makeInts и скомпилируйте снова. Вы увидите, что выделение памяти из-за замыкания пропало. Ещё лучше изменить объявление printInts таким образом:

void printInts(scope int[] delegate() dg)

Добавление scope к параметру функции гарантирует, что никакие ссылки в этом параметре не могут выйти за пределы функции. Иначе говоря, становится невозможным присвоить делегат dg глобальной переменной или вернуть его из функции. В результате отпадает необходимость создавать замыкание, так что никакого выделения памяти не будет. См. в документации об указателях на функции, делегатах и замыканиях, а также о классах хранения параметров функций.

Резюме

Учитывая, что GC языка D сильно отличается от того, что есть в языках вроде Java и C#, его производительность будет иметь другую характеристику. Кроме того, программы на D как правило производят гораздо меньше мусора, чем программы на языках вроде Java, где почти все типы имеет ссылочную семантику. Полезно это понимать, приступая к своему первому проекту на D. Стратегии, которые применяют опытные программисты на Java, чтобы уменьшить влияние GC на производительность, здесь вряд ли применимы.

Хотя определённо существует программы, где паузы на сборку мусора абсолютно неприемлемы, их, пожалуй, меньшинство. В большинстве проектов на D можно и нужно начинать с простых приёмов из пункта 2 в начале статьи, а затем адаптировать код к использованию @nogc и core.memory.GC там, где требуется производительность. Параметры командной строки, представленные в этой статье, помогут найти места, где это может быть необходимо.

Чем больше времени проходит, тем проще становится управлять сборщиком мусора в программах на D. Идёт организованная работа над тем, чтобы сделать Phobos стандартную библиотеку D как можно более совместимой с @nogc. Улучшения языка, такие как предложение Уолтера о выделении памяти под исключения, должны значительно ускорить этот процесс.

В будущих статьях мы рассмотрим, как выделять память, не прибегая к GC, и использовать её параллельно с памятью из GC, чем заменить недоступные в @nogc-коде возможности языка и многое другому.

Спасибо Владимиру Пантелееву, Гильяму Пьола (Guillaume Piolat) и Стивену Швайхофферу (Steven Schveighoffer) за ценные отзывы о черновике этой статьи.

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

Когда сборщик мусора отключён через GC.disable или запрещён к использованию атрибутом функции @nogc, память всё ещё надо откуда-то выделять. И даже если вы используете GC на всю катушку, всё равно желательно минимизировать объём и количество выделений памяти через GC. Это означает выделение памяти или на стеке, или в обычной куче. Эта статья будет посвящена первому. Выделение памяти в куче будет предметом следующей статьи.

Выделение памяти на стеке

Самая простая стратегия выделения памяти в D такая же, как в C: избегать использование кучи и использовать стек, насколько возможно. Если нужен массив, и его размер известен во время компиляции, используйте статический массив вместо динамического. Структуры имеют семантику значений и по умолчанию создаются на стеке, а классы имеют семантику ссылок и обычно создаются в куче (обычной, в стиле C, или управляемой GC); предпочтение следует отдавать структурам, когда это возможно. Возможности D, доступные во время компиляции, помогают достичь многого из того, что иначе было бы невозможно.

Статические массивы

Статические массивы в D требуют, чтобы размер был известен во время компиляции.

// OKint[10] nums;// Ошибка: переменную x нельзя прочитать во время компиляцииint x = 10;int[x] err;

В отличие от динамических массивов, инициализация статических массивов через литерал не выделяет память через GC. Длины массива и литерала должны совпадать, иначе компилятор выдаст ошибку.

@nogc void main() {    int[3] nums = [1, 2, 3];}

Если передать статический массив в функцию, принимающую срез массива, то автоматически происходит получение среза, что делает статические массивы взаимозаменяемыми с динамическими.

void printNums(int[] nums) {    import std.stdio : writeln;    writeln(nums);}void main() {    int[]  dnums = [0, 1, 2];    int[3] snums = [0, 1, 2];    printNums(dnums);    printNums(snums);}

Находить при помощи флага -vgc места, где создаётся динамические массивы, и по возможности заменять их на статические простая и эффективная техника. Только берегитесь случаев вроде такого:

int[] foo() {    auto nums = [0, 1, 2];    // Сделать что-то с nums...    return nums;}

В этом примере заменить nums на статический массив было бы неправильно. Функция вернула бы срез памяти, выделенной на стеке, а это программная ошибка. К счастью, компилятор не даст вам этого сделать.

С другой стороны, если возвращаемое значение зависит от какого-то условия, имеет смысл выделить память в куче только при необходимости, а не при каждом вызове функции. В данном примере мы локально создаём статический массив, а на выходе из функции создаём его динамическую копию. Встречайте свойство .dup:

int[] foo() {    int[3] nums = [0, 1, 2];    // Пусть x  результат какой-то операции над nums    bool condition = x;    if(condition) return nums.dup;    else return [];}

Эта функция всё ещё выделяет память GC через .dup, но делает это только если это нужно. Обратите внимание, что в данном случае [] эквивалентен null это срез, у которого длина (свойство length) равна 0, а свойство ptr возвращает null.

Структуры против классов

Экземпляры структур в D по умолчанию создаются на стеке, но при желании их можно создать в куче. Структуры, созданные на стеке, реализуют предсказуемое уничтожение: деструктор вызывается при выходе из области видимости.

struct Foo {    int x;    ~this() {        import std.stdio;        writefln("#%s says bye!", x);    }}void main() {    Foo f1 = Foo(1);    Foo f2 = Foo(2);    Foo f3 = Foo(3);}

Программа печатает то, что вы и ожидаете:

#3 says bye!#2 says bye!#1 says bye!

Классы, будучи типом с семантикой ссылок, почти всегда создаются в куче. Обычно это делается через GC при помощи new, хотя это можно сделать и без GC при помощи собственного аллокатора. Но никто не говорил, что их нельзя создать на стеке. При помощи шаблона [std.typecons.scoped](http://personeltest.ru/aways/dlang.org/phobos/std_typecons.html#.scoped) из стандартной библиотеки это очень просто сделать.

class Foo {    int x;    this(int x) {         this.x = x;     }    ~this() {        import std.stdio;        writefln("#%s says bye!", x);    }}void main() {    import std.typecons : scoped;    auto f1 = scoped!Foo(1);    auto f2 = scoped!Foo(2);    auto f3 = scoped!Foo(3);}

Этот пример функционально работает точно так же, как и предыдущий пример со структурами, и выводит тот же результат. Предсказуемое уничтожение достигается при помощи функции core.object.destroy, которая позволяет вызывать деструкторы вне сборок мусора.

Обратите внимание, что на данный момент ни scoped, ни destroy нельзя использовать в @nogc-функциях. Это не всегда плохо, потому что необязательно помечать функцию соответствующим аттрибутом, чтобы избежать GC, но это может стать головной болью, если вы пытаетесь запихнуть всё в @nogc-код. В следующих статьях мы рассмотрим некоторые проблемы проектирования, которые возникают при использовании nogc, и как их избежать.

При создании собственного типа выбор между структурой и классом в основном зависит от того, как его планируется использовать. Для простых данных (Plain Old Data, POD) очевидным кандидатом будет структура, тогда как для какого-нибудь GUI, где крайне полезны будут иерархии наследования и динамические интерфейсы, предпочтительным будет класс. Кроме этих очевидных случаев, есть также ряд соображений, которые могут послужить темой отдельного поста. Пока что держите в уме, что вне зависимости от того, используете ли вы для своего типа структуры или классы, его экземпляры всегда можно создавать на стеке.

alloca

Поскольку стандартная библиотека C доступна в языке D из коробки, для выделения памяти на стеке также можно использовать функцию alloca. Она особенно полезна, когда для массива желательно избежать использования GC, но размер массива неизвестен во время компиляции. Следующий пример создаёт на стеке динамический массив, размер которого известен только во время выполнения:

import core.stdc.stdlib : alloca;void main() {    size_t size = 10;    void* mem = alloca(size);    // Slice the memory block    int[] arr = cast(int[])mem[0 .. size];}

Как и в C, при использовании alloca нужно соблюдать осторожность: не переполните стек. И как и в случае с локальными статическими массивами, нельзя возвращать срез arr из функции. Вместо этого возвращайте arr.dup.

Простой пример

Предположим, что вы хотите создать тип Queue, представляющий структуру данных типа очередь. Характерной для D реализацией такого типа будет шаблонная структура, статическим параметром которой будет хранимый тип. В Java коллекции сильно опираются на интерфейсы, и рекомендуется объявлять экземпляр, используя тип интерфейса вместо типа имплементации. В D структуры не поддерживают наследование, но во многих случаях они могут реализовывать абстрактные интерфейсы благодаря проектированию через интроспекцию (Design by Introspection). Эта парадигма позволяет программировать общие интерфейсы, которые верифицируются во время компиляции без нужды в интерфейсе как отдельном типе, и потому могут работать со структурами, классами и, благодаря UFCS, даже свободными функциями (если они находятся в той же области видимости).

На русском про DbI можно прочитать на Хабре. (прим. пер.)

Очевидным выбором для внутреннего хранилища в нашей реализации Queue будут массивы. Кроме того, есть возможность сделать хранилище статическим массивом, если предполагается ограничить очередь фиксированным размером. Поскольку это уже и так шаблон, мы без труда добавим ещё один параметр: статический параметр-значение со значением по умолчанию. Теперь можно с лёгкостью указать во время компиляции, должен ли массив быть статическим, и если да, то сколько места он будет требовать.

// Размер `Size` по умолчанию 0 означает использование в качестве // внутреннего хранилища динамического массива; ненулевой размер// означает использование статического массиваstruct Queue(T, size_t Size = 0) {    // Тип константы будет автоматически определён как двоичный.    // Уровень доступа `public` позволит DbI-шаблону вне этого модуля    // определять, может ли Queue расти или нет.    enum isFixedSize = Size > 0;    void enqueue(T item)     {        static if(isFixedSize) {            assert(_itemCount < _items.length);        }        else {            ensureCapacity();        }        push(item);    }    T dequeue() {        assert(_itemCount != 0);        static if(isFixedSize) {            return pop();        }        else {            auto ret = pop();            ensurePacked();            return ret;        }    }    // Доступно только в очереди с неограниченным размером    static if(!isFixedSize) {        void reserve(size_t capacity) {             /* Выделить память под несколько элементов */         }    }private:       static if(isFixedSize) {        T[Size] _items;         }    else T[] _items;    size_t _head, _tail;    size_t _itemCount;    void push(T item) {         /* Добавить item, обновить _head и _tail */        static if(isFixedSize) { ... }        else { ... }    }    T pop() {         /* Изъять item, обновить _head и _tail */         static if(isFixedSize) { ... }        else { ... }    }    // Доступно только в очереди с неограниченным размером    static if(!isFixedSize) {        void ensureCapacity() { /* Выделить память, если нужно */ }        void ensurePacked() { /* Сжать массив, если нужно */}    }}

Теперь в клиентском коде можно вот так создавать экземпляры:

Queue!Foo qUnbounded;Queue!(Foo, 128) qBounded;

Очередь qBounded не выделяет память из кучи. Как работает qUnbounded, зависит от реализации. При помощи интроспекции можно проверить во время компиляции, имеет ли экземпляр очереди фиксированный размер. Для этого мы добавили удобную константу isFixedSize:

void doSomethingWithQueueInterface(T)(T queue){    static if(T.isFixedSize) { ... }    else { ... }}

Вместо этого можно было бы использовать встроенные возможности языка: __traits(hasMember, T, "reserve"), или стандартную библиотеку: hasMember!T("reserve"). Выражение __traits и пакет стандартной библиотеки std.traits отличные инструменты для DbI; последнему стоит отдавать предпочтение при схожей функциональности.

Заключение

Это был краткий обзор способов выделения памяти на стеке для избежания обращений к GC. Использовать их там, где возможно, простой способ свести к минимуму размер и количество выделений памяти через GC и тем самым смягчить возможное влияние сборок мусора на производительность.

В следующей статье серии мы рассмотрим способы выделять память в обычной куче, минуя GC.

Мы продолжаем цикл статей о сборщике мусора в языке D. Этот вторая часть статьи, посвящённой выделению памяти за пределами GC. В первой части говорилось о выделении памяти на стеке. Теперь мы рассмотрим выделение памяти из кучи.

Хотя это только четвёртая публикация в этой серии, это уже третья, в которой я рассказываю о способах избежать использования GC. Не обманитесь: я не пытаюсь отпугнуть программистов от сборщика мусора в языке D. Как раз наоборот. Понимание того, когда и как обходиться без GC, необходимо для эффективного его использования.

Ещё раз проговорю, что для эффективной сборки мусора нужно снижать нагрузку на GC. Как уже говорилось в первой и последующих статьях серии, это не значит, что от него нужно полностью отказываться. Это значит, что нужно быть рассудительным в том, сколько и как часто выделять память через GC. Чем меньше выделений памяти, тем меньше остаётся мест, где может начаться сборка мусора. Чем меньше памяти находится в куче сборщика мусора, тем меньше памяти ему нужно сканировать.

Невозможно точно и всеобъемлюще определить, в каких приложениях влияние GC будет ощутимым, а в каких нет это очень сильно зависит от конкретной программы. Но можно смело сказать, что в большинстве приложений нет необходимости отключать GC временно или полностью, но когда это всё-таки нужно, то важно знать, обходиться без него. Очевидное решение выделять её на стеке, но D также позволяет выделять память в обычной куче, минуя GC.

Вездесущий Си

Хорошо это или плохо, C окружает нас повсюду. На сегодняшний день любая программа, на каком бы языке она бы ни была написана, на каком-то уровне наверняка обращается к API языка C. Несмотря на то, что спецификация C не определяет стандартного ABI, его платформо-зависимые причуды достаточно широко известны, чтобы большинство языков умело с ним взаимодействовать. Язык D не исключение. На самом деле, все программы на D по умолчанию имеют доступ к стандартной библиотеке C.

Пакет core.stdc набор модулей D, транслированных из заголовков стандартной библиотеки C. Когда линкуется исполняемый файл на D, вместе с ним линкуется и стандартная библиотека C. Чтобы получить к ней доступ, нужно только импортировать соответствующие модули.

import core.stdc.stdio : puts;void main() {    puts("Hello C standard library.");}

Те, кто только начал знакомство с D, могут думать, что обращение к коду на C требует аннотации extern(C), или, после недавней статьи Уолтера Брайта D as a Better C, что код нужно компилировать с флагом -betterC. Ни то, ни другое не верно. Обычные функции в D могут вызывать функции из C без всяких дополнительных условий, кроме как наличия extern(C) в объявлении вызываемой функции. В примере выше объявление puts находится в модуле core.stdc.stdio и это всё, что нам нужно, чтобы её вызвать.

malloc и его друзья

Раз в D у нас есть стандартная библиотека C, значит, нам доступны функции malloc, calloc, realloc и free. Чтобы получить их в своё распоряжение, достаточно импортировать core.stdc.stdlib. А благодаря магии срезов языка D использовать их для работы с памятью без GC проще простого.

import core.stdc.stdlib;void main() {    enum totalInts = 10;    // Выделить место под 10 значений типа int.    int* intPtr = cast(int*)malloc(int.sizeof * totalInts);    // assert(0) (и assert(false)) всегда остаются в исполняемом файле, даже     // если проверки assert выключены, что делет их удобными для обработки     // сбоев в malloc.    if(!intPtr) assert(0, "Out of memory!");    // Освобождает память на выходе из функции. В этом примере это     // необязательно, но полезно в других функциях, которые временно    // выделают память.    scope(exit) free(intPtr);    // Снять срез с указателя, чтобы получить более удобную     // пару указатель+длина.    int[] intArray = intPtr[0 .. totalInts];}

Таким образом мы обходим не только GC, но и обычную для D инициализацию значениями по умолчанию. В массиве значений типа T, выделенном через GC, все элементы были бы инициализированы значением T.init для int это 0. Если вы хотите имитировать стандартное поведение D, потребуются дополнительные усилия. В данном примере мы могли бы просто заменить malloc на calloc, но это будет корректно только для целых чисел. Например, float.init это float.nan, а не 0.0f. Позже мы к этому ещё вернёмся.

Конечно, чтобы сделать наш код более идиоматичным, мы должны обернуть malloc и free в специальные функции и работать уже только со срезами. Минимальный пример:

import core.stdc.stdlib;// Выделяет бестиповый блок памяти, с которым можно работать через срез.void[] allocate(size_t size){    // Результат malloc(0) зависит от имплементации (может вернуть null или какой-то адрес), но это явно не то, что мы хотим делать.    assert(size != 0);    void* ptr = malloc(size);    if(!ptr) assert(0, "Out of memory!");    // Возвращает срез с указателя, чтобы адрес был сцеплен с размером    // блока памяти.    return ptr[0 .. size];}T[] allocArray(T)(size_t count) {     // Убедимся, что мы учитываем размер элементов массива!    return cast(T[])allocate(T.sizeof * count); }// Две версии deallocate для удобстваvoid deallocate(void* ptr){       // free handles null pointers fine.    free(ptr);}void deallocate(void[] mem) {     deallocate(mem.ptr); }void main() {    import std.stdio : writeln;    int[] ints = allocArray!int(10);    scope(exit) deallocate(ints);    foreach(i; 0 .. 10) {        ints[i] = i;    }    foreach(i; ints[]) {        writeln(i);    }}

Функция allocate возвращает void[] вместо void*, потому что срез несёт в себе количество выделенных байт в своём свойстве length. В нашем случае, поскольку мы выделяем память под массив, мы могли бы из allocate возвращать указатель, а в allocArray уже снимать с него срез, но тогда каждому, кто вызывал бы allocate напрямую, пришлось бы учитывать размер блока памяти. То, что в C длина массива отделена от него самого, источник большого количества ошибок, и чем раньше мы их объединим, тем лучше. Дополните наш пример обёртками для calloc и realloc, и вы получите заготовку для менеджера памяти, основанного на куче языка C.

К слову, предыдущие три примера (да, даже шаблон allocArray) работают и -betterC, и без него. Но в дальнейшем мы будем придерживаться обычного кода на D.

Чтобы не текло, как из-под крана

Когда вы работаете со срезами памяти, расположенной за пределами GC, будьте осторожны с добавлением новых элементов, конкатенацией и изменением размера. По умолчанию, операторы дополнения ~= и конкатенации ~, применённые к динамическим массивам и срезам, выделяют память через GC. Конкатенация всегда выделяет новый блок памяти для объединённого массива (или строки). Оператор дополнения обычно выделяет память только если это требуется. Как показывает следующий пример, это требуется всегда, когда дан срез памяти за пределами GC.

import core.stdc.stdlib : malloc;import std.stdio : writeln;void main(){    int[] ints = (cast(int*)malloc(int.sizeof * 10))[0 .. 10];    writeln("Capacity: ", ints.capacity);    // Сохранить указатель на массив для сравнения    int* ptr = ints.ptr;    ints ~= 22;    writeln(ptr == ints.ptr);}

Должно вывести следующее:

Capacity: 0false

Ёмкость 0 указывает, что добавление следующего элемента вызовет выделение ресурсов. Массивы, выделенные через GC, обычно имеют свободное место сверх запрошенного, так что добавление элементов может произойти без выделения новой памяти. Это свойство отвечает скорее за память, на которую указывает массив, нежели за сам массив. Память, выделенная через GC, ведёт внутренний учёт того, сколько элементов в нём может храниться до того, как потребуется выделение новой памяти. В нашем примере, поскольку место под ints было выделено не через GC, никакого учёта не происходит, поэтому добавление следующего элемента обязательно вызовет выделение памяти (см. статью Стивена Швайхоффера D slices за дополнительной информацией).

Это нормально, когда вы хотите именно этого, но если вы этого не ожидаете, то легко столкнётесь с утечкой памяти из-за того, что выделяете память через malloc и никогда её не освобождаете.

Взгляните на эти две функции:

void leaker(ref int[] arr){    ...    arr ~= 10;    ...}void cleaner(int[] arr){    ...    arr ~= 10;    ...}

Несмотря на то, что массив тип с семантикой ссылок, то есть изменение существующих элементов массива внутри функции изменит их и в оригинальном массиве, в функции они передаются по значению. Всё, что влияет на структуру массива (например, изменение свойств length и ptr) повлияет только на локальную переменную внутри функции. Оригинальный массив не изменится если его не передали по ссылке.

Если передать в leaker массив, выделенный в куче языка C, то добавление нового элемента приведёт к выделению нового массива через GC. Хуже того: если после этого освободить память, передав в free его свойство ptr (которое теперь уже указывает на адрес в куче, управляемой GC, а не в куче языка C), то мы попадём на территорию неопределённого поведения. Зато с функцией cleaner всё нормально. Любой массив, переданный в неё, останется неизменным. Внутри неё произойдёт выделение памяти через GC, но свойство ptr исходного массива всё ещё будет указывать на первоначальный блок памяти.

Пока вы не перезаписываете исходный массив и не выпускаете его из области видимости, проблем не будет. Функции вроде cleaner могут что угодно делать со своим локальным срезом, и снаружи всё будет в порядке. Если вы хотите избежать выделений памяти, то вы можете повесить на функции, к которым у вас есть доступ, атрибут @nogc. Если это невозможно или нежелательно, то либо сохраняйте отдельно указатель, возвращаемый malloc, чтобы потом передать его в free, либо напишите собственные функции для дополнения и конкатенации, либо пересмотрите свою стратегию выделения памяти.

Обратите внимание на тип Array из модуля std.container.array: он не зависит от GC, и может быть полезно использовать его, чем управлять памятью вручную.

Другие API

Стандартная библиотека C не единственный игрок на поле выделения памяти в куче. Существует несколько альтернативных реализаций malloc, и любую из них можно использовать. Потребуется вручную скомпилировать исходники и слинковать с получившимися объектами, но это не неподъёмная задача. Также можно воспользоваться системными API: например, в Win32 доступна функция HeapAlloc (просто импортируйте core.sys.windows.windows). Если есть указатель на блок памяти, то вы всегда можете снять с него срез и использовать в программе на D так же, как если бы вы получили его через GC.

Агрегатные типы

Если бы нас волновало только выделение массивов, то мы могли бы сразу перейти к следующему разделу. Однако нам нужно разобраться также со структурами и классами. В этой статье мы сфокусируемся только на структурах. Следующие несколько статей в этой серии будут посвящены исключительно классам.

Выделить память под один экземпляр структуры или целый массив зачастую не сложнее, чем с типом int.

struct Point { int x, y; }Point* onePoint = cast(Point*)malloc(Point.sizeof);Point* tenPoints = cast(Point*)malloc(Point.sizeof * 10);

Идиллия разрушается, когда имеется конструктор. Функция malloc и её друзья не умеют создавать объекты языка D. К счастью, Phobos предоставляет шаблонную функцию, которая умеет это делать.

Функция std.conv.emplace принимает либо указатель на типизированную память, либо void[], а также опциональные аргументы, и возвращает указатель на полностью готовый экземпляр этого типа. Следующий пример показывает, как использовать emplace и с malloc, и с нашей функцией allocate из предыдущих примеров:

struct Vertex4f {     float x, y, z, w;     this(float x, float y, float z, float w = 1.0f)    {        this.x = x;        this.y = y;        this.z = z;        this.w = w;    }}void main(){    import core.stdc.stdlib : malloc;    import std.conv : emplace;    import std.stdio : writeln;    Vertex4f* temp1 = cast(Vertex4f*)malloc(Vertex4f.sizeof);    Vertex4f* vert1 = emplace(temp1, 4.0f, 3.0f, 2.0f);     writeln(*vert1);    void[] temp2 = allocate(Vertex4f.sizeof);    Vertex4f* vert2 = emplace!Vertex4f(temp2, 10.0f, 9.0f, 8.0f);    writeln(*vert2);}

Функция emplace также инициализирует все переменные значениями по умолчанию. Помните, что структуры в D не обязательно имеют конструктор. Вот что будет, если мы уберём конструктор из реализации Vertex4f:

struct Vertex4f {    // x, y и z инициализируются значением float.nan    float x, y, z;    // w инициализируется значением 1.0f    float w = 1.0f;}void main(){    import core.stdc.stdlib : malloc;    import std.conv : emplace;    import std.stdio : writeln;    Vertex4f vert1, vert2 = Vertex4f(4.0f, 3.0f, 2.0f);    writeln(vert1);    writeln(vert2);        auto vert3 = emplace!Vertex4f(allocate(Vertex4f.sizeof));    auto vert4 = emplace!Vertex4f(allocate(Vertex4f.sizeof), 4.0f, 3.0f, 2.0f);    writeln(*vert3);    writeln(*vert4);}

Программа выведет следующее:

Vertex4f(nan, nan, nan, 1)Vertex4f(4, 3, 2, 1)Vertex4f(nan, nan, nan, 1)Vertex4f(4, 3, 2, 1)

Итак, emplace позволяет инициализировать созданные в куче структуры таким же образом, что и созданные на стеке с конструктором или без него. Она также работает со встроенными типами вроде int и float. Также у этой функции есть версия, предназначенная для классов, но к этому мы вернёмся в следующей статье. Только всегда помните, что emplace создаёт один экземпляр, а не массив экземпляров.

std.experimental.allocator

Весь предыдущий текст описывает основы создания собственного менеджера памяти. Во многих случаях лучше воздержаться от того, чтобы лепить что-то самому, и вместо этого воспользоваться пакетом std.experimental.allocator из стандартной библиотеки D. Это высокоуровневое API, которое использует низкоуровневые техники вроде тех, что описаны выше, а также парадигму проектирования через интроспекцию (Design by Introspection), чтобы облегчить создание аллокаторов различных типов, которые умеют выделять память под экземпляры типов и целые массивы, производить инициализацию и вызов конструкторов. Аллокаторы вроде Mallocator и GCAllocator можно либо использовать напрямую, либо комбинировать с другими строительными блоками, когда нужно что-то специфическое. Реальный пример их использования библиотека emsi-containers.

Держим GC в курсе

Поскольку обычно не рекомендуется отключать GC полностью, большинство программ на D, которые выделяют память за пределами GC, сочетают её с памятью, выделенной через GC. Чтобы сборщик мусора мог корректно работать, он должен знать обо всех внешних ссылках на память из GC. Например, основанный на malloc связный список может содержать ссылки на экземпляры классов, созданные через new.

GC можно известить об этом при помощи GC.addRange.

import core.memory;enum size = int.sizeof * 10;void* p1 = malloc(size);GC.addRange(p1, size);void[] p2 = allocate!int(10);GC.addRange(p2.ptr, p2.length);

Когда блок памяти больше не нужен, можно вызвать соответствующую функцию GC.removeRange, чтобы предотвратить его сканирование. Этим вы не освобождаете этот блок памяти. Это нужно сделать вручную через free или интерфейс аллокатора, который вы для него использовали. Обязательно прочитайте документацию, прежде чем использовать эти функции.

Поскольку мы выделяем память за пределами GC во многом для того, чтобы уменьшить количество сканируемой памяти во время сборки мусора, то может показаться, что всё это обесценивает наши старания. Но так думать неправильно. Если за пределами сборщика мусора хранятся ссылки на память из него, то жизненно важно, чтобы он об этом знал. Иначе GC может освободить память, на которую всё ещё есть ссылки. Функция addRange предназначена специально для таких ситуаций. Если есть уверенность, что блок внешней памяти не содержит ссылок на объекты из GC, то addRange вызывать не нужно.

Предупреждение

Будьте внимательны при использовании addRange. Поскольку эта функция реализована в стиле C и принимает указатель на блок памяти вместе с количеством байт в нём, то здесь можно ошибиться.

struct Item { SomeClass foo; }auto items = (cast(Item*)malloc(Item.sizeof * 10))[0 .. 10];GC.addRange(items.ptr, items.length);

GC будет сканировать блок памяти в 10 байт. Свойство length возвращает количество элементов в срезе массива. Это не то же самое, что и общий размер этих элементов в байтах если только это не срез типа void[] (или срез элементов размером в один байт, таких как byte и ubyte). Правильно будет так:

GC.addRange(items.ptr, items.length * Item.sizeof);

Пока в API рантайма не появится альтернатива, лучше написать для этой функции обёртку, принимающую параметр типа void[].

void addRange(void[] mem) {    import core.memory;    GC.addRange(mem.ptr, mem.length);}

Тогда вызов addRange(items) будет делать всё правильно. Неявное преобразование среза в тип void[] означает, что mem.length будет выдавать тот же результат, что items.length * Item.sizeof.

Цикл статей о GC продолжается

Эта статья осветила самые основы того, как использовать кучу, не прибегая к GC. Помимо классов, в нашем рассказе остался ещё один зияющий пробел: что делать с деструкторами. Я сохраню эту тему для следующей статьи, где она будет очень к месту. Вот что запланировано для следующей из цикла статей о GC. Оставайтесь на связи!

Спасибо Уолтеру Брайту (Walter Bright), Гильяму Пьола (Guillaume Piolat), Адаму Руппу (Adam D. Ruppe) и Стивену Швайхофферу (Steven Schveighoffer) за неоценимую помощь в подготовке этой статьи.