Производительность
Cache vs big-O: тест с выбором ответа
Суть Тест с выбором на синтез по всему юниту — memory hierarchy, cache lines, false sharing, branch prediction, раскладка данных и чтение perf-профиля.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на senior-высоте — в орбитеШесть вопросов поперёк всего юнита. Ни один — не определение для заучивания: каждый отражает решение, которое ты принимаешь, когда «быстрый» алгоритм проигрывает «медленному», а big-O об этом молчит.
Цель
Убедись, что связываешь memory hierarchy, поведение cache line, false sharing, branch prediction и раскладку данных в один диагностический рефлекс: прочитал профиль, назвал причину в константном множителе, выбрал подходящий фикс.
Викторина
Completed
Связный список из 1M узлов итерируется в ~17 раз медленнее массива из 1M int, хотя оба O(N). Какое утверждение лучше объясняет разрыв?
Heads-up Big-O асимптотичен и верен — оба O(N). Он опускает константу на операцию, которую задаёт memory hierarchy: ~1 нс при попадании в кэш против ~100 нс при промахе в RAM.
Heads-up Число инструкций на узел сопоставимо; CPU простаивает в ожидании памяти, а не на лишней арифметике. Стоимость — это latency промаха, а не количество операций.
Heads-up Даже когда оба рабочих набора превышают кэш, массив всё равно выигрывает: последовательный доступ префетчится, а pointer-chasing data-dependent и непредсказуем. Дело в паттерне доступа, а не только в ёмкости.
Викторина
Completed
Команда меняет порядок внутреннего цикла matrix multiply с row-major на column-major на матрице 10 000×10 000 double и видит ~9x замедление. Арифметика идентична. Корневая причина?
Heads-up Оба порядка цикла — O(N²) с одинаковым числом операций. Регрессия целиком в константном множителе (cache-miss rate), а не в асимптотическом классе.
Heads-up Никакой флаг не исправит шаг в 80 000 байт. Сам паттерн доступа ломает prefetcher и SIMD; фикс — переупорядочить циклы или cache-oblivious tiling, а не флаг.
Heads-up Это квадратная матрица 10k×10k — строки и столбцы одинаковой длины. Разрыв задаёт раскладка в памяти (row-major хранение), а не размерность.
Викторина
Completed
Массив счётчиков сделали lock-free через атомики, и он стал медленнее версии с локом по мере роста числа потоков. perf показывает IPC 0.4 и 72% cache-miss rate. Диагноз?
Heads-up Атомики — не локи. Lock contention проявляется как off-CPU wait time; эта сигнатура — высокая загрузка CPU, обвал IPC, высокий cache-miss rate — это memory-bound трафик когерентности, то есть false sharing.
Heads-up Горстка uint64-счётчиков — это ~128 байт, тривиально резидентна в L1. Дефект — несколько ядер пишут в одну 64-байтную линию, а не ёмкость.
Heads-up У атомарного add нет data-dependent ветки. Промахи веток поднимают branch-miss counter, а не cache-miss counter; цифра 72% указывает прямо на память.
Викторина
Completed
Сортировка массива перед суммированием элементов выше порога даёт 2–3x ускорение, несмотря на лишнюю O(N log N) сортировку. Почему это окупается?
Heads-up Каждый элемент после сортировки всё равно сравнивается с порогом — число сравнений не меняется. Выигрыш — в предсказуемости ветки, а не в меньшем числе сравнений.
Heads-up Линейное сканирование массива уже cache-friendly, отсортирован он или нет. Доминирующий эффект здесь — branch prediction, а не локальность.
Heads-up Авто-векторизация не зависит от порядка сортировки. Документированное, не зависящее от архитектуры ускорение — от превращения непредсказуемой ветки в предсказуемую.
Викторина
Completed
Горячий ML-цикл работает в 5 раз медленнее эталонного C++-порта; perf показывает IPC 0.8 и 25% L3 miss rate. Кто-то предлагает добавить SIMD-интринсики. Какой первый шаг правильный?
Heads-up SIMD на AoS-данных вынуждает gather/scatter (~10x от contiguous load) и ничего не даёт memory-bound циклу. IPC 0.8 + 25% L3 miss — проблема раскладки; SIMD на плохой раскладке не покупает ничего.
Heads-up Флаги стоит проверить, но они не превратят чередующуюся AoS-раскладку в contiguous SIMD-дружественные данные. Сигнатура — memory-bound, а не недо-оптимизированные вычисления.
Heads-up Обе версии используют один алгоритм; 5x разрыв при высоком L3 miss rate — это константная стоимость раскладки, а не асимптотическая разница.
Викторина
Completed
perf stat на горячем цикле показывает IPC 0.40, branch-miss 25% и LLC-miss 47%. Можно сначала исправить одно. Что и почему?
Heads-up 10–30-цикловый flush реален, но промах в RAM — ~300 циклов, и 47% обращений к L3 промахиваются. Memory stall здесь — больший рычаг; сначала фикс раскладки, затем ветки.
Heads-up IPC — не ручка, а результат простоев. Он равен 0.40, потому что CPU ждёт память и мисспредикты веток. Убери эти причины — и IPC поднимется сам.
Heads-up Ничто в профиле не указывает на асимптотический класс; он указывает на константные множители — раскладку и поведение веток. 'Лучший' big-O с худшей локальностью легко может быть медленнее.
Итог
Сквозная линия юнита — одно дерево решений: big-O оценивает рост стоимости с N, но memory hierarchy задаёт константу, и она колеблется ~100x в зависимости от раскладки. Contiguous бьёт pointer-chasing; порядок цикла должен совпадать с порядком хранения; записи на поток нуждаются в своей cache line; непредсказуемым веткам нужна сортировка или branchless; работа по одному полю хочет SoA. Когда перед тобой профиль — сначала читай miss rate и IPC, назови причину в константном множителе и применяй подходящий фикс: измеряй, не угадывай.