Несколько лет назад я был на панели, которая давала интервью кандидатам для относительно старшей позиции программиста C.
Один из стандартных вопросов, которые я задавал, касался методов оптимизации. Я был очень удивлен, что у некоторых кандидатов нет ответов.
Итак, в интересах составления списка для потомков - какие методы и конструкции вы обычно используете при оптимизации программ на С?
Ответы на оптимизацию для скорости и размера как принято.
Прежде всего, не оптимизируйте слишком рано. Это не редкость тратить время, тщательно оптимизируя кусок кода, только чтобы обнаружить, что это не было узким местом, которое, по вашему мнению, было. Или, говоря иначе: "Прежде чем вы сделаете это быстро, сделайте это"
Изучите, есть ли какой-либо вариант для оптимизации алгоритма перед оптимизацией кода. Будет легче найти улучшение производительности, оптимизируя плохой алгоритм, чем оптимизировать код, а затем выбросить его, когда вы все равно измените алгоритм.
И выясните, почему вам нужно оптимизировать в первую очередь. Чего вы пытаетесь достичь? Если вы пытаетесь, скажем, улучшить время отклика на какое-то событие, если есть возможность изменить порядок выполнения, чтобы свести к минимуму критические области времени. Например, если вы пытаетесь улучшить реакцию на какое-либо внешнее прерывание, можете ли вы сделать какую-либо подготовку в мертвое время между событиями?
Как только вы решили, что вам нужно оптимизировать код, какой бит вы оптимизируете? Используйте профилировщик. Сфокусируйте свое внимание (сначала) на наиболее часто используемых областях.
Итак, что вы можете сделать в этих областях?
Большинство вариантов, перечисленных выше, могут использоваться как часть обычной практики без каких-либо негативных последствий. Однако, если вы действительно пытаетесь добиться максимальной производительности: - Исследуйте, где вы можете (безопасно) отключить проверку ошибок. Это не рекомендуется, но это сэкономит вам пространство и циклы. - Поручите части вашего кода в ассемблере. Это, конечно, означает, что ваш код больше не переносится, но там, где это не проблема, вы можете найти экономию здесь. Имейте в виду, что есть потенциально потерянное время для перемещения данных в регистры и из них, которые у вас имеются (т.е. Для удовлетворения использования вашего компилятора в регистре). Также имейте в виду, что ваш компилятор должен выполнять довольно хорошую работу самостоятельно. (конечно, есть исключения)
Как говорили все остальные: профиль , профиль профиля.
Что касается реальных техник, то, о которых я не думаю, уже упоминалось:
Разделение горячих и холодных данных. Оставаться в кэше CPU невероятно важно. Один из способов помочь в этом - это разделить ваши структуры данных на часто используемые ( "горячий" ) и редко доступный ( "холодный" ) раздел.
Пример: предположим, что у вас есть структура для клиента, которая выглядит примерно так:
struct Customer
{
int ID;
int AccountNumber;
char Name[128];
char Address[256];
};
Customer customers[1000];
Теперь давайте предположим, что вы хотите получить доступ к ID и учетному номеру много, но не столько имя и адрес. Вы бы разделили его на две части:
struct CustomerAccount
{
int ID;
int AccountNumber;
CustomerData *pData;
};
strut CustomerData
{
char Name[128];
char Address[256];
}
CustomerAccount customers[1000];
Таким образом, когда вы перебираете свой "клиентский" массив, каждая запись составляет всего 12 байт, поэтому вы можете вставить еще много записей в кеш. Это может быть огромной победой, если вы можете применить ее к ситуациям, таким как внутренний цикл механизма рендеринга.
Моя любимая техника - использовать хороший профилировщик. Без хорошего профиля, рассказывающего вам, где находится узкое место, никакие трюки и приемы не помогут вам.
Наиболее распространенными методами, которые я встречал, являются:
Что касается общих рекомендаций, большинство из них уже озвучены:
Для оптимизации низкого уровня:
Поскольку моим приложениям обычно не требуется много процессорного времени по дизайну, я сосредотачиваюсь на размере моих двоичных файлов на диске и в памяти. То, что я делаю в основном, ищет массивы с статическим размером и заменяет их динамически распределенной памятью, где это стоит дополнительных усилий по освобождению памяти позже. Чтобы сократить размер двоичного файла, я ищу большие массивы, которые инициализируются во время компиляции и помещают инициализацию во время выполнения.
char buf[1024] = { 0, };
/* becomes: */
char buf[1024];
memset(buf, 0, sizeof(buf));
Это приведет к удалению 1024 нулевых байтов из секции .DATA и вместо этого создаст буфер в стеке во время выполнения и заполнит его нулями.
EDIT: О да, и мне нравится кэшировать вещи. Это не C, но в зависимости от того, что вы кешируете, это может дать вам огромный импульс производительности.
PS: Пожалуйста, сообщите нам, когда ваш список закончен, мне очень любопытно.;)
Избегайте использования кучи. Используйте устройства с препятствиями или пул-распределитель для объектов одинакового размера. Поместите мелкие вещи с коротким сроком службы на стек. alloca все еще существует.
Предварительно зрелая оптимизация - это корень всего зла! ;)
Если возможно, сравните с 0, а не с произвольными числами, особенно в циклах, потому что сравнение с 0 часто реализуется с помощью отдельных более быстрых команд ассемблера.
Например, если возможно, напишите
for (i=n; i!=0; --i) { ... }
вместо
for (i=0; i!=n; ++i) { ... }
Другая вещь, о которой не упоминалось:
Основа/общая:
некоторые вещи, которые действительно помогли:
Выберите размер/память:
Выбирайте скорость (будьте осторожны):
Трудно суммировать...
Структуры данных:
Алгоритмы:
Низкий уровень:
Самое важное: Мера рано, Мера часто и никогда не делает предположений, основывайте свое мышление и оптимизацию на данных, полученных профилировщиком (используйте PTU).
Еще один намек на то, что производительность является ключом к успеху приложения и должна учитываться во время разработки, и у вас должны быть четкие целевые показатели производительности.
Это далеко не исчерпывающий, но должен предоставить интересную базу.
В наши дни важнее всего оптимизировать:
Не беспокойтесь об оптимизации, которые включают в себя копирование и вставку кода (например, разворачивание цикла) или переупорядочение циклов вручную. Компилятор обычно делает лучше, чем вы, делая это, но большинство из них недостаточно умны, чтобы отменить его.
Сбор профилей исполнения кода дает вам 50% пути. Другие 50% занимаются анализом этих отчетов.
Кроме того, если вы используете GCC или VisualС++, вы можете использовать "оптимизацию с учетом профиля", где компилятор будет получать информацию от предыдущих исполнений и переназначать инструкции, чтобы сделать процессор более счастливым.
Встроенные функции! Вдохновленный профилирующими вентиляторами здесь я профилировал мое приложение и обнаружил небольшую функцию, которая немного ускоряет работу с MP3-фреймами. Это составляет около 90% всех вызовов функций в моем приложении, поэтому я сделал это inline и voila - теперь программа использует половину процессорного времени, которое она делала раньше.
На большинстве встроенных систем я работал, не было профилирующих инструментов, поэтому неплохо было бы использовать профилировщик, но не очень практичный.
Первое правило в оптимизации скорости - найти свой критический путь.
Обычно вы обнаружите, что этот путь не так длинный и не такой сложный. Трудно сказать в общих чертах, как оптимизировать это, это зависит от того, что вы делаете и что в ваших силах сделать. Например, вы обычно избегаете memcpy по критическому пути, поэтому когда-либо вам нужно использовать DMA или оптимизировать, но что делать, если у вас нет DMA? проверьте, является ли реализация memcpy лучшей, если не переписать ее.
Не используйте динамическое размещение вообще во встроенных, но если вы по какой-то причине не делаете этого в критическом пути.
Правильно упорядочивайте приоритеты своих потоков, что правильно - это реальный вопрос, и это явно зависит от конкретной системы.
Мы используем очень простые инструменты для анализа бутылочных шеек, простых макросов, которые хранят метку времени и индекс. Мало (2-3) работает в 90% случаев найдет, где вы проводите свое время.
И последнее - это обзор кода очень важный. В большинстве случаев мы очень часто избегаем проблем с производительностью при просмотре кода.
Кроме того, вы должны измерять производительность.
Иногда вам приходится решать, будет ли вам больше пространства или больше скорости, что приведет к почти противоположным оптимизации. Например, чтобы получить максимальную отдачу от вас, вы pack структуры, например. #pragma pack (1) и используйте битовые поля в структурах. Для большей скорости вы устанавливаете для согласования с предпочтениями процессоров и избегаете бит-полей.
Другим трюком является выбор правильных алгоритмов повторного калибровки для растущих массивов через realloc или, тем более, создание собственного менеджера кучи на основе вашего конкретного приложения. Не предполагайте, что тот, который поставляется вместе с компилятором, является наилучшим решением для каждого приложения.
Если у кого-то нет ответа на этот вопрос, возможно, они мало что знают.
Также может быть, что они знают много. Я много знаю (ИМХО:-), и если бы меня задали этот вопрос, я бы спросил вас: почему вы думаете, что важно?
Проблема заключается в том, что любые априорные представления о производительности, если они не сообщаются конкретной ситуацией, являются догадками по определению.
Я думаю, что важно знать методы кодирования для производительности, но я думаю, что еще важнее знать не использовать их, пока диагностика не покажет, что есть проблема и что это такое.
Теперь я собираюсь противоречить себе и сказать, если вы это сделаете, вы узнаете, как распознать проектные подходы, которые приводят к неприятностям, чтобы вы могли их избежать, и новичку, который звучит как преждевременная оптимизация.
Чтобы дать вам конкретный пример, это приложение C, которое было оптимизировано.
Отличные списки. Я просто добавлю один совет, который я не видел в приведенных выше списках, который в некоторых случаях может дать огромную оптимизацию для минимальных затрат.
объединительный компоновщик
Если у вас есть приложение, разделенное на два файла, скажем main.c и lib.c, во многих случаях вы можете просто добавить \#include "lib.c" в свой main.c. Это полностью обходит компоновщик и позволяет значительно повысить эффективность оптимизации для компилятора.
Такой же эффект может быть достигнут при оптимизации зависимостей между файлами, но стоимость изменений обычно выше.
Иногда Google - лучший инструмент для оптимизации алгоритмов. Когда у меня есть сложная проблема, немного поиска показывает, что некоторые ребята с PhD нашли сопоставление между этой и хорошо известной проблемой и уже выполнили большую часть работы.
Я бы рекомендовал оптимизировать использование более эффективных алгоритмов и не делать это как запоздалая мысль, но с самого начала кодировать ее так. Пусть компилятор детализирует мелкие вещи, поскольку он знает больше о целевом процессоре, чем вы.
Во-первых, я редко использую циклы для поиска вещей, добавляю элементы в хеш-таблицу, а затем использую хэш-таблицу для поиска результатов.
Например, у вас есть строка для поиска, а затем 50 возможных значений. Поэтому вместо того, чтобы делать 50 strcmps, вы добавляете все 50 строк в хэш-таблицу и даете каждому уникальный номер (вам нужно только сделать это один раз). Затем вы просматриваете целевую строку в хеш-таблице и имеете один большой переключатель со всеми 50 случаями (или имеют указатели на функции).
Когда вы просматриваете вещи с общими наборами ввода (например, css-правила), я использую быстрый код для отслеживания единственно возможных состязаний, а затем итерация думает, что они найдут совпадение. Как только у меня есть совпадение, я сохраняю результаты в хеш-таблице (как кеш), а затем использую результаты кеша, если позже получаю тот же самый ввод.
Мои главные инструменты для быстрого кода:
hashtable - для быстрого поиска и результатов кэширования
qsort - это единственный вид, который я использую
bsp - для поиска вещей на основе области (рендеринг карты и т.д.)