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

Question

В следующем коде:

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

Вызывается ли функция-член size() для каждой итерации цикла или только один раз?

Answer 1

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

for(initialization; condition; increment)
    body;

расширяется до чего-то вроде

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

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

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

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

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

---

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

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

Answer 2

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

Однако, на что следует обратить внимание, это:

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

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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 [См. Комментарий Стива Джессопа ниже.]

Answer 6

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

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

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

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

Answer 7

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

Если гарантированный размер вектора не изменяется в цикле, лучшеиспользуйте предварительно рассчитанный размер, иначе выбора нет и необходимо использовать 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 << "";
}

Answer 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 и другие вещи.

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

Но!если вы хотите, чтобы компилятор выполнял оптимизацию по вашему коду, НИКОГДА не ставьте volatile, например так:

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

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

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

Компилятор постарается не перемещать i из регистров ЦП в RAM.Не гарантируется, что он сможет это сделать, но он сделает это лучше;)

Answer 9

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

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

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