Как оптимизировать код C и C ++ в 2018 году

Почему производительность так важна

Мы все еще ограничены нашим текущим оборудованием. Есть множество областей, в которых этого недостаточно: нейронные сети и виртуальная реальность, и это лишь некоторые из них. Есть множество устройств, где время автономной работы имеет решающее значение, и мы должны считать каждый тик ЦП. Даже когда мы говорим об облаках, микросервисах и лямбдах, существуют огромные центры обработки данных, которые потребляют огромное количество электроэнергии.

Даже скучная рутина тестов может незаметно начать выполняться через 5 часов. А это сложно. Производительность программы не имеет значения, только пока она не имеет значения.

Современный способ выжать из кремния производительность - это делать оборудование все более и более сложным.

Мы живем во времена, когда компьютеры крошечные, ядер много, а память - узкое место (молитвенное поведение еще предстоит определить).

Знакомство с современным оборудованием

ЦП

• миллиарды транзисторов
• пытается предсказать будущее
• отслеживает зависимости данных и инструкций
• выполняет команды параллельно и не по порядку
• программируемый (имеет собственный микрокод)
• знает о методах виртуализации памяти и ЦП
• имеет некоторые высокоуровневые инструкции (криптографические хеш-функции)
• есть даже какая-то нейронная сеть для предсказания ветвей¹
• пока обнаружено несколько критических уязвимостей

DRAM

• миллиарды конденсаторов
• миллиарды конденсаторов, правда - вот и все

DRAM (динамическая память с произвольным доступом), в которой для хранения каждого бита используются ячейки памяти, состоящие из одного конденсатора и одного транзистора. Это самый дешевый и самый высокий по плотности, поэтому он используется для основной памяти в компьютерах².

Загрузка и сохранение памяти часто являются узким местом.

Стоимость одного обращения к памяти составляет около 100 наносекунд³. Это означает, что процессор с тактовой частотой 1 ГГц может потратить 100 и более тиков на ожидание значения из памяти. Так что кеширование значений в памяти вместо того, чтобы каждый раз пересчитывать, может происходить буквально в 100 раз медленнее. Чего-чего?!

Несмотря на то, что ЦП достаточно умен, чтобы заблаговременно получать данные, во многих случаях программисты по-прежнему несут ответственность за структуру памяти и шаблоны доступа.

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

Современные компиляторы могут вносить в код множество модификаций для повышения производительности. Программисту полезно знать, что может делать компилятор, а что нет.

~ Агнер Фог «Оптимизация программного обеспечения на C ++» ⁴

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

К сожалению, нет ничего магического. Оптимизирующие компиляторы C и C ++ далеки от идеала; очень важно понимать, что находится под капотом компилятора. В конце концов, это инструмент, который мы используем ежедневно.

Есть это отличное видео⁵: Понимание оптимизации компилятора - Чендлер Каррут - Открытие ключевой конференции C ++ 2015 (также есть ссылка на слайды в конце)

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

Я попытался повторить каждый пример из презентации Чендлера сам, используя clang -emit-llvm, и большинство примеров кода здесь были созданы непосредственно с помощью LLVM. Хотя некоторые списки были беззастенчиво скопированы со слайдов Чендлера Каррута.

Понимание производительности означает понимание оптимизаторов.

~ Чендлер Каррут «Открытие ключевой конференции C ++ 2015»

Несмотря на то, что следующие списки были сделаны с помощью LLVM (clang), те же принципы применимы к GCC и, в некоторой степени, ко всем современным оптимизирующим компиляторам.

Знакомство с LLVM IR

Компиляторы в значительной степени полагаются на форму статического единственного присваивания (SSA), то есть: требуется, чтобы каждая переменная была назначена точно один раз, а каждая переменная была определена раньше используется ⁷.

Привет, мир

Приведенный выше код должен быть очень простым:

• функции - @g и @f
• типы - i32
• значения (переменные) - %a, %b,…
• инструкции - add, call, ret

Поток управления

Операция br - переход по флагу и переход к (соответствующей) операции с меткой. Он контролирует весь поток управления.

Поток данных

Опять же: каждой переменной присваивается ровно один раз, и каждая переменная определяется перед использованием.

Но как мы можем получить значение, которое определено только в условной ветви, например %d в приведенном выше примере?

Ответ - инструкция phi, которая объединяет значения ветвей в одно в зависимости от того, откуда вы пришли.

Если мы пришли из entry, то %result = %c, если пришли из then, то %result = %d.

Это оно

LLVM IR настолько прост. Есть много других инструкций, но ничего кроме этого.

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

Чем занимаются оптимизаторы

Шаг 1. Очистка

Интерфейс компилятора создает специальный IR-код, как будто объем памяти неограничен; его заботит только создание шаблонов, «знакомых» оптимизатору.

Вот пример:

Это то, что мы получим, если запустим clang -cc1 -emit-llvm -O0 example.c -o example.ll (без оптимизации). Интерфейс LLVM помещает все в память, поэтому есть цепочки из alloca, store и load:

На этапе очистки компилятор пытается заменить инструкции, связанные с памятью, значениями формы SSA. Позже будет решено, выделять ли память или использовать регистры. Некоторые переменные (часто большинство) будут вообще исключены.

Вот что происходит, когда мы включаем оптимизацию (-O1):

Конечно, этот код не просто очищается, но и оптимизируется. Теперь вы можете увидеть, как LLVM IR повторяет код C.

icmp сравнивает целые числа, указатели или векторы и возвращает логическое значение. Первый аргумент - это ключевое слово, указывающее тип сравнения. Здесь icmp eq означает сравнение на равенство. Другие примеры: ult - без знака меньше, sge - со знаком больше или равно и т. Д.

getelementptr - это инструкция, которая обрабатывает всю арифметику указателей в LLVM. Независимо от того, есть ли элемент массива или поле структуры. Последний аргумент getelementptr - это индекс элемента.

<result> = getelementptr inbounds <ty>, <ty>* <ptrval>{, [inrange] <ty> <idx>}*

(Ссылка на Справочное руководство по языку LLVM)

Шаг 2. Канонизация

Есть много возможных способов написать один и тот же код с помощью операторов потока управления:

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

Таким образом, каждый цикл становится каноническим циклом, оператор if-then - каноническим if-then и так далее.

Вернемся к первому примеру:

Вот соответствующий список LLVM IR, но немного измененный для лучшей читаемости.

Без оптимизации:

Канонический код if-then:

Во-первых, это код, который проверяет количество аргументов if (argc != 2).

Перед: icmp ne - сравнить, если не равно инструкция. Теперь мы видим icmp eq - сравнивать, если равно. Оптимизатору не нужно обрабатывать инструкцию icmp ne, даже если она поддерживается LLVM IR.

Другое отличие состоит в том, что метка if.then и путь выполнения кода исчезли. Теперь метка return обрабатывает ту же логику с узлом phi.

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

Шаг 3: свернуть абстракции

Я думаю, что то, что отличает C ++ от всех других языков, с которыми я когда-либо работал, - это способность создавать абстракции, которые рушатся.

~ Чендлер Каррут «Открытие ключевой встречи, посвященной C ++ 2015».

С точки зрения оптимизатора есть три основных абстракции:

1. Функции, вызовы и график вызовов
2. Память, загрузка и сохранение
3. Циклы

1. Функции, вызовы и граф вызовов

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

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

Встроить или нет - это решение наиболее критичное для создания быстрого кода.

К счастью, многие функции были просто ярлыками для других функций. Они должны легко удаляться.

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

HHVM (HipHop Virtual Machine) - это виртуальная машина PHP с JIT. Он был создан для замены HipHop (транспилятора исходного кода PHP в C ++) на Facebook.

Когда весь код Facebook запускался в HHVM после 12 месяцев разработки, он был в 7 раз медленнее⁸.

Предлагаю вам посмотреть слайды презентации, но хочу отметить одну вещь:

Когда код делает несвязанный код быстрее или медленнее, подозревается кеширование.

~ Кейт Адамс «PHP на металле», слайды

Команда HHVM провела впечатляющее расследование, чтобы найти виновника: агрессивно встраиваемый memcpy. Размер кода функции memcpy на их платформе составлял 11 КБ, что приводило к перегрузке кеша. Этот код везде в программе вытеснил полезные данные из кэша ЦП.

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

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

Кстати, ключевое слово inline практически не имеет ничего общего с самим процессом встраивания.

Исправление от u / quicknir на Reddit:

[ключевое слово inline] фактически используется как подсказка в gcc и, возможно, других компиляторах. В O1 только функции, отмеченные как встроенные, рассматриваются для встраивания

2. Память, загрузка и хранение

Как было сказано, интерфейс компилятора генерирует код, как будто память бесконечна.

Для следующей функции:

LLVM производит этот неоптимизированный код:

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

Хотя оптимизированный код выглядит очень разумно:

Здесь сияет форма SSA. Оптимизатор просматривает загрузку и сохранение памяти и пытается найти фактические значения. В приведенном выше примере это делается легко.

Теперь давайте попробуем более сложный пример:

Неоптимизированный ИК:

Обратите внимание, что подпись функции была изменена. Новая подпись позволяет компилятору помещать аргументы в регистры.

Раньше: (Point * this, Point arg)

После: (Point * this, i64 arg.x, i64 arg.y)

В этом примере поток данных становится более сложным. Мы получаем доступ к нескольким ячейкам памяти, мы сохраняем промежуточные результаты в стеке, мы имеем дело с неявным указателем this.
LLVM пытается понять, что происходит, с разделением памяти. Он пытается восстановить отдельные соседние нагрузки и сохраняет обратно в структуры и массивы.

Посмотрим, как с этим справится оптимизатор.

LLVM IR с -O1:

Приведенная выше инструкция insertvalue вставляет значение в поле члена в массиве структурных значений. Он работает по индексу элемента аналогично getelementptr.

<result> = insertvalue <aggregate type> <val>, <ty> <elt>, <idx>{, <idx>}* ; yields <aggregate type>

В первый раз мы берем неопределенное {i64, i64} комплексное значение и вставляем %r.x в индекс 0:

%r_1 = insertvalue { i64, i64 } undef, i64 %r.x, 0

Затем мы создаем %r_2 из %r_1.

%r_2 = insertvalue { i64, i64 } %r_1, i64 %r.y, 1

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

В противном случае доступ к ОЗУ был бы буквально в 100 раз медленнее.

Самый быстрый код - тот, который не запускается.

3. Петли

Цикл - это то место, где программа проводит большую часть своего времени, и, естественно, именно циклы являются основными целями оптимизатора. Именно здесь в мире компиляторов ведется много исследований.

Давайте посмотрим на следующий цикл:

Всего существует около 160 строк неоптимизированного кода LLVM IR (не забывайте о тоннах выделения памяти, нескольких вызовах функций STL, коде времени выполнения C ++). Итак, в этом небольшом цикле происходит много всего.

Вот небольшой фрагмент неоптимизированного IR:

LLVM превращает эти 160 строк в почти 170 строк совершенно другого IR-кода. Мы подойдем к этому шаг за шагом.

Предполагая, что все вышеупомянутые методы оптимизации не работают, сворачивается память и абстракции функций. На этом этапе ИК-код функции sum может выглядеть так:

Опять же, есть каноническая форма. Оптимизатору очень важно отличать цикл от любого другого оператора потока управления.

Теперь у нас есть loop.ph - так называемый предварительный заголовок цикла и loop.exit узлы. Их цель - быть единственным и единственным входом и выходом из цикла. Метка loop имеет loop.ph и себя в качестве предшественников, а loop.exit имеет loop в качестве единственного предшественника.
Метка exit функции отличается, поскольку мы можем попасть туда, пропуская весь цикл.

loop.exit имеет этот необычный phi узел только с одним аргументом (строка 23):

%x.lcssa = phi i32 [ %x.next, %loop ]

Это форма SSA, позволяющая сказать, что x.next живет вне цикла. Таким образом, можно было взять значение из цикла.

Это каноническая форма цикла. После его распознавания применяются несколько методов оптимизации.

Прежде всего оптимизатор пытается решить, нужен ли вообще цикл. Например, если оптимизатор может определить размер массива, произойдет развертывание цикла. Это то, в чем действительно хорош каждый компилятор C ++, поскольку форма SSA естественным образом облегчает распространение констант.

Второй класс оптимизаций имеет тенденцию выводить избыточные операции из цикла, и форма SSA позволяет это легко. Есть только одна loop.ph точка входа, а loop.exit - единственный выход. Оптимизатор отслеживает каждый phi узел, следовательно, он знает, что изменяется внутри и вне цикла. Программисту не нужно кэшировать vector.size() или аналогичные вызовы в локальную переменную - это не Python. Оптимизатор переместит весь ненужный код из тела цикла.

Другой метод связан с условиями перехода внутри цикла. Как правило, оптимизатор стремится не только перемещать условие за пределы цикла, но и создавать отдельные специализированные циклы для каждого случая.

После запуска вышеупомянутых методов код цикла становится чище и меньше, и именно здесь он оптимизируется для максимальной загрузки ЦП.

Современные процессоры имеют высокоэффективные конвейеры с одной командой и несколькими данными (SIMD). Следовательно, оптимизатор выполняет циклическую векторизацию - частный случай SIMD. В нашем примере с функцией sum это просто означает: выполнить одну и ту же инструкцию add несколько раз за итерацию.

Оптимизированный код может выглядеть несколько устрашающе. Прежде чем вы попытаетесь пройти через это, сделаем короткое вступление.

В этом коде есть три разных цикла:

1. loop.vec32 - это основной векторизованный цикл. Внутри этого цикла мы видим add nsw <4 x i32> - складываем два вектора по 4 32-битных целых числа в каждом (результат также является вектором <4 x i32>). Более того, этот цикл развернут, поэтому он перебирает 32 x 32-битных целых числа за итерацию. Конечно, в массиве должно быть 32 или более правильно выровненных элемента.
2. loop.vec8 - это векторизованный цикл меньшего размера, который работает с двумя <4 x i32> векторами - 8 x 32-битные целые числа.
3. loop.scalar - наш оригинальный цикл. Все, что он делает, это суммирует два 32-битных целых числа одно за другим add nsw i32. Этот цикл является запасным вариантом, когда в массиве меньше 8 элементов.

Трудно следовать арифметике размера массива - LLVM заменил дорогостоящие инструкции деления, такие как div или mod, на _80 _ / _ 81 _ / _ 82_, это работает, потому что правый операнд является степенью двойки. За исключением уловок с размером, код должен быть довольно простым.

Массив длиной 129 попадет в loop.vec32, затем попадет в loop.scalar, пропуская ветку loop.vec8; в то время как наличие 130 элементов заставит его поразить все ветви. Небольшой массив из 7 или менее элементов будет проходить только через loop.scalar.

В чем дело программиста

Под слоганом «не навреди» компилятор будет оптимизировать только для среднего случая. Вы должны знать конкретные пути кода и поток данных высокого уровня, которые необходимо настроить.

Сравнительный анализ - это сложно

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

Чем больше знаешь, тем лучше. Важно понимать свои инструменты и среду. Как работает профилировщик? Какие флаги компилятора повлияют на расследование? Что именно они делают? Как уменьшить шум оборудования и ОС? Что происходит внутри этого долгого системного вызова? Эффективны ли эти инструкции на этой модели ЦП? Измеряю ли я производительность пустого цикла?
У Чендлера Каррута есть еще один замечательный доклад по тестированию производительности и использованию профилировщика⁹ (я не могу не порекомендовать этого парня - это его хлеб с маслом, чтобы заставить наш код C и C ++ работать быстрее ).

Понимание кода сборки не помешает. Хорошо. Со временем болит меньше. Сайт Агнера Фога¹⁰ - отличная отправная точка для изучения оборудования и методов оптимизации на низком уровне.

Медианы, средние значения и 95-й процентиль часто практически ничего не значат; наоборот - они могут обернуть все полезные сигналы шумом. Интерпретация результатов тестов может быть сложной задачей. Узнай немного статистики и теорию эксперимента навсегда.

Контроль доступа к оперативной памяти

Если не выполняются очень интенсивные вычисления с использованием ЦП, узким местом становится загрузка и сохранение памяти.

Проблема сложная, и есть на что обратить внимание.

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

«Что должен знать каждый программист о памяти» Ульриха Дреппера ² - это то, что вам нужно прочитать, если вы заботитесь о производительности.

Последовательный доступ к ОЗУ намного лучше случайного

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

Алгоритм криптовалюты CryptoNote пытается обеспечить защиту от аппаратных майнеров (ASIC), используя большой кусок памяти, доступ к которому должен осуществляться случайным образом.
Случайный доступ к памяти во многих отношениях вредит параллельному выполнению.

Выравнивание данных

Некоторые процессоры заставили нас поверить в существование такого понятия, как невыровненный доступ. Иногда нам даже повезло, что мы не снизили производительность (если мы не коснемся границ строк кэша ЦП).
Несмотря на то, что простые операции чтения и записи могут выполняться без проблем на процессорах на базе x86, для инструкций Atomics и SIMD требуется строгое согласование данных. Невыровненный доступ к памяти вызовет аппаратную панику на большинстве процессоров ARM.

Какой-то код сериализации / десериализации является распространенным источником несовпадающих данных.

Кеши ЦП

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

Простое практическое правило (с точки зрения производительности): то, что часто используется вместе, должно храниться вместе.

Рассмотрим следующий пример.
Представьте, что мы хотим найти некоторые элементы на основе их битовой маски. Что-то вроде этого:

Здесь мы прокачиваем каждый элемент (32+ байта) через кеши ЦП, просто чтобы стереть данные из кешей и выбросить их на следующей итерации. Но мы можем использовать кеш намного лучше, перетасовывая области памяти.

Давайте удалим int mask из структуры Foo и переместим все маски в отдельный массив:

Таким образом, кеш-память ЦП не расходуется на бесполезный (в нашем случае) value1, value2, …, а компилятор превратит тело цикла: foomasks[i] & needle в векторизованный код, который одновременно обрабатывает несколько масок.
Такая оптимизация может дать существенное улучшение. . (При условии, что количество элементов велико, а избирательность по маске низкая).

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

Запись в память в обход кешей ЦП

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

Семейство встроенных функций _mm_stream_siXXX создает нагрузки с использованием вневременной подсказки в памяти.

Предварительная выборка данных из памяти

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

Один из способов предварительной выборки данных - выполнить встроенную инструкцию компилятора, например __builtin_prefetch в GCC или _mm_prefetch из заголовка xmmintrin.h.

Другой способ - начать чтение желаемых данных из другого потока.

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

Прогноз ветвления

Темы доступа к памяти и прогнозирования ветвлений сильно взаимосвязаны. Одна вещь, которая может пригодиться, - это указать компилятору на определенную вероятность перехода. Это можно сделать с помощью известного макроса likely/unlikely (GCC __builtin_expect) или лучше, с помощью оптимизации на основе профиля.

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

Однако по моему опыту, это не дает значительного улучшения производительности. Такую оптимизацию следует рассматривать как последнее средство для получения небольшого общего прироста.

Посмотрите на счетчики производительности процессора

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

Инструмент perf и OProfile в Linux позволяют получить доступ к аппаратным счетчикам производительности, Xcode может делать это на Mac, и есть множество инструментов от поставщиков процессоров, например, Intel® Performance Counter Monitor.

Сделайте ваши намерения видимыми для компилятора

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

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

Давайте возьмем нашу sum функцию из примера с циклами и вызовем ее с постоянным значением:

LLVM IR (-O2):

Вся программа была выполнена во время компиляции. Все, что std::__XZZF_you_re_sick_of_this_cr*p_::__iterator__Stable_v1_XYZ_operator ушло. Распределение кучи Vector через std::allocator вызовов пропало - осталось return 10.

Я не думаю, что этот пример справедливый - форма SSA упрощает постоянное распространение, но я считаю, что это очень впечатляюще.

Передача аргументов по ссылке (указателю) может иметь скрытые затраты

Этот код может затруднить оптимизатору. Теперь решение: «вставлять ли foo» зависит от доступа к памяти (зависимость данных) и от функции bar (зависимость кода).

Но const…

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

Представьте себе такие ситуации:

… Или указатель на приведение указателя, или уловки с массивом, или целочисленные переполнения, или переполнения буфера. Не говоря уже о скучном const_cast, есть бесконечные возможности создать псевдоним одной и той же области памяти в C и C ++, намеренно или случайно.

Вторая мысль - это параллелизм. Если общих данных нет, то и блокировать нечего. Современные многоядерные процессоры могут выполнять высокопараллельное выполнение, и нет необходимости тратить драгоценные циклы на блокировки (вместо этого мы предпочитаем майнить криптовалюту).

Во многих случаях возврат аргументов вместо их передачи по ссылке позволяет компилятору видеть поток данных и создавать более эффективный код.

Не используйте элементы структуры для хранения промежуточных результатов

Это еще один способ усложнить работу оптимизатора:

Теперь оптимизатору нужно подумать о this указателе и рассудить, есть ли побочные эффекты. Людям также будет сложно прочитать такой код.

Чистые функции намного легче читать как людям, так и компиляторам.

Примите современный стандарт C / C ++

Стандарты C ++ 11 и более новые обеспечивают семантику перемещения и оптимизацию возвращаемого значения (RVO).

И C, и C ++ имеют слишком много случаев, когда поведение наших программ зависит от внутренней реализации компилятора. Современные стандарты стараются убрать эти темные углы и минимизировать возможные повреждения от УБ.

Кроме того, новые компиляторы предоставляют дополнительные инструменты, такие как линтеры, средства проверки, средства форматирования и т. Д.

Не выполняйте работу компилятора

Попытайтесь обнаружить ошибку в этом развернутом вручную цикле:

Приведенный выше пример взят из замечательной статьи команды статического анализатора PVS-Studio. ³

Строка 14: осталось a[1] от копирования и вставки, где должно быть a[5].

Опять же, разворачивание цикла - это то, с чем компиляторы C и C ++ могут справиться без какой-либо помощи программиста.

Исключения на современных процессорах имеют практически нулевые накладные расходы

Важно отметить, что «нулевые накладные расходы» не означают нулевых затрат - конечно, использование чего-либо всегда влечет за собой определенные затраты. Скорее, принцип нулевых накладных расходов C ++ всегда означал, что (а) «вы не платите за то, что не используете» и (б) «когда вы все же используете это, вы не можете [разумно] написать это более эффективно, рука."

~ Херб Саттер «Детерминированные исключения с нулевыми накладными расходами: большие значения» ¹⁵

Конечно, [близкие к] нулю накладные расходы случаются только для счастливого пути. ЦП должен выполнять финализаторы кадра и перемещаться по стеку, вызывая кучу промахов в кэше, перетасовку TLB и т. Д. При возникновении исключения.

В любом случае вы бы не стали имитировать сопоставление шаблонов с исключениями, не так ли?

Исправление от u / matthieum на Reddit

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

Александр Крижановский на Facebook предоставил ссылку¹⁶ на статью « Внутренние устройства обработки исключений C ++ » - подробное объяснение того, как исключения обрабатываются библиотекой времени выполнения C ++.

Используйте как можно больше дезинфицирующих средств и статических анализаторов

Это не совет по производительности, но поскольку вы здесь:

Самое важное, что я сделал как программист в последние годы, - это активно заниматься статическим анализом кода.

~ Джон Кармак из книги «Углубленный анализ статического кода» на Gamasutra¹⁴

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

Компилятор - это еще одна программа

Оптимизирующие компиляторы настолько сложны, что мы осмеливаемся сказать, что ни один оптимизирующий компилятор не был бы полностью безошибочным!

~ Ахо, Лам, Сетхи, Уллман в компиляторах: принципы, методы и инструменты, 2-е издание

Вся наша отрасль несовершенна. Черт возьми, мы все ужасны.

Обязательная ссылка на xkcd:

Оптимизирующий компилятор наверняка может иметь некоторые ошибки; он может, например, выбросить связанный с безопасностью код, потому что он не используется явно; Компилятор даже может сам внести новую уязвимость.

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

TL;DR

• Сложность программных систем набирает обороты
• Оборудование становится более сложным и разнообразным
• ЦП быстрый и сложный; DRAM медленный и дешевый
• Мы должны делегировать наиболее низкоуровневую оптимизацию ЦП компилятору и сосредоточиться на потоке данных программы и создании удобочитаемого кода.
• Понимание производительности также означает понимание оптимизирующего компилятора.
• Современные оптимизирующие компиляторы - очень способные звери, но все же далеки от идеала
• Оптимизация структуры памяти и схем доступа окупается хорошо
• Локальная оптимизация иногда может показывать потрясающие результаты на микротестах, снижая при этом общую производительность приложения.

Если вы хотите поиграть с LLVM

На GitHub есть Makefile Voodoo
Если вы когда-нибудь хотели перевести фрагмент C / C ++ в LLVM IR и списки ассемблера - просто поместите файл '.c' или '.cpp' в этот каталог и запустить make. Он должен создавать списки ".ll" и ".asm" для каждого уровня оптимизации: -O0 ..- O3 -Os

На Mac с установленными инструментами Xcode и командной строки он должен работать мгновенно. Наверное.

использованная литература

1: Hacker News: нейронная сеть обнаружена глубоко внутри кремниевого мозга Samsung Galaxy S7

2: « Полупроводниковая память в Википедии»

3: Цифры задержки, которые должен знать каждый программист

4: Оптимизация программного обеспечения на C ++: руководство по оптимизации для платформ Windows, Linux и Mac от Агнера Фога (pdf)

5: YouTube: Общие сведения об оптимизации компилятора - Чендлер Каррут - Открытие ключевой конференции C ++ 2015

6: Понимание оптимизации компилятора - Чендлер Каррут - Слайды вступительного выступления по C ++ 2015 (pdf)

7: Википедия: SSA - Статическая форма однократного назначения

8: PHP на слайдах из металла. Автор Кейт Адамс

9: YouTube: CppCon 2015: Чендлер Каррут« Настройка C ++: тесты, процессоры и компиляторы! О боже! »»

10: Ресурсы по оптимизации программного обеспечения от Агнера Фога

11: Ваш генератор нагрузки, вероятно, лжет вам - примите красную таблетку и узнайте, почему

12: Что каждый программист должен знать о памяти, часть 1.

13: PVS-Studio –– Главный вопрос программирования, рефакторинга и всего остального

14: Подробно: статический анализ кода на Gamasutra

15: Детерминированные исключения с нулевыми накладными расходами: выброс значений от Херба Саттера

16: Внутреннее устройство обработки исключений C ++ от Николаса Браиловского