Список распространенных методов оптимизации на C ++

Могу ли я иметь большой список общих методов оптимизации на C ++?

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

Два способа писать лучшие программы:

Лучше всего использовать язык

  1. Код Завершить Стив Макконнелл
  2. Эффективный C ++
  3. Исключительный C ++

профайл приложения

  1. Определите, какие области кода занимают сколько времени
  2. Посмотрите, можете ли вы использовать лучшие структуры данных / алгоритмы, чтобы ускорить работу

Существует не так много языковой оптимизации, которую можно сделать – она ​​ограничена использованием языковых конструкций (учитесь на # 1). Основное преимущество исходит от № 2 выше.

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

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

void FlipBuffer(unsigned char *start, unsigned char *end) { unsigned char temp; while (start <= end) { temp = _bitRev[*start]; *start++ = _bitRev[*end]; *end-- = temp; } } 

который вращает 1-битный буфер кадра на 180 gradleусов. _bitRev - таблица с 256 байтами обратных бит. Этот код примерно такой же жесткий, как вы можете его получить. Он работал на 8-мегагерцовом controllerе лазерного принтера 68 тыс. И занимал примерно 2,5 секунды для бумаги с ограниченным размером бумаги. Чтобы избавить вас от деталей, клиент не мог выдержать 2,5 секунды. Решение было таким же алгоритмом. Разница заключалась в том, что

  1. Я использовал таблицу 128K и работал на словах вместо байтов (68K намного счастливее слов)
  2. Я использовал устройство Даффа, чтобы развернуть цикл так же сильно, как и в короткой ветви
  3. Я включил оптимизацию, чтобы пропустить пустые слова
  4. Я, наконец, переписал его в сборке, чтобы воспользоваться инструкцией sobgtr (вычесть один и разветвить на большее) и иметь «свободный» шаг приращения и предварительные декременты в правильных местах.

Итак, 5x: алгоритм не меняется.

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

Не забывайте о нескольких вещах:
– «Мы должны забыть о небольшой эффективности, скажем, около 97% времени: преждевременная оптимизация – корень всего зла». (c) Дональд Кнут
– Мы могли бы получить больше, если мы будем оптимизировать алгоритмы, чем код.
– Мы будем оптимизировать только медленные части существующего кода, которые будут обнаружены профилировщиком или другим специальным инструментом.

Agner Fog проделал большую работу, анализируя вывод нескольких компиляторов относительно конструкций C ++. Вы найдете его работу здесь: http://www.agner.org/optimize/ .

Intel предлагает отличный документ – «Справочное руководство по оптимизации архитектуры Intel® 64 и IA-32», которое вы найдете на http://www.intel.com/products/processor/manuals/index.htm . Хотя он в основном предназначен для архитектур IA-32, он содержит общие рекомендации, которые могут применяться на большинстве платформ. Очевидно, что это и гид Агнера Фога немного пересекаются.

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

Вам может быть интересно: Оптимизация C ++ Wikibook

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

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

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

Классическим примером программного обеспечения является SGI Indy Irix 5.1 , отчасти потому, что у пользователей с интенсивной графикой теперь есть компьютеры Mac и Windows, а не SGI.

«Самое страшное в производительности 5.1 – это то, что никто не знает, где именно. Если вы начнете спрашивать, вы получите много указаний на пальцы и теории, но мало фактов. В майском докладе я предложил« теорию 5% », , в котором говорится, что каждая добавленная мелочь (Motif, интернационализация, drag and drop, DSO, несколько шрифтов и т. д.) стоит примерно 5% от машины. После 15 или 20 из них большая часть производительности ушла «.

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

Вы спрашивали сайты / источники, содержащие оптимизацию.

Некоторые хорошие были предложены.

Могу добавить, что почти все говорят, что профилирование – лучший, если не единственный способ найти проблемы с производительностью.

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

ДОБАВЛЕНО:

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

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

То, что кажется невиновным методом однострочного вызова для абстрактных объектов, заставляет вас забыть, что этот вызов может стоить вам. Умножьте эту тенденцию на несколько уровней абстракции, и вы найдете такие вещи, как, например, тратите все свое время на распределение и сбор таких вещей, как iteratorы и classы коллекций, когда простые массивы с индексацией были бы достаточными (и не менее поддерживаемыми), но менее «правильными» ».

Это проблема с «общей мудростью». Это часто противоположно мудрости.

Большинство методов являются специфическими для компилятора , поскольку разные компиляторы оптимизируют по-разному.

Если вы хотите, чтобы некоторые советы по оптимизации были агностически компиляторами, вот два для вас:

  1. Не делай этого.
  2. (только для экспертов!): Не делайте этого еще.

(извинения Майклу А. jacksonу )

++ p обычно быстрее, чем p ++, а -p – быстрее, чем p–, особенно для объектов типов с перегруженными префиксами и постфиксными приращениями и декрементами, поскольку форма префикса просто увеличивает или уменьшает что-то и возвращает новое значение, тогда как постфиксная форма увеличивает или уменьшает что-то, но для того, чтобы вернуть ее, нужно сохранить прежнее значение. То есть вместо (замените int вашим любимым classом здесь)

 for ( int i ( 0); i < x; i++) 

всегда писать

 for ( int i ( 0); i < x; ++i) 
  1. Профилируйте свой код, чтобы узнать, что на самом деле занимает больше всего времени
  2. Убедитесь, что вы используете правильный алгоритм
  3. Если вы делаете много хрустких чисел, будьте дружелюбны с вашим кешем и старайтесь делать все возможное на куске данных сразу, поэтому его не нужно многократно загружать в кеш.

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

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

Единственный оптимизационный совет по C ++, о котором я могу думать, это «понять, что означает ваш код». Поймите, когда C ++ копирует временные ряды, понимает, какие конструкторы и деструкторы вызывается, когда.

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

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

Изменить : комментарий о том, что функторы против указателей функций являются встроенными. Вот объяснение:

Функции обычно компилируются изолированно. Итак, что компилятор знает о функции F, которая принимает указатель на функцию FP в качестве аргумента? Ничего, он должен искать, где вызвано F, и, возможно, там он может найти определенный ключ относительно того, на что указывает FP. Если он сможет определить, что при вызове отсюда FP ВСЕГДА укажет на функцию G, то да, она может сделать встроенную версию F с встроенным внутри нее для этого конкретного сайта вызова. Но он не может просто встраивать G без наложения F, потому что F может быть вызван из других мест, где ему передается другой указатель на функцию. И даже тогда это требует некоторых дорогостоящих глобальных оптимизаций, чтобы определить, что все может быть встроено.

Представьте себе, что вы передаете такой функтор, как это:

 struct Ftor { void operator()() { ... } }; 

поэтому функция F выглядит так:

 void F(const FTor& ft) { ... ft(); ... } 

теперь компилятор точно знает, какая функция вызывается: строка 2 в функции вызывает функцию Ftor :: operator (). И поэтому вызов может быть легко встроен.

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

 template  void F(const F& ft) { ... ft(); ... } 

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

У меня была довольно большая std :: map, которую я генерировал с использованием объекта Microsoft CString в качестве ключа. Производительность была неприемлемой. Поскольку все мои строки были одинаковыми по длине, я создал оболочку classа вокруг старомодного массива символов фиксированного размера, чтобы эмулировать интерфейс CString. К сожалению, я не помню точного ускорения, но это было значительным, и итоговая производительность была более чем достаточной.

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

Template Meta-Programming может использоваться для перехода от динамического polymorphismа к компиляции временного polymorphismа, создавая безумно оптимальный код в процессе. Современная C ++ Design от Alexandrescu – это хорошая книга, которая подробно описывает TMP. Не каждая страница посвящена оптимизации, но это часто повторяющееся рассмотрение в программах.

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

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

Я имею в виду (как идею), если вы получите 30% -ное улучшение производительности, выбрав немного лучший алгоритм (или class коллекции / контейнера), улучшение, которое вы можете ожидать от рефакторинга, связанного с C ++, будет не более 2%. Улучшение дизайна может дать вам что-то более 30%.

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

Вот пара поймать все пути для оптимизации.

Нет никакого способа решения проблем с оптимизацией … они всегда настроены вручную на аппаратное / программное обеспечение / системные соображения.


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

  1. компилировать с помощью «show assembly output» и «максимальной оптимизации»,
  2. посмотрите на сборку
  3. идентифицировать неэффективность, которая разрушает оптимизацию компилятора или плохое кэширование
  4. Перекодируйте fragment
  5. если он все еще плохой цикл возвращается к 2.
  6. сделанный

Пример здесь: Каков самый быстрый способ обмена значениями в C?


Общие советы:

http://www.ceet.niu.edu/faculty/kuo/exp/exp6/figuree6-1.jpg :

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

http://sofru.miximages.com/c%2B%2B/fig1.gif :

  • Проверьте, не является ли память или I / O OR CPU
  • Атака, которая когда-либо является ограничивающим фактором

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

Пара конкретных примеров:

  1. Использование структур массивов в отличие от массива структур (classический пример DOP и OOP)
  2. Использование ограничения в C ++, когда вы знаете, что два указателя не указывают на одно и то же место памяти

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

Подробнее здесь: https://people.cs.clemson.edu/~dhouse/courses/405/papers/optimize.pdf

  • Есть ли разница в производительности между i ++ и ++ i в C?
  • Как вы проверяете время работы кода VBA?
  • std :: vector reserve () и push_back () быстрее, чем resize () и индекс массива, почему?
  • Как увидеть, какие плагины делают Vim медленным?
  • Как рассчитать или аппроксимировать медиану списка без сохранения списка
  • Перетащить пакетный файл для нескольких файлов?
  • Когда, если когда-либо, цикл разворачивания по-прежнему полезен?
  • Практики кодирования, которые позволяют компилятору / оптимизатору выполнять более быструю программу
  • Читать файл As String
  • Могут ли какие-либо процессоры реального мира не использовать IEEE 754?
  • Смотрите и очистите кеши / буферы Postgres?
  • Interesting Posts

    Все в .NET является объектом?

    Как я могу эффективно выбрать контейнер стандартной библиотеки в C ++ 11?

    Как получить вертикальное разделение терминала на Mac для выполнения различных действий?

    Является ли выражение / start /, / end / range когда-либо полезным в awk?

    Как получить текущее время и дату на C ++?

    mysql DECLARE WHILE вне хранимой процедуры как?

    Учебники о javaagents

    BadImageFormatException. Это произойдет при работе в режиме 64 бит с установленными 32-битными клиентскими компонентами Oracle

    Как сервер может вызывать асинхронные изменения на HTML-странице, созданной JSF?

    Настройки Windows 10 не проиндексированы

    Как получить атрибут отображаемого имени члена Enum через код бритвы MVC?

    Телевизионные записи WTV и DVR-MS, следует ли я де-чередовать или нет?

    Как заставить валидацию зависеть от нажатой кнопки?

    Почему некорректная попытка пароля занимает намного больше времени, чем правильная?

    delete vs delete в C ++

    Давайте будем гением компьютера.