Компиляторы *

Но действительно ли это так? И что вообще значит «запустить»?

Ведь все так и делают)

• запрет возврата из функции ссылок на временное значение,
• [[indeterminate]] и уменьшение количества Undefined Behavior,
• диагностика при =delete;,
• арифметика насыщения,
• линейная алгебра (да-да! BLAS и немного LAPACK),
• индексирование variadic-параметров и шаблонов ...[42],
• вменяемый assert(...),
• и другие приятные мелочи.

Некоторые паттерны стало возможно использовать на практике только благодаря безопасности Rust по памяти, а на C++ они слишком опасны. В статье приведён один такой пример.

Работая над внутренней библиотекой, написанной на Rust, я создал тип ошибок для парсера, у которых должна быть возможность сделать Clone без дублирования внутренних данных. В Rust для этого требуется указатель с подсчётом ссылок (reference-counted pointer) наподобие Rc.

Поэтому я написал свой тип ошибок, использовал его как вариант ошибок fallible-функций, и продолжил двигаться дальше.

Задавались ли вы когда-нибудь вопросом, можно ли полноценно программировать при помощи директивы #define в языке C? Полнота по Тьюрингу шаблонов C++ известна весьма широко, например, люди пишут трассировщики лучей, делающие все вычисления во время компиляции (вместо времени исполнения). А как обстоят дела с препроцессором C? Вопрос оказался сильно нетривиальнее, и эта история является, на мой вкус, отличным анекдотом для курса лекций по теории компиляторов, что я готовлю в данный момент. В частности, для лучшего понимания происходящего здесь, рекомендую ознакомиться со второй статьёй, которую я опубликовал параллельно этой: лексер и парсер.

Чтобы не было обманутых впечатлений, предупрежу сразу, что рейтрейсера не будет, но про́клятый код будет очень даже! Итак, поехали. Для начала, почему я вообще задался этим вопросом? Если обычный код компьютерной графики вам скучен, следующий раздел можно пропустить, перематывайте до последней картинки.

Вам когда-нибудь приходилось задаваться вопросом, как работает компилятор, но так руки и не дошли разобраться? Тогда этот текст для вас. Мне тоже не доводилось заглядывать под капот, но тут так случилось, что мне нужно прочитать курс лекций о компиляторах местным третьекурсникам. Кто встречался с некомпетентными преподавателями? Здравствуйте, это я :)

Итак, чтобы самому разобраться в теме, я собираюсь написать транслятор с эзотерического языка программирования wend (сокращение от week-end), который я только что сам придумал, в обычный ассемблер. Задача уложиться в несколько сотен строк питоновского кода. Основной репозиторий живёт на гитхабе (не забудьте заглянуть в мой профиль и посмотреть другие tiny* репозитории).

Хотя уменьшение сегодня уже необязательно, оно всё равно лучше.

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

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

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

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

В современном мире, где ИИ постепенно заменяет программистов, отнимая у них работу и совершая переворот в том, как мы подходим к рассуждениям о коде, нам, возможно, следует быть более открытыми к мыслям людей, недавно пришедших в нашу отрасль? На самом деле, показанный выше код — идеальный пример компромисса между временем и задействованной памятью. Мы жертвуем временем и в то же время памятью и временем компьютера! Поистине чудесный алгоритм!

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

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

Простое, нестандартное процессорное ядро с открытым кодом, которое может быть использовано для создания микроконтроллера в базисе ПЛИС, в том числе ПЛИС - ОП.

• улучшенный static_assert,
• переменная _,
• оптимизация и улучшение для std::to_string,
• Hazard Pointer,
• Read-Copy-Update (так же известное как RCU),
• native_handle(),
• целая вереница классов *function*,
• множество доработок по constexpr,
• std::submdspan,
• и прочие приятные мелочи.

Это история о баге, который бы заставил вас рвать на себе волосы. Из-за такого бага вы можете подумать: «Но это невозможно, должно быть, компилятор сломался, других вариантов нет!»

А баг компилятора — это серьёзно: за двенадцать лет программирования на C++ я обнаружил (и написал отчёт) всего... об одном. И могу сказать, что перед отправкой отчёта о баге GCC, я максимально тщательно протестировал и проверил его, чтобы не выглядеть идиотом.

Впрочем, ладно, вот моя история.

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

Наверное, многие слышали, что неопределённое поведение (undefined behavior, UB) -- постоянный источник разнообразных багов, иногда очень забавных, иногда довольно жутких. Тема также неоднократно освещалась и на Хабре, навскидку раз, два, три (и даже целый тег есть). Однако чаще всего статьи по данной теме посвящены тому, как можно отстрелить себе ногу, голову или случайно сжечь свой жёсткий диск, исполнив какой-нибудь опасный код. Я же намерен сделать акцент на том, зачем авторы языков программирования надобавляли всей этой красоты, и как оптимизатор может её эксплуатировать. Всё будет проиллюстрировано наглядными примерами из LLVM и присыпано байками из собственного опыта, так что наливайте себе чай, располагайтесь поудобнее, и погнали.

Немного о bfc

Brainfuck — очень глупый язык. Там есть лента из 30к ячеек, по байту каждая. Команды bfc это:

• Передвижение по ленте влево и вправо (символы < и >)
• Увеличение и уменьшение значения в ячейке (символы + и -)
• Ввод и вывод текущей ячейки (символы . и ,)
• И цикл while, который продолжается пока значение в текущей ячейке не ноль. [ и ] это начало и конец цикла соответственно

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

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

Коротко обо мне. Меня зовут Макс, и так получилось, что я вот уже 10 лет, почти с самого начала своей карьеры, занимаюсь оптимизирующими компиляторами. Я начинал в Intel, потом перешёл в Azul Systems, год провёл в Cadence и вернулся обратно, всё это время занимаясь компиляторными оптимизациями для Java, C++ и нейросетевых моделей. На момент написания статьи у меня чуть за 900 патчей в LLVM, большинство из них посвящено цикловым оптимизациям.

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

Итак, поехали.