Неоднократно называет размер () на контейнере (во время цикла) плохо?
По причинам эффективности я всегда стараюсь не писать циклы как это:
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) { ... }
или используйте контейнерные итераторы.
Но как плохо первое решение действительно? Я не забываю читать в Meyers, что это будет квадратично вместо линейного, потому что вектор не знает своего размера и неоднократно должен рассчитывать. Но разве современные компиляторы не обнаружат это и оптимизируют его далеко?
4 ответа
vector :: size () работает с постоянным временем и обычно реализуется как тривиальная встроенная функция, которая оптимизируется отдельно. Не пытайтесь оптимизировать его вручную.
Рассмотрим следующую глупую функцию:
void sum (vector<int>& vec, int* sumOut)
{
*sumOut = 0;
for(std::size_t i = 0; i < vec.size(); ++i)
{
*sumOut += vec[i];
}
}
Фактическая сгенерированная сборка будет зависеть от компилятора и реализации вектора , но я думаю, что в большинстве случаев компилятор должен перечитывать размер вектора из памяти каждый раз во время цикла. Это связано с тем, что указатель sumOut потенциально может перекрывать (псевдоним) внутреннее хранилище вектора размера (при условии, что вектор вектор хранит свой размер в int), поэтому размер может быть изменен петля. Если вы вызываете такую функцию часто, это может привести к большому количеству циклов, потому что вы касаетесь памяти больше, чем вам нужно.
Три возможных решения:
Сохранить размер в локальной переменной. В идеале размер получится хранятся в реестре и не касаются память вообще. Даже если это должно быть положить в стек, компилятор должен иметь возможность заказать загружает / хранит более эффективно.
Используйте
__ restrictна выходе указатель. Это сообщает компилятору что указатель не может перекрывает что-либо еще, поэтому пишет в не требует перезагрузки ничего еще.Обратный цикл. Прекращение условие теперь проверяется на 0 вместо этого
vec.size ()никогда не позвонил снова.
Из них, я думаю, №1 самый чистый, но некоторые люди могут предпочесть №3. №2, вероятно, наименее удобен для чтения, но может быть быстрее, чем другие (потому что это означает, что данные вектора могут быть прочитаны более эффективно).
Для получения дополнительной информации о псевдонимах см. презентацию Кристера Эриксона на GDC по оптимизации памяти ; там есть пример, почти идентичный этому.
Я помню, как читал у Мейерса, что он будет квадратичным, а не линейным, потому что вектор не знает своего размера и постоянно должен считать.
Вы путаете вектор и список . значение размера вектора хранится в векторе; list требует пересечения фактического списка.
Самый простой способ узнать, оптимизируется ли что-то компилятором, - это сравнить выходные данные компилятора на языке ассемблера.
Тем не менее, эти два фрагмента кода на самом деле не эквивалентны. Что, если размер вектора изменится во время итерации по нему? Компилятор должен быть очень и очень умным, чтобы окончательно доказать, что размер вектора не может измениться.
Действительно ли эта крошечная оптимизация стоит дополнительных усилий в реальном мире? vec.size () просто возвращает сохраненное значение. Он не пересчитывает длину.