Не так давно мои МФТИ-шные контесты по C для первого курса (которые больше недоступны через ejudge) были добавлены на Яндекс контест, о чём я писал вот тут: https://t.me/cpp_lects_rus/187

Сейчас случилось ещё более радостное событие: задачи были добавлены на stepik.

https://stepik.org/209865

Громадное спасибо Артёму Ершову https://t.me/iam28th за эту замечательную работу!

#c_graduate

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

https://youtu.be/fLUnJGwEmYY

https://rutube.ru/video/6753137f2fe26ea94101956c5ac2f4e4/

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

#compilers

Всем привет. Очередная лекция по компиляторам завтра в 9 утра, а сегодня вечер пятницы и небольшой брейн-тизер по C++.

template<typename T = void>
int foo(int x) { return 1; }

int foo(...) { return 2; }

template<typename T = void>
int bar() { return 1; }

int bar(...) { return 2; }

int main() {
    std::cout << foo(2) << std::endl; // ?
    std::cout << bar() << std::endl;  // ???
}

https://godbolt.org/z/qfsEvxh4E

Громадное спасибо за него Владиславу Белову https://t.me/you_are_RTshnik наткнувшемуся на эту красоту во время выполнения одного из моих заданий.

Задача довольно обычная — объяснить в чём разница с детальными ссылками на C++23. Призов не будет, кроме зрительских симпатий.

P. S. книгу обещают перепечатать к 15 ноября.

UPD: Уважаемый подписчик Артём Колпаков @ddvamp развил и усилил пример до https://godbolt.org/z/ab31ah199

#questions #cpp_postgraduate

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

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

https://youtu.be/diSnBssZ1dQ

https://rutube.ru/video/00ea76b6e9c1406fdc7814ab16ce1c8d/

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

#compilers

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

Настало время познакомиться с базовыми оптимизациями и ввести фреймворк для работы с 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