В прошлую субботу выступил на Zero Cost Conf

https://youtu.be/lwIBp6cc-HY

Если кратко, то из всех конференций этого лета эта была лучше прочих организована. Формально она была бесплатная, реально Яндекс не поскупился. Меня даже загриммировали, чтобы я не бликовал, это невероятно.

#conference #riscv

Немного о планах на предстоящий учебный год.

Ссылки на стримы бакалаврского и магистерского курса будут выкладываться в дискорд в соответствующие текстовые каналы: https://discord.gg/vSEp8yW
В стримах возможно удалённое участие, также будут оставаться записи.

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

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

#official

Выложил запись первого семинара по основам C

https://youtu.be/7YhRFx-oyW4

Буду стараться выкладывать в субботу утром, но это пилотный выпуск и я задержался с монтажом. Разумеется надо будет посмотреть как зайдёт. Небольшой дисклеймер: это не лекции. Я считаю что студенты ходят на лекции по C и их веду не я. Но я объясняю достаточно теории чтобы можно было вместо лекций просто читать Кернигана и Ричи и всё понимать.

Записывать это куда сложнее чем записывать лекции. Я выбрал такой вариант: на семинаре я первые минут 30-40 что-то говорю и даю задание на семинар. Потом студенты примерно 1.5 часа решают задачи и это на видео не попадает. И в конце я снова беру слово. Так что запись поделена местом где нужно остановить видео и тоже решать задачи.

#c_graduate

Вторая часть первого семинара по основам C.

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

Мы продолжаем изучать основы программирования на C. На этом семинаре будут разобраны системы счисления. Чтобы проще делать перевод между системами счисления, мы введём понятие массива. Кроме того мы сразу же используем системы счисления для построения алгоритма эффективного возведения в степень по модулю. Также мы разберём расширенный алгоритм Евклида который я давал на дом в прошлый раз и посмотрим очень красивое построение рекуррентности для решения этой задачи.

#c_graduate

Дополнения к семинару 1.2

Я сегодня уже выкладывал и стирал этот пост т.к. он был не идеален. Теперь надеюсь останется.

1.2.1.

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

Интересно что я не сразу это понял сам, хотя если бы меня попросили посчитать i в степени i у меня не было бы проблем. К счастью мне всё объяснили: https://cs.stackexchange.com/questions/162098

1.2.2.

Многие заметили что наивное обобщение русского крестьянского умножения и возведения в степень перестаёт работать на сверхстепень и в этом смысле проблема RPS коварна. Всё дело в том, что шагом для возведения в степень является умножение и для умножения (a * b) mod m = ((a mod m) * (b mod m)) mod m. Но для возведения в сверхстепень шагом должно являться возведение в степень, а там это очевидно не так.

Простой контрпример:
(2 ^ 4) mod 5 = 1
(2 ^ 9) mod 5 = 2

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

1.2.3.

Один из студентов сделал интересное решение проблемы NS, не использующее дополнительного массива, а вместо этого использующее обратный ход рекурсии: https://youtu.be/oWGrH0R8iwU?t=3508

Интересно, что компиляторы gcc и clang сильно расходятся в вопросе оптимизации этого кода: clang на O3 не делает ничего. Что делает на O3 gcc я бы охарактеризовал как двойной прыжок с переворотом в воздухе: https://godbolt.org/z/o6bjs3aP1

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

#c_graduate

Третья и завершающая часть первого семинара по языку C,

https://youtu.be/qaCsf7wOpRQ

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

А впереди нас ждёт допсеминар по Unix Shell, запись которого я выложу в ближайший вторник.

#c_graduate

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

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

https://youtu.be/KLv-5jWlKjM

В этом видео речь пойдёт о работе в консоли. Мы научимся работать с пакетным менеджером, узнаем основы идеологии Unix, научимся писать сначала однострочники, а потом и полноценные bash-скрипты, освоим несколько консольных супероружий, таких как grep sed и awk и многое другое. В конце мы с некоторой грустью поймём границы применения техники.

#c_graduate

Начинаем второй логический семинар по языку C. Он будет также из трёх частей и будет посвящён времени и памяти.

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

https://youtu.be/duVH3_hp60I

#c_graduate

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

https://godbolt.org/z/qa59c5MM1

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

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

#questions
#compilers

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

Я хотел добиться, чтобы мне упростили a * c - a * d - b * c - e * f + e * d + b * f до (a - b) * (c - d) - (e - b) * (f - d). Там сначала разминочный вопрос который сетка с лёгкостью прошла, а вот дальше...

https://chat.openai.com/share/8894392f-253b-4ade-a059-d2dad90619da

У меня не получилось.

Хочется обратиться к экспертам в инжиниринге запросов на моём канале. А вы сможете добиться от нейросети правильного ответа?

#llm
#questions

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

https://youtu.be/ZizuOhdl5oA

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

#c_graduate

Заканчиваем семинар посвященный времени и памяти: разбираем функции для работы со временем и псевдослучайные числа. Начинаем со времени, знакомимся с функциями для работы с ним. Далее мы мотивируем рандомизированные алгоритмы и знакомимся с псевдослучайными числами. После перерыва на решение задач я также разберу структуры и побитовое решето с прошлого семинара.

https://youtu.be/qpSCYugCknk

#c_graduate

В семинаре 2.3 кто-то мог в конце пропустить небольшой шедевр от одного из студентов.

Вот чуточку причёсанная мной но близкая к оригиналу студенческая трактовка Problem FT. Определяет простоту числа через тест Ферма.

https://godbolt.org/z/PsvMs3fG1

Обратите внимание: программа совершенно корректно справляется с 49979687 (простое) и с 271747319 (составное 15791×17209).

Разумеется проблема тут в том что вместо настоящего случайного числа rand() использован просто адрес функции rand и он себя показывает неплохим случайным числом (!)

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

#questions #c_graduate

Вести с полей систем сборки и управления пакетами.

1. Наконец-то cmake 3.28 + clang 17 позволяют использовать модули.

https://www.kitware.com/import-cmake-the-experiment-is-over/

2. Выложили (пока что по ссылке) доклад на CppCon'23 где тот же Хоффман содокладчик по Common Package Specification.

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

Таймлайн. В скобках -- мои примечания.

00:00 Начало и цели доклада
05:16 Зачем вообще управлять зависимостями: результаты интересного опроса что самое болезненное в C++, обзор наиболее неприятных проблем.
13:50 План исправления ситуации: замена зоопарка пекеджей единым стандартом. Плавный переход с CMake. Модули добавляют срочности этому плану.
21:43 Локальный максимум управления зависимостями: в больших компаниях уже функционирует нечто самописное (и всё что я видел было невероятно уродливым), в маленьких компаниях люди джедайствуют как могут (обычно у каждого свой build shell script врапает частые строчки для вызова CMake). Проблемы монореп и сабмодулей.
30:30 Решение: международный стандарт для экосистемы C++.

Тут микрофон уходит к Хоффману.

32:20 Что такое вообще библиотека?
34:30 Взаимодействие системы сборки с менеджментом зависимостей (я бы тут усилил тезис: почему все ненавидят менеджмент зависимостей). Подход через autotools. Эволюция CMake. Уроки которые мы выучили из модулей CMake. Пример FindQT4 и почему в CMake нет FindQT6 как отдельной команды.
48:45 Спецификация Common Package Specification и простое демо CPS в CMake. Некоторые планы на будущее развитие CMake в этом направлении.
59:20 Более высокоуровневые цели для будущей экосистемы в целом и ответы на вопросы.

Собственно спецификацию можно посмотреть вот тут:

https://cps-org.github.io/cps/index.html

#talks

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

#c_graduate

https://youtu.be/5LSAiYAchbk

Возврат к генезису на втором курсе: https://www.youtube.com/watch?v=e5__34DFz5Y в самом начале видео.

Выложил первую часть третьего логического семинара.

Мы уверенно закончили с теорией чисел и переходим угадайте к чему. Правильно — к сортировке и поиску. Начнём мы с довольно простых сортировок и довольно прямолинейного поиска. Кроме того я добавил немного вещей, касающихся языка C — например чтение cdecl, указатели на функции и основы константности.

https://youtu.be/6hTaAwUNbiw

P. S. На этой неделе дети писали контрольную, так что на следующей неделе выкладки не будет. До 3.2 будет двухнедельная пауза.

#c_graduate

Всем привет. Ближайшие события с моим участием.

18 ноября буду рассказывать про открытую архитектуру RISCV на митапе Сбердевайса
21 ноября участвую в дискуссии про технические интервью для C++ разработчиков на митапе Yadro

На митапе Yadro кстати осталась ещё тонна свободных мест для бесплатного оффлайн-участия так что не бойтесь регистрироваться.

#conference

Выложил вторую часть третьего семинара по языку C для первого курса.

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

https://youtu.be/f2f5zXqptFY

#c_graduate

Немного странного C++.

Уважаемый читатель моего канала @MSerhiy обнаружил забавную вещь: для структур и для примитивных типов вот в этом примере действуют разные правила перегрузки: https://godbolt.org/z/YT9bo7ore

Я довольно быстро раскопал ответ в стандарте.

C++20, [expr.type] "If a prvalue initially has the type “cv T”, where T is a cv-unqualified non-class, non-array type, the type of the expression is adjusted to T prior to any further analysis"

Но я что-то задумался в процессе. Вот чисто гипотетически: а зачем так было сделано? Чему и когда это поможет? У меня нет идей.

Предлагаю в этой ветке поспекулировать насчёт источника этого правила.

#questions