Это закреплённый пост, начните с его прочтения.

Прецедентные правила канала (просто почитайте и соотнесите с ними то что вы хотите написать): https://t.me/cpp_lects_rus/169

В качестве технического дополнения: пожалуйста не оставляйте в группе канала постов, не прикреплённых к веткам обсуждения.

Пост-предложка для сбора запросов на новые ветки: https://t.me/cpp_lects_rus/172

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

#author_event -- встречи с читателями
#c_graduate -- изложение на C для первого курса
#conference -- что-то касающееся конференций в которых я участвую
#combinatorics -- что-то про комбинаторику
#compilers -- алгоритмы оптимизирующей компиляции
#computability -- что-то про вычислимость
#cpp_graduate -- изложение на C++ для второго курса
#cpp_postgraduate -- изложение на C++ для магистратуры
#interview -- интервью со мной в разных местах
#graphics -- что-то про GPU или GPGPU
#happynewyear -- традиционное подведение итогов года
#knuth -- вольные переводы Дональда Кнута
#llm -- общение с микроволновками
#official -- под этим тегом я говорю от своего лица, обычно какие-то технические вещи и объявления
#publications -- публикации в научных журналах и не только
#riscv — нечто про открытую и расширяемую архитектуру RISC-V
#talks -- обзоры чужих докладов
#toolchain -- что-то про системы компиляции, а также ассемблеры линкеры и всё такое
#torrent -- публичная выкладка пакетами
#questions -- предложения что-то обсудить

Размечены все существующие посты. Если найдёте ошибки в разметке сообщайте.

Ютуб-канал с моими лекциями: https://www.youtube.com/@tilir
Рутуб-канал с ними же: https://rutube.ru/u/cpplectsrus/

Курс по языку C: https://youtube.com/playlist?list=PL3BR09unfgchRxdDws74aY4mlSk9eYGEs
Базовый курс по C++: https://www.youtube.com/playlist?list=PL3BR09unfgciJ1_K_E914nohpiOiHnpsK
Магистерский курс по C++: https://www.youtube.com/playlist?list=PL3BR09unfgcgf7R88ZQRQqWOdLy4pRW2h
Оптимизирующие компиляторы: https://www.youtube.com/playlist?list=PL3BR09unfgcjBG1H9xRUesaQX6nCsobs1

#official

Интересный пример предварительной пессимизации (или несовершенства компиляторов, как посмотреть), инспирированный решением одного моего студента.

https://godbolt.org/z/qa59c5MM1

Тут очевидно, что функция double_area делает то же самое, что wicked_double_area (если раскрыть скобки). Мало того, весь контекст локальный и всё доступно для оптимизаций. Но и clang и gcc не справляются — в генерированном коде получается шесть умножений против двух.

Кто возьмётся исследовать что происходит?

#questions
#compilers

Итак, книга приехала из типографии чуть раньше, чем должна была.

Поэтому также чуть раньше выкладываю первое видео курса по этой книге. Можно читать книгу и смотреть курс ))

Видео будут появляться каждую субботу с утра где-то до конца декабря.

https://youtu.be/shvOI7SQ3q4

https://rutube.ru/video/3702d41e19ad5fd3b653820b530023dd/

Первая лекция очень простая и ознакомительная — на ней мы поговорим о тех задачах, которые решает компилятор, о синтаксисе и семантике программ, рассмотрим разные оптимизации и в конце введём HIR — High Level IR, которым будем пользоваться при дальнейшем изложении.

#toolchain #compilers

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

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

https://youtu.be/0DQOmHfPErA

https://rutube.ru/video/8efdba83efac337400af15a8c81e7dbb/

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

#compilers

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

https://youtu.be/fLUnJGwEmYY

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

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

#compilers

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

На этой лекции мы наконец-то построим 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

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

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

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

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

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

#compilers

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

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

https://youtu.be/LzIvDMvZx6w

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

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

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

#compilers

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

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

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

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

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

#compilers

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

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

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

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

https://youtu.be/RK8HfK6giL8

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

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

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

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

#compilers

Официальный пост для развёрнутых отзывов к книге "Оптимизирующие компиляторы, структура и алгоритмы".

https://www.chitai-gorod.ru/product/optimiziruyushchie-kompilyatory-struktura-i-algoritmy-3059667

https://www.litres.ru/book/konstantin-vladimirov/optimiziruuschie-kompilyatory-struktura-i-algoritmy-71185981/

И на курс к ней: https://www.youtube.com/playlist?list=PL3BR09unfgcjBG1H9xRUesaQX6nCsobs1

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

Не постите сюда конкретные баги, пост с errata будет следующим. Этот пост -- чисто поделиться впечатлениями.

#official #compilers

Официальный пост для errata к книге "Оптимизирующие компиляторы, структура и алгоритмы".

https://www.chitai-gorod.ru/product/optimiziruyushchie-kompilyatory-struktura-i-algoritmy-3059667

https://www.litres.ru/book/konstantin-vladimirov/optimiziruuschie-kompilyatory-struktura-i-algoritmy-71185981/

И на курс к ней: https://www.youtube.com/playlist?list=PL3BR09unfgcjBG1H9xRUesaQX6nCsobs1

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

#official #compilers