Обстоятельная статья о том, что нужно, чтобы быстро транспонировать матрицу. Андрей Гудков берёт самую наивную реализацию на C++ (два вложенных цикла, dst[c,r] = src[r,c]) и шаг за шагом разгоняет её на x86_64 до 25 раз.

Казалось бы, куда проще: ни деления, ни корней, просто перекладываем байты. Но именно поэтому транспонирование оказывается идеальным полигоном для изучения узких мест железа. Тут вылезает всё разом: высокая задержка памяти, особенности устройства кэша и неспособность компилятора векторизовать код сам.

По пути автор каждый раз находит бутылочное горлышко, объясняет его на уровне тактов процессора и придумывает обход. Этапы примерно такие:

🔘Наивная версия как точка отсчёта.
🔘Разворот порядка обхода.
🔘Блочная разбивка матрицы под размер кэш-линии.
🔘Программный префетч.
🔘 Векторизация на 64-битном SIMD, потом на 256-битном.
🔘 Буферизация вывода.

Полезного по дороге много. Например, наглядно показано, во сколько обходится промах кэша: попадание в L1d почти бесплатно (4-5 тактов), L2 уже 12-15, L3 — 40-45, а промах до RAM стоит до 300 тактов. И что любой доступ к одному байту на самом деле тянет в кэш всю 64-байтную линию, поэтому весь фокус в том, чтобы успеть подгрузить данные заранее.

Хорошее чтение на вечер, если интересна low-level оптимизация под x86_64. Со схемами, анимацией обхода кэша и кодом каждой версии.

https://gudok.xyz/transpose/

@prog_stuff