Производительность
Cache vs big-O: тест на свободное воспроизведение
Воспроизведение по памяти бьёт перечитывание. На каждый промпт скажи или запиши полный ответ из памяти до того, как откроешь модельный — именно усилие припоминания чинит ментальную модель, а не узнавание правильно выглядящего варианта.
Восстанови костяк юнита, не подглядывая: почему паттерн доступа бьёт число операций, как cache line порождает false sharing, когда сортировка бьёт branchless, почему SoA включает SIMD и какая petlя perf-stat связывает всё вместе.
- 01Почему O(N) сканирование contiguous массива может бить O(log N) обход дерева в production, и где это перестаёт быть верным?
- 02Объясни false sharing: как протокол MESI превращает независимые записи на поток в баг производительности, и как его обнаружить и исправить.
- 03Когда сортировка (O(N log N)) бьёт branchless-переписывание для data-dependent ветки, а когда branchless — лучший инструмент?
- 04Почему SoA включает SIMD там, где AoS вынуждает gather/scatter, и в чём размен?
- 05Помимо cache hit rate, какие два ограничения лимитируют memory-bound цикл, и как отличить их от cache miss?
- 06Сформулируй петлю инженерии производительности для этого юнита и какая метрика указывает на какой класс фикса.
Если ты восстановил каждый ответ по памяти, ты держишь костяк юнита: memory hierarchy задаёт ~100x константу, которую big-O игнорирует; cache lines — это 64-байтные единицы владения, превращающие соседние записи в false sharing; сортировка и branchless — два инструмента для одной проблемы непредсказуемой ветки; SoA разблокирует SIMD и bandwidth, которые AoS блокирует; а петля perf-stat сопоставляет каждую метрику её фиксу. Сначала измеряй, назови причину в константном множителе, исправь раскладку или ветки, перемеряй.