Практика языка C (МФТИ, 2023-2024). Семинар 7.2. Конвейер.

Рет қаралды 5,381

Күн бұрын

Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.
На этом занятии мы окажемся максимально глубоко и решим сразу две интересных загадки. Первая приведёт нас к концепции конвейера, на которой мы остановимся и внимательно её изучим. Вторая же приведёт нас к ещё более удивительным открытиям, касающимся истинной природы кешей.
Семинарист: Константин Владимиров.
Дата: 8 апреля 2024 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.
Предыдущий семинар: • Практика языка C (МФТИ...
Следующий семинар: • Практика языка C (МФТИ...
Слайды к занятиям: cs.mipt.ru/wp/?page_id=7775
Примеры кода: github.com/tilir/c-graduate
Задачник: olymp1.vdi.mipt.ru/
Timeline
00:00 Исполнение программы
10:45 Конвейер
15:12 Предсказание переходов
26:30 Упражняемся в ассемблере
31:08 Хитрая оптимизация
36:50 Out of order
44:00 Время решать задачи
46:40 Загадочный бинарный поиск
52:18 Реалистичные кеши
01:02:30 Разгадка: ассоциативность
01:10:28 Бонус про замеры кешей
Errata
* Тут пока пусто

Пікірлер: 27

@alex_s_ciframi Күн бұрын

Константин, спасибо за лекцию. 19:44 - так, ежели это отсортировать, то if становится не нужен )

@user-yy6ig3wm2h 9 күн бұрын

Большое спасибо, очень информативно

@pompei2 2 ай бұрын

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

@sibedir 2 ай бұрын

Каждый вторник жду видосов от Сера Троглодита. Каждые выходные - от Константина. 👍

@tilir 2 ай бұрын

Удивительное сравнение, вроде ничего общего. Хотя я тоже люблю геройские стримы ))

@sibedir 2 ай бұрын

@@tilir общее в таланте создавать ламповость и умиротворяющее повествование )

@serglarionov5560 2 ай бұрын

Преподаватель от бога!

@v_zalygin 2 ай бұрын

Спасибо за семинар!

@alexanderspeshilov839 10 күн бұрын

К разделу "хитрая оптимизация" (31:26). Дело было вечером, делать было нечего, я немного поэкспериментировал с кодом и данной оптимизацией. 1. У меня gcc выкидывает умножение и вместо imul делает условную загрузку регистра cmovle. 2. Попытка использовать хак типа mask = (128 - arr[j]) >> 31 и потом arr[j] & mask никак не меняет время выполнения. 3. Зато помогает явный переход в unsigned. Флаг сразу считаем в unsigned, явно переводим arr[j] в unsigned и потом умножаем. Тогда gcc делает cmp+cmovle+add и всё, cdqe не растягивает, ничего лишнего не делает. В данном случае такая оптимизация безопасна. У меня время в итоге такое: наивный несортированный ~ 3.5 наивный сортированный ~ 0.55 предложенная оптимизация ~ 0.7 (сорт == несорт) оптимизация c unsigned ~ 0.59 (сорт == несорт) - на 15% быстрее PS: Я также помотрел clang. Там есть отличия, любопытные, но непринципиальные. PPS: Бессмысленность и хрупкость последней оптимизации я отлично понимаю. Полез потыкать пример просто из интереса - проврить (128 - arr[j]) >> 31, но случайно увлёкся :) PPPS: На то как лишние конвертации signed съедают производительность я натыкался раньше, поэтому попробовал.

@rayrayray4653 2 ай бұрын

Классно!!!

@ruslankhl 2 ай бұрын

Спасибо!

@user-fw3kx2ix3p 2 ай бұрын

Как обычно лайк за ранее)❤

@tilir 2 ай бұрын

Вот это правильный подход. Если что всегда можно отжать обратно ))

@barsik5943 2 ай бұрын

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

@AnarchySane Ай бұрын

В такие моменты начинаю понимать почему Си будет еще очень живее всех живых. ❤ Ощущаю себя тупым, но я же JS’эсер 😂

@Stedmiel 2 ай бұрын

24:40 в аппаратные счетчики умеет дефолтный линуксовый perf, к слову говоря. на винде это умеет делать не менее дефолтный ETW, но насколько помню- там было все не очень хорошо с документацией.

@alexeydurnev9500 2 ай бұрын

Константин! Огромное спасибо за семинар, очень кратко и максимально по делу! Есть вопрос: В обращении к студентам вы упомянули архитектуру их задания и распределение ролей в команде. Будут ли еще на канале видео, посвященные программной архитектуре? Или по взаимодействию в команде разработчиков?

@tilir 2 ай бұрын

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

@MVZ1983 Ай бұрын

Аппаратные кэши, конвейеры, транзисторы, конденсаторы... Как же низко мы пали!

@johndick996 2 ай бұрын

Константин, большое спасибо за семинар!

@alexloktionoff6833 2 ай бұрын

Pipeline - дословно трубопровод. Это похоже калька с русского термина водопроводный принцип организации управления, который впервые открыто ввел советский ученый А.С. Лебедев. Сейчас уже известно что и до этого была аппаратура специального назначения и на западе и в СССР, которая использовала этот принцип, но открыто впервые использовал его все-таки Лебедев. И хотя принцип работы может и проще объяснять на примере заводского конвейера, мне кажется важно помнить о корнях.

@tilir 2 ай бұрын

Я кстати никогда не понимал а почему трубопровод. С водой текущей по трубе ничего не случается, а казалось бы суть именно в изменениях. В историческом смысле вы, вероятно, правы, похоже термин растёт именно отсюда. Вообще конечно очень не повезло что на заре вычислительной техники в СССР не было малого бизнеса и неоткуда было взяться ни советскому Интелу ни советскому IBM. В итоге вся ветка получилась кривоватой и не выпрямилась до сих пор.