Краткое введение в высокопроизводительные вычисления на C++ для CPU

HPC

C++

Эта заметка описывает мой личный взгляд на то, как писать эффективный и надежный код для CPU. Статья ориентируется на С++, но значительная часть обсуждения CPU, кэшей, паттернов доступа к памяти и профилирования применима к Rust, Go и другим компилируемым языкам.

Автор

Николай Мальковский

Дата публикации

16 марта 2026 г.

Поскольку вы программист на C++, вероятность того, что вы слегка одержимы производительностью, выше среднего. А если нет, то вы, вероятно, по крайней мере с пониманием относитесь к такой точке зрения. (Если производительность вас совсем не интересует, аудитория Python разработчиков дальше по коридору)

Из пункта 42 книги С. Майерса “Effective Modern C++”, 2015.

Статья задумана как краткое введение и больше всего подходит студентам, имеющим опыт программирования на занятиях, но не в реальных проектах. Для профессионалов статья может быть полезной в качестве референса, чтобы не пугать новичков чем-то в духе Что каждый программист должен знать о памяти.

В статье расскажу про “starter pack”: godbolt.org, профилирование, бенчмарки, особенности CPU и его взаимодействия с памятью, когда есть ли смысл от асимптотических оптимизаций и почему важно при этом пользоваться санитайзерами, отслеживать coverage и вообще более трепетно относится к надёжности.

Прежде чем начать

О мелких оптимизациях стоит забывать, скажем, примерно в 97% случаев: преждевременная оптимизация — корень всех зол. Но нельзя упускать возможности в тех самых критичных 3%

Д. Кнут, “Structured Programming with go to Statements” (ACM Computing Surveys, 6(4), 1974).

Эта мысль отлично выдержала проверку временем. Она была сформулирована 50 лет назад, но по-прежнему остается верной, несмотря на то, насколько сильно изменилась разработка программного обеспечения. Не весь код является критичным к производительности, и это на самом деле хорошо. Например, в ML/AI матричное умножение и работа с attention KV cache могут занимать почти все вычисления, а все остальное можно писать на Python без заметной деградации. Суть в том, что, если вас интересует результат, стоит помнить: обычно лишь небольшая часть кода отвечает за большую часть времени выполнения. Это обычно и называют «узким местом» (bottleneck). Поиск узких мест — это первый приоритет в HPC-разработке. Если начать оптимизировать до того, как узкие места найдены, заметный результат обычно появляется только в достаточно очевидных случаях, например если вы используете квадратичный алгоритм сортировки. Во всех остальных случаях вы, скорее всего, будете оптимизировать что-то несущественное.

С учетом этого есть два распространенных способа обнаружения узких мест:

Бенчмарки, то есть измерения производительности на целевых сценариях
Профилирование, то есть углубленный анализ исходного кода при запуске программы под профилировщиками, которые обычно показывают долю времени CPU по функциям или строкам, а также множество других метрик.

Подробнее об этом ниже.

Быстрый код часто менее надежен

Канонический пример — различие между методом at и operator[] у std::vector. at(i) проверяет условие i < size() и выбрасывает исключение std::out_of_range, тогда как operator[] этого не делает и приводит к неопределенному поведению (UB), если i >= size(). operator[] выполняет меньше операций, но он менее надежен, и ответственность за то, чтобы не вызывать его при i >= size(), лежит на разработчике.

В критичном к производительности коде мы, вероятно, захотим использовать operator[] и многие другие техники, которые делают код менее надежным. Вот несколько стандартных способов повысить надежность:

Компиляция со строгими флагами предупреждений, например -Wall -Wextra -Werror
Высокое покрытие тестами, то есть в идеале не должно оставаться строк исходного кода, которые не выполнялись при тестировании, хотя даже 100% покрытия не гарантируют, что проблемы не проявятся позже. Покрытие можно измерять отдельной coverage-сборкой.
Тестирование с sanitizer-сборками. Стандартные C++-санитайзеры включают address, undefined и thread. Это инструментированные сборки с дополнительными проверками. Например, AddressSanitizer позволяет обнаружить выход за границы при обращении через operator[].

Замечание: многие разработчики считают это обязательным для любого C++ проекта.

Типы сборки

Вот стандартные варианты сборки (в терминах CMake):

Debug: базовая диагностическая сборка. Ее можно запускать, например, в gdb с возможностью остановиться на любой строке во время выполнения и посмотреть текущее состояние программы (переменные, память и т. д.). Обычно она компилируется с отключенными оптимизациями через -O0.
Release: стандартная сборка для production-использования. Во многих toolchain’ах она использует оптимизации уровня -O3 и обычно работает значительно быстрее, чем Debug. Из-за этих оптимизаций отладка становится заметно менее удобной, потому что соответствие между строками исходного кода и итоговым бинарником уже не такое прямое.
RelWithDebInfo: диагностическая сборка с флагами -O2 -g, то есть код здесь немного менее оптимизирован, чем в Release, но заметно удобнее для отладки и профилирования.

Нестандартные, но рекомендуемые сборки:

AddressSanitize: сборка и линковка с -fsanitize=address -fno-omit-frame-pointer. Такая конфигурация делает программу очень чувствительной к ошибкам работы с памятью. Существуют и другие санитайзеры, например undefined behaviour и thread, но для нашего случая AddressSanitizer обычно важнее всего.
Coverage: сборка с --coverage для последующей генерации coverage-отчетов, то есть запуска тестов и проверки того, какие строки кода были выполнены, а какие нет.

Release и RelWithDebInfo подходят для бенчмарков и профилирования, AddressSanitize и Coverage — для тестирования, а Debug — для отладки.

Базовые сведения о CPU

Теперь мы знаем, как писать относительно надежный код, но перед тем как его оптимизировать, нам все еще нужно немного разобраться в железе.

CPU обрабатывает все последовательно … или нет?

Если вы читали статьи о различии между GPU и CPU, то наверняка видели тезис о том, что GPU предназначен для массового параллелизма, а CPU — для последовательных вычислений. Это правда, но в CPU тоже есть некоторый параллелизм. Он не такой мощный, как у GPU, но все равно очень важен. Он возникает из следующего:

Несколько ядер: вероятно, самый очевидный источник
Несколько исполнительных блоков: внутри одного ядра обычно есть не один исполнительный блок, а несколько — арифметические устройства (ALU), блоки вычислений с плавающей точкой (FPU), предсказатели ветвлений, специализированные блоки для криптографии и так далее.
SIMD-блоки: их стоит упомянуть отдельно. Большая часть вычислений выполняется как арифметика над машинными словами, которые чаще всего имеют размер 64 бита. В некоторых случаях, когда мы хотим применить одну операцию сразу к нескольким элементам данных (то есть SIMD, single instruction multiple data), это можно собрать в одну инструкцию над 128-, 256- или 512-битными регистрами. На многих современных Intel CPU можно рассчитывать на 256-битные векторные регистры (AVX-2), частично доступны 512-битные регистры (AVX-512).

Я не слишком квалифицирован, чтобы подробно объяснять устройство CPU-конвейера, но могу с уверенностью сказать, что правильное использование перечисленного выше вполне может дать ускорение в 10x-100x на одном и том же коде. Значительная часть оптимизаций C++ компилятора как раз и состоит в перестановке и перепланировании ассемблерных инструкций. При этом такие техники, как разворачивание циклов или ручное программирование SIMD, тоже остаются актуальными.

RAM означает random access memory … или нет?

Изначальная идея RAM состояла в том, что CPU имеет более или менее равномерный доступ к любой ее ячейке, но в реальности доступ не вполне равномерен. Он достаточно равномерен, однако типичные ориентировочные значения задержки доступа составляют 70-120 нс. И снова, я не претендую на подробное объяснение того, как именно работает память, и отсылаю к What Every Programmer Should Know About Memory.

Более важно, чем эта неидеальная равномерность RAM, то, что RAM намного медленнее CPU. Например, частоты Intel-процессоров лежат примерно в диапазоне 1-6 ГГц, то есть это 0.2-1.0 нс на цикл, тогда как доступ к RAM занимает около 100 нс. Именно эта разница и является основной причиной существования CPU-кэшей: нам нужно быстрое промежуточное хранилище данных. Здесь работает простая эвристика: чем больше объем памяти, тем медленнее к ней доступ. Иерархия CPU/RAM выглядит примерно так:

Уровень (от ближайшего к дальнему)	Типичный размер	Типичное время доступа (циклы)	Типичное время доступа (нс)	Примечания
Регистры	~0.5–4 КиБ архитектурного состояния (зависит от ISA)	~0–1	~0–0.3	Операнды читаются как часть выполнения инструкции; по сравнению с кэшем и памятью доступ практически «бесплатный».
L1 D-cache	~32 КиБ / ядро	~3–5	~1.0–1.5	Самый быстрый кэш данных; типичный размер cache line — 64 байта.
L1 I-cache	~32 КиБ / ядро	~3–5 (со стороны выборки инструкций)	~1.0–1.5	Кэш инструкций; обычно сравним по масштабу с L1D.
L2 cache	~512 КиБ – 2 МиБ / ядро	~10–16	~3–6	Часто приватный для каждого ядра (или небольшой группы ядер).
L3 / LLC (shared)	~16–96 МиБ (типично на всю систему)	~30–60	~10–25	Общий для нескольких ядер; зависит от slice/mesh hop/chiplet topology.
DRAM (local NUMA)	~8–512+ ГиБ (типично на всю систему)	~150–300+	~60–120+	Сильно зависит от row hits/misses, конкуренции за память и очередей контроллера.
DRAM (remote NUMA)	то же	~250–500+	~100–200+	Дополнительные переходы по межсоединению; под нагрузкой может быть еще хуже.

Когда, например, вы выполняете линейный проход по массиву и что-то делаете с его элементами, обычно одновременно работают кэширование (например, сохранение недавно использованных данных в более быстрых уровнях кэша) и prefetching (то есть предварительная подгрузка блоков данных, которые, вероятно, скоро понадобятся). Важно, что паттерн доступа при линейном проходе по массиву легко предсказать, тогда как линейный проход по связному списку предсказать заметно сложнее. Это, кстати, одна из причин, почему linked list довольно редко используется, базовым контейнеров в большинстве языков остаётся динамический массив.

Выравнивание адресов

Стоит добавить еще немного деталей о взаимодействии CPU, кэша и RAM. Базовая единица, с которой работает кэш, — это кэш линия (cache line), то есть блок размером 64 байта на большинстве CPU. Кэш и подсистема памяти внутренне работают с выровненными кэш линиями, т.е. вся RAM условно разделена на блоки по размеру кэш линии и когда произвольный блок данных запрашивается из RAM, фактически загружаются все кэш линии, отвечающие за данные в запрошенном блоке. Отсюда возникает например такая проблема: предположим, у вас есть массив объектов, и вы хотите эффективно обрабатывать его блоками с помощью SIMD-инструкций. Пусть мы используем 512-битные AVX-512-инструкции, а размер кэш линии тоже равен 512 битам. Если начало массива выровнено по границе кэш линии, то обработка одного пакета может потребовать одной загрузки/выгрузки кэш линии плюс собственно вычисления. Если же массив не выровнен, то операция может потребовать уже две загрузки/выгрузки. При линейном проходе это не обязательно критично, но при изолированных обращениях такое вполне может приводить к заметной потере производительности.

Для гарантии выравнивания адресов C++17 предоставляет функцию выделения памяти std::aligned_alloc, параметризованную требуемым выравниванием, а также спецификатор alignas(...).

Замечание: на Windows/MSVC std::aligned_alloc исторически был менее удобен и менее переносим на практике, чем на POSIX-подобных платформах, поэтому многие проекты по-прежнему используют _aligned_malloc/_aligned_free или собственные абстракции аллокаторов.

False sharing

И наконец, false sharing — это распространенная проблема в многопоточном коде. Предположим, мы хотим использовать несколько потоков на нескольких ядрах CPU. Напомним, что у каждого ядра есть собственные приватные кэши (как минимум L1, а часто и L2), тогда как более высокие уровни кэша могут быть общими. Проблема возникает в тот момент, когда разные потоки записывают разные переменные, которые случайно оказались на одной и той же кэш линии. Хотя сами переменные логически независимы, протокол когерентности кэшей отслеживает владение на уровне кэш линии целиком, поэтому вся линия начинает постоянно «прыгать» между ядрами.

Важно, что это не data race: потоки могут работать с совершенно разными элементами, но если эти элементы попадают в одну кэш линию, производительность все равно может резко просесть. Вот минимальный пример:

for (int i = 0; i < arr.size(); i += thread_count) {
  for (int t = 0; t < thread_count; ++t) {
    DoWorkInSeperateThread(arr[i + t]);
  }
}

Потоки работают с разными элементами, но из-за чередующегося паттерна доступа одна кэш линия легко может содержать данные, которые несколько потоков пытаются обновлять одновременно. Например, если arr содержит 64-битные int и размер кэш линии 64 байта, то в одну кэш линию помещается 8 элементов! При таком способе обхода 8 соседних потоков могут постоянно инвалидировать кэш линии друг друга, хотя они никогда не обращаются к одному и тому же элементу массива. Более удачный вариант выглядит так:

for (int t = 0; t < thread_count; ++t) {
  auto block_size = (arr.size() + thread_count - 1) / thread_count;
  for (int i = 0; i < block_size && (i + t * block_size) < arr.size(); ++i) {
    DoWorkInThread(arr[i + t * block_size], threads[t]);
  }
}

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

Диагностические инструменты

Теперь мы готовы оптимизировать код, но сначала нам нужно уметь находить узкие места.

Бенчмарки

Технически бенчмарки можно писать и вручную, например с помощью std::chrono::high_resolution_clock, но в бенчмаркинге слишком много подводных камней, поэтому обычно лучше использовать специализированные библиотеки. Самые распространенные варианты:

Эти библиотеки предоставляют типичные инструменты для бенчмаркинга: структурированный вывод, корректную статистику, прогрев и так далее. В Google Benchmark, например, есть функция DoNotOptimize, которая помогает избежать типичной ошибки, когда компилятор просто выбрасывает измеряемый код, потому что он не влияет на результат.

Профилировщики

Windows

Описанные здесь методы хорошо работают на Linux, и я в целом рекомендую использовать WSL/Linux, но если профилировать нужно именно на Windows, то Intel VTune — очень сильный вариант. Если у вас Intel CPU, стоит начать именно с VTune; на других процессорах он, конечно, уже не так хорош. У AMD есть uProf, но мой личный опыт с ним был настолько неудачным, что я бы скорее рекомендовал любой другой доступный вариант.

Учтите, что вы всегда можете установить Windows Subsystem for Linux (WSL) и проводить профилирование там.

Linux/WSL

Базовый инструмент здесь — это утилита perf (на Ubuntu-подобных системах она обычно ставится через пакеты семейства linux-tools-*). Базовый пайплайн выглядит так:

perf record -o <profile_dump> <command>, то есть запуск <command> с одновременным сбором профиля с относительно небольшим overhead. Через опцию --event можно выбрать, что именно вы хотите измерять: cycles, cache misses, branch mispredictions и так далее.
perf annotate <profile_dump>, то есть просмотр профиля прямо в командной строке, хотя лично я бы рекомендовал использовать и более удобные инструменты, например hotspot.

Полезная информация обычно появляется только если код собран в режиме RelWithDebInfo, то есть с флагами -O2 -g. Также стоит отметить, что Google Benchmark умеет работать с hardware events. Для этого нужно включить BENCHMARK_ENABLE_LIBPFM=ON и установить libpfm4-dev. После этого Google Benchmark сможет агрегировать запрошенные аппаратные счетчики для бенчмаркируемых функций.

Еще один хороший инструмент под Linux — valgrind, универсален и довольно прост в использовании, но у него есть серьезный недостаток: он очень медленный. Измерения могут быть весьма полезными, однако время выполнения вырастет в 10-50 раз.

Приоритеты оптимизации

Теперь мы знаем, как находить узкие места, и можем перейти к оптимизации. Ниже — последний блок про то, что и почему имеет смысл оптимизировать в первую очередь.

Асимптотическая сложность

После всего сказанного выше может показаться странным, что я ставлю эту тему на первое место, и я это понимаю. У меня нет точной статистики, но я считаю, что большая часть проблем с производительностью в программном обеспечении связана с неудачным использованием стандартных контейнеров, то есть массивов, очередей, стеков, хеш-таблиц, бинарных деревьев поиска и так далее. И мне кажется, что это справедливо для любого языка. В большинстве случаев, если применим бинарный поиск, то он либо окажется быстрее линейного, либо сама задача никогда не станет узким местом. То же самое относится к квадратичным и логарифмическим алгоритмам сортировки и ко многим другим вещам.

С другой стороны, если копнуть глубже и рассмотреть что-то заметно более сложное, чем STL-алгоритмы и структуры данных, мы быстро попадаем в область, где хорошая асимптотика далеко не всегда превращается в хорошую практическую производительность. К сожалению, в этом смысле теория разошлась с практикой примерно 30 лет назад. Основные причины такие:

Большинство простых идей, которые одновременно хороши и в теории, и на практике, уже были придуманы и реализованы.
Асимптотически лучше — значит лучше на бесконечности; на практике это иногда буквально означает бесконечность. Так называемые галактические алгоритмы могут быть лучшими в теории, но никогда не станут практичными.
Упрощенные вычислительные модели: существуют теоретические работы, которые учитывают дополнительные аспекты по сравнению с классической сложностью на машине Тьюринга, например размер машинного слова, cache-oblivious алгоритмы или модели с внешней памятью, но моделей, одинаково хорошо работающих и в теории, и на практике, довольно мало.
Есть области вроде криптографии, где асимптотическая сложность по-прежнему ключевая.

И наконец, небольшой, но интересный пример: выше я писал, что логарифмические алгоритмы сортировки лучше квадратичных, но есть хорошо известный контрпример: на очень маленьких массивах сортировка вставками оказывается самой быстрой. Это используется в GCC и MSVC, а также использовалось в Clang до интересных находок от AlphaDev.

В любом случае основная мысль здесь в том, что асимптотическая сложность очень важна, но хороший инженер должен понимать, когда она действительно важна, а когда — нет.

Паттерны доступа к памяти

Важность этого пункта напрямую следует из разделов про RAM и CPU-кэши. Лучший пример, где это особенно важно, — матричное умножение. Рассмотрим учебную реализацию:

for (int i = 0; i < n; ++i) {
  for (int j = 0; j < n; ++j) {
    for (int k = 0; k < n; ++k) {
      c[i][j] += a[i][k] * b[k][j];
    }
  }
}

Предположим, что a, b и c — это std::vector<std::vector<float>> или что-то похожее. Такая реализация может оказаться очень далека от пиковых возможностей CPU из-за плохого паттерна доступа к памяти. Почти любое руководство по ускорению матричного умножения начинает с изменения порядка циклов с ijk на ikj, что заменяет неудачный проход по столбцу во внутреннем цикле на более удачный проход по строке и может дать ускорение в 3x-10x. Чтобы приблизиться к пиковой производительности, уже потребуется очень точный контроль потока данных между кэшем и регистрами + SIMD, многопоточность и альтернативные layout’ы матриц (посмотрите, например, это недавнее видео по теме). И важный момент в том, что ничего из этого не является асимптотической оптимизацией. Более того, насколько мне известно, субкубические алгоритмы умножения матриц почти не применяются на практике, за исключением, возможно, некоторых простых вариантов метода Штрассена для достаточно больших матриц.

Векторизация / SIMD

Мы уже несколько раз касались темы SIMD. Если у вас сложные вычисления и узкое место находится не в I/O, имеет смысл убедиться, что используемые алгоритмы способны задействовать SIMD. На этом этапе очень полезен еще один инструмент — godbolt.org, в первую очередь для просмотра ассемблерного вывода. Это простой способ увидеть, какие именно инструкции генерируются. В простых случаях компилятор сделает работу за вас, например для линейных проходов с несложной агрегацией. В других случаях придется делать это вручную; посмотрите, например, на такой пример параллельного просмотра таблиц в simdjson, про этот метод можно подробнее почитать в статье Два универсальных SIMD алгоритма.

Вот еще один пример того, где SIMD важен: если посмотреть на реализацию string::find в GCC или Clang/libc++, можно удивиться, увидев довольно «наивную» структуру поиска. Почему там не используется отличный $\mathcal{O}(n)$ алгоритм Кнута-Морриса-Пратта? Уверен, что авторы стандартных библиотек вполне способны его реализовать. Причина в том, что, хотя наивный алгоритм выполняет больше сравнений, эти сравнения легко группировать в блоки. Строки длиной 32 байта можно сравнивать на большинстве CPU одной SIMD-инструкцией, а AVX-512 позволяет сравнивать 64-байтные блоки, что покрывает большую часть практических случаев. KMP, напротив, требует последовательных сравнений, которые плохо ложатся на SIMD. Начиная с C++17 есть и альтернативный интерфейс — std::boyer_moore_searcher, если у вас действительно нетипичный случай поиска по строке.

Если хочется подробнее почитать про SIMD, посмотрите на руководства по интринсикам от Intel и ARM. Также стоит помнить, что std::simd ожидается в C++26.

Ветвления

Проблема ветвлений универсальна для любого конвейерного или параллельного исполнения. Если заранее известно, что вы будете делать дальше, появляется возможность для оптимизации за счет грамотного планирования; если же на каком-то шаге нужно дождаться текущего состояния и только потом выбрать дальнейшие действия, возможность планировать заранее исчезает. К сожалению, это верно и для CPU. В некоторых ситуациях может код без ветвления может оказаться быстрее кода с ветвлением несмотря на необходмиость большего числа вычислений. Например код

result = condition * if_expression + !condition * else_expression;

всегда вычиялющий как if_expression так и else_expression будет быстрее

if (condition)
  result = if_expression;
else
  result = else_expression;

вычисляющий только один из выражений при условии, что оба достаточно простые, точного критерия тут вам врядли кто-то даст – проверяйте реальную производительность и смотрите во что компилируется программа.

В любом случае в критичном к производительности коде стоит избегать лишних ветвлений. В C++20 появились атрибуты [[likely]] и [[unlikely]], с помощью которых разработчик может подсказать компилятору вероятности ветвления. Это именно подсказка о вероятном направлении ветки, а не гарантия того, как именно будет исполняться код.

Арифметика

Ситуации, в которых действительно нужно оптимизировать арифметические вычисления, встречаются относительно редко. Если вы все же оказались в такой ситуации, то я мало чем могу помочь, кроме рекомендации использовать godbolt.org — это один из самых полезных инструментов в таком сценарии. И не забывайте о том, что процессор предоставляет намного больше, чем просто стандартную целочисленную и булеву арифметику: например, есть BMI/BMI2 (битовые манипуляции), FMA (fused multiply-add), AES (Advanced Encryption Standard), CLMUL (carry-less multiplication), GFNI (Galois field new instructions) и другие.

Ссылки

--- title: "Краткое введение в высокопроизводительные вычисления на C++ для CPU" description: "Эта заметка описывает мой личный взгляд на то, как писать эффективный и надежный код для CPU. Статья ориентируется на С++, но значительная часть обсуждения CPU, кэшей, паттернов доступа к памяти и профилирования применима к Rust, Go и другим компилируемым языкам." author: "Николай Мальковский" date: "2026-03-16" categories: [HPC, C++] image: "hpc_thumbnail.png" draft: false --- ![](hpc_title.jpg) > Поскольку вы программист на C++, вероятность того, что вы слегка одержимы производительностью, выше среднего. А если нет, то вы, вероятно, по крайней мере с пониманием относитесь к такой точке зрения. (Если производительность вас совсем не интересует, аудитория Python разработчиков дальше по коридору) > > Из пункта 42 книги С. Майерса “Effective Modern C++”, 2015. Статья задумана как краткое введение и больше всего подходит студентам, имеющим опыт программирования на занятиях, но не в реальных проектах. Для профессионалов статья может быть полезной в качестве референса, чтобы не пугать новичков чем-то в духе [Что каждый программист должен знать о памяти](http://codelabs.ru/reading/drepper-wepskam.pdf). В статье расскажу про "starter pack": godbolt.org, профилирование, бенчмарки, особенности CPU и его взаимодействия с памятью, когда есть ли смысл от асимптотических оптимизаций и почему важно при этом пользоваться санитайзерами, отслеживать coverage и вообще более трепетно относится к надёжности. # Прежде чем начать > О мелких оптимизациях стоит забывать, скажем, примерно в 97% случаев: преждевременная оптимизация — корень всех зол. Но нельзя упускать возможности в тех самых критичных 3% > > Д. Кнут, “Structured Programming with go to Statements” (ACM Computing Surveys, 6(4), 1974). Эта мысль отлично выдержала проверку временем. Она была сформулирована 50 лет назад, но по-прежнему остается верной, несмотря на то, насколько сильно изменилась разработка программного обеспечения. Не весь код является критичным к производительности, и это на самом деле хорошо. Например, в ML/AI матричное умножение и работа с attention KV cache могут занимать почти все вычисления, а все остальное можно писать на Python без заметной деградации. Суть в том, что, если вас интересует результат, стоит помнить: обычно лишь небольшая часть кода отвечает за большую часть времени выполнения. Это обычно и называют «узким местом» (*bottleneck*). Поиск узких мест — это первый приоритет в HPC-разработке. Если начать оптимизировать до того, как узкие места найдены, заметный результат обычно появляется только в достаточно очевидных случаях, например если вы используете квадратичный алгоритм сортировки. Во всех остальных случаях вы, скорее всего, будете оптимизировать что-то несущественное. С учетом этого есть два распространенных способа обнаружения узких мест: - *Бенчмарки*, то есть измерения производительности на целевых сценариях - *Профилирование*, то есть углубленный анализ исходного кода при запуске программы под *профилировщиками*, которые обычно показывают долю времени CPU по функциям или строкам, а также множество других метрик. Подробнее об этом ниже. ## Быстрый код часто менее надежен Канонический пример — различие между методом `at` и `operator[]` у `std::vector`. `at(i)` проверяет условие `i < size()` и выбрасывает исключение `std::out_of_range`, тогда как `operator[]` этого не делает и приводит к неопределенному поведению (UB), если `i >= size()`. `operator[]` выполняет меньше операций, но он менее надежен, и ответственность за то, чтобы не вызывать его при `i >= size()`, лежит на разработчике. В критичном к производительности коде мы, вероятно, захотим использовать `operator[]` и многие другие техники, которые делают код менее надежным. Вот несколько стандартных способов повысить надежность: - **Компиляция со строгими флагами предупреждений**, например `-Wall -Wextra -Werror` - **Высокое покрытие тестами**, то есть в идеале не должно оставаться строк исходного кода, которые не выполнялись при тестировании, хотя даже 100% покрытия не гарантируют, что проблемы не проявятся позже. Покрытие можно измерять отдельной coverage-сборкой. - **Тестирование с sanitizer-сборками**. Стандартные C++-санитайзеры включают `address`, `undefined` и `thread`. Это инструментированные сборки с дополнительными проверками. Например, AddressSanitizer позволяет обнаружить выход за границы при обращении через `operator[]`. *Замечание: многие разработчики считают это обязательным для любого C++ проекта.* ## Типы сборки Вот стандартные варианты сборки (в терминах CMake): - **Debug**: базовая диагностическая сборка. Ее можно запускать, например, в gdb с возможностью остановиться на любой строке во время выполнения и посмотреть текущее состояние программы (переменные, память и т. д.). Обычно она компилируется с отключенными оптимизациями через `-O0`. - **Release**: стандартная сборка для production-использования. Во многих toolchain'ах она использует оптимизации уровня `-O3` и обычно работает значительно быстрее, чем Debug. Из-за этих оптимизаций отладка становится заметно менее удобной, потому что соответствие между строками исходного кода и итоговым бинарником уже не такое прямое. - **RelWithDebInfo**: диагностическая сборка с флагами `-O2 -g`, то есть код здесь немного менее оптимизирован, чем в Release, но заметно удобнее для отладки и профилирования. Нестандартные, но рекомендуемые сборки: - **AddressSanitize**: сборка и линковка с `-fsanitize=address -fno-omit-frame-pointer`. Такая конфигурация делает программу очень чувствительной к ошибкам работы с памятью. Существуют и другие санитайзеры, например undefined behaviour и thread, но для нашего случая AddressSanitizer обычно важнее всего. - **Coverage**: сборка с `--coverage` для последующей генерации coverage-отчетов, то есть запуска тестов и проверки того, какие строки кода были выполнены, а какие нет. Release и RelWithDebInfo подходят для бенчмарков и профилирования, AddressSanitize и Coverage — для тестирования, а Debug — для отладки. # Базовые сведения о CPU Теперь мы знаем, как писать относительно надежный код, но перед тем как его оптимизировать, нам все еще нужно немного разобраться в железе. ## CPU обрабатывает все последовательно ... или нет? Если вы читали статьи о различии между GPU и CPU, то наверняка видели тезис о том, что GPU предназначен для массового параллелизма, а CPU — для последовательных вычислений. Это правда, но в CPU тоже есть *некоторый* параллелизм. Он не такой мощный, как у GPU, но все равно очень важен. Он возникает из следующего: - **Несколько ядер**: вероятно, самый очевидный источник - **Несколько исполнительных блоков**: внутри одного ядра обычно есть не один исполнительный блок, а несколько — арифметические устройства (ALU), блоки вычислений с плавающей точкой (FPU), предсказатели ветвлений, специализированные блоки для криптографии и так далее. - **SIMD-блоки**: их стоит упомянуть отдельно. Большая часть вычислений выполняется как арифметика над машинными словами, которые чаще всего имеют размер 64 бита. В некоторых случаях, когда мы хотим применить одну операцию сразу к нескольким элементам данных (то есть *SIMD*, single instruction multiple data), это можно собрать в одну инструкцию над 128-, 256- или 512-битными регистрами. На многих современных Intel CPU можно рассчитывать на 256-битные векторные регистры (AVX-2), частично доступны 512-битные регистры (AVX-512). Я не слишком квалифицирован, чтобы подробно объяснять устройство CPU-конвейера, но могу с уверенностью сказать, что правильное использование перечисленного выше вполне может дать ускорение в 10x-100x на одном и том же коде. Значительная часть оптимизаций C++ компилятора как раз и состоит в перестановке и перепланировании ассемблерных инструкций. При этом такие техники, как разворачивание циклов или ручное программирование SIMD, тоже остаются актуальными. ## RAM означает *random access memory* ... или нет? Изначальная идея RAM состояла в том, что CPU имеет более или менее равномерный доступ к любой ее ячейке, но в реальности доступ не вполне равномерен. Он *достаточно равномерен*, однако типичные ориентировочные значения задержки доступа составляют 70-120 нс. И снова, я не претендую на подробное объяснение того, как именно работает память, и отсылаю к [What Every Programmer Should Know About Memory](http://codelabs.ru/reading/drepper-wepskam.pdf). Более важно, чем эта неидеальная равномерность RAM, то, что RAM намного медленнее CPU. Например, частоты Intel-процессоров лежат примерно в диапазоне 1-6 ГГц, то есть это 0.2-1.0 нс на цикл, тогда как доступ к RAM занимает около 100 нс. Именно эта разница и является основной причиной существования CPU-кэшей: нам нужно быстрое промежуточное хранилище данных. Здесь работает простая эвристика: *чем больше объем памяти, тем медленнее к ней доступ*. Иерархия CPU/RAM выглядит примерно так: | Уровень (от ближайшего к дальнему) | Типичный размер | Типичное время доступа (циклы) | Типичное время доступа (нс) | Примечания | |---|---:|---:|---:|---| | Регистры | ~0.5–4 КиБ архитектурного состояния (зависит от ISA) | ~0–1 | ~0–0.3 | Операнды читаются как часть выполнения инструкции; по сравнению с кэшем и памятью доступ практически «бесплатный». | | L1 D-cache | ~32 КиБ / ядро | ~3–5 | ~1.0–1.5 | Самый быстрый кэш данных; типичный размер cache line — 64 байта. | | L1 I-cache | ~32 КиБ / ядро | ~3–5 (со стороны выборки инструкций) | ~1.0–1.5 | Кэш инструкций; обычно сравним по масштабу с L1D. | | L2 cache | ~512 КиБ – 2 МиБ / ядро | ~10–16 | ~3–6 | Часто приватный для каждого ядра (или небольшой группы ядер). | | L3 / LLC (shared) | ~16–96 МиБ (типично на всю систему) | ~30–60 | ~10–25 | Общий для нескольких ядер; зависит от slice/mesh hop/chiplet topology. | | DRAM (local NUMA) | ~8–512+ ГиБ (типично на всю систему) | ~150–300+ | ~60–120+ | Сильно зависит от row hits/misses, конкуренции за память и очередей контроллера. | | DRAM (remote NUMA) | то же | ~250–500+ | ~100–200+ | Дополнительные переходы по межсоединению; под нагрузкой может быть еще хуже. | Когда, например, вы выполняете линейный проход по массиву и что-то делаете с его элементами, обычно одновременно работают кэширование (например, сохранение недавно использованных данных в более быстрых уровнях кэша) и prefetching (то есть предварительная подгрузка блоков данных, которые, вероятно, скоро понадобятся). Важно, что паттерн доступа при линейном проходе по массиву легко предсказать, тогда как линейный проход по связному списку предсказать заметно сложнее. Это, кстати, одна из причин, почему linked list довольно редко используется, базовым контейнеров в большинстве языков остаётся динамический массив. ## Выравнивание адресов Стоит добавить еще немного деталей о взаимодействии CPU, кэша и RAM. Базовая единица, с которой работает кэш, — это *кэш линия* (cache line), то есть блок размером 64 байта на большинстве CPU. Кэш и подсистема памяти внутренне работают с *выровненными кэш линиями*, т.е. вся RAM условно разделена на блоки по размеру кэш линии и когда произвольный блок данных запрашивается из RAM, фактически загружаются все кэш линии, отвечающие за данные в запрошенном блоке. Отсюда возникает например такая проблема: предположим, у вас есть массив объектов, и вы хотите эффективно обрабатывать его блоками с помощью SIMD-инструкций. Пусть мы используем 512-битные AVX-512-инструкции, а размер кэш линии тоже равен 512 битам. Если начало массива выровнено по границе кэш линии, то обработка одного пакета может потребовать одной загрузки/выгрузки кэш линии плюс собственно вычисления. Если же массив не выровнен, то операция может потребовать уже две загрузки/выгрузки. При линейном проходе это не обязательно критично, но при изолированных обращениях такое вполне может приводить к заметной потере производительности. Для гарантии выравнивания адресов C++17 предоставляет функцию выделения памяти `std::aligned_alloc`, параметризованную требуемым выравниванием, а также спецификатор `alignas(...)`. *Замечание:* на Windows/MSVC `std::aligned_alloc` исторически был менее удобен и менее переносим на практике, чем на POSIX-подобных платформах, поэтому многие проекты по-прежнему используют `_aligned_malloc`/`_aligned_free` или собственные абстракции аллокаторов. ## False sharing И наконец, false sharing — это распространенная проблема в многопоточном коде. Предположим, мы хотим использовать несколько потоков на нескольких ядрах CPU. Напомним, что у каждого ядра есть собственные приватные кэши (как минимум L1, а часто и L2), тогда как более высокие уровни кэша могут быть общими. Проблема возникает в тот момент, когда разные потоки записывают разные переменные, которые случайно оказались на одной и той же кэш линии. Хотя сами переменные логически независимы, протокол когерентности кэшей отслеживает владение на уровне кэш линии целиком, поэтому вся линия начинает постоянно «прыгать» между ядрами. Важно, что это не data race: потоки могут работать с совершенно разными элементами, но если эти элементы попадают в одну кэш линию, производительность все равно может резко просесть. Вот минимальный пример: ```cpp for (int i = 0; i < arr.size(); i += thread_count) { for (int t = 0; t < thread_count; ++t) { DoWorkInSeperateThread(arr[i + t]); } } ``` Потоки работают с разными элементами, но из-за чередующегося паттерна доступа одна кэш линия легко может содержать данные, которые несколько потоков пытаются обновлять одновременно. Например, если `arr` содержит 64-битные `int` и размер кэш линии 64 байта, то в одну кэш линию помещается 8 элементов! При таком способе обхода 8 соседних потоков могут постоянно инвалидировать кэш линии друг друга, хотя они никогда не обращаются к одному и тому же элементу массива. Более удачный вариант выглядит так: ```cpp for (int t = 0; t < thread_count; ++t) { auto block_size = (arr.size() + thread_count - 1) / thread_count; for (int i = 0; i < block_size && (i + t * block_size) < arr.size(); ++i) { DoWorkInThread(arr[i + t * block_size], threads[t]); } } ``` В этом случае false sharing становится намного меньше, потому что каждый поток в основном работает со своим непрерывным блоком данных. Некоторое взаимодействие все еще возможно около границ блоков, поэтому идельно всё-таки позаботиться о выравнивании и, опционально, паддинге так, чтобы от записи разных потоков вообще не делили кэш линии. # Диагностические инструменты Теперь мы готовы оптимизировать код, но сначала нам нужно уметь находить узкие места. ## Бенчмарки Технически бенчмарки можно писать и вручную, например с помощью `std::chrono::high_resolution_clock`, но в бенчмаркинге слишком много подводных камней, поэтому обычно лучше использовать специализированные библиотеки. Самые распространенные варианты: - [Google benchmark(recommended)](https://github.com/google/benchmark) - [ankerl::nanobench](https://github.com/martinus/nanobench) - [Catch2](https://github.com/catchorg/Catch2) Эти библиотеки предоставляют типичные инструменты для бенчмаркинга: структурированный вывод, корректную статистику, прогрев и так далее. В Google Benchmark, например, есть функция `DoNotOptimize`, которая помогает избежать типичной ошибки, когда компилятор просто выбрасывает измеряемый код, потому что он не влияет на результат. ## Профилировщики ### Windows Описанные здесь методы хорошо работают на Linux, и я в целом рекомендую использовать WSL/Linux, но если профилировать нужно именно на Windows, то **Intel VTune** — очень сильный вариант. Если у вас Intel CPU, стоит начать именно с VTune; на других процессорах он, конечно, уже не так хорош. У AMD есть `uProf`, но мой личный опыт с ним был настолько неудачным, что я бы скорее рекомендовал любой другой доступный вариант. Учтите, что вы всегда можете установить Windows Subsystem for Linux (WSL) и проводить профилирование там. ### Linux/WSL Базовый инструмент здесь — это утилита `perf` (на Ubuntu-подобных системах она обычно ставится через пакеты семейства `linux-tools-*`). Базовый пайплайн выглядит так: - `perf record -o <profile_dump> <command>`, то есть запуск `<command>` с одновременным сбором профиля с относительно небольшим overhead. Через опцию `--event` можно выбрать, что именно вы хотите измерять: cycles, cache misses, branch mispredictions и так далее. - `perf annotate <profile_dump>`, то есть просмотр профиля прямо в командной строке, хотя лично я бы рекомендовал использовать и более удобные инструменты, например `hotspot`. Полезная информация обычно появляется только если код собран в режиме `RelWithDebInfo`, то есть с флагами `-O2 -g`. Также стоит отметить, что Google Benchmark умеет работать с hardware events. Для этого нужно включить `BENCHMARK_ENABLE_LIBPFM=ON` и установить `libpfm4-dev`. После этого Google Benchmark сможет агрегировать запрошенные аппаратные счетчики для бенчмаркируемых функций. Еще один хороший инструмент под Linux — **valgrind**, универсален и довольно прост в использовании, но у него есть серьезный недостаток: он очень медленный. Измерения могут быть весьма полезными, однако время выполнения вырастет в 10-50 раз. # Приоритеты оптимизации Теперь мы знаем, как находить узкие места, и можем перейти к оптимизации. Ниже — последний блок про то, что и почему имеет смысл оптимизировать в первую очередь. ## Асимптотическая сложность После всего сказанного выше может показаться странным, что я ставлю *эту* тему на первое место, и я это понимаю. У меня нет точной статистики, но я считаю, что большая часть проблем с производительностью в программном обеспечении связана с неудачным использованием стандартных контейнеров, то есть массивов, очередей, стеков, хеш-таблиц, бинарных деревьев поиска и так далее. И мне кажется, что это справедливо для любого языка. В большинстве случаев, если применим бинарный поиск, то он либо окажется быстрее линейного, либо сама задача никогда не станет узким местом. То же самое относится к квадратичным и логарифмическим алгоритмам сортировки и ко многим другим вещам. С другой стороны, если копнуть глубже и рассмотреть что-то заметно более сложное, чем STL-алгоритмы и структуры данных, мы быстро попадаем в область, где хорошая асимптотика далеко не всегда превращается в хорошую практическую производительность. К сожалению, в этом смысле теория разошлась с практикой примерно 30 лет назад. Основные причины такие: - Большинство простых идей, которые одновременно хороши и в теории, и на практике, уже были придуманы и реализованы. - Асимптотически лучше — значит лучше на бесконечности; на практике это иногда буквально означает бесконечность. Так называемые [галактические алгоритмы](https://en.wikipedia.org/wiki/Galactic_algorithm) могут быть лучшими в теории, но никогда не станут практичными. - Упрощенные вычислительные модели: существуют теоретические работы, которые учитывают дополнительные аспекты по сравнению с классической сложностью на машине Тьюринга, например размер машинного слова, cache-oblivious алгоритмы или модели с внешней памятью, но моделей, одинаково хорошо работающих и в теории, и на практике, довольно мало. - Есть области вроде криптографии, где асимптотическая сложность по-прежнему ключевая. И наконец, небольшой, но интересный пример: выше я писал, что логарифмические алгоритмы сортировки лучше квадратичных, но есть хорошо известный контрпример: на очень маленьких массивах сортировка вставками оказывается самой быстрой. Это используется в GCC и MSVC, а также использовалось в Clang до интересных находок от [AlphaDev](https://en.wikipedia.org/wiki/AlphaDev#LLVM_standard_sorting_library). В любом случае основная мысль здесь в том, что асимптотическая сложность очень важна, но хороший инженер должен понимать, когда она действительно важна, а когда — нет. ## Паттерны доступа к памяти Важность этого пункта напрямую следует из разделов про RAM и CPU-кэши. Лучший пример, где это особенно важно, — матричное умножение. Рассмотрим *учебную* реализацию: ```cpp for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { c[i][j] += a[i][k] * b[k][j]; } } } ``` Предположим, что `a`, `b` и `c` — это `std::vector<std::vector<float>>` или что-то похожее. Такая реализация может оказаться очень далека от пиковых возможностей CPU из-за плохого паттерна доступа к памяти. Почти любое руководство по ускорению матричного умножения начинает с изменения порядка циклов с `ijk` на `ikj`, что заменяет неудачный проход по столбцу во внутреннем цикле на более удачный проход по строке и может дать ускорение в 3x-10x. Чтобы приблизиться к пиковой производительности, уже потребуется очень точный контроль потока данных между кэшем и регистрами + SIMD, многопоточность и альтернативные layout'ы матриц (посмотрите, например, это недавнее [видео](https://www.youtube.com/watch?v=GHctcSBd6Z4) по теме). И важный момент в том, что ничего из этого не является асимптотической оптимизацией. Более того, насколько мне известно, субкубические алгоритмы умножения матриц почти не применяются на практике, за исключением, возможно, некоторых простых вариантов метода Штрассена для достаточно больших матриц. ## Векторизация / SIMD Мы уже несколько раз касались темы SIMD. Если у вас сложные вычисления и узкое место находится не в I/O, имеет смысл убедиться, что используемые алгоритмы способны задействовать SIMD. На этом этапе очень полезен еще один инструмент — [godbolt.org](godbolt.org), в первую очередь для просмотра ассемблерного вывода. Это простой способ увидеть, какие именно инструкции генерируются. В простых случаях компилятор сделает работу за вас, например для линейных проходов с несложной агрегацией. В других случаях придется делать это вручную; посмотрите, например, на такой пример параллельного просмотра таблиц в [simdjson](https://github.com/simdjson/simdjson/blob/master/src/generic/stage1/utf8_lookup4_algorithm.h), про этот метод можно подробнее почитать в статье [Два универсальных SIMD алгоритма](https://habr.com/ru/articles/964608/). Вот еще один пример того, где SIMD важен: если посмотреть на реализацию `string::find` в [GCC](https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/basic_string.tcc) или [Clang/libc++](https://github.com/llvm/llvm-project/blob/main/libcxx/include/string), можно удивиться, увидев довольно «наивную» структуру поиска. Почему там не используется отличный $\mathcal{O}(n)$ алгоритм [Кнута-Морриса-Пратта](https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm)? Уверен, что авторы стандартных библиотек вполне способны его реализовать. Причина в том, что, хотя наивный алгоритм выполняет больше сравнений, эти сравнения легко группировать в блоки. Строки длиной 32 байта можно сравнивать на большинстве CPU одной SIMD-инструкцией, а AVX-512 позволяет сравнивать 64-байтные блоки, что покрывает большую часть практических случаев. KMP, напротив, требует последовательных сравнений, которые плохо ложатся на SIMD. Начиная с C++17 есть и альтернативный интерфейс — [`std::boyer_moore_searcher`](https://en.cppreference.com/w/cpp/utility/functional/boyer_moore_searcher.html), если у вас действительно нетипичный случай поиска по строке. Если хочется подробнее почитать про SIMD, посмотрите на руководства по интринсикам от [Intel](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html) и [ARM](https://developer.arm.com/architectures/instruction-sets/intrinsics/). Также стоит помнить, что `std::simd` ожидается в C++26. ## Ветвления Проблема ветвлений универсальна для любого конвейерного или параллельного исполнения. Если заранее известно, что вы будете делать дальше, появляется возможность для оптимизации за счет грамотного планирования; если же на каком-то шаге нужно дождаться текущего состояния и только потом выбрать дальнейшие действия, возможность планировать заранее исчезает. К сожалению, это верно и для CPU. В некоторых ситуациях может код без ветвления может оказаться быстрее кода с ветвлением несмотря на необходмиость большего числа вычислений. Например код ```cpp result = condition * if_expression + !condition * else_expression; ``` всегда вычиялющий как `if_expression` так и `else_expression` будет быстрее ```cpp if (condition) result = if_expression; else result = else_expression; ``` вычисляющий только один из выражений при условии, что оба достаточно простые, точного критерия тут вам врядли кто-то даст -- проверяйте реальную производительность и смотрите во что компилируется программа. В любом случае в критичном к производительности коде стоит избегать лишних ветвлений. В C++20 появились атрибуты `[[likely]]` и `[[unlikely]]`, с помощью которых разработчик может подсказать компилятору вероятности ветвления. Это именно подсказка о вероятном направлении ветки, а не гарантия того, как именно будет исполняться код. ## Арифметика Ситуации, в которых действительно нужно оптимизировать арифметические вычисления, встречаются относительно редко. Если вы все же оказались в такой ситуации, то я мало чем могу помочь, кроме рекомендации использовать [godbolt.org](godbolt.org) — это один из самых полезных инструментов в таком сценарии. И не забывайте о том, что процессор предоставляет намного больше, чем просто стандартную целочисленную и булеву арифметику: например, есть BMI/BMI2 (битовые манипуляции), FMA (fused multiply-add), AES (Advanced Encryption Standard), CLMUL (carry-less multiplication), GFNI (Galois field new instructions) и другие. # Ссылки - Ulrich Drepper, [What Every Programmer Should Know About Memory](http://codelabs.ru/reading/drepper-wepskam.pdf). - [Google Benchmark](https://github.com/google/benchmark) - [ankerl::nanobench](https://github.com/martinus/nanobench) - [Catch2](https://github.com/catchorg/Catch2) - [Intel Intrinsics Guide](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html) - [ARM Intrinsics Search Engine](https://developer.arm.com/architectures/instruction-sets/intrinsics/) - [simdjson](https://github.com/simdjson/simdjson) - [GCC libstdc++ `basic_string` implementation](https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/basic_string.tcc) - [LLVM libc++ `string` implementation](https://github.com/llvm/llvm-project/blob/main/libcxx/include/string) - [cppreference: `std::boyer_moore_searcher`](https://en.cppreference.com/w/cpp/utility/functional/boyer_moore_searcher.html) - [Wikipedia: Galactic algorithm](https://en.wikipedia.org/wiki/Galactic_algorithm) - [Wikipedia: Knuth-Morris-Pratt algorithm](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm) - [Wikipedia: AlphaDev](https://en.wikipedia.org/wiki/AlphaDev#LLVM_standard_sorting_library) - [How to Multiply Matrices Fast](https://www.youtube.com/watch?v=GHctcSBd6Z4) - [Два универсальных SIMD алгоритма](https://habr.com/ru/articles/964608/)