Фундаментальные знания по основам программирования
Разместить рекламу: @tproger_sales_bot
Правила общения: https://tprg.ru/rules
Другие каналы: @tproger_channels
Сайт: https://tprg.ru/site
Регистрация в перечне РКН: https://tprg.ru/zrgj
Post #4871
1.41K

Почему идеальный алгоритм тормозит: физика памяти и кеш-френдли-код
Вы написали алгоритм, который по сложности O(n) и должен летать, но на практике он еле ползёт. Скорее всего, проблема не в количестве операций, а в том, как данные расположены в памяти. Процессор не читает их по одному байту — он захватывает блоки (кеш-линии), и если код заставляет его прыгать по разным адресам, мощнейший CPU простаивает в ожидании.
В статье объясняют, что такое кеш-френдли-подход и почему одни и те же структуры данных на разных языках работают с разной скоростью. Разбирают, как устроены уровни кеша, почему обход матрицы по строкам быстрее, чем по столбцам, и как предсказуемость ветвлений влияет на производительность. Отдельно показывают, где применимы программные кеши вроде Redis и в чём подвох.
Если хотите перестать гадать, почему код «тупит», и начать писать так, чтобы процессор был на вашей стороне, смотрите материал: https://thecode.media/keshfrendli-kod/
@prog_point (теперь ещё в VK и Max)
Вы написали алгоритм, который по сложности O(n) и должен летать, но на практике он еле ползёт. Скорее всего, проблема не в количестве операций, а в том, как данные расположены в памяти. Процессор не читает их по одному байту — он захватывает блоки (кеш-линии), и если код заставляет его прыгать по разным адресам, мощнейший CPU простаивает в ожидании.
В статье объясняют, что такое кеш-френдли-подход и почему одни и те же структуры данных на разных языках работают с разной скоростью. Разбирают, как устроены уровни кеша, почему обход матрицы по строкам быстрее, чем по столбцам, и как предсказуемость ветвлений влияет на производительность. Отдельно показывают, где применимы программные кеши вроде Redis и в чём подвох.
Если хотите перестать гадать, почему код «тупит», и начать писать так, чтобы процессор был на вашей стороне, смотрите материал: https://thecode.media/keshfrendli-kod/
@prog_point (теперь ещё в VK и Max)
- ❤ 2















