Многократно вызывает размер() на контейнере (во время цикла)?

По соображениям эффективности я всегда избегаю писать такие петли, как это:

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) { ... }

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

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

Ответы

Ответ 1

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

Ответ 2

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

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

Ответ 3

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

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

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

Ответ 4

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

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 сохраняет свой размер в int), поэтому размер может быть изменен циклом. Если вы так много называете такую ​​функцию, это может привести к множеству циклов, потому что вы прикасаетесь к памяти больше, чем вам нужно.

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

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

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

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

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

Подробнее о aliasing см. презентация Christer Ericson GDC по оптимизации памяти; там пример, почти идентичный этому в нем.