Эффективные стратегии оптимизации для современных компиляторов С++

Ответ 1

Есть ли какая-либо польза для замены контейнеров/алгоритмов STL ручными? В частности, моя программа включает в себя очень большую очередь приоритетов (в настоящее время std:: priority_queue), манипуляция которой занимает много времени. Является ли это чем-то стоящим в этом вопросе, или реализация STL, скорее всего, будет самой быстрой?

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

Некоторые контейнеры (например, map, set, list) полагаются на множество манипуляций с указателями. Хотя он несовместим, он часто может привести к более быстрому коду, чтобы заменить их на vector. Результирующий алгоритм может идти от O(1) или O(log n) до O(n), но из-за локальности кэша он может быть намного быстрее на практике. Профиль должен быть уверен.

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

В то же время для std::vectors, требуемые размеры которого неизвестны, но имеют достаточно небольшую верхнюю границу, выгодно ли их заменять статически распределенными массивами?

Опять же, это может помочь небольшая сумма, в зависимости от варианта использования. Вы можете избежать выделения кучи, но только если вам не нужен ваш массив, чтобы пережить стек... или вы могли бы reserve() размер в vector, поэтому при перераспределении меньше копий.

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

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

Насколько кэширующими являются компиляторы? Например, стоит ли искать переупорядочение вложенных циклов?

Я видел драматические (серьезно драматические) ускорения в этой области. Я видел больше улучшений от этого, чем позже увидел из многопоточности моего кода. Вещи, возможно, изменились за последние пять лет - только один способ убедиться - профиль.

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

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

• Помните о вызовах конструктора скрытых копий на больших объектах. В некоторых случаях рассмотрите возможность замены указателями.

• Профиль, профиль, профиль. Настройте области, которые являются узкими местами.

Ответ 2

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

Общий процесс:

• Научитесь любить просмотр дизассемблирования в своем отладчике или если ваша система сборки генерирует промежуточные файлы сборки (.s), если это вообще возможно. Следите за изменениями или для вещей, которые выглядят вопиющими - даже не знакомы с данной архитектурой набора инструкций, вы должны быть в состоянии увидеть некоторые вещи достаточно четко! (Иногда я просматриваю серию файлов .s с соответствующими изменениями .cpp/.c, просто чтобы использовать прекрасные инструменты из моего SCM, чтобы наблюдать за кодом и соответствующим изменением asm с течением времени.)
• Получить профилировщик, который может смотреть ваши счетчики производительности процессора, или, по крайней мере, догадываться о пропущенных кешах. (AMD CodeAnalyst, cachegrind, vTune и т.д.).

Некоторые другие специфические вещи:

• Поймите строгий псевдоним. Как только вы это сделаете, используйте restrict, если у вас есть его компилятор. (Исследуйте здесь тоже беспорядок!)
• Проверьте различные режимы с плавающей запятой на вашем процессоре и компиляторе. Если вам не нужен денормализованный диапазон, выбор режима без этого может привести к повышению производительности. (Похоже, что вы уже сделали некоторые вещи в этой области, основываясь на вашем обсуждении режимов округления.)
• Определенно избегайте allocs: вызов reserve на std::vector, если вы можете, или используйте std::array, когда знаете размер во время компиляции.
• Использовать пулы памяти, чтобы увеличить локальность и уменьшить накладные расходы. также для обеспечения выравнивания по шкале и предотвращения ping-ponging.
• Используйте распределители кадров, если вы выделяете вещи в предсказуемых шаблонах и можете позволить себе освободить все за один раз.
• Do знать об инвариантах. Что-то, что вы знаете, инвариантно, возможно, не относится к компилятору, например, к использованию элемента структуры или класса в цикле. Я нахожу, что самый простой способ попасть в правильную привычку - это дать имя всему, и предпочитают называть вещи за пределами циклов. Например. const int threshold = m_currentThreshold; или, возможно, Thing * const pThing = pStructHoldingThing->pThing; К счастью, вы обычно можете видеть вещи, которые нуждаются в этом лечении в режиме разборки. Это также помогает при отладке позже (делает окно watch/locals более приятным в отладочных сборках)!
• Избегайте записи в циклах, если это возможно - накапливайте сначала, затем пишите или выполняйте несколько записей вместе. YMMV, конечно.

WRT ваш вопрос std::priority_queue: вставка вещей в вектор (бэкэнда по умолчанию для priority_queue) имеет тенденцию перемещать множество элементов вокруг. Если вы можете разбить фазы, где вы вставляете данные, затем сортируйте их, а затем прочитайте их после сортировки, вам, вероятно, будет намного лучше. Хотя вы определенно потеряете местонахождение, вы можете найти более самонастраивающуюся структуру, такую ​​как std:: map или std:: set, которая стоит накладных расходов, но это действительно зависит от ваших шаблонов использования.

Ответ 3

Есть ли какая-либо польза для замены контейнеров/алгоритмов STL вручную?
Я бы рассматривал это как последний вариант. Контейнеры и алгоритмы STL были тщательно протестированы. Создание новых является дорогостоящим с точки зрения времени разработки.

В то же время для std::vectors, требуемые размеры которого неизвестны, но имеют достаточно малую верхнюю границу, выгодно ли их заменять статически распределенными массивами?
Сначала попробуйте зарезервировать пространство для векторов. Ознакомьтесь с методом std::vector::reserve. Вектор, который продолжает расти или меняться на большие размеры, будет тратить динамическую память и время выполнения. Добавьте код, чтобы определить хорошее значение для верхней границы.

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

Насколько кэширующими являются компиляторы? Например, стоит ли искать переупорядочение вложенных циклов?
Современные компиляторы очень хорошо знают кэши команд (конвейеры) и стараются не перезагружать их. Вы всегда можете помочь своему компилятору, написав код, который использует меньше ветвей (от if, switch, конструкций циклов и вызовов функций).

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

Учитывая научный характер программы, числа с плавающей запятой используются повсюду. Существенным узким местом в моем коде были конверсии с плавающей запятой на целые числа: компилятор выдавал код, чтобы сохранить текущий режим округления, изменить его, выполнить преобразование, а затем восстановить старый режим округления --- даже если ничего в программе когда-либо меняли режим округления! Отключение этого поведения значительно ускорило мой код. Есть ли какие-либо похожие связанные с плавающей запятой ошибки, о которых я должен знать?
Для точности держите все как double. Отрегулируйте для округления только при необходимости и, возможно, перед отображением. Это подпадает под правило оптимизации: используйте меньше кода, исключая посторонний или мертвый код.

Также см. раздел выше о резервировании пространства в контейнерах перед их использованием.

Некоторые процессоры могут загружать и хранить числа с плавающей запятой либо быстрее, либо целыми. Это потребует сбора данных профиля перед оптимизацией. Однако, если вы знаете, что существует минимальное разрешение, вы можете использовать целые числа и изменить свою базу на минимальное разрешение. Например, при работе с деньгами США целые числа могут использоваться для представления 1/100 или 1/1000 доллара.

Одно из последствий того, что С++ компилируется и связывается отдельно, заключается в том, что компилятор не может выполнить то, что может показаться очень простой оптимизацией, такой как вызовы метода перемещения, такие как strlen(), из условий завершения цикла. Есть ли такая оптимизация, как эта, которую я должен искать, потому что они не могут быть выполнены компилятором и должны выполняться вручную?
Это неверное предположение. Компиляторы могут оптимизировать на основе сигнатуры функции, особенно если параметры правильно используют const. Мне всегда нравится помогать компилятору, перемещая постоянный материал за пределы цикла. Для верхнего предельного значения, такого как длина строки, назначьте его переменной const перед циклом. Модификатор const поможет оптимизатору.

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

С другой стороны, есть ли какие-либо методы, которых я должен избегать, потому что они могут помешать компилятору автоматически оптимизировать код?
Я бы избегал "микрооптимизации". Если у вас есть какие-либо сомнения, распечатайте код сборки, сгенерированный компилятором (для области, которую вы опросили), в самой высокой настройке оптимизации. Попробуйте переписать код, чтобы выразить код сборки компилятора. Оптимизируйте этот код, если сможете. Все, что требуется, требует инструкций на платформе.

Идеи и концепции оптимизации

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

2. Устранение требований
Меньше кода, больше производительности.

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

4. Рассмотрим организацию данных. Оптимизируйте данные.
Организуйте часто используемые поля в substructures. Установите размеры данных, чтобы они вписывались в строку кэша данных. Удалите постоянные данные из структур данных.
Используйте const спецификатор как можно больше.

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

6. Рассмотрите оптимизацию ввода/вывода (Включает файловый ввод-вывод).
Большинство I/O предпочитает меньшее количество больших фрагментов данных для многих небольших фрагментов данных. Жесткие диски любят вращаться. Более крупные пакеты данных имеют меньше накладных расходов, чем меньшие пакеты.
Отформатируйте данные в буфер, а затем напишите буфер.

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

Это должно занять некоторое время.: -)

Ответ 4

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

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

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

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

• Я заметил, что вы не указали использование инструкций типа SSE. Могут ли они быть применимы к вашему типу числа хруст?

Желаем удачи.

Ответ 5

Здесь - хорошая статья по этому вопросу.

Ответ 6

О контейнерах STL.

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

Люди утверждают о сложности алгоритмов, используемых в STL. Здесь STL хорош: O (1) для list/queue, вектор (амортизированный) и O (log (N)) для map. Но это не является настоящим узким местом производительности для типичного приложения! Для многих приложений реальным узким местом является операции кучи (malloc/free, new/delete и т.д.).

Типичная операция на list стоит всего несколько циклов процессора. На a map - несколько десятков, может быть больше (это, конечно, зависит от состояния кэша и log (N)). И типичные операции кучи стоят от hunders до тысяч (!!!) циклов процессора. Для многопоточных приложений, например, им также требуется синхронизация (блокированные операции). Плюс к некоторым ОС (например, Windows XP) функции кучи полностью реализованы в режиме ядра.

Таким образом, что фактическая производительность контейнеров STL в типичном сценарии преобладает над количеством операций кучи, которые они выполняют. И здесь они катастрофичны. Не потому, что они реализованы плохо, но из-за их дизайна. То есть, это вопрос дизайна.

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

http://www.codeproject.com/KB/recipes/Containers.aspx

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

Но недавно я обнаружил, что я не единственный, кто думал об этом. boost::intrusive - это библиотека контейнера, которая реализована так же, как и я.

Я предлагаю вам попробовать (если вы этого еще не сделали)

Ответ 7

вот какой материал я использовал:

• шаблоны, чтобы специализировать границы внутренних окружностей (делает их очень быстрыми)
• использовать __restrict__ ключевые слова для проблем с псевдонимами
• зарезервировать векторы заранее до нормальных значений по умолчанию.
• избегать использования карты (она может быть очень медленной)
• вектор append/insert может быть значительно медленным. Если это так, необработанные операции могут ускорить его выполнение.
• Согласование по N-байтовой памяти (Intel имеет прагму, выровненную, http://www.intel.com/software/products/compilers/docs/clin/main_cls/cref_cls/common/cppref_pragma_vector.htm)
• пытается сохранить память в кэшах L1/L2.
• скомпилированный с помощью NDEBUG
• используя oprofile, используйте opannotate для поиска определенных строк (надстройка stl хорошо видна тогда).

здесь представлены образцы данных профиля (чтобы вы знали, где искать проблемы)

 * Output annotated source file with samples
 * Output all files
 *
 * CPU: Core 2, speed 1995 MHz (estimated)
--
 * Total samples for file : "/home/andrey/gamess/source/blas.f"
 *
 * 1020586 14.0896
--
 * Total samples for file : "/home/andrey/libqc/rysq/src/fock.cpp"
 *
 * 962558 13.2885
--
 * Total samples for file : "/usr/include/boost/numeric/ublas/detail/matrix_assign.hpp"
 *
 * 748150 10.3285

--
 * Total samples for file : "/usr/include/boost/numeric/ublas/functional.hpp"
 *
 * 639714  8.8315
--
 * Total samples for file : "/home/andrey/gamess/source/eigen.f"
 *
 * 429129  5.9243
--
 * Total samples for file : "/usr/include/c++/4.3/bits/stl_algobase.h"
 *
 * 411725  5.6840
--

пример кода из моего проекта

template<int ni, int nj, int nk, int nl>
inline void eval(const Data::density_type &D, const Data::fock_type &F,
                 const double *__restrict Q, double scale) {

    const double * __restrict Dij = D[0];
    ...
    double * __restrict Fij = F[0];
    ...

    for (int l = 0, kl = 0, ijkl = 0; l < nl; ++l) {
        for (int k = 0; k < nk; ++k, ++kl) {
            for (int j = 0, ij = 0; j < nj; ++j, ++jk, ++jl) {
                for (int i = 0; i < ni; ++i, ++ij, ++ik, ++il, ++ijkl) {

Ответ 8

Есть ли какая-либо польза для замены контейнеров/алгоритмов STL вручную?

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

Единственное исключение, которое я видел, - заменить copy-on-write std::string на тот, который не требует синхронизации потоков.

для std::vectors, требуемые размеры которого неизвестны, но имеют достаточно малую верхнюю границу, выгодно ли их заменять статически распределенными массивами?

Вряд ли. Но если вы используете много времени на выделение до определенного размера, может оказаться выгодным добавить вызов reserve().

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

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

Насколько кэширующими являются компиляторы? Например, стоит ли искать переупорядочение вложенных циклов?

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

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

Угу. Недавно я обнаружил ту же проблему.

Одно из последствий того, что С++ компилируется и связывается отдельно, заключается в том, что компилятор не может выполнить то, что может показаться очень простой оптимизацией, такой как вызовы метода перемещения, такие как strlen(), из условий завершения цикла.

Некоторые компиляторы могут справиться с этим. Visual С++ имеет параметр "генерация кода времени", который эффективно повторяет вызов компилятора для дальнейшей оптимизации. И в случае таких функций, как strlen, многие компиляторы распознают это как внутреннюю функцию.

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

Когда вы оптимизируете этот низкий уровень, существует несколько надежных правил. Компиляторы будут отличаться. Измерить свое текущее решение и решить, слишком ли он медленный. Если да, придумайте гипотезу (например, "Что делать, если я заменю внутренние операторы if на таблицу поиска?" ). Это может помочь ( "устраняет киоски из-за неудачных предсказаний отрасли" ), или это может повредить ( "шаблон доступа к поиску нарушает согласованность кеша" ). Экспериментируйте и измерьте постепенно.

Я часто клонирую прямую реализацию и использую #ifdef HAND_OPTIMIZED/#else/#endif для переключения между эталонной версией и измененной версией. Это полезно для последующего обслуживания и проверки кода. Я выполняю каждый успешный эксперимент для изменения управления и сохраняю журнал (электронную таблицу) с номером списка изменений, временем выполнения и пояснением для каждого шага оптимизации. Когда я узнаю больше о том, как работает код, журнал облегчает резервное копирование и отключение в другом направлении.

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

Ответ 9

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

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

Вот пример такого рода процессов.

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

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

Ответ 10

И я думаю, что основной намек, который может вам дать, это: measure, measure, measure. Это и улучшение ваших алгоритмов.
То, как вы используете определенные функции языка, версию компилятора, реализацию std lib, платформу, машину, - все это играет роль в производительности, и вы не упомянули многих из них, и никто из нас никогда не имел вашей точной настройки.

Относительно замены std::vector: используйте замену (например, этот) и просто попробуйте.

Ответ 11

Насколько кэширующими являются компиляторы? Например, стоит ли искать переупорядочение вложенных циклов?

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

Ответ 12

Есть ли какая-либо польза для замены STL контейнеры/алгоритмы с ручным прокатом из них? В частности, моя программа включает в себя очень большую очередь приоритетов (в настоящее время std:: priority_queue) чья манипуляция занимает много общее время. Это что-то стоит глядя или STL реализация, скорее всего, максимально быстрый?

STL, как правило, самый быстрый, общий случай. Если у вас очень конкретный случай, вы можете увидеть ускорение с ручным прокатом. Например, std:: sort (обычно quicksort) - это самый быстрый общий вид, но если вы заранее знаете, что ваши элементы уже упорядочены, то выбор вставки может быть лучшим выбором.

В аналогичных строках для std::vectorsчьи требуемые размеры неизвестны, но имеют достаточно малую верхнюю границу, выгодно заменить их на статически распределенные массивы?

Это зависит от того, где вы собираетесь выполнять статическое распределение. Одна вещь, которую я пробовал по этой линии, - это статическое выделение большого количества памяти в стеке, а затем повторное использование позже. Результаты? Память кучи была значительно быстрее. Просто потому, что элемент находится в стеке, он не ускоряет доступ к нему - скорость стековой памяти также зависит от таких вещей, как кеш. Статически выделенный глобальный массив может быть не быстрее, чем куча. Я предполагаю, что вы уже пробовали такие методы, как просто резервирование верхней границы. Если у вас много векторов с одинаковой верхней границей, рассмотрите возможность улучшения кеша с помощью вектора structs, содержащего элементы данных.

Я обнаружил, что динамическая память распределение часто является серьезным узкое место и устранение этого может привести к значительным ускорениям. Как последствие. Мне интересно в результативность компромиссов с возвратом большие временные структуры данных значение против возврата указателем vs. передавая результат по ссылке. Является существует способ надежно определить будет ли компилятор использоваться RVO для данного метода (при условии, что вызывающему абоненту не требуется изменять результат, конечно)?

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

Как кэшировать, компиляторы имеют тенденцию быть? Например, стоит ли смотреть в переупорядочение вложенных циклов?

Я обнаружил, что они не особенно осведомлены о кеше. Проблема в том, что компилятор не понимает вашу программу и не может предсказать подавляющее большинство ее состояний, особенно если вы сильно зависнете от кучи. Если у вас есть профилировщик, который поставляется вместе с вашим компилятором, например, Visual Studio Profile Guided Optimization, то это может привести к отличным ускорениям.

Учитывая научный характер программы с плавающей запятой используется везде. Значительный узкое место в моем коде конверсии с плавающей запятой на integers: компилятор будет генерировать код для сохранения текущего режима округления, изменить его, выполнить преобразование, затем восстановить старый режим округления --- хотя ничто в программе когда-либо меняли режим округления! Отключение этого поведения значительно ускорил мой код. Есть ли похожие связанные с плавающей запятой должен знать?

Существуют разные модели с плавающей запятой - Visual Studio дает настройку компилятора fp: fast. Что касается точных эффектов такого рода, я не могу быть уверен. Однако вы можете попробовать изменить точность с плавающей запятой или другие параметры в своем компиляторе и проверить результат.

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

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

Одной из других вещей, которые я хочу отметить, является использование нестандартных расширений для компилятора, например, предоставленное Visual Studio __assume. http://msdn.microsoft.com/en-us/library/1b3fsfxw(VS.80).aspx

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

Изменить: я понял, что многие предложения, которые я опубликовал, напрямую ссылаются на Visual Studio. Это правда, но GCC почти наверняка предоставляет альтернативы большинству из них. Я просто лично имею опыт работы с VS.

Ответ 13

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

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

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

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

Что касается плавающей запятой, вы абсолютно должны использовать SSE. Это не обязательно требует изучения SSE самостоятельно, так как существует множество библиотек высокооптимизированного SSE-кода, которые выполняют всевозможные важные научные вычислительные операции. Если вы компилируете 64-битный код, компилятор может автоматически генерировать некоторый SSE-код, поскольку SSE2 является частью набора инструкций x86_64. SSE также сэкономит вам часть накладных расходов с плавающей запятой x87, поскольку она не преобразует обратно и обратно в 80-битные значения внутри. Эти преобразования также могут быть источником проблем с точки зрения точности, поскольку вы можете получать разные результаты из одного и того же набора операций в зависимости от того, как они скомпилируются, поэтому хорошо избавиться от них.

Ответ 14

Если вы работаете, например, с крупными матрицами, подумайте о том, как использовать ваши петли для улучшения местоположения. Это часто приводит к значительным улучшениям. Вы можете использовать VTune/PTU для отслеживания пропусков кэша L2.

Ответ 15

Одним из следствий компиляции и связывания С++ по отдельности является то, что компилятор не может выполнить то, что может показаться очень простой оптимизацией, такой как вызовы метода перемещения, такие как strlen(), из условий завершения цикла. Есть ли такая оптимизация, как эта, которую я должен искать, потому что они не могут быть выполнены компилятором и должны выполняться вручную?

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

• Компиляторы Microsoft Visual С++
• Компилятор Intel С++
• LLVC-НКА
• GCC (думаю, не уверен)

Ответ 16

Я удивлен, что никто не упомянул эти два:

• Оптимизация времени ссылки clang и g++ из 4.5 в оптимизации оптимизации ссылок. Я слышал, что в случае g++ эвристика по-прежнему довольно мрачна, но она должна быстро улучшаться с момента размещения основной архитектуры.

  Преимущества варьируются от межпроцессорных оптимизаций на уровне объектных файлов, включая высокодоступные материалы, такие как inling of virtual calls (devirtualization)

• Вложение проекта может показаться некоторым очень грубым, но это очень грубовато, что делает его настолько мощным: это сумма при сбросе всех ваших заголовков и .cpp файлов в единственный, действительно большой .cpp файл и скомпилировать его; в основном это даст вам те же преимущества оптимизации ссылок в вашей поездке в 1999 году. Конечно, если ваш проект действительно большой, вам все равно понадобится машина 2010 года; эта вещь будет есть вашу оперативную память, как нет завтра. Однако даже в этом случае вы можете разбить его в более чем одном огромном файле .cpp no-so-damn.

Ответ 17

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

Внутренние возможности SSE Google для получения дополнительной информации об этом.

Ответ 18

Вот что-то, что сработало для меня один раз. Я не могу сказать, что это сработает для вас. У меня был код в строках

switch(num) {
   case 1: result = f1(param); break;
   case 2: result = f2(param); break;
   //...
}

Затем я получил серьезное повышение производительности, когда я изменил его на

// init:
funcs[N] = {f1, f2 /*...*/};
// later in the code:
result = (funcs[num])(param);

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

Ответ 19

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

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

Сначала я написал свои собственные классы управления STL, сетью и файлами.

Все мои классы контейнеров ( "MySTL" ) управляют своими собственными блоками памяти, чтобы избежать многочисленных вызовов alloc (new)/free (delete). Выпущенные объекты помещаются в пул блоков памяти, которые необходимо повторно использовать при необходимости. Таким образом, я улучшаю производительность и защищаю свой код от фрагментации памяти.

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

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

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

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

[02:01] -alpha.ip.tv- Время работы: 525дней 12hrs 43mins 7secs