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