C++ and other lectures

Выложил своё выступление на конференции Аскон от 25 апреля сего года. По сути это очень сжатый (мне урезали таймслот до 40 минут и я выживал в этих пределах как мог) рассказ про многопоточность с нуля и до транзакционной памяти. Огромная благодарность организаторам за отличные съёмки, монтаж и разрешение выложить на своём канале. https://www.youtube.com/watch?v=R1XcV5vHn0I #conference

Всем привет. После размышлений и консультаций, было решено что пиринговый экзамен по курсу устроим в следующую субботу, 27 мая. В течении недели есть время на подготовку. Проголосовали "за" в опросе 45 человек, вполне достаточно для экзамена. Если решите сдавать, добавляйтесь в группу https://t.me/+RtzEqpc4OKpmYzhi вся остальная информация о формате проведения и прочем — будет там. #official

Моё прошлогоднее выступление на C++ Russia наконец-то выложили в открытый доступ (раньше было только по ссылке). https://www.youtube.com/watch?v=YJd6Ig4ihJ0 Напоминаю что у этого выступления есть follow-up и допглавы: https://www.youtube.com/watch?v=-aE1hD9OWRk где мы погружаемся глубже и разбираем те же вопросы более обстоятельно. #conference #graphics

Всем привет. Есть такая идея — для всех кто вместе со всеми нами весь год смотрел магистерский курс провести пиринговый экзамен (когда вы пишете задание и оно отправляется на проверку двум людям и вам тоже приходят два задания других людей). Задание будет состоять из двух задач. Одна вида "спроектируйте класс" (нечто многопоточное или с умными указателями или с аллокаторами или всё вместе), другая вида "напишите код" (обычно что-то с корутинами или параллелизмом или вместе). Четыре часа на выполнение (можно не отлаживать код до идеального состояния, достаточно продемонстрировать идею), потом четыре часа на кросс-проверку. Сколько людей хотело бы в таком участвовать в какие-нибудь ближайшие выходные? Сейчас устрою опрос, проголосуйте там если хотите, а этот пост оставлю для комментариев. #official

Выложил последнюю лекцию курса. Она завершает изложение корутин и в отличие от прошлой существенно уходит от изложения прошлого года. Я подключаю многопоточку и она помогает мне раскрыть главную тайну корутин. https://youtu.be/WZhxMwKaXmw Это завершает мой магистерский курс и я сам не верю что мне удалось его записать и выложить. У меня бы это не получилось без Юлия Тарасова https://t.me/botan_razdolb который на всех этих лекциях был оператором и звукорежиссером (и немного продюсером). Базовый курс 2021-22 и магистерский курс 2022-23 вместе это главное что есть на моём канале. Дальнейшие творческие планы -- это записать наконец-то базовый курс по языку C и ассемблеру. Также хочется записать курс по вычислимости. И может быть что-то по бэкендам компиляторов. Летом я скорее всего также запишу и выложу несколько обещанных лекций по системам сборки (я обещал на 1к в телеграме и приближается 10к на ютубе). Ну и ещё бы перезаписать тулчейн с понями, так как слайдов явно добавилось и пони тоже. В общем как мне сказала сейчас ChatGPT когда я попросил её сделать последнюю фразу этого поста: "пусть каждый ваш день будет наполнен сияющими моментами и вдохновением, а ваши мечты сбываются с легкостью. Идите вперед и покоряйте мир своим уникальным блеском".

Выложил первую часть последней лекции лекцию магистерского курса — мы начинаем сопрограммы. https://youtu.be/mDajl0pIUjQ Сначала мы потратим немного времени на обзор разновидностей сопрограмм, потом исследуем их основные части и дальше нас ждёт много интересных упражнений: собственный генератор, исследование объектов ожидания и разбор тонких и сложных проблем.

Всем привет. И снова настало время обратиться за небольшой помощью к залу. В своей лекции про многопоточность я использую иллюстрацию замечательного русского художника В. Г. Сутеева (три котёнка это три потока, труба это критическая секция. И вот я подумал почему бы не попросить картинку у нейросети. Я использовал Кандинского 2.1 и пытался формулировать запросы. Запросы были такие: "три котёнка в трубе", "три котёнка ползут по трубе", "три котёнка внутри трубы". Я сгенерировал наверное изображений тридцать, прикладываю три самых симпатичных. Но это всё не то. Мне нужна картинка как три котёнка забегают в лежащую на земле трубу по одному. Приглашаются эксперты в общении с нейросетями. Будет здоров если вы добьётесь от любой распространённой нейросетки какой надо картинки и расскажете мне и всем нам как вы это сделали, а мы поучимся. #llm #questions

На канале введена система тегов. #c_graduate -- изложение на C для первого курса #cpp_graduate -- изложение на C++ для второго курса #cpp_postgraduate -- изложение на C++ для магистратуры #toolchain -- что-то про системы компиляции, а также ассемблеры линкеры и всё такое #official -- под этим тегом я говорю от своего лица, обычно какие-то технические вещи и объявления. #questions -- предложения что-то обсудить #conference -- что-то касающееся конференций в которых я участвую #talks -- обзоры чужих докладов #llm -- общение с микроволновками #torrent -- публичная выкладка пакетами #combinatorics -- что-то про комбинаторику #graphics -- что-то про GPU или GPGPU #knuth -- вольные переводы Дональда Кнута Размечены все существующие посты. Если найдёте ошибки в разметке сообщайте. #official

Выложил новую лекцию по C++. На этот раз она посвящена параллелизму. https://youtu.be/nvjQTt2RM8A После того как мы выбрались из атомиков, она гораздо более расслабленная. Начнём мы с рассмотрения параллелизма через политики стандартных алгоритмов. Далее исследуем варианты написания собственных параллельных алгоритмов через std::async. Далее нас ждут GPGPU и основы SYCL. В конце придёт время для того чтобы заглянуть в будущее и посмотреть что встретит нас в 2026-м году и далее.

Выложил финальную лекцию по атомикам. На этой лекции мы завершаем рассмотрение этой огромной темы. Наконец-то мы напишем bounded lock-free queue и снимем замеры. Но до этого нам предстоит разобраться с моделями памяти и теорией относительности. Лекция заканчивается большим списком литературы. https://youtu.be/Y1q_Z2T2UcE

Немного контента для гурманов. Шестой уже по счёту черновик допсеминара для первого курса по лексическому и синтаксическому анализу (рассматривается рекурсивный спуск, изложение на С). В чистовом варианте т.е. с видео и обработанным звуком в публичном доступе планирую в следующем году. https://youtu.be/pZntrD8a6dc

Выложил вторую лекцию по атомикам. Искренне ей горжусь так как впервые мне удалось, если можно так выразится, правильно расставить телегу и лошадь. Ранее я методически ориентировался на Саттера с его juggling razor blades, но, как показала практика, Саттер уделяет много внимания более редкой и экзотической проблеме ABA, упуская более распространённую и насущную проблему гонки вокруг удаления в lock-free программах (reclamation problem). https://youtu.be/hb_kREmFnX0 Начнём мы с того, что погрузимся в неприятные части атомиков. Начав с рассмотрения уже знакомых нам проблем проектирования, таких как API races (а также посмотрев способ их решения через формальные методы), мы пойдём к более сложным и специфичным проблемам. Первая такая проблема это и будет тот самый reclamaition -- ранний отзыв указателя. Вторая проблема это ABA. Мы поговорим о том какими способами (как аппаратными так и на уровне языка) мы решаем такие проблемы. Закончим мы тем, что потрогаем вопросы переупорядочения. В первые пять минут — ещё раз объяснение про иерархию свободы от блокировок. Никогда не устаю такое объяснять.

Выложил очередную лекцию магистерского курса — вторую лекцию про атомики. Эта лекция — нечто, чем я в этом году обоснованно горжусь. Всегда ранее я недостаточно хорошо освещал этот материал (и мне даже удивительно насколько мало людей замечали подвох). Мало того, в знаменитом докладе Саттера, который Juggling razor blades содержится та же ошибка — рассматривая более тяжёлую и редкую проблему ABA он вообще не уделяет внимание более простой и распространённой проблеме отзыва указателя. И вообще в сети не так просто найти эталонно хорошее изложение таких вещей. И вот мне кажется, что на этот раз у меня получилось правильно расставить телегу и лошадь. https://youtu.be/hb_kREmFnX0 Начнём мы с рассмотрения уже знакомых нам проблем проектирования, таких как API races (а также посмотрев способ их решения через формальные методы). А вот потом мы пойдём к более сложным и специфичным проблемам. Первая такая проблема это тот самый reclamaition -- конкурентное удаление или ранний отзыв указателя в lock-free программах. Вторая проблема это то самое ABA. Мы поговорим о том какими способами (как аппаратными так и на уровне языка) мы решаем такие проблемы. Закончим мы тем, что потрогаем лапкой вопросы переупорядочения.

return 1; } Теперь функция next_turn ищет оптимальное количество спичек для взятия, проверяя, что после хода противника останется достаточное количество спичек, чтобы выиграть игру. Если оптимальный ход недоступен, функция возвращает 1, чтобы взять одну спичку и надеяться на ошибку противника. Эта реализация должна работать правильно на входных данных, которые вы указали. --- Здесь я сдался -- она так и не смогла ничего понять и пройти контест.

assistant: Извините за предыдущую ошибку. Вы правы, что текущая реализация функции next_turn не гарантирует победу. Давайте попробуем найти оптимальную стратегию, учитывая ваши предложения. Итак, было 100 спичек, я взял 33, вы взяли 12. Осталось 55 спичек. На этом этапе, я могу взять от 1 до 24 спичек. Если я взял 3 спички, то останется 52 спички. Ваши возможные ходы будут от 1 до 6 спичек. В любом случае, я смогу забрать последнюю спичку. Давайте перепишем функцию next_turn с учетом этой стратегии: int next_turn(int total, int possible) { if (total == 1) { return 1; } if (total <= possible + 1) { return total - 1; } for (int i = 1; i <= possible; i++) { int remaining = total - i; int opponents_max = 2 * i; int optimal_choice = -1; for (int j = 1; j <= opponents_max; j++) { int next_remaining = remaining - j; int next_opponents_max = 2 * j; if (next_remaining <= next_opponents_max + 1) { optimal_choice = i; break; } } if (optimal_choice != -1) { return optimal_choice; } } // Если оптимальный ход недоступен, берем одну спичку и надеемся на ошибку противника return 1; } Теперь функция next_turn должна выбирать количество спичек, которое гарантирует победу, учитывая условие ограничения на количество спичек, которое можно взять, исходя из предыдущего хода противника. Если оптимальный ход недоступен, функция возвращает 1, чтобы взять одну спичку и надеяться на ошибку противника. user: Смотрите, на входных данных 10 9 вы берёте 9 спичек. Значит на следующий ход я выигрываю забирая последнюю. Ваша правильная стратегия тут будет такой: взять 2 спички и тогда что бы я ни взял от 1 до 4, ваши ответы будут такими: если я беру одну то вы берёте две, если я две то вы одну, если я три то вы две и если я четыре то вы одну. И таким образом во всех случаях вы побеждаете. Попробуйте поправить вашу программу чтобы она реализовала такую стратегию. assistant: Извините за ошибку в предыдущей реализации. Вы правы, моя стратегия была неправильной. Давайте попробуем еще раз. int next_turn(int total, int possible) { if (total == 1) { return 1; } if (total <= possible + 1) { return total - 1; } int remaining = total; int opponents_max = possible; int optimal_choice = -1; for (int i = 1; i <= possible; i++) { int next_remaining = remaining - i; int next_opponents_max = 2 * i; if (next_remaining <= next_opponents_max + 1) { optimal_choice = i; break; } } if (optimal_choice == -1) { optimal_choice = 1; } return optimal_choice; } Теперь функция next_turn ищет оптимальное количество спичек, чтобы взять исходя из условия ограничения на количество спичек, которое можно взять, исходя из предыдущего хода противника. Если оптимальный ход недоступен, функция возвращает 1, чтобы взять одну спичку и надеяться на ошибку противника. Эта реализация должна работать правильно на входных данных, которые вы указали. user: Но вы же снова при входе 10 и 9 берете 9, ничего не поменялось! assistant: Извините, я сделал ошибку в предыдущем коде. Давайте попробуем снова с исправленной версией функции next_turn: int next_turn(int total, int possible) { if (total == 1) { return 1; } if (total <= possible + 1) { return total - 1; } int my_turn; for (my_turn = 1; my_turn <= possible; my_turn++) { int opponent_max = 2 * my_turn; int remaining_after_my_turn = total - my_turn; int opponent_turn; for (opponent_turn = 1; opponent_turn <= opponent_max; opponent_turn++) { int remaining_after_opponent_turn = remaining_after_my_turn - opponent_turn; if (remaining_after_opponent_turn <= 2 * opponent_turn + 1) { break; } } if (opponent_turn > opponent_max) { return my_turn; } }

Благодаря моему бывшему студенту и коллеге Саше, который сейчас работает в Канаде, получил возможность поэкспериментировать с ChatGPT4. Ниже лог попытки использовать её для решения на языке C задачи HWF (это задача для первого курса). Ниже результаты выгрузки. user это я. assistant это нейросеть. --- user: Два игрока играют в интересную игру: изначально дано N спичек. Первый игрок берёт любое количество, но не все сразу спички. Теперь второй может взять не больше, чем вдвое больше чем первый. Далее первый берёт не больше чем вдвое больше второго. И так далее. Выигрывает тот, кто взял последнюю спичку Партия 1: 11 спичек. Первый берёт 4, второй может взять до 8 и берёт 7, победа. Запись партии: 11.4,7! Партия 2: 11.3,3,5! Партия 3: 11.3.2.1.1.1.1.2! Ваша посылка должна состоять из функции, которая по общему количеству оставшихся (total) и количеству допустимых к взятию (possible) спичек будет возвращать сколько спичек она хочет взять Разумеется, ваша функция всегда должна делать оптимальный ход Если оптимальный ход невозможен (все ходы плохи), разумно взять одну спичку и дать противнику шанс сделать ошибку int next_turn(int total, int possible) { // TODO: ваш код здесь } assistant: Вам нужно определить оптимальный ход для игрока, чтобы он смог выиграть игру, следуя условиям игры. Вот функция, которая реализует требуемую логику: int next_turn(int total, int possible) { if (total <= possible + 1) { return total - 1; // Выигрышный ход: забираем все спички, кроме одной } // Находим максимальное число спичек, которое можно взять, чтобы оставить оптимальное количество спичек противнику int max_matches_to_take = (total - 1) / (possible + 1); // Если все ходы приводят к поражению, берем одну спичку и надеемся на ошибку противника if (max_matches_to_take == 0) { return 1; } // Если возможно, берем максимально возможное количество спичек, чтобы оставить оптимальное количество спичек противнику if (max_matches_to_take <= possible) { return max_matches_to_take; } // В остальных случаях берем одну спичку и надеемся на ошибку противника return 1; } Функция next_turn определяет оптимальный ход для игрока на основе текущего состояния игры. Если оптимальный ход недоступен, игрок берет одну спичку и надеется на ошибку противника. user: Обратите внимание, что на каждый ход вы можете взять не более чем вдвое больше спичек, чем противник взял в предыдущем ходу. Кроме того, при входных аргументах 100 99 вы взяли 99 спичек и противник следующим ходом выигрывает. Предполагается, что выигрывать должны вы. Правильный ответ в таких условиях — взять три спички. assistant: Извините за недопонимание. Я учту условие о том, что можно взять не более чем вдвое больше спичек, чем противник взял в предыдущем ходу, и предложу исправленный код функции next_turn. int next_turn(int total, int possible) { for (int i = 1; i <= possible; i++) { int remaining = total - i; int opponents_max = 2 * i; if (remaining <= opponents_max + 1) { // Оставляем оппоненту невозможную ситуацию, гарантируя себе победу return i; } } // Если оптимальный ход недоступен, берем одну спичку и надеемся на ошибку противника return 1; } Теперь функция next_turn выбирает количество спичек, которое гарантирует победу, учитывая условие ограничения на количество спичек, которое можно взять, исходя из предыдущего хода противника. Если оптимальный ход недоступен, функция возвращает 1, чтобы взять одну спичку и надеяться на ошибку противника. user: Рассмотрим снова вход 100 99. Вы теперь берёте 33 спички. Следующим ходом противник берёт 12 спичек и это гарантирует ему в дальнейшем выигрыш при любой вашей стратегии. Чтобы вам это продемонстрировать и объяснить как переписать программу, давайте доиграем эту партию. Итак, было 100 спичек, вы взяли 33, я взял 12. Ваш следующий ход? Попробуйте учесть все варианты и выиграть партию.

Выложил очередную лекцию магистерского курса — первую в длинной серии про атомики. Сейчас начинается премьера, а через полтора часа лекция будет доступна для произвольного просмотра по разметке. https://youtu.be/JRUbzoVfkkw На этой лекции мы начнём с обстоятельной работы над ошибками. Надеюсь мне удалось сделать её и увлекательной и поучительной. Ну а дальше всё по обычной схеме. Введение в атомики это классика жанра и что-то там менять только портить. В этом году я заново снял замеры и их можно сравнить с 2019-м, они несколько поменялись (хотя в общем разница между Intel Gen8 и Intel Gen11 не фатальная). Закончим мы разбором thread local переменных.

Работа над ошибками (нужна помощь зала). В комментариях мой уважаемый подписчик Роман Митин указал что я на лекции показал неправильный пример bounded MPMC queue -- на самом деле извлечение и вставка там шли с одного конца и таким образом это был скорее bounded MPMC stack. Для многопоточной среды разница не так велика -- задачи ставятся в "очередь" и разбираются консьюмерами и в общем по циклограмме работы сложно отличить что там было. Но я решил сделать настоящую очередь и заодно улучшить тесты. И вот тут я обратил внимание что у меня было ещё несколько ошибок, пока в комментариях не замеченных. (1) В случае multi-producer делать wake_and_done надо на всех продьюсеров один раз иначе бывает так что консьюмеры повыходили но не все продьюсеры ещё закончили. (2) Саму функцию wait_and_pop надо делать с сигнатурой bool wait_and_pop(T &Data) чтобы понимать есть там что консьюмить или нет (3) Внутри консьюмеров условие должно выглядеть так: CondCons.wait(Lk, [this] { return !empty() || done(); }); if (empty()) return false; Даже если у нас сигнализирован done, задачи могут быть недоразобраны и поэтому критерий return false это только empty. (4) Внутри push признак done вообще проверять не надо т.к. это признако отработки всех продьюсеров. Там играет роль только full. (5) В интерфейсе необходим метод is_empty_and_done() чтобы по нему консьюмеры понимали когда начинать выходить. В общем это жесть. Пять ошибок в довольно простом коде и я не уверен что я ещё чего-то не пропустил. Полу-финальные версии bounded stack и bounded queue с тестами на то что они не теряют задач я выложил сюда: https://github.com/tilir/cpp-masters/blob/master/queues/classic_queue.cc https://github.com/tilir/cpp-masters/blob/master/queues/classic_stack.cc Нужна помощь зала в проверке не упустил ли я ещё чего-нибудь. Хочу в среду с этого начать лекцию и не хотелось бы облажаться ещё в чём-нибудь столь же тонком.