Разница в производительности между повторением один раз и повторением дважды?

Question

Рассмотрим что-то вроде ...

for (int i = 0; i < test.size(); ++i) {
        test[i].foo();
        test[i].bar();
}

Теперь рассмотрим ..

for (int i = 0; i < test.size(); ++i) {
        test[i].foo();
}
for (int i = 0; i < test.size(); ++i) {
        test[i].bar();
}

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

Answer 1

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

Есть еще один эффект, о котором вы, возможно, захотите беспокоиться. Если ваш размер контейнера достаточно велик, то первый случай будет выполняться быстрее. Это потому, что, когда он достигает test[i].bar(), test[i] будет кэшироваться. Во втором случае с разделенными циклами кэш будет перегружен, поскольку для каждой функции test[i] всегда нужно перезагружать.

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

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

test[0].foo();
test[0].bar();
test[1].foo();
test[1].bar();
test[2].foo();
test[2].bar();
// ...
test[test.size()-1].foo();
test[test.size()-1].bar();

в то время как второй делает:

test[0].foo();
test[1].foo();
test[2].foo();
// ...
test[test.size()-1].foo();
test[0].bar();
test[1].bar();
test[2].bar();
// ...
test[test.size()-1].bar();

Так что, если ваш bar() предполагает, что все foo() запущены, вы сломаете его, если смените второй случай на первый. Аналогично, если bar() предполагает, что foo() не был запущен на более поздних объектах, то переход от второго случая к первому нарушит ваш код.

Так что будьте осторожны и документируйте, что вы делаете.

Answer 2

Метка производительности, справа.

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

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

Учитывая, что у вас есть один семейный автомобиль (CPU), с какой стати вы бы:

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

Это не имеет ничего общего с ценой на бензин в 9:00 в субботу, или с временем, затрачиваемым на кофе в кафе, или стоимостью каждой итерации.

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

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

Masseratis не может преодолевать пробки быстрее, чем универсалы.

Answer 3

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

Большинство компиляторов, вероятно, будут хранить .size() в переменной до начала цикла, поэтому время .size() будет сокращено.

Следовательно, время внутри двух циклов for будет одинаковым, а у другой части будет вдвое больше.

Answer 4

Есть много аспектов в таком сравнении.

Во-первых, сложность для обоих вариантов равна O(n), поэтому разница в любом случае невелика.Я имею в виду, вы не должны заботиться об этом, если вы пишете довольно большую и сложную программу с большими n и «тяжелыми» операциями .foo() и bar().Таким образом, вы должны заботиться об этом только в случае очень маленьких простых программ (например, это программы для встроенных устройств).

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

В-третьих, если компилятор не оптимизировал ваш код, разница в производительности будет сильно зависеть от целевого процессора .Рассмотрим цикл в терминах команд сборки - он будет выглядеть примерно так (язык псевдо-ассемблера):

LABEL L1:
          do this    ;; some commands
          call that
          IF condition
          goto L1
          ;; some more instructions, ELSE part

Т.е. каждый проход цикла является просто оператором IF.Но современные процессоры не любят IF.Это связано с тем, что процессоры могут переставлять инструкции, чтобы выполнить их заранее или просто избежать холостого хода.С помощью инструкций IF (фактически, условного перехода или перехода) процессоры не знают, могут ли они переставить работу или нет.
Существует также механизм, называемый предиктор ветвления . Из материала Википедии :

branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure.

Это "смягчает" эффект IF, даже если предсказание неверно, оптимизация не будетвыполнила.

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

Answer 5

Для ваших примеров у вас есть дополнительное беспокойство о том, насколько дорогой .size(), так как он сравнивается для каждого шага i в большинстве языков.Ну, это зависит, это, безусловно, все относительно.Если .foo() и .bar() стоят дорого, то стоимость реальной итерации, вероятно, будет незначительной по сравнению.Если они довольно легкие, то это будет больший процент вашего времени выполнения.Если вы хотите узнать о конкретном случае проверить его , это единственный способ убедиться в вашем конкретном сценарии.

Лично я бы пошел на одну итерациюдешевая сторона наверняка (если только вам не нужно, чтобы звонки .foo() происходили до звонков .bar()).