Выложил пятую лекцию курса по компиляторам.

Настало время познакомиться с базовыми оптимизациями и ввести фреймворк для работы с SSA-представлением. Эта лекция посвящена двум основным идеям: продвижению информации вниз по графу потока управления (constant propagation, copy propagation, value range propagation) и удалению избыточности (global value numbering, partial redundancy elimination).

https://youtu.be/6yo4ofdLRfU

https://rutube.ru/video/62a76dc317939e381df018f6a61be6e0/

Я понимаю, что сложно. Держитесь, впереди самое интересное.

#compilers

Выложил шестую лекцию курса по компиляторам.

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

https://youtu.be/V6hWKXvUQvo

https://rutube.ru/video/74991603431c25f8d08631b6a5c8e2bf/

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

#compilers

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

https://www.youtube.com/watch?v=dfl9IYa9gPU&t=10367s

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

Но я постарался говорить мягко и выделить в основном позитивные моменты, которых там тоже много.

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

#conference #interview

Выложил лекцию по цикловым оптимизациям

Здесь мы остановимся на основных оптимизациях циклов и попробуем их уложить в некую систему. Основными осями этой системы будут обработка индуктивностей и обработка инвариантов. Мы разберём LSR, раскрутку циклов, их пилинг и многое другое.

https://www.youtube.com/watch?v=OsiqdpCXBtY

https://rutube.ru/video/339ee2a715b0bceabf22cecd3db6f9fb/

В лекции есть небольшая деталь для гурманов.

#compilers

Продолжаю выводить в свет своих учеников. На этот раз предлагаю всеобщему вниманию наше совместное выступление с Марком Гончаровым @EverRester на RISC-V meetup в Нижнем Новгороде.

https://www.youtube.com/watch?v=9hG9pFS-O7w

В первой части я рассказываю про RISC-V и масштабируемую векторизацию, а также про цикловые оптимизации в нашем компиляторе. Это довольно обычный контент. Во второй части становится интереснее: Марк рассказывает про библиотеку SLEEF и про векторизацию циклов с математическими функциями внутри.

Мне кажется Марк проявил себя как отличный докладчик. Обязательно напишите ему что-нибудь в комментарии к видео.

#conference #riscv

Поздний пятничный вечер и пиво -- хороший фон для нашего с Полухиным и Гусаровым стендапа, записанного на C++ митапе Yadro.

https://youtu.be/LcnZKLmOUVo

Мне кажется, дискуссия была неплоха. Одна из лучших шуток это 43:55 -- моя подводка, а потом идеальная добивка от Антона. Мы не репетировали, честно.

Очередная лекция по компиляторам выйдет утром.

#conference

Выложил лекцию по межпроцедурным оптимизациям.

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

https://youtu.be/LzIvDMvZx6w

https://rutube.ru/video/26054b88c9ae1760cfd3244a369ae7ae

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

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

#compilers

Немного заслуженных поздравлений.

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

И я к таким заданиям обычно добавляю: поскольку очевидно кто-то не прав, вы получите высшую оценку за экзамен автоматом, т.е. безо всякого экзамена, если вы сделаете коммит в clang или gcc (смотря кто не прав) и его примут.

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

https://github.com/llvm/llvm-project/pull/118003

Мой студент Владислав Белов @sick_hoof со второго раза влил фикс в кланг. Первый раз его влили, но там в расширенных тестах упал assert и его откатили. Тот assert оказался ошибочным и в этом патче был торжественно удалён.

Ниже некоторые тесты, которые Владислав написал на свой коммит.

Вот тут он ожидает ошибку:

  template<typename T> struct A {
    typedef int M;
    struct B {
      typedef void M;
      struct C;
      struct D;
    };
  };

  template<typename T> struct A<T>::B::D : A<T*> {
    M m;
    // expected-error@-1 {{field has incomplete type 'M' (aka 'void'}}
  };

А вот тут он ошибки не ожидает, это должно работать:

  template<typename T> struct G {
    struct B {
      typedef int M;
      struct C {
        typedef void M;
        struct D;
      };
    };
  };

  template<typename T> struct G<T>::B::C::D : B {
    M m;
  };

Я полагаю, достойные студенты растут. Боевые. Самому иногда страшно становится.

#cpp_postgraduate

Выложил девятую (предпоследнюю лекцию) в курсе.

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

https://www.youtube.com/watch?v=Kbv21aYCoyM

https://rutube.ru/video/000c34fb9c7107f443b0caaa7a29275b

Смотреть стоит хотя бы ради упомянутой конструкции Пробстинга. Очень красивая штука. Ну и тем, кого постоянно волновало что это за новый Global ISel в LLVM и откуда он растёт, тоже ИМХО будет полезно.

#compilers

В продолжение https://t.me/cpp_lects_rus/199

Новости книги.

Наконец-то чистовой тираж был отпечатан и разъехался по магазинам, ищите во всех книжных.

Читатели, купившие книгу первого (бракованного) тиража, могут:

1. Либо сделать бесплатную замену в любом магазине.
2. Либо оставить себе книгу из первого тиража и для выдачи бесплатной электронной версии прислать на адрес dostuplitres@gmail.com почту, к которой привязан аккаунт литрес, а также подтверждение покупки книги (чек/скрин + фото книги). В течение недели редакция соберёт письма, после запросит промокоды и, когда их сформируют, вышлет на указанные адреса

P. S. и завтра с утра последняя лекция курса будет на youtube.

#official

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

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

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

И я надеюсь вам понравилось.

https://youtu.be/RK8HfK6giL8

https://rutube.ru/video/7396f97feffd6f971570fe1bc38de413/

Когда я выложил примерно половину этого курса, я увидел, что у лекций почти нет просмотров. Меня это как-то деморализовало, я ожидал всплеск интереса. Но мой студент Владик меня утешил. Он сказал, что даже когда все прочие мои курсы перестанут смотреть, этот продолжит набирать аудиторию. Будем надеяться.

P. S. У меня также предусмотрены пара интересных конкурсов с призами в виде книги (издательство обещало оплатить доставку по РФ). Скоро начнём.

P. P. S. Далее на канале нас ждёт прикладная лекция по цикловым и межпроцедурным оптимизациям в RISC-V, прочитанная мной в Сириусе (Сочи) и, бонусная рождественская лекция с ещё одним интересным содокладчиком. Не отключайтесь.

#compilers

Небольшой пятничный чиллаут. Ребята из альянса RISC-V сделали неожиданную и странную штуку -- из довольно большой панельной дискуссии в Сириусе они вырезали только моё выступление и далее только мои ответы на вопросы уважаемой аудитории. Как я понимаю, это случилось потому, что никто кроме меня их не попросил это выложить. Очень жаль, кроме меня там были и другие очень интересные спикеры.

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

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

https://rutube.ru/video/7195e749cee30a138e3950d871251ea9/

#conference #riscv

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

https://youtu.be/L2aPTxzLFUQ

https://rutube.ru/video/f4d9c2056c7daf05cff5a14ce4cc628a/

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

#toolchain #conference #riscv

Меня очень редко зовут на интервью (и почему-то обычно перед Новым Годом).

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

https://youtu.be/u3uuGrptpBs

В этом интервью я:

* Ностальгирую по токсичным форумам нулевых
* Защищаю Windows
* Критикую free software
* Высказываюсь решительно за IDE
* Положительно отзываюсь о JavaScript и 1C разработке
* Объясняю почему системное программирование неполноценно
* Даю интервьюеру советы по использованию email
* Рекомендую Алгол-68 как первый язык программирования

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

#interview

Очередной гордости за учеников пост и немного ворчания.

Анастасия Черникова, которую многие из вас уже видели на моём канале, когда мы с ней выступали на конференции Сбера, была принята в апстрим LLVM с её патчем на добавление RISC-V бэкенда для утилиты llvm-exegesis.

Ссылка на патч:

https://github.com/llvm/llvm-project/pull/89047

Доклад с Настей (увы про экзегезис там немного, но есть):

https://www.youtube.com/watch?v=5HKSeLSIya4

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

И вот я бы очень хотел к этому посту прикрепить видео нашего с Настей выступления на конференции Стачка в Питере, где мы с ней этот самый llvm-exegesis докладывали.

Увы... и это первый раз в моей практике, когда организаторы продолбали запись выступления. Собственно они потеряли не только нас с Настей.

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

Тем не менее несмотря на всё это я бы не стал об этом даже писать (мало ли какие бывают накладки) если бы не история с видео, что, конечно, уже просто край. Я удержусь от предложения организаторам переименовать конференцию, использовав вместо "Стачки" какой-нибудь другой советский термин, например "Колхоз".

Давайте лучше сконцентрируемся на позитиве и поздравим Настю с прекрасным достижением, а лучший и более расширенный доклад про llvm-exegesis мы имеем высокие шансы услышать на более серьёзной конференции https://sysconf.pro куда Настя уже подала заявку. На этот раз выступать она будет уже одна и от себя и очень надеюсь, что её там утвердят.

#conference

Пришло время для особой рождественской лекции.

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

Я её готовил не один, с материалом мне помогал мой студент Тимур, который также выступил моим со-докладчиком. Его, точно также как Марка и Настю, вы ещё тут увидите.

https://youtu.be/skhIRK3cUBM

https://rutube.ru/video/f89fa9c9fc11a3cd4c66aa387e767f41

Новогодний пост подведения итогов будет 31-го.

#computability

Пост итогов 2024-го года.

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

Главный итог для меня -- вышла моя книга по компиляторам и я выложил сопутствующий ей видео-курс.
Книга: https://www.chitai-gorod.ru/product/optimiziruyushchie-kompilyatory-struktura-i-algoritmy-3059667
Курс: https://www.youtube.com/playlist?list=PL3BR09unfgcjBG1H9xRUesaQX6nCsobs1

Я также записал до конца практический курс по языку C: https://www.youtube.com/playlist?list=PL3BR09unfgchRxdDws74aY4mlSk9eYGEs

Особое спасибо Юлию Тарасову, Владиславу Белову и Марку Гончарову без которых ничего бы не было.

Я также опубликовал ряд эссе. Хочется подсветить два:
1. Про поведение на моём канале https://telegra.ph/Styortye-kommentarii-moih-zabanennyh-podpischikov-04-13
2. Про тезис и тест Тьюринга https://telegra.ph/Tezis-Tyuringa-09-06

Для меня этот год снова был годом активного участия в конференциях. Пожалуй даже с элементами оверкоммитмента. Самые важные:
Yadro meetup про цену абстракции: https://youtu.be/cK4cMdx9QeQ
МТС про RISC-V: https://youtu.be/qoNjayusCX4
C++ Russia про разрешение имён: https://youtu.be/kJ6RvI9A1bU

На некоторых конференциях я выступал не один и вообще начал выводить в свет своих учеников.
Сбер Гига Конф про LLVM с Настей Черниковой: https://youtu.be/5HKSeLSIya4
RISC-V meetup про SLEEF с Марком Гончаровым: https://youtu.be/9hG9pFS-O7w
Лекция про вычислимость с Тимуром Голубовичем: https://youtu.be/skhIRK3cUBM

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

Также я со своей командой заопенсорсил генератор тестов для системной верификации llvm-snippy и ходил всюду его докладывал. И продолжу делать это.
Heisenbug про snippy: https://youtu.be/ceAK85rAkfY&t=146s
Zero cost conf про snippy: https://youtu.be/A8FSh8eFj1w

Мой телеграм-канал вырос до более чем 6.5к человек и мой youtube-канал до более чем 24к. Фактически это делает мой youtube-канал более популярным чем большинство крупных русскоязычных конференций (С++ Russia 15к, Heizenbug 19.5к, Истовый Инженер 11.5к, True Tech 2.7к, SaluteTech 2.2к). Хорошо, что есть YfD с его 67к, так что мне ещё есть куда расти. Это ставит передо мной интересную диллему: а надо ли мне вообще куда-то ездить? Может наоборот пора звать к себе гостей? Пока что я решил, что поезжу и уже записался на три конференции, посмотрим как пойдёт.

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

Ещё я хочу поездить в этом году по городам России и дружественных безвизовых государств, провести встречи с читателями. Как минимум Москва, Питер, Нижний и Новосибирск, с высокой вероятностью Екатеринбург и Минск, в идеале -- в каждый город собравший 10+ лайков под вот этим постом (и под предшествующим ему): https://t.me/cpp_lects_rus/197

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

Всех с наступающим Новым Годом!

#official #happynewyear

В качестве, видимо, новогоднего подарка мне, на канале NDC выложили прекрасный доклад Шона Парента:

Locknote: Local Reasoning in C++ - Sean Parent - NDC TechTown 2024 https://youtu.be/bhizxAXQlWc

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

---

00:00 Failed software projects.

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

10:00 Local reasoning.

Что такое возможность рассуждать о свойствах программы локально? Это возможность убедиться в корректности части кода, независимо от контекста в котором эта часть будет использована. Ключ к такой возможности это корректное использование API на стороне client и его разумное проектирование на стороне implementor.

Также немного о предусловиях: тщательно выписываем предусловия конкретных функций, выносим общие предусловия.

15:56 Mutation

Почему мы вообще хотим использовать модифицируемые переменные? Нищета программирования с иммутабельными структурами на примере замены двигателя. Очень часто именно мутабельные переменные проще для доказательства свойств. Дуализм трансформации и действия.

void a(T& x) { x = t(x); } // a from t
T t(T x) { a(x); return x; } // t from a

Но см. ниже, этот дуализм работает не всегда.

18:38 Laws of exclusivity

std::vector a{0, 1, 1, 0};
erase(a, a[0]);
println("{}", a);

Не запуская годболт, догадайтесь что будет на экране. Потом посмотрите пример. Удивительно, но это даже не UB.

Далее Парент приводит правила исключения одновременных ссылок для Swift и Rust. Фактически то же правило есть в C++ (если вы не хотите проблем), но убедиться в его соблюдении -- задача разработчика.

29:05 Projections and Objects

Проекция это получение ссылки на часть объекта. Проекции могут быть инвалидированы как итераторы для контейнера или как отображение или как повисшая ссылка и т.д.

Оказывается дуализм между действием и трансформацией, описанный выше работает только для инкапсулированных (contained) объектов, но не для их проекций. Нам нужно чтобы выполнялся equational reasoning -- свободная замена равных подвыражений в выражениях.

Главное при проектировании типа для объектов это отношение часть/целое. Это отношение обладает свойствами связанности, ацикличности, сепарабельности и владения.

Если бы у нас были только отношения части и целого, то проблема, поставленная в начале, была бы решена. Увы, мир сложнее.

45:20 Extrinsic relashionships

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

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

54:40 Structural complexity

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

01:05:24 Summary

---

От себя добавлю что именно такого рода разматывание внешних связей между сущностями и то, как это привело к гораздо лучшему проектированию генератора llvm-snippy, я показывал на Zero-cost conf прошлого года. Но там от меня это был конкретный пример проектирования, к тому же изрядно перемешанный с деталями предметной области. Здесь же Шон Парент даёт очищенную эссенцию такого подхода, практически с математической точностью формулировок.

#talks

Уважаемый подписчик Vadim Flyagin прислал ссылку на опен-сорсную книгу по C23 от одного из авторов нового стандарта языка C.

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

https://gustedt.wordpress.com/2024/10/15/the-c23-edition-of-modern-c

Конкретная ссылка: https://inria.hal.science/hal-02383654v2/file/modernC.pdf

#c_graduate

Продолжаем разговорные жанры. Выступил на Pure Virtual Cast. Обсудили предстоящую конференцию, книгу и всякие общие вопросы.

https://www.youtube.com/live/c6eNjazhRCQ

Have fun.

#interview