Ускоряем вложенные циклы на 30%

/****************** about ******************/

Меня зовут Алексей Голобурдин, я программирую с 2004 года и на этом канале делюсь своим опытом. Я основатель и руководитель компаний:

[losos]

В small_outer_loop еще процент попадания в кеш процессора будет выше т.к. при обращении к table[row][column] вероятность попадания в кеш выше если на предыдущей итерации мы обращались к table[row][column-1] чем если мы обращались table[row-1][column]

Для чистоты эксперимента я бы попробовал с одинаковыми значениями ROWS и COLUMNS запустить чтобы еще понять на сколько влияет кеш

[harry-smith]

на 03:09 то что ты называешь iterations - это скорее количество запусков блоков кода
общее количество итераций операции суммирования все равно остается ROW*COLUMN

то есть переход из блока в блок выполнения отнимает время, занятно

[First_NameSecond_Name]

Я программированием не занимаюсь и то понял в чем фишка. А фишка в том, что переменная iteretion расположена и во внешнем и во внутреннем цикле. А правильно было располагать только во внутреннем цикле. А из за того, что эта переменная нарастает в обоих циклах, то да в первом случае до 600, а во втором до 505, вот на это время и тратится, а если эту переменную оставить только во внутреннем цикле то в обоих случаях itatetion=500 будет и время выполнения большого и малого станет, наверно, одно и то же.

[kaluginpeter]

Привет, интересные мысли, как и сам ролик. По идее разница возникает в количестве инициализации inner loop и чем больше outer loop, тем медленнее код: n + (n*m)*c, где n - outer, m - inner, c - extra time какое-то действие. Ну и по ходу, в кеш будет больше попаданий при row traversal, чем в column traversal, кеш в линию хранится конкретно в C/C++, в других языках возможно другое будет... Ведь какой из факторов наиболее важный: Количество инициализаций и итераций, доступ к памяти, хешируемость?

[普京的手机]

Кстати, tuple(… for … in …) будет работать на ⅓ медленнее, чем tuple([… for … in …]), но во время выполнения работы должно занимать несколько больше памяти (it depends насколько)

[pavelzagain]

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

[julesbois]

Кажется в комментах непонимание того, что автор имел в виду под словом "итерация", что же всё-таки подсчитывает переменная iterations.
Здесь мы подсчитываем сколько раз за эти два вложеных цикла вычислялись loop conditions. Не важно, что там в теле цикла. Эти самые loop conditions не бесплатны. Ну и инкрементт переменной цикла тоже чего-то стоит. IMO

[olegssh]

В более сложных структурах может появится еще одна ось z - трехмерная матрица. Там уже будет три цикла - по матрицам, по строкам и в конце по колонкам строки матрицы.

[normno]

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

[maksimkuznetsov]

Будет чудно, если собеседующий задаст вопрос по nested loops после этого видео, а кандидат ответит потому, что посмотрел это видео.

[lemopsone]

Забавно, что эта оптимизация имеет место быть в любом ЯП, никогда об этом прежде не задумывался :)

Рассмотрим простейший код на ассемблере (MASM x86):
mov ecx, 0
outerLoop:
cmp ecx, 100
je done
mov ebx, 0
innerLoop:
cmp ebx, 5
je innerLoopDone
inc ebx
jmp innerLoop
innerLoopDone:
inc ecx
jmp outerLoop
done:

Видим, что ecx == row, ebx == column, и, соответственно, тела внутреннего и внешнего циклов отличаются всего одной коммандой - `mov ebx, 0` - той самой инициализацией внутреннего цикла (обнулением счетчика ebx). Соответственно, единственное отличие между big_outer_loop и small_outer_loop - количество обнулений счётчика, которое и является первоисточником разницы в скорости выполнения :)

Ради интереса воссоздал пример автора на C, с отключенной оптимизацией: скорость выполнения двух циклов отличается на ~15%, и, по сути, заключается в одной лишь дополнительной комманде ассембли... (ну и само собой в кэшировании данных процессором, но это уже другая история)

[usualneko]

Если вспомнить что питон позволяет "нормально" итерировать объекты - без индексов, а просто "for item in iterable", и писать функцию в таком стиле - "for row in table: for column in row: overall_time += column", то можно сэкономить еще немного времени (у меня получается что "нормальный" цикл быстрее суммы на 15-20%)

[km-academy_ru]

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

[perl]

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

[newrlan]

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

[abdulgoniyfarhodov]

было интересно, даже не задумывался об этом раньше

[dolotube]

1:10 Ответ на вопрос до просмотра видео - да, есть разница, выгоднее внешний цикл делать с меньшей стороной, так уменьшается количество _инициализаций_ внутреннего цикла.
2:52 Замечание по ходу - было бы правильнее называть не итерациями, а проверкой условия в цикле, поскольку итерации внутреннего проходят во время итерации внешнего, а не где-то рядом дополнительно. В итоге сумма всегда увеличивалась 500 раз, а условия циклов проверялись соответственно 100+5*100=600 и 5+100*5=505 раз. Параллельное представлено как последовательное. И отмечу, что это не 30% разница, то есть не единственный фактор.

Но общая мысль интересная, спасибо.

[a.osethkin]

Спасибо большое. Очень понравилась. Глаза открылыись на то, что такое есть. Прям прикольно

[gsm]

Можно ли внутри функции «пересобрать» структуру, чтобы можно было применить map и ускорит ли это исполнение?

[mobiledeveloper]

Интересно что автор увидел лишние итерации, но не понял что именно влияет на производительность и сделал неверные выводы