Производительность
Cache vs big-O: опровергни учебник
Прочитать, что кэш доминирует над big-O — не то же самое, что заставить «медленный» алгоритм выиграть по часам. Собери бенчмарк, где O(N) contiguous структура бьёт O(log N) на указателях, затем профилируй и чини горячий цикл, пока perf stat не докажет, что константные множители ушли.
Преврати ментальную модель юнита в воспроизводимую инженерную петлю: измерь через perf, назови причину в константном множителе (локальность, ветка, false sharing, bandwidth), примени подходящий фикс раскладки и подтверди реальное wall-clock ускорение числами до/после на идентичном входе.
Возьми memory-bound горячий цикл (свой или один из двух стартеров ниже) и выгони 3–5x wall-clock ускорение, исправляя константные множители — раскладку, порядок доступа и предсказуемость веток — не меняя big-O алгоритма, доказывая каждый шаг измерениями perf.
- Таблица до/после: wall-clock время, IPC, LLC miss rate и branch-miss rate — всё измерено на идентичном входе на той же машине, не оценено.
- perf-профиль (perf record + annotate или эквивалент), показывающий, как доля промахов/простоев на горячей строке сжимается после фикса — перепрофилировано, а не предположено.
- 3–5x ускорение хотя бы на одном горячем цикле, с доминирующей метрикой, сдвинутой в здоровый диапазон (IPC >2.0, или LLC miss <10%, или branch miss <5%, в соответствии с диагностированной причиной).
- Абзац с разбором: назови причину в константном множителе, использованный рычаг и точку перелома N, при которой асимптотически лучшая структура перестаёт проигрывать.
- Добавь cache-oblivious или tiled-вариант (blocked matrix transpose / multiply) и покажи, что он выигрывает на каждом уровне кэша против наивного цикла, не зашивая размеры кэша.
- Распараллель агрегацию и намеренно вызови false sharing на разделяемом массиве счётчиков; покажи регрессию в perf c2c / IPC, затем исправь 64-байтным паддингом и перемеряй.
- Добавь huge pages (madvise(MADV_HUGEPAGE) или hugetlbfs) для рабочего набора >1 ГБ и измерь TLB-driven изменение throughput независимо от локальности кэша.
- Добавь CI-гейт производительности: прогоняй бенчмарк на канарейке, диффай IPC и LLC miss rate против main и роняй сборку, если любое регрессирует за порог — защита в стиле Discord/Bun от тихих регрессий раскладки.
Это петля, которую ты будешь гонять в каждом реальном инциденте производительности: сначала измерь через perf, назови причину в константном множителе по метрикам, чини на уровне раскладки (SoA, struct split, переупорядочивание циклов, tiling, паддинг) до того, как тянуться к SIMD или другому big-O, и подтверди числами до/после на идентичном входе. Доказать ложь учебника один раз на бенчмарке — увидеть, как contiguous O(N) структура бьёт O(log N) на указателях, и найти точку перелома — делает production-рефлекс мышечной памятью.