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

Question

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

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

Я знаю, что оптимизация очень зависит от компилятора и архитектуры. Я использую компилятор Intel C ++ для Core 2 Duo, но мне также интересно, что хорошо работает для gcc или для «любого современного компилятора».

Вот некоторые конкретные идеи, которые я рассматриваю:

• Есть ли польза от замены контейнеров / алгоритмов STL на свернутые вручную? В частности, моя программа включает очередь с очень большим приоритетом (в настоящее время std::priority_queue), манипулирование которой занимает много общего времени. Стоит ли изучать это, или реализация STL уже, вероятно, самая быстрая из возможных?
• Аналогичным образом, для std::vector s, чьи необходимые размеры неизвестны, но имеют достаточно малую верхнюю границу, выгодно ли заменять их статически распределенными массивами?
• Я обнаружил, что динамическое выделение памяти часто является серьезным узким местом, и что его устранение может привести к значительному ускорению. Как следствие, я заинтересован в компромиссах производительности, связанных с возвратом больших временных структур данных по значению, возвратом по указателю или передачей результата по ссылке. Есть ли способ надежно определить, будет ли компилятор использовать RVO для данного метода (при условии, конечно, что вызывающей стороне не нужно изменять результат)?
• Насколько кеш-ориентированными являются компиляторы? Например, стоит ли переупорядочивать вложенные циклы?
• Учитывая научную природу программы, числа с плавающей запятой используются повсеместно. Существенным узким местом в моем коде были преобразования из числа с плавающей запятой в целые числа: компилятор генерировал код, чтобы сохранить текущий режим округления, изменить его, выполнить преобразование, а затем восстановить старый режим округления - даже если в программе ничего не было когда-либо менял режим округления! Отключение этого поведения значительно ускорило мой код. Есть ли какие-либо похожие ошибки, связанные с плавающей точкой, о которых мне следует знать?
• Одним из следствий компиляции и связывания C ++ по отдельности является то, что компилятор не может выполнить то, что может показаться очень простой оптимизацией, такой как вызов методов метода, например strlen (), из условий завершения цикла. Есть ли какая-либо оптимизация, подобная этой, на которую мне следует обратить внимание, потому что они не могут быть выполнены компилятором и должны выполняться вручную?
• С другой стороны, есть ли какие-либо методы, которые мне следует избегать , потому что они могут мешать компилятору автоматически оптимизировать код?

Наконец, чтобы пресечь определенные виды ответов в зародыше:

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

Answer 1

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

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

Answer 2

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

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

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

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

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

Answer 3

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

Answer 4

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

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

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

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

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

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

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

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

[02:01] -alpha.ip.tv- Время безотказной работы: 525дней 12ч 43минс 7сек

Answer 5

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

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);

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

Answer 6

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

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

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

Answer 7

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 8

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

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

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

• Проектный вклад действительно большой .cpp файл и скомпилируйте его; в основном это даст вам те же преимущества оптимизации времени соединения в вашей поездке в 1999 году. Конечно, если ваш проект действительно большой, вам все равно понадобится машина 2010 года; эта штука съест твою оперативную память, как будто завтрашнего дня нет. Тем не менее, даже в этом случае вы можете разбить его на более чем один неимоверно огромный .cpp файл

Answer 9

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

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