Методы оптимизации петли в C++

Question

Для повышения производительности в наших приложениях мы должны рассмотреть методы оптимизации цепей на этапе разработки.

Я покажу вам несколько различных способов перебирать простой std::vector<uint32_t> v:

1. неоптимизированного цикл с индексом:

   uint64_t sum = 0; 
   for (unsigned int i = 0; i < v.size(); i++) 
       sum += v[i]; 
   

2. неоптимизированного цикл с итератором:

   uint64_t sum = 0; 
   std::vector<uint32_t>::const_iterator it; 
   for (it = v.begin(); it != v.end(); it++) 
       sum += *it; 
   

3. Сохраненная std::vector::end итераторов:

   uint64_t sum = 0; 
   std::vector<uint32_t>::const_iterator it, end(v.end()); 
   for (it = v.begin(); it != end; it++) 
       sum += *it; 
   

4. Преинкремент итераторы:

   uint64_t sum = 0; 
   std::vector<uint32_t>::const_iterator it, end(v.end()); 
   for (it = v.begin(); it != end; ++it) 
       sum += *it; 
   

5. Range на основе цикла:

   uint64_t sum = 0; 
   for (auto const &x : v) 
       sum += x; 
   

Существуют также другие способы построения цикла в C++; например, используя std::for_each, BOOST_FOREACH и т. д.

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

Кроме того, в приложениях с критическими характеристиками может быть полезно развернуть петли: как я мог это сделать?

Answer 1

Нет жесткого правила, поскольку оно зависит от реализации . Если меры, которые я сделал несколько лет назад, являются типичными, однако: о единственном, что делает разницу кэширует итератор конца. Pre-or post-fix не делает разницы , независимо от типа контейнера и итератора.

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

Конечно, эти меры были для одного компилятора (g ++) на одной системе с определенным оборудованием. Единственный способ, которым вы можете знать для своей среды, - это измерить себя.

RE Ваша заметка: вы уверены, что включена полная оптимизация. Мои меры не показали разницы между 3 и 4, и я сомневаюсь в том, что компиляторы сегодня оптимизируют меньше.

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

Честно говоря, когда я делал измерение, я был удивлен , что кэширование конца итератор сделал разницу, даже для вектора, где, как не было никакой разницы между pre- и после инкремента, даже для обратного итератора на карту. В конце концов, также был добавлен end(); Фактически, каждая функция , используемая в моих тестах, была встроена.

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

std::vector<uint32_t>::const_iterator current = v.begin(); 
std::vector<uint32_t>::const_iterator end = v.end(); 
switch ((end - current) % 4) { 
case 3: 
    sum += *current ++; 
case 2: 
    sum += *current ++; 
case 1: 
    sum += *current ++; 
case 0: 
} 
while (current != end) { 
    sum += current[0] + current[1] + current[2] + current[3]; 
    current += 4; 
} 

Answer 2

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

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

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

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

• Cache все, что вы можете
• Храните мелкие распределения до минимума, особенно в цикле
• сделать так много вещей const, как вы можете. Это дает компилятору дополнительные возможности для микро-оптимизации.
• Узнайте свой набор инструментов хорошо, и использовать эти знания
• Узнайте вашу архитектуру хорошо, и использовать эти знания
• Научиться читать код сборки и проверьте результат сборки от вашего компилятора

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

Here - отличное руководство по написанию исполнителей C++ в среде Intel.

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

Answer 3

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

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

Там имеется большое количество информации о сглаживании указателей (включая What is the strict aliasing rule?), но у Майка Актона есть прекрасная информация о pointer aliasing.

restrict ключевое слово (см What does the restrict keyword mean in C++? или, опять же, Mike Acton), доступны через расширения компилятора на протяжении многих лет и кодифицированы в C99 (в настоящее время доступна только в качестве расширения компилятора в C++), предназначен для борьбы с этим. Способ использовать это в вашем коде гораздо более C-подобный, но может позволить компилятору лучше оптимизировать цикл, по крайней мере, на примерах вы Дано:

uint64_t sum = 0; 
uint32_t *restrict velt = &v[0]; 
uint32_t *restrict vend = velt + v.size(); 
while(velt < vend) { 
    sum += *velt; 
    velt++; 
} 

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

Answer 4

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

Answer 5

Если вы используете лязг, а затем передать его в эти флаги:

-Rpass-missed=loop-vectorize 
    -Rpass-analysis=loop-vectorize 

В Visual C++ добавить это к сборке:

/Qvec-report:2 

Эти флаги будут сообщать вам, если петля не в состоянии vectorize (и дать вам часто загадочное сообщение, объясняющее почему).

В общем, предпочитайте варианты 4 и 5 (или std :: for_each). В то время как clang и gcc обычно выполняют достойную работу в большинстве случаев, Visual C++ имеет тенденцию ошибаться с осторожностью. Если область видимости неизвестна (например, ссылка или указатель, переданный в функцию или этот указатель), то часто не выполняется векторизация (контейнеры в локальной области почти всегда будут векторизовать).

#include <vector> 
#include <cmath> 

// fails to vectorise in Visual C++ and /O2 
void func1(std::vector<float>& v) 
{ 
    for(size_t i = 0; i < v.size(); ++i) 
    { 
    v[i] = std::sqrt(v[i]); 
    } 
} 

// this will vectorise with sqrtps 
void func2(std::vector<float>& v) 
{ 
    for(std::vector<float>::iterator it = v.begin(), e = v.end(); it != e; ++it) 
    { 
    *it = std::sqrt(*it); 
    } 
} 

Clang и gcc также не защищены от этих проблем. Если вы всегда берете копию начала/конца, то это не может быть проблемой.

Вот еще один классик, который печально сказывается на многих компиляторах (clang 3.5.0 терпит неудачу в этом тривиальном тесте, но он исправлен в clang 4.0). Он получает много!

struct Foo 
{ 
    void func3(); 
    void func4(); 
    std::vector<float> v; 
    float f; 
}; 

// will not vectorise 
void Foo::func3() 
{ 
    // this->v.end() !! 
    for(std::vector<float>::iterator it = v.begin(); it != v.end(); ++it) 
    { 
    *it *= f; // this->f !! 
    } 
} 

void Foo::func4() 
{ 
    // you need to take a local copy of v.end(), and 'f'. 
    const float temp = f; 
    for(std::vector<float>::iterator it = v.begin(), e = v.end(); it != e; ++it) 
    { 
    *it *= temp; 
    } 
} 

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