Почему идеальный алгоритм тормозит: физика памяти и кеш-френдли-код

Вы написали алгоритм, который по сложности O(n) и должен летать, но на практике он еле ползёт. Скорее всего, проблема не в количестве операций, а в том, как данные расположены в памяти. Процессор не читает их по одному байту — он захватывает блоки (кеш-линии), и если код заставляет его прыгать по разным адресам, мощнейший CPU простаивает в ожидании.

В статье объясняют, что такое кеш-френдли-подход и почему одни и те же структуры данных на разных языках работают с разной скоростью. Разбирают, как устроены уровни кеша, почему обход матрицы по строкам быстрее, чем по столбцам, и как предсказуемость ветвлений влияет на производительность. Отдельно показывают, где применимы программные кеши вроде Redis и в чём подвох.

Если хотите перестать гадать, почему код «тупит», и начать писать так, чтобы процессор был на вашей стороне, смотрите материал: https://thecode.media/keshfrendli-kod/

@prog_point (теперь ещё в VK и Max)