Какие методы кодирования вы используете для оптимизации программ на C?

Question

Несколько лет назад я был на панели, которая проводила собеседование с кандидатами на относительно старшую позицию программиста C.

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

Итак, в интересах составления списка для потомков - какие методы и конструкции вы обычно используете при оптимизации программ на С?

Ответы на оптимизацию для скорости и размера как принято.

Answer 1

Сбор профилей выполнения кода дает вам 50% пути оттуда. Другие 50% занимаются анализом этих отчетов.

Кроме того, если вы используете GCC или VisualC++, вы можете использовать «оптимизацию с учетом профиля», где компилятор будет получать информацию от предыдущих исполнений и переназначать инструкции, чтобы сделать процессор более счастливым.

Answer 2

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

Answer 3

наиболее распространенные методы я столкнулся являются:

• петля разворачивая оптимизации
• петли для лучшего кэш предвыборкой (т.е. сделать N операций в M циклов вместо NxM особых операций)
• данных совместив
• встроенные функции
• ручные отрывки из соображений безопасности

Что касается общих рекомендаций, большинство из них уже озвучивали:

• выбирать более Algos
• использование профилировщика
• не оптимизировать, если он не дает 20-30% прирост производительности

Answer 4

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

Answer 5

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

Answer 6

Для оптимизации низкого уровня:

1. START_TIMER/STOP_TIMER макросы из FFmpeg (точность синхронизации уровня для измерения любого кода).
2. Oprofile, конечно, для профилирования.
3. Огромное количество ручной сборки (просто сделайте wc -l в каталоге x264/common/x86, а затем запомните большую часть кода).
4. Тщательное кодирование в целом; более короткий код обычно лучше.
5. Умные низкоуровневые алгоритмы, такие как 64-разрядный писатель битового потока, который я написал, который использует только один, если и не больше.
6. Explicit write-combining.
7. Принимая во внимание важные странные аспекты процессоров, например Intel's cacheline split issue.
8. Поиск случаев, когда можно без потерь или почти без потерь сделать раннее завершение, когда проверка раннего прекращения стоит намного меньше, чем скорость, которую он получает от нее.
9. На самом деле встроенная сборка для задач, которые намного больше подходят для SIM-блока x86, таких как медианные вычисления (требуется проверка времени компиляции для поддержки MMX).

Answer 7

Предварительно зрелая оптимизация - это корень всех злых! ;)

Answer 8

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

char buf[1024] = { 0, }; 
/* becomes: */ 
char buf[1024]; 
memset(buf, 0, sizeof(buf)); 

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

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

PS: Пожалуйста, сообщите нам, когда ваш список будет закончен, мне очень любопытно. ;)

Answer 9

Другое дело, что не было упомянуто:

• Знайте свои требования: не оптимизировать для ситуаций, которые вряд ли или не произойдет, сосредоточиться на наиболее взрыва на дыбы

Answer 10

Встроенные функции! Вдохновленный профилирующими вентиляторами здесь я профилировал мое приложение и обнаружил небольшую функцию, которая немного ускоряет работу с MP3-фреймами. Это составляет около 90% всех вызовов функций в моем приложении, поэтому я сделал это inline и voila - теперь программа использует половину процессорного времени, которое она делала раньше.

Answer 11

Прежде всего, не оптимизируйте слишком рано. Это не редкость тратить время на тщательную оптимизацию куска кода только для того, чтобы найти, что это не было узким местом, которое, по вашему мнению, было. Или, говоря иначе: «Прежде чем вы начнете быстро, заставьте его работать»

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

И выясните, почему вам нужно оптимизировать в первую очередь. Чего вы пытаетесь достичь? Если вы пытаетесь, скажем, улучшить время отклика на какое-то событие, если есть возможность изменить порядок выполнения, чтобы свести к минимуму критические области времени. Например, когда вы пытаетесь улучшить ответ на какое-либо внешнее прерывание, можете ли вы сделать какую-либо подготовку в мертвое время между событиями?

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

Итак, что вы можете сделать в этих областях?

• свести к минимуму проверку состояния. Условия проверки (например, условия завершения циклов) - это время, которое не расходуется на фактическую обработку. Проверка состояния может быть сведена к минимуму с помощью таких методов, как циклическое разворачивание.
• В некоторых случаях проверка условий также может быть устранена с помощью указателей функций. Например, если вы используете конечный автомат, вы можете обнаружить, что внедрение обработчиков для отдельных состояний в виде небольших функций (с однородным прототипом) и сохранение «следующего состояния» путем хранения указателя функции следующего обработчика более эффективно, чем использование большой оператор switch с кодом обработчика, реализованным в отдельных случаях. YMMV.
• минимизировать вызовы функций. Функциональные вызовы обычно несут нагрузку на сохранение контекста (например, запись локальных переменных, содержащихся в регистрах в стек, сохранение указателя стека), поэтому, если вам не нужно делать вызов, это время сохраняется. Один из вариантов (если вы оптимизируете скорость, а не пространство) - использовать встроенные функции.
• Если вызовы функций неизбежны, минимизируйте данные, передаваемые этим функциям. Например, пропущенные указатели, вероятно, будут более эффективными, чем передача структур.
• При оптимизации скорости выберите типы данных, которые являются родным для вашей платформы. Например, на 32-битном процессоре, вероятно, будет более эффективно управлять 32-битными значениями, чем 8 или 16-битные значения. (обратите внимание - стоит проверить, что компилятор делает то, что, по вашему мнению, есть. У меня были ситуации, когда я обнаружил, что мой компилятор настаивал на выполнении 16-разрядной арифметики на 8-битных значениях со всеми преобразованиями и от конверсий поехать с ними)
• Найдите данные, которые могут быть предварительно рассчитаны, и либо вычислить во время инициализации, либо (еще лучше) во время компиляции. Например, при реализации CRC вы можете либо вычислить свои значения CRC «на лету» (с использованием полинома напрямую), что отлично подходит для размера (но ужасно для производительности), либо вы можете создать таблицу всех промежуточных значений - намного быстрее, в ущерб размеру.
• Локализовать данные. Если вы манипулируете блобом данных, часто ваш процессор может ускорить процесс, сохраняя все это в кеше. И ваш компилятор может использовать более короткие инструкции, которые подходят для более локализованных данных (например, инструкции, которые используют битовые смещения вместо 32 бит).
• В том же духе локализовать ваши функции. По тем же причинам.
• Выполните предположения, которые вы можете сделать о выполняемых вами операциях, и найдите способы их использования. Например, на 8-битной платформе, если единственная операция, которую вы делаете с 32-битным значением, является шагом, вы можете обнаружить, что вы можете сделать лучше, чем компилятор, путем вложения (или создания макроса) специально для этой цели, вместо использования обычной арифметической операции.
• Избегайте дорогостоящих инструкций - деление является ярким примером.
• Ключевое слово "register" может быть вашим другом (хотя, надеюсь, ваш компилятор имеет довольно хорошее представление об использовании вашего регистра).Если вы собираетесь использовать «register», вероятно, вам придется объявить локальные переменные, которые вы хотите «зарегистрировать» в первую очередь.
• Будьте совместимы с вашими типами данных. Если вы делаете арифметику на смеси типов данных (например, шорты и ints, удваиваете и плаваете), то компилятор добавляет неявные преобразования типов для каждого несоответствия. Это потраченные впустую циклы процессора, которые могут не понадобиться.

Большинство вариантов, перечисленных выше, могут использоваться как часть обычной практики без каких-либо негативных последствий. Однако, если вы действительно пытаетесь добиться максимальной производительности: - Исследуйте, где вы можете (безопасно) отключить проверку ошибок. Это не рекомендуется, но это сэкономит вам пространство и циклы. - Ручная часть вашего кода в ассемблере. Это, конечно, означает, что ваш код больше не переносится, но там, где это не проблема, вы можете найти сбережения здесь. Имейте в виду, что есть потенциально потерянное время для перемещения данных в регистры и из них, которые у вас имеются (т. Е. Для удовлетворения использования вашего компилятора в регистре). Также имейте в виду, что ваш компилятор должен выполнять очень хорошую работу самостоятельно. (конечно, есть исключения)

Answer 12

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

Первое правило в оптимизации скорости - найти свой критический путь.
Обычно вы обнаружите, что этот путь не так длинный и не такой сложный. Трудно сказать в общих чертах, как оптимизировать это, это зависит от того, что вы делаете и что вам нужно. Например, вы обычно избегаете memcpy по критическому пути, поэтому когда-либо вам нужно использовать DMA или оптимизировать, но что делать, если у вас нет DMA? проверьте, является ли реализация memcpy лучшей, если не переписать ее.
Не используйте динамическое размещение вообще во встроенных, но если вы по какой-то причине не делаете этого в критическом пути.
Правильно распределите приоритеты своей нити, что является правильным вопросом, и это явно зависит от конкретной системы.
Мы используем очень простые инструменты для анализа бутылочных шеек, простого макроса, который хранит отметку времени и индекс. Немногие (2-3) пробежки в 90% случаев найдут, где вы проводите время.
И последний Код код очень важный. В большинстве случаев мы избегаем проблемы производительности во время просмотра исходного кода очень эффективным способом :)

Answer 13

основы/общее:

• Не оптимизировать, когда у вас нет никаких проблем.
• Знать свою платформу/CPU ...
• ... знаю, что это тщательно
• знать ваш ABI
• Пусть компилятор делать оптимизацию, просто помочь ему с работой.

некоторые вещи, которые на самом деле помогли:

Opt для размера/памяти:

• Используйте битовые для хранения BOOLS
• повторного использования больших глобальных массивов путем накладывания с профсоюзом (быть осторожны)

Opt для скорости (осторожно):

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

Answer 14

Трудно Подводя итог ...

• структуры данных:

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

• Алгоритмов:

  • времени Тека думать о вашей проблеме и найти правильный алгоритм.
  • Знайте ограничения алгоритма, который вы выбрали (сортировка по методу radix-sort/quick-sort для 10 элементов, которые нужно отсортировать, может быть не лучшим выбором).

• Низкий уровень:

  • Что касается последних процессоров не рекомендуется раскатать цикл, который имеет маленькое тело. Процессор обеспечивает свой собственный механизм обнаружения для этого и будет замыкаться на весь участок его конвейера.
  • Доверьтесь HW prefetcher. Разумеется, если ваши структуры данных хорошо разработаны;)
  • Уход за вашей пропущеной линией кэша L2.
  • Постарайтесь уменьшить как можно больше локальный рабочий набор вашего приложения, поскольку процессоры склоняются к меньшим кэшам на каждый сердечник (C2D пользовался максимальным объемом 3 МБ на каждый ядро, где iCore7 обеспечит максимум 256 КБ на ядро ​​+ 8 МБ, общий для всех сердечники для четырехъядерного кристалла.).

Самое главное: Измерить рано, Измерить часто и никогда никогда не делает предположений, основывать свое мышление и оптимизацию на данных, полученных с помощью профилировщика (пожалуйста, используйте PTU).

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

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

Answer 15

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

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

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

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

Мои основные инструменты для ускорения кода являются:

Хеш - для быстрого поиска и для кэширования результатов

QSort - это единственный вид, я использую

БСП - для поиска вещей, основанный на площади (отображение карты и т. д.)

Answer 16

1. Измерение производительности.
2. Используйте реалистичные и нетривиальные ориентиры. Помните, что "everything is fast for small N".
3. Используйте профайлер, чтобы найти горячие точки.
4. Уменьшение количества распределений динамической памяти, доступа к диску, доступа к базе данных, доступа к сети и переходов пользователя/ядра, поскольку они часто имеют тенденцию быть горячими точками.
5. Измерение производительности.

Кроме того, вы должны измерить производительность.

Answer 17

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

Например, если это возможно, написать

for (i=n; i!=0; --i) { ... } 

вместо

for (i=0; i!=n; ++i) { ... } 

Answer 18

Как и все остальные сказал: профиль, профиль профиль.

Что касается реальных методов, один, что я не думаю, было упомянуто еще:

Горячая & Холодная Разделение данных: Оставаясь в кэше процессора является невероятно важно. Одним из способов помочь это можно, разбив ваши структуры данных на часто посещаемые («горячие») и редко доступные («холодные») разделы.

Пример: Предположим, что у вас есть структура для клиента, который выглядит примерно так:

struct Customer 
{ 
    int ID; 
    int AccountNumber; 
    char Name[128]; 
    char Address[256]; 
}; 

Customer customers[1000]; 

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

struct CustomerAccount 
{ 
    int ID; 
    int AccountNumber; 
    CustomerData *pData; 
}; 

struct CustomerData 
{ 
    char Name[128]; 
    char Address[256]; 
}; 

CustomerAccount customers[1000]; 

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

Answer 19

Иногда вам приходится решать, будет ли вам больше пространства или больше скорости, что приведет к почти противоположным оптимизации. Например, чтобы получить максимальную отдачу от вас, вы создаете структуры pack. #pragma pack (1) и использовать bit fields в строениях. Для большей скорости вы устанавливаете для согласования с предпочтениями процессоров и избегаете битполей.

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

Answer 20

В эти дни, самые важные вещи в optimzation являются:

• уважая кэш - попытаться получить доступ к памяти в простых моделей, а не раскатывать петли просто для удовольствия. Используйте массивы вместо структур данных с большим количеством преследователей указателей, и это, вероятно, будет быстрее для небольших объемов данных. И не делайте ничего слишком большого.
• избегая латентности - старайтесь избегать делений и вещей, которые медленны, если другие вычисления зависят от них немедленно. Доступ к памяти, зависящий от других обращений к памяти (т. Е. [B [c]]) является плохим.
• избегая непредсказуемости - много случаев, когда непредсказуемые условия или условия, которые приводят к большей задержке, действительно повредят вам. Здесь много полезных математических трюков, но они увеличивают задержку и полезны только в том случае, если они вам действительно нужны. В противном случае просто напишите простой код и не получите сумасшедших условий цикла.

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

Answer 21

Если у кого-то нет ответа на этот вопрос, возможно, они мало знают.

Возможно также, что они знают много. Я много знаю (ИМХО :-), и если бы меня задали этот вопрос, я бы хотел спросить вас: почему вы думаете, что это важно?

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

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

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

Чтобы предоставить конкретный пример, this is a C application that was optimized.

Answer 22

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

• перепускной линкер

  , если у вас есть какое-то приложение делится на два файла, скажем main.c и lib.c, во многих случаях вы можете просто добавить \#include "lib.c" в вашем main.c Это будет полностью шунтирования компоновщик и позволяют гораздо более эффективную оптимизацию для компилятора.

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

Answer 23

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