Проблема производительности для вектора :: размер() в цикле в С++

Ответ 1

В теории это называется каждый раз, поскольку цикл for:

for(initialization; condition; increment)
    body;

расширяется до значения

{
    initialization;
    while(condition)
    {
        body;
        increment;
    }
}

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

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

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

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

Изменить:, как говорили другие, в общем случае с контейнерами лучше использовать итераторы, но для vector это не так важно, потому что произвольный доступ к элементам через operator[] гарантированно будет O (1); на самом деле с векторами обычно это сумма указателя (векторная база + индекс) и разыменование с увеличением указателя (предшествующий элемент + 1) и разыменование итераторов. Поскольку целевой адрес все тот же, я не думаю, что вы можете получить что-то от итераторов с точки зрения локальности кеша (и даже если это так, если вы не идете по массивам в сложных циклах, вы не должны даже заметить такие вид улучшений).

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

Ответ 2

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

Почему бы не использовать vector<int>::iterator вместо этого?

Ответ 3

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

Однако вы должны обратить внимание на следующее:

• Правильный тип для векторного индекса std::vector<T>::size_type.
• Существуют типы (например, некоторые итераторы), где i++ может быть медленнее, чем ++i.

Следовательно, цикл должен быть:

for(vector<int>::size_type i=0; i<var.size(); ++i)
  ...

Ответ 4

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

Поэтому нет большого выбора, который он просто должен быть.

Ответ 5

Как говорили другие

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

поверх которого

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

Ответ 6

I подумайте, что если компилятор может окончательно вывести, что переменная var не изменяется внутри "тела цикла"

for(int i=0; i< var.size();i++) { 
    // loop body
}

то вышеуказанное может быть перенесено на нечто эквивалентное

const size_t var_size = var.size();
for( int i = 0; i < var_size; i++ ) { 
    // loop body
}

Однако я не совсем уверен, поэтому комментарии приветствуются:)

Кроме того,

• В большинстве ситуаций функция члена size() встроена, поэтому проблема не вызывает беспокойства

• Возможно, проблема связана с end(), которая всегда используется для циклизации на основе итератора, т.е. it != container.end()

• Пожалуйста, используйте size_t или vector<int>::size_type для типа i [См. комментарий к Стив Джессопу ниже.]

Ответ 7

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

for(vector<int>::size_type i=0, size = var.size(); i < size; ++i) 
{
//do something
}

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

Ответ 8

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

for (int i = 0 ; i < n ; ++i)
{
   for ( int j = 0 ; j < n ; ++j)
       printf("%d ", arr[i][j]);
   printf("\n");
}
for (int j = 0 ; j < n ; ++j)
{
   for ( int i = 0 ; i < n ; ++i)
       printf("%d ", arr[i][j]);
   printf("\n");
}

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

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

Но! если вы хотите, чтобы компилятор делал это с оптимизацией по вашему коду, NEVER put volatile, например:

for(volatile int i = 0 ; i < 100; ++i)

Это предотвращает оптимизацию компилятора. Если вам нужен другой совет для использования, используйте регистр вместо volatile.

for(register int i = 0 ; i < 100; ++i)

Компилятор попытается не переместить я из регистров CPU в ОЗУ. Это не гарантирует, что он может это сделать, но он будет делать это лучше всего;)

Ответ 9

Протестировал его на 900 000 итераций. Его время составляет 43 секунды для предварительно рассчитанного размера и 42 секунды для использования вызова size().

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

#include <iostream>
#include <vector>

using namespace std;

int main() {
vector<int> v;

for (int i = 0; i < 30000; i++)
        v.push_back(i);

const size_t v_size = v.size();
for(int i = 0; i < v_size; i++)
        for(int j = 0; j < v_size; j++)
                cout << "";

//for(int i = 0; i < v.size(); i++)
//      for(int j = 0; j < v.size(); j++)
//              cout << "";
}