Dlang. Новый движок CTFE

В течение последних 9 месяцев велась работа над проектом под названием NewCTFE, в котором переписываются методы выполнения функций времени компиляции (СTFE). СTFE считается одной из технологий способных изменить D.

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

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

private immutable ubyte[128] uri_flags = // indexed by character
({
ubyte[128] uflags;
// Compile time initialize
uflags['#'] |= URI_Hash;
foreach (c; 'A' .. 'Z' + 1)
{
uflags[c] |= URI_Alpha;
uflags[c + 0x20] |= URI_Alpha; // lowercase letters
}
foreach (c; '0' .. '9' + 1) uflags[c] |= URI_Digit;
foreach (c; ";/?:@&=+$,") uflags[c] |= URI_Reserved;
foreach (c; "-_.!~*'()") uflags[c] |= URI_Mark;
return uflags;
})();

Вместо заполнения таблицы магическими значениями используется простой экспрессивный литерал функции. Это намного проще понять и отладить, чем некоторые непрозрачные статические массивы. ({ запускает функцию-литерал, а }) закрывает ее. () в конце говорит компилятору немедленно вызвать этот литерал, чтобы uri_flags стал результатом литерала.

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

Более подробное обсуждение CTFE смотрите в статье H. S. Teoh D Wiki.

Конечно, подобный метод может быть применен и к более сложным проблемам. Например, std.regex можно использовать со специализированным автоматом для выполнения регулярного выражения во время компиляции с использованием CTFE. Однако, как только std.regex используется с CTFE для нетривиальных паттернов, то время компиляции может стать чрезвычайно длительным (в D все, что занимает больше секунды при компиляции — избыточность :)). В конце концов, по мере усложнения паттернов, у компилятора появится нехватка памяти, и, возможно, произойдёт крах всей системы.

Причина этого может крыться в текущей архитектуре интерпретатора CTFE. Это интерпретатор AST (абстрактного синтаксического дерева) — это означает, что он интерпретирует AST во время его обхода. Чтобы представить результат интерпретируемых выражений, он использует классы узлов DMD в AST. Это означает, что на каждое вновь встреченное выражение будет выделено один или несколько узлов AST. В ограниченном цикле интерпретатор может легко создать более 100.000.000 узлов и использовать несколько гигабайт оперативной памяти. Это может быстро израсходовать память.

В issue 12844 имеет место проблема, что std.regex занимает более 16 ГБ ОЗУ для одного шаблона. Также есть issue 6498 , которая показывает, что выполняется простой от 0 до 10.000.000 узлов во время выполнения CTFE и что приводит к критичной нехватки памяти.

Простое освобождение узлов не устраняет проблему, так мы точно не знаем, какие узлы необходимо освободить, и что cделает весь компилятор очень медленным из-за сборщика мусора. К счастью, есть еще один подход, который не выделяет память для каждого вновь встреченного выражения. Он включает в себя компиляцию функции в виртуальную ISA (архитектуру набора инструкций). Эта виртуальная ISA, также известная как байт-код, затем передается выделенному интерпретатору для этой ISA (в случае, когда виртуальный ISA совпадает с ISA хоста, мы называем его JIT (Just in Time) интерпретатором).

Проект NewCTFE занимается реализацией такого интерпретатора байт-кода. Написание фактического интерпретатора (эмулятора CPU для виртуального CPU/ISA) достаточно просто. Однако компиляция кода для виртуального ISA выполняется в точности так же, как и при компиляции его в реальном ISA (хотя виртуальная ISA имеет дополнительное преимущество, которое может быть расширено для индивидуальных потребностей, но это затруднит выполнение JIT позже). Вот почему потребовался всего месяц, чтобы пучить первые простые примеры, работающие на новом движке CTFE, и почему немного более сложные из них все еще не работают даже после 9 месяцев разработки. В конце статьи вы найдете примерный график выполненной к настоящему времени работы (см. оригинал).

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

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

Данная статья является переводом статьи Штефана Коха, который является разработчиком sqlite-d, встроенного пакета в D для работы с sqlite, также он внес свой вклад в такие проекты, как SDC (Stupid D Compiler) и vibe.d. Он также был ответственен за 10% -ное повышение производительности в текущей реализации CTFE в D и в настоящее время пишет новый движок CTFE.

Оригинал статьи смотрите по ссылке The D Blog/The New CTFE Engine.

Перегородки из стекла в Москве, от производителя стеклянные безрамные перегородки заказать стеклянные перегородки на заказ, свое производство, скидки новым клиентам.

Написать ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *