Как стать автором
Обновить

11lc — инновационный компилятор для нового языка программирования

Время на прочтение23 мин
Количество просмотров17K
Данная статья посвящена находящемуся на стадии проектирования компилятору 11lc. В ней перечисляются наиболее яркие особенности этого компилятора.

Отсутствие скрытой неэффективности


Это свойство скорее языка программирования 11l, нежели компилятора. Однако оно настолько важно и настолько отличает язык 11l от C++, D или даже Nim, что я решил разобрать его подробно в данной статье.

Уолтер Брайт, создатель языка D, писал:
Templates in C++ have evolved from little more than token substitution into a programming language in itself. Many useful aspects of C++ templates have been discovered rather than designed.

Так вот, как я считаю, нечто похожее произошло и с семантикой перемещения (move semantics). И в C++ и в D она появилась достаточно поздно, и если бы эти языки проектировались с опорой на семантику перемещения изначально, то в них было бы гораздо меньше скрытой неэффективности (hidden inefficiency). О чём идёт речь? Рассмотрю это на примере C++.
  1. std::vector<Person> persons;
    ...
    Person p;
    ...
    persons.push_back(p);
    
    В строке с push_back(p) произойдёт копирование объекта p, хотя обычно объект p после push_back(p) не используется и более эффективно делать push_back(std::move(p)).

    Компилятор 11lc отслеживает последнее обращение к p и "заменяет" его на move(p) автоматически. Такая особенность делает возможным оставить только одну форму push_back() (точнее append()) — принимающую Person&&. Скрытое копирование в 11l запрещено, и такой код:
    Person p
    ...
    persons.append(p)
    persons.append(p)
    
    будет недействителен. Если же такое необходимо (добавить в persons объект p два раза, или другими словами: добавить p и его копию), тогда следует в первом append() обозначить это намерение явно, написав persons.append(copy(p)).
    Эта же особенность 11l позволяет автоматически "оборачивать" Person в UniquePtr (например в случае когда размер Person в байтах достаточно большой). Причём по задумке эта автоматика должна быть настолько хорошей, чтобы необходимости явного использования UniquePtr вообще не возникало.
  2. В C++ можно забыть & в типе аргумента функции, т.е. написать к примеру:
    void f(const std::set<int> st)
    {
        ...
    }
    
    что фактически не имеет смысла, т.к. делает лишнее копирование объекта типа std::set<int> при передаче его в функцию f. В 11l указать такой тип аргумента функции в принципе невозможно: если написать fn f(Set[Int] st), то аргумент будет передаваться по константной ссылке (тип const std::set<int> & в C++), а если написать fn f(Set[Int] &st), то по неконстантной (std::set<int>&).
  3. В C++ можно запросто написать:
    auto el = map[key];
    
    при этом элемент map-ы будет молча скопирован в el. В 11l такое разрешается только для простых типов (Int, Float), но если элементами map-ы являются сложные объекты, то запись var el = map[key] является запрещённой и следует писать либо var& el = map[key] (аналог auto& el = map[key]; в C++), либо var el = copy(map[key]).

    Аналогично, в C++ допустима такая запись:
    std::map<int, std::set<int>> table;
    
    auto f(int k) // забыли `&` после `auto`
    {
        return table[k];
    }
    
    В 11l же это [как можно догадаться] недопустимо (функцию необходимо объявить как fn f(Int k) -> &, либо возвращать copy(table[k])).

    Забыть & в C++ можно и в range-based for:
    for (auto p : table) // на каждой итерации будет копироваться set<int>
        ...
    
  4. И наконец, запись v2 = v1; в C++ [а также в D, Nim и многих других языках] может скрывать под собой ресурсоёмкую операцию поэлементного копирования объекта v1. В 11l же такая запись допустима лишь в двух случаях: тип v1 является простым (Int, Float, Tuple) и его копирование дёшево, либо в данном выражении осуществляется последнее обращение к v1 — в таком случае будет выполнена операция v2 = std::move(v1);. Если требуется поэлементное копирование, то в 11l его следует обозначать явно записью v2 = copy(v1).

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

И, кроме того, такое поведение компилятора также страхует от множества ошибок.
К примеру, в Nim вполне возможно написать так:
github.com/andreaferretti/kmeans/pull/2:

var s = g[c]
s.add(p)
This copies g[c] into a new variable s, instead of modifying g[c] directly. That's probably not what you want!
В 11l же запись var s = g[c] недействительна [нужно писать либо var& s = g[c], либо var s = copy(g[c])].

Отслеживание последнего обращения к объекту позволяет раньше разрушать его (ASAP destruction policy, как в Mojo).
Кроме повышения эффективности такой подход даёт возможность небольшого упрощения кода.
Например, в Python не получится сделать так:
f = open('output.cpp', 'w')
f.write('int main() {}')
os.system('g++ output.cpp')
т.к. во время вызова os.system() файл output.cpp на диске будет пустым. Для исправления этого Python-кода необходимо добавить f.close() перед os.system() либо использовать with. В 11l же файл f будет закрыт сразу же после последнего обращения к f.

Или вот такой пример кода на 11l:
var a = []
loop
   ... // использует `a`

var b = []
loop
   ... // использует `b` и `a`
// сразу по окончании цикла `a` будет разрушено

var c = []
loop
   ... // использует `c` и `b`
// сразу по окончании цикла `b` будет разрушено
// Далее используется только `c`

Без раннего разрушения для сохранения эффективности [в данном случае речь про экономию памяти] такой код пришлось бы переписать так:
var c = []
{
var b = []
{
var a = []
loop
   ... // использует `a`

loop
   ... // использует `b` и `a`
}
loop
   ... // использует `c` и `b`
}

"Смысловые" оптимизации


Увы, я не смог подобрать подходящее слово для такого нового вида высокоуровневых оптимизаций в компиляторе. Поэтому, попробую пояснить свою идею на конкретных примерах.
Вот пара строк кода на Python:
if key in dic:
    dic[key] += '...'
В любой существующей реализации Python поиск key в dic в случае наличия этого ключа в словаре будет осуществляться два раза: в выражении key in dic и в выражении dic[key], хотя по смыслу достаточно лишь однократного поиска. Т.к. именно в этом и заключается намерение программиста, пишущего такой код. (Пишущего такой код по причине того, что язык Python просто не позволяет выразить это намерение явно средствами языка. Т.е. проблему невозможности выражения некоторого намерения языковыми средствами можно решить на уровне оптимизатора! [В данном случае: осуществлять поиск key в dic только один раз.])
Хотя данный пример не очень показателен, т.к. 11l позволяет выразить такое намерение явно:
var&? sref = dic.get(key)
if sref != null
   sref ‘’= ‘...’
либо более коротко:
if var& sref = dic.get(key) // символ `?` здесь нужно опустить
   sref ‘’= ‘...’

Рассмотрим более практичный пример.
Пусть есть csv-файл с таким содержимым:
Номер,Наименование,Количество
1,Ножницы,2
2,Карандаш,3
Необходимо вывести содержимое этого файла, представив каждую строку в формате <Наименование>: <Количество>, т.е. в данном случае:
Ножницы: 2
Карандаш: 3
Конечно, номера столбцов ‘Наименование’ и ‘Количество’ можно захардкодить в программе, но правильнее будет сделать так:
import csv

reader = csv.reader(open('test.csv', encoding = 'utf-8'))
header = next(reader)
НаименованиеIndex = header.index('Наименование')
КоличествоIndex   = header.index('Количество')
for row in reader:
    print(row[НаименованиеIndex] + ': ' + row[КоличествоIndex])

На 11l такая программа записывается значительно короче:
loop(row) csv:read(‘test.csv’)
   print(row[‘Наименование’]‘: ’row[‘Количество’])

Две строки кода [против 6 у Python], которые семантически делают то же самое.
[Если интересно, вот соответствующий C++ код, который генерирует транспайлер 11l → C++.]
(Да, в Python есть csv.DictReader, используя который синтаксис получается аналогичный коду на 11l, но DictReader создаёт OrderedDict на каждую строку (запись) csv файла, и обращение к row по индексам, как в Python-коде выше, будет быстрее. Но в данном случае моей задачей было показать на что похож код, генерируемый компилятором 11l.)

Также, рекомендую к прочтению мою коротенькую статью ‘Вывод типов переменных, направленный на повышение производительности программ’.
Применительно к практике это означает, что вместо строки на Python specials_set = set('йьъЙЬЪ') (из этой статьи) в 11l можно написать просто var specials = ‘йьъЙЬЪ’, а конкретный тип для specials [StringView, Set, HashSet или вообще что-то не имеющее имени] назначит компилятор.
Аналогично можно поступить и с массивами. Так, запись var numbers = [1, 2, 7, 9] может создать CompileTimeConstArray (массив, размещённый в .rodata [сегменте неизменяемых данных программы]), StaticArray (массив, размещённый на стеке), Array (динамический массив), Set или HashSet в зависимости от использования numbers в последующем коде.

Думаю, здесь будет уместно дать пояснение какой логикой я руководствуюсь при разработке синтаксиса языка программирования и компилятора. [Это пояснение выразить на словах я затрудняюсь, поэтому приведу конкретный пример.]
Рассмотрим такой код на Python:
arr2d = [[0] * 5] * 3
arr2d[2][4] = 1
print(arr2d)
Тех, кто уже знаком с этой "фишкой" Питона, результат работы этого кода не удивит (код выведет [[0, 0, 0, 0, 1], [0, 0, 0, 0, 1], [0, 0, 0, 0, 1]]). Я же считаю такое поведение языка программирования просто неприемлемым. Выражение [[0] * 5] * 3 должно либо создавать честный двухмерный массив (точнее, массив массивов) целых чисел, равных нулю, либо это должно быть синтаксической ошибкой (т.к. вероятность того, что намерением программиста, написавшего [[0] * 5] * 3, было именно получить "поведение Python" ничтожно мала [и уж другие программисты, читающие такой код, явно не догадаются о намерении его автора]). Да, конечно, просто запомнить "как правильно" ([[0] * 5 for _ in range(3)]) не составляет большого труда, но когда массив не двух-, а трёх- или четырёхмерный, это уже становится попросту некрасиво. По этой причине, запись [[0] * 5] * 3 в 11l создаёт честный двухмерный массив (массив массивов), а если требуется поведение Python, тогда следует обозначить это явно записью [share([0] * 5)] * 3.

Конфигурация Debug Optimized


У нас на проектах [King's Bounty и Royal Quest] было три конфигурации сборки клиента: Debug, Final и Debug Optimized. Так вот, в процессе разработки использовалась практически всегда только последняя конфигурация [Debug Optimized] — это когда остаются отладочные проверки, в том числе ASSERT'ы (например, проверки на границы массивов), но включены почти все оптимизации. Конфигурацией Debug пользоваться было очень некомфортно из-за крайне низкой производительности — ощущение было такое, как будто игру запускали на каком-нибудь Pentium II.

Так я пришёл к идее о том, что конфигурация Debug вообще не нужна. Компилятор должен оптимизировать код таким образом, чтобы сохранялась возможность полноценной отладки. [Главная оптимизация, отсутствие которой приводит к такой низкой производительности конфигурации Debug, — это размещение локальных переменных в регистрах, а не на стеке.]

Одно время я вообще думал о возможности единой конфигурации сборки, но немного познакомившись с техниками оптимизирующих компиляторов понял, что это — нереалистичная задумка. [Хотя вот Go как-то обходится одной конфигурацией, но ценой отказа от агрессивных оптимизаций, присутствующих в C++.] Теперь я считаю, что Release сборку для генерирования максимально оптимизированного кода (с использованием какого-нибудь LLVM) оставить придётся, но вот от Debug конфигурации отказаться просто необходимо — её место должна занять Debug Optimized, обладающая следующими особенностями:
  1. Быстрая компиляция (в идеале как в Go или как в Delphi).
  2. Консервативная/умеренная оптимизация. Примерно уровня -O1 в GCC, с некоторыми оптимизациями из -O2.
  3. Гарантированная оптимизация хвостовой рекурсии (tail-call optimization). Даёт возможность полагаться на эту оптимизацию и писать код в функциональном стиле. [Ни в C++, ни в Python такой гарантированной оптимизации нет.]

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

Кроме того, для улучшения отладки желательно реализовать:
  1. Loop counter deoptimization — в случае если компилятор как-то оптимизировал работу со счётчиком цикла, при отладке выполняется обратное вычисление, позволяющее посмотреть актуальное текущее значение переменной-счётчика цикла.
    Вот простенький пример кода на Си:
    for (int i=0; i<100; i++)
        printf("%i\n", i*5);
    
    Если поставить точку останова на строке printf("%i\n", i*5);, то при отладке Release-сборки значение счётчика цикла i нельзя посмотреть по причине того, что в регистре-счётчике цикла компилятор сохранил умноженное на 5 значение (т.е. на каждой итерации к регистру прибавляется 5, а не 1, и цикл оканчивается по достижении 500, а не 100). Чтобы посмотреть "значение" i было возможно, отладчик должен понимать, что в регистре-счётчике цикла хранится пятикратное значение, которое необходимо просто поделить на 5.
    [Кстати, даже без умножения на 5 отладчик в MSVC до 2017 версии отказывался показывать значение счётчика цикла i и вообще любых переменных, размещённых в регистрах.]
  2. Constant unfolding — "деоптимизация", выполняемая отладчиком во время отладки, которая позволяет по шагам показать вычисление констант, которые в реальности вычисляются на этапе компиляции. Например: в var c = max([1, 2, 3]) можно заглянуть в функцию max и виртуально пройти по шагам в этой функции, хотя реально значение c вычисляется на этапе компиляции и во время выполнения функция max не вызывается.
  3. Deinlining — позволяет отладчику [как бы] входить в функции, которые были встроены, включая поддержку точек останова (breakpoints) внутри встроенных функций {что [очевидно] приводит к фактической установке точек останова во всех местах использования встроенной функции (аналогично уже сделано в отладчике MSVC при установке точки останова внутри шаблонной функции — отладчик автоматически устанавливает точки останова во всех инстанцированных экземплярах данной шаблонной функции)}.

32on64


Идея использовать 32-разрядные указатели в 64-разрядных процессах не нова, однако здесь я предложу более оригинальное решение.
Представляю вашему вниманию 32on64x4 — режим представления указателей по умолчанию в компиляторе 11lc.
Если взять любой аллокатор памяти общего назначения, то адрес выделяемых им блоков памяти не может быть выровнен менее, чем на 4 байта. Другими словами, младшие 2 бита адреса всегда равны нулю. «Почему бы это не использовать?» — подумал я и решил, что можно хранить значение указателя, сдвинутое вправо на 2 бита (т.е. делённое на 4). Таким образом, процессу становится доступно 16 Гб адресного пространства. Чего для большинства пользовательских приложений более чем достаточно.

Если требуется сохранить адрес объекта размером менее 4-х байт (например, адрес символа строки), тогда придётся хранить полноценный 64-разрядный указатель. Так, в StringView указатель на начало строки будет 64-разрядным. Но на практике это не создаёт проблем, т.к. StringView используется как правило лишь в качестве аргумента для передачи в функции, а в этом случае передаваться будет в любом случае 64-битный указатель. Так же как и в регистрах указатели всегда будут 64-разрядные. В 32-битную сжатую форму указатели преобразуются только тогда, когда их нужно записать в память.
Обратите внимание, что в типе String указатель на строку можно сделать сжатым (т.е. 32-разрядным) по той причине, что он получен от аллокатора памяти. Т.к. даже если запросить у аллокатора 1 байт, то выделенный блок будет в любом случае выровнен на 4 байта (а зачастую — на 8 или даже на 16 байт). А вот итератор по строке должен быть 64-разрядным, т.к. итератор может указывать на 1-й, на 2-й и на какой угодно символ строки.
Вопрос реализации я подробно здесь разбирать не буду, но предварительное исследование не выявило никаких принципиальных проблем. Стандартные функции выделения памяти использовать, разумеется, не получится, но VirtualAlloc() и mmap() прекрасно справляются с выделением виртуальной памяти по заданным адресам от практически самого начала адресного пространства. Указать ImageBase в PE или ELF-файле [чтобы адреса глобальных объектов можно было хранить в сжатых 32-битных указателях] также проблем не представляет.

Также можно сделать доступным режим 32on64x1 (при котором процессу доступно только 4 Гб памяти) — он чуть быстрее, чем 32on64x4, т.к. не нужно умножать/делить указатели на 4 при загрузке/сохранении, и кроме того, указатели на объекты любого размера (в том числе менее 4-х байт) — 32-разрядные, как и строковые итераторы.

И режим 32on64x8, при котором 32-разрядный указатель умножается на 8, за счёт чего процессу доступно 32 Гб памяти. Но минус этого режима по сравнению с 32on64x4 заключается в том, что выделение 4-х байт фактически выделяет 8 байт, выделение 9-12 байт выделяет 16, выделение 17-20 байт выделяет 24 и т.д., а также в том, что указатели на объекты размером 4 байта занимают 64 бита (напомню, что в 32on64x4 такие указатели занимают 32 бита). [Хотя есть и дополнительный (помимо 32 Гб доступной памяти) плюс по сравнению с 32on64x4 — в выделяемых блоках памяти гарантированно помещается два указателя, и даже самые маленькие блоки могут быть объединены в цепочки блоков, в противном случае самые маленькие блоки [размером в один указатель] требуют особой обработки, и работа с ними значительно менее эффективна по сравнению с блоками большего размера (см. ChunkSm в ltalloc).]

Хочу заметить, что режим 32on64x2 не имеет смысла: производительность у него будет такая же, как у 32on64x4, а памяти доступно меньше.

Для чего вообще заморачиваться с такими режимами, существенно усложняя компилятор? Ну, на увеличение производительности до 40% [как сказано на странице в Википедии] я как-то не слишком рассчитываю, а вот экономию памяти на 15-30% получить вполне реально. А иначе для чего в V8 был реализован подобный механизм под названием Pointer Compression?

Ну и старичка Кнута порадовать заодно:
Knuth: Recent News:

A Flame About 64-bit Pointers

It is absolutely idiotic to have 64-bit pointers when I compile a program that uses less than 4 gigabytes of RAM. When such pointer values appear inside a struct, they not only waste half the memory, they effectively throw away half of the cache.
...
Unfortunately, the -mlong32 option was introduced only for MIPS computers, years ago. Nobody has yet adopted such conventions for today's most popular architecture. ...

Please, somebody, make that possible.

Inline breakpoints


Многие компиляторы и отладчики уже поддерживают эту возможность, поэтому я не буду на ней останавливаться подробно. Просто пишу, чтобы не забыть про эту редко используемую, но весьма полезную фичу. [Кроме того, отладчик должен давать возможность сделать Step Over не на следующую строку кода, а на следующий оператор в текущей строке кода.]

Показ наиболее точной ошибки компиляции


Показ всех найденных компилятором ошибок имеет смысл в случае, когда время компиляции достаточно большое и хочется получить максимум информации за одну итерацию.
Но для быстрокомпилируемого языка программирования [такого как 11l] не имеет большого смысла показывать более одной ошибки компиляции, а имеет смысл показывать наиболее точную ошибку.
И не я один разделяю такую позицию:
Rejuvenating the Microsoft C/C++ Compiler [comments]:
with the compiler just stopping immediately on first error. That way one not only gets a potentially blazingly fast compilation (...), but one may also avoid or at least reduce the really long & ungrokable error message avalanches.
...
I support the idea to stop on first compilation error too

С точки зрения пользовательского интерфейса я вижу это так: в IDE после нажатия F7 [компиляция текущего файла/проекта] (либо скажем Ctrl + F5 [компиляция и запуск без отладки]) при обнаружении компилятором ошибки, выделение устанавливается на место ошибки (именно выделение, а не просто курсор: если обнаружен необъявленный идентификатор, то он выделяется целиком) и рядом показывается всплывающее окошко с текстом сообщения об ошибке компиляции [и возможно даже с вариантами исправления от компилятора, на которые можно щёлкнуть, что исправит файл исходного кода и сразу же перезапустит компиляцию, после чего IDE вернётся к отображению и точному месту того файла, где была нажата клавиша F7/F5/Ctrl+F5].

Встроенный статический анализатор кода


Параллельно с разработкой компилятора имеет смысл разрабатывать встроенный в него статический анализатор кода. За основу я предлагаю взять предупреждения, выдаваемые PVS-Studio, только необходимо отфильтровать из всего огромного множества выдаваемых PVS-Studio предупреждений только те, которые имеют низкие затраты ресурсов [процессор, память] на их обнаружение и которые не дают ложных срабатываний {а таковыми являются, к примеру, практически все предупреждения упоминаемые в этой статье}. Вообще, действительно полезных предупреждений не так много. Их можно найти автоматически парсингом статей в блоге PVS-Studio, посвященных статическому анализу проектов с открытым исходным кодом (т.е. достаточно рассматривать [на предмет включения в 11lc] только те предупреждения, которые там упоминаются).

Встроенный "менеджер пакетов"


В языке 11l импорт модулей осуществляется неявно — можно просто обращаться к нужной функции пиша имя_модуля:имя_функции(...). Например, если в файле исходного кода на 11l встречается fs:list_dir(‘.’), то модуль fs "симпортируется" автоматически. Но я решил не останавливаться на этой [и без того весьма оригинальной] идее, а пойти ещё дальше и… полностью отказаться от [отдельного/самостоятельного] менеджера пакетов!

Так, если запустить компиляцию исходного файла на 11l, в котором присутствует обращение к неизвестному модулю (например, вызывается функция markdown:to_html(mdtext)), то в этом случае компилятор 11lc автоматически скачает, установит этот модуль [markdown в данном случае] и продолжит компиляцию.
Немного технических подробностей
При обращении к любому модулю (посредством записи имя_модуля:имя_функции(...) либо используя синтаксис включения имён [{к примеру, запись math:pi,e, которая соответствует Python-коду from math import pi, e; запись os:*, соответствующая from os import * или запись numpy: :np, соответствующая import numpy as np}]) он ищется:
  1. В стандартной библиотеке языка 11l.
  2. В каталоге с текущим исходным файлом (ищется файл с именем имя_модуля.11l, либо подпапка с именем модуля).
  3. В локальном каталоге модулей [т.е. в установленных локально модулях].
  4. В глобальном каталоге модулей.

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

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

Сверх-быстрый dynamic_cast


Как программисту разработчику игр мне нередко приходилось заменять dynamic_cast в C++ коде на какие-то самописные велосипеды, ибо реализация dynamic_cast в компиляторах того времени, когда я занимался разработкой игр, была основана на сравнении строк(!) и являлась страшным тормозом. В новых версиях MSVC это, похоже, исправили, и dynamic_cast работает всего лишь в 40 раз медленнее сравнения указателей vptr (вот код теста сравнения производительности).

Для иерархий классов/типов без множественного наследования (либо с ограниченным множественным наследованием) можно обеспечить гарантированно сверх-быстрый dynamic_cast следующим образом: для определения возможности приведения указателя базового класса/типа к указателю производного достаточно простой проверки принадлежности vptr (указателя на vtable) диапазону от DestType.vtable до vtable последнего типа ветви дерева наследования отрастающей от DestType. Чтобы такое работало, необходимо чтобы таблицы виртуальных функций (vtable) всех классов/типов были отсортированы в памяти иерархически особым образом (в порядке прямого обхода в глубину).

Для проверки принадлежности указателя [и вообще любого целого числа, как беззнакового, так и со знаком] диапазону (т.е. что-то вроде start ≤ p ≤ end) достаточно всего лишь одной проверки (а не двух, как можно подумать) — uintptr_t(p) - uintptr_t(start) <= uintptr_t(end) - uintptr_t(start).

Для поддержки динамически подключаемого кода (например, плагинов) можно делать резерв в дереве классов/типов [для новых (объявленных в плагинах) классов/типов в иерархии], по исчерпанию которого vtables новых классов/типов будут размещаться в отдельной области памяти, что потребует дополнительной проверки указателей на vtable на принадлежность дереву всех классов/типов основной программы, но всё равно будет работать очень быстро.

Проверки времени выполнения


В 11lc предполагается реализовать 4 режима проверок времени выполнения (run-time checks):
  • fastest: режим максимальной производительности [т.е. вообще без проверок времени выполнения] — аналог release-сборки C/C++.
  • fast: добавляется минимум проверок, которые оказывают незначительное влияние на производительность (например: проверки выхода индексов за границы массивов); используется по умолчанию и он соответствует транспайлеру 11l → C++.
  • safe: добавляется проверка переполнений арифметических операций. При возникновении ошибки переполнения необходимо показывать не просто номер строки кода, а конкретный оператор, в котором произошло переполнение, например:
    r = a * b + c
              ^
    Runtime error: integer overflow in addition
    
    И дополнительно следует выдавать предложение по исправлению ошибки переполнения (в данном случае например добавить преобразование к Long: r = Long(a * b) + c) в виде патча. Пользователь приложения при наличии исходников, даже если он не программист, сможет применить патч и попробовать скомпилировать и запустить исправленное приложение.
    Также целесообразно сохранять полный дамп памяти процесса {в Windows: через вызов MiniDumpWriteDump(..., MiniDumpWithFullMemory|..., ...)}, чтобы его можно было открыть в отладчике и посмотреть значение локальных переменных и содержимое памяти на момент возникновения ошибки переполнения. (Ну это в случае когда приложение было запущено на машине пользователя [чтобы пользователь мог отправить дамп разработчику], а на машине разработчика лучше сразу открывать процесс в отладчике.)
  • safest: все опасные ссылки заменяются на WeakPtr, обходы контейнеров становятся безопасными [т.е. добавление/удаление элемента в контейнер при обходе этого же контейнера является допустимым, хотя и не гарантирует, что обойдутся все элементы (либо, как в C# порождается исключение)]. В целом безопасность в режиме safest соответствует Java, C# и другим подобным высокоуровневым языкам программирования.

Режим сохранения всех входных данных для быстрого/лёгкого обнаружения ошибки в программе


Предположим, программа упала у пользователя с ошибкой переполнения арифметической операции. Сохранение полного дампа памяти процесса — это хорошо, но оно позволит программисту посмотреть значение локальных переменных и содержимое памяти лишь на момент возникновения этой ошибки. При этом понимание того, а каким путём программа дошла до этой ошибки, будет затруднительно. Поэтому я предлагаю добавить специальный режим в компилятор, при включении которого программа при своём выполнении сохраняет абсолютно все входные данные (аргументы командной строки, консольный ввод от пользователя, содержимое читаемых программой файлов и пр.). И если в процессе работы программы возникла ошибка, то становится возможным для её быстрого/лёгкого обнаружения перезапустить программу в режиме "подмены всех входных данных" (подмены на те, что были сохранены во время её предыдущего исполнения, которое завершилось ошибкой).

Аллокатор памяти


С момента разработки мной ltalloc в 2013 году появилось довольно много других сверх-быстрых аллокаторов памяти общего назначения: smmalloc, rpmalloc, mimalloc. Кроме того, некоторые аллокаторы значительно проапгрейдились. Так, например, в TCMalloc появились:
  1. Новый режим per-CPU caching (более быстрый по сравнению с традиционным per-thread caching).
  2. Поддержка C++14's sized ::operator delete.
  3. Поддержка C++17's overaligned ::operator new и ::operator delete.

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

Почему реализацию аллокатора памяти лучше делать на уровне компилятора, а не через глобальные переопределяемые функции или операторы, как это сделано в C++?
Во-первых, режимы представления указателей 32on64x4 и 32on64x8 достаточно сложно реализовать в компиляторах языков C, C++ и вообще любых других языков программирования, в которых такие режимы не закладывались при проектировании, т.е. тут нужна поддержка как со стороны языка, так и со стороны компилятора.
И, во-вторых, это даёт возможность некоторых оптимизаций:
  • указание размера освобождаемого блока памяти (в C++14 это называется «sized ::operator delete») полезно только если размер этот известен на этапе компиляции, а если не известен, то всё равно необходимо проверять является ли выделенный блок системным или частью чанка, и проще вытащить значение size-class из заголовка чанка, чем вычислять его в run-time на основе размера;
  • если требуется выделить огромный массив из объектов, конструктор которых равнозначен заполнению всех байт объекта нулями (это не только целые числа, но и вещественные, а также указатели и все объекты, которые являются их композицией), то можно не выполнять это зануление явно после выделения памяти, а полагаться на тот факт, что память, выделенная VirtualAlloc() или mmap(), будет гарантированно обнулена при первом обращении к любой из её страниц; такой трюк уже применяется в других языках программирования (там человек спрашивает, почему одинаковый по смыслу код в Фортране работает намного быстрее, чем в C++; суть в том, что компилятор Фортрана догадывается использовать calloc() вместо явной инициализации нулями массива из 3 миллиардов вещественных чисел, а компилятор C++ не может повторить такой трюк, т.к. контейнеры STL не обращаются к malloc() напрямую, а используют глобальный operator new, который может быть переопределён, а потому, полагаться на то, что полученная им память будет заполнена нулями, не получится).

Но то, что глобальный аллокатор памяти в C++ можно переопределять — это, конечно, имеет свои плюсы. Главный — это возможность сравнить производительность различных аллокаторов памяти применительно к конкретному приложению. Если бы аллокатор был зашит в компилятор C++ с закрытым исходным кодом (как MSVC), то переопределить его было бы очень сложно. Но этот плюс теряет актуальность применительно к 11lc, т.к. встроенный аллокатор будет очень эффективным и код компилятора в любом случае будет открыт [так что при необходимости можно будет пересобрать компилятор с другим аллокатором памяти].

Эффективная стандартная библиотека


Ещё один смежный вопрос: делать ли стандартную библиотеку частью компилятора, либо это будет "что-то сбоку". Я считаю, что для максимальной эффективности стандартная библиотека (особенно, типы-контейнеры) должна быть частью компилятора.
Небольшое отступление на основе моего прошлого опыта, который, впрочем, уже не слишком актуален
В том же C++ (версии до C++11) де-юре STL является частью стандарта языка, но де-факто — она где-то сбоку, причём настолько сбоку, что у нас в последнем проекте [RQ] в коде клиента (за движок которого я отвечал) STL не использовалась вообще и практически не использовалась даже crt [C runtime] — весь необходимый функционал был реализован непосредственно через вызовы WinAPI. Да и вообще любой серьёзный игровой движок, насколько я знаю, реализует все необходимые контейнеры (строки, динамические массивы, set/hashset, map/hashmap и т.д.) и STL не использует. Впрочем, эта позиция у меня сформировалась 15 лет назад и, возможно, сейчас положение изменилось и в STL-контейнеры завезли таки эффективную реализацию на всех актуальных платформах. Хотя вот Titus Winters в 2020 жалуется на комитет по стандартизации C++ по поводу излишней заботы о сохранении обратной совместимости ABI, из-за чего не получается оптимизировать std::unordered_map:
Hash performance has been extensively researched for years now, and between table lookup optimizations and hash improvements, we believe we could provide an API-compatible unordered_map/std::hash implementation that improves existing performance by 200-300% on average. This is disallowed by ABI constraints.
И ещё примерно год назад я слышал жалобы от участника соревнований по спортивному программированию, что set в C++ работает медленнее set-а в Python.
К примеру, эффективная реализация динамического массива должна учитывать особенности аллокатора памяти, например, при запросе 800 байт (100 объектов по 8 байт каждый) по факту может быть выделено 1024 байта. Тогда реализация массива должна это учесть и скорректировать capacity на реально выделенный размер блока (в данном примере capacity должна установиться в 128, в противном случае при попытке добавить в массив 101-й элемент произойдёт выделение нового блока памяти [обычно в 1.5-2 раза большего размера] и весь массив будет перемещён в новый блок, а старый блок затем будет освобождён — всего этого можно не делать, если знать, что фактически памяти было выделено для 128-ми элементов массива, а не ста, как было запрошено). Замечу, что в стандартной библиотеке языка Си [который вроде как считается высокопроизводительным языком] нет возможности узнать, сколько именно байт выделил вызов malloc(). Но нестандартная функция _msize() в MSVC возвращает всегда ровно столько же, сколько было запрошено, а функция malloc_usable_size() в GCC возвращает чуть больше, но практически столько же, что как бы намекает на то, что с производительностью/фрагментацией malloc/free в такой реализации гарантированно будут проблемы при большом числе аллокаций широко варьируемого размера [речь про GCC, к MSVC претензия в том, что невозможно узнать размер реально выделенного блока LFH]. Занятно, что кто-то даже предлагал сделать ltalloc стандартным аллокатором памяти в musl. Но, судя по всему, проще [чем убедить заменить стандартный аллокатор musl] разработать новый язык программирования и компилятор, что, собственно, я и предлагаю сделать.


В заключение, в чём масштабная задумка языка 11l. [И обоснование того, зачем ему такой крутой компилятор.]

Я верю, что возможно создать язык программирования, столь же низкоуровневый как C и C++, и при этом обладающий выразительностью Python [что ни говорите, а какой-нибудь Nim не дотягивает до Python, и писать на нём не так приятно]. Язык, который можно использовать как скриптовый. И подключать его [с поддержкой hot reload] к низкоуровневому движку, написанному на этом же языке, т.к. нет надобности в более низкоуровневом языке.

Сейчас я пишу эти строки в Sublime Text. Это замечательный инструмент, и мне нравится писать плагины на Python, но… он [Python] — медленный. И какие-то вещи приходится выносить во внешние Python-скрипты, транспилировать их в 11l, чтобы получить быстрый исполняемый файл. И было бы здорово, если бы и редактор и плагины были написаны на одном языке, быстром как C++, удобном как Python, и с возможностью прозрачной отладки как кода самого редактора, так и его плагинов. И чтобы был нативный GUI-фреймворк, такой же удобный, как Electron, только без тормозов и дикого потребления ресурсов.

Несмотря на амбициозность этой идеи, она более скромная, чем например у Mojo [исполнять один код на CPU и на GPU, являясь при этом полным надмножеством Python] или чем у daScript/Daslang:
It's not a script:

This looks like any other script:
...
It's a lie.… It has pointers and pointer arithmetics. Static arrays. Structures.
...
There is no hidden overhead, or abstraction penalties.
...
In daScript conception the idea was ‘never have to rewrite to C or C++’. So far never had to.
In fact naively written daScript typically outperforms naively written C++...
...
And thats exactly why daScript is not a script.

  • its not simple
  • you don't write your game logic in it, you write your everything in it. yes your physics, your renderer, your shaders, and, one day, perhaps your kernel drivers.
  • no, it does not get slow, and you never have to rewrite it to C++. or C. ever
Шейдеры — это уже перебор. А вот kernel drivers… почему бы и нет. В общем, идея создать современный широкоуровневый язык программирования для центральных процессоров.
Но не просто язык, а язык сочетающий лучшие синтаксические решения современных языков. Да, синтаксис 11l разрабатывался не в изоляции, а с оглядкой на возможности и особенности других современных языков программирования. И в 11l достаточно много заимствований.
Примеры заимствований из других языков программирования (не считая C++ и Python)
  • Zig. Оператор разыменования указателя .* (сишный префиксный * мне не нравится, да и разработчикам Go тоже [хоть они его и оставили]).
  • daScript. Кортежи с именованными элементами. Когда я решил посмотреть в мануале, а как в daScript пишутся именованные аргументы при вызове функций, наткнулся на var b : tuple<i:int; f:float>. Это настолько гениально, что я сразу же решил добавить это в 11l. (Правда, синтаксис, разумеется, отличается: Tuple[Int i, Float f] b или просто (Int i, Float f) b. И, как оказалось, подобное уже есть в Swift: var b : (i:Int, f:Float), но узнал я об этом позже.)
  • Ruby. Название функций перегруженных операторов просто по их обозначению (т.е. просто fn +(...), а не fn `+`(...), fn __add__(...) или fn operator+(...)).
  • Kotlin. Неявное имя единственного параметра лямбда-выражений (it), концепция null-безопасности.
  • Swift. О. Тут вообще целая куча заимствований: квалификатор & при передаче аргумента в функцию (чтобы при вызове например fill(&arr, 0) было сразу видно, что функция изменяет arr), типы кортежей (например (String, Int)) и динамических массивов (например [Int]), перегрузка функций на основе имён аргументов, аналог guard let else (в 11l — var else) и if let (в 11l — if var), force unwrap, implicitly unwrapped optionals, а также overflow-операторы (только в 11l они пишутся немного по-другому: +&, -& и *& вместо &+, &- и &*).
Впрочем, это уже отступление от темы статьи и писать больше при синтаксис 11l здесь я не буду.

Резюмируя, хочу высказать такую мысль, что гайды, наподобие C++ Core Guidelines, должны быть зашиты в компилятор, а не в головы программистов.
Теги:
Хабы:
Всего голосов 30: ↑27 и ↓3+33
Комментарии57

Публикации

Истории

Ближайшие события