К разделу "хитрая оптимизация" (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 съедают производительность я натыкался раньше, поэтому попробовал.
1:06:43 Константин, не знаете ли вы, параллелятся ли аппаратно обращения к разным set внутри кэшей? (т.е. нужно ли ждать завершения работы с set0, чтобы начать следующее действие с set1) Если так, то кажется даже в случае одного прохода по памяти при попадании в один set мы будем получать замедление
24:40 в аппаратные счетчики умеет дефолтный линуксовый perf, к слову говоря. на винде это умеет делать не менее дефолтный ETW, но насколько помню- там было все не очень хорошо с документацией.
Константин! Огромное спасибо за семинар, очень кратко и максимально по делу! Есть вопрос: В обращении к студентам вы упомянули архитектуру их задания и распределение ролей в команде. Будут ли еще на канале видео, посвященные программной архитектуре? Или по взаимодействию в команде разработчиков?
Ну там были довольно специфичные рекомендации для самых маленьких. А так да, может быть когда-нибудь я что-то такое запишу. Но для этого надо сперва исчерпать технические темы, а у меня пока слишком большой бэклог ))
Pipeline - дословно трубопровод. Это похоже калька с русского термина водопроводный принцип организации управления, который впервые открыто ввел советский ученый А.С. Лебедев. Сейчас уже известно что и до этого была аппаратура специального назначения и на западе и в СССР, которая использовала этот принцип, но открыто впервые использовал его все-таки Лебедев. И хотя принцип работы может и проще объяснять на примере заводского конвейера, мне кажется важно помнить о корнях.
Я кстати никогда не понимал а почему трубопровод. С водой текущей по трубе ничего не случается, а казалось бы суть именно в изменениях. В историческом смысле вы, вероятно, правы, похоже термин растёт именно отсюда. Вообще конечно очень не повезло что на заре вычислительной техники в СССР не было малого бизнеса и неоткуда было взяться ни советскому Интелу ни советскому IBM. В итоге вся ветка получилась кривоватой и не выпрямилась до сих пор.
Для меня кэши проца всегда были какими-то неприступными крепостями, а тут раз-раз и всё ясно стало. Большая благодарность лектору от всей души
Каждый вторник жду видосов от Сера Троглодита.
Каждые выходные - от Константина. 👍
Удивительное сравнение, вроде ничего общего. Хотя я тоже люблю геройские стримы ))
@@tilir общее в таланте создавать ламповость и умиротворяющее повествование )
Преподаватель от бога!
Большое спасибо, очень информативно
Спасибо за семинар!
Спасибо!
Константин, спасибо за лекцию.
19:44 - так, ежели это отсортировать, то if становится не нужен )
Так мы же не знаем изначально сортировали или нет.
Мы заранее не знаем отсортирован вход или нет.
Классно!!!
К разделу "хитрая оптимизация" (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 съедают производительность я натыкался раньше, поэтому попробовал.
1:06:43 Константин, не знаете ли вы, параллелятся ли аппаратно обращения к разным set внутри кэшей? (т.е. нужно ли ждать завершения работы с set0, чтобы начать следующее действие с set1) Если так, то кажется даже в случае одного прохода по памяти при попадании в один set мы будем получать замедление
Кстати интересная задача для экспериментирования.
Как обычно лайк за ранее)❤
Вот это правильный подход. Если что всегда можно отжать обратно ))
Константин, большое спасибо за лекцию! Какую литературу Вы можете посоветовать по данной тематике?
Харрис и Харрис если хочется глубоко понять тему.
24:40 в аппаратные счетчики умеет дефолтный линуксовый perf, к слову говоря. на винде это умеет делать не менее дефолтный ETW, но насколько помню- там было все не очень хорошо с документацией.
виртуально на ваших семинарах находится примерно по четыре тысячи любопытных глаз
Константин! Огромное спасибо за семинар, очень кратко и максимально по делу! Есть вопрос: В обращении к студентам вы упомянули архитектуру их задания и распределение ролей в команде. Будут ли еще на канале видео, посвященные программной архитектуре? Или по взаимодействию в команде разработчиков?
Ну там были довольно специфичные рекомендации для самых маленьких. А так да, может быть когда-нибудь я что-то такое запишу. Но для этого надо сперва исчерпать технические темы, а у меня пока слишком большой бэклог ))
Аппаратные кэши, конвейеры, транзисторы, конденсаторы... Как же низко мы пали!
В такие моменты начинаю понимать почему Си будет еще очень живее всех живых. ❤
Ощущаю себя тупым, но я же JS’эсер 😂
Pipeline - дословно трубопровод. Это похоже калька с русского термина водопроводный принцип организации управления, который впервые открыто ввел советский ученый А.С. Лебедев. Сейчас уже известно что и до этого была аппаратура специального назначения и на западе и в СССР, которая использовала этот принцип, но открыто впервые использовал его все-таки Лебедев. И хотя принцип работы может и проще объяснять на примере заводского конвейера, мне кажется важно помнить о корнях.
Я кстати никогда не понимал а почему трубопровод. С водой текущей по трубе ничего не случается, а казалось бы суть именно в изменениях. В историческом смысле вы, вероятно, правы, похоже термин растёт именно отсюда. Вообще конечно очень не повезло что на заре вычислительной техники в СССР не было малого бизнеса и неоткуда было взяться ни советскому Интелу ни советскому IBM. В итоге вся ветка получилась кривоватой и не выпрямилась до сих пор.
Быстрее бы...
Жесть
Это очередной этап, в котором я понимаю что оптимизировать алгоритмы можно еще глубже.
Возникает вопрос как процесс написания программы, учитывающей использование аппаратных кэшей, сочетается с векторизацией