Повторно ли вызывать size () для контейнера (во время цикла) плохо?

Question

Из соображений эффективности я всегда избегаю написания таких циклов:

for(std::size_t i = 0; i < vec.size(); ++i) { ... }

, где vec - контейнер STL. Вместо этого я либо делаю

const std::size_t vec_size = vec.size();
for(std::size_t i = 0; i < vec_size; ++i) { ... }

или используйте контейнерные итераторы.

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

Answer 1

vector::size() является постоянным временем и обычно реализуется как тривиальная встроенная функция, которая оптимизируется. Не пытайтесь оптимизировать его вручную.

Answer 2

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

Вы запутались vector и list. Значение размера vector хранится в векторе; list требует трансверсального фактического списка.

Answer 3

Рассмотрим следующую глупую функцию:

void sum (vector<int>& vec, int* sumOut)
{
    *sumOut = 0;
    for(std::size_t i = 0; i < vec.size(); ++i)
    {
        *sumOut += vec[i];      
    }
}

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

Три возможных решения:

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

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

3. Обратный цикл. Прекращение условие теперь проверяется на 0 вместо этого vec.size() никогда позвонил снова.

Из них, я думаю, # 1 - самый чистый, но некоторые люди могут предпочесть # 3. # 2, вероятно, наименее удобен для читателя, но может быть быстрее других (поскольку это означает, что данные вектора могут быть прочитаны более эффективно).

Для получения дополнительной информации о псевдонимах см. Презентация Кристера Эриксона GDC по оптимизации памяти ; там есть пример, почти идентичный этому.

Answer 4

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

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

Теперь, в реальном мире, эта крошечная оптимизация действительно стоит дополнительных усилий?vec.size() просто возвращает сохраненное значение.Он не пересчитывает длину.