Производительность разваливается одной петли на две петли

Question

Добрый день,

Предположим, что у вас есть простой цикл, как показано ниже ...

for(int i=0;i<10;i++) 
{ 
    //statement 1 
    //statement 2 
} 

Предположим, что утверждение 1 и утверждение 2 были O (1). Кроме того, небольшие накладные расходы на «запуск» другого цикла будут разрушать то, что цикл для двух (не вложенных, но последовательных) циклов будет столь же быстрым? Например ...

for(int i=0;i<10;i++) 
{ 
    //statement 1 
} 
for(int i=0;i<10;i++) 
{ 
    //statement 2 
} 

Почему я задал такой глупый вопрос в том, что у меня есть система Collision Detection (CDS), который имеет цикл по всем объектам. Я хочу, чтобы «полочки» функциональность моей системы CDS, так что я могу просто позвонить

cds.update(objectlist); 

вместо того, чтобы сломать мою систему CDs вверх. (Не беспокойтесь о моей реализации CDS ... Я думаю, что я знаю, что я делаю, я просто не знаю, как это объяснить, что мне действительно нужно знать, если я возьму огромный успех за цикл через все мои объекты снова.

Answer 1

Это зависит от вашего приложения.

Возможные Недостатки (расщепления):

• ваши данные не помещаются в кэш L1 для данных, поэтому вы загружаете его один раз для первого цикла, а затем загрузить его на вторую петлю

Возможные Прибыли (расщепления):

• ваш цикл прод ains many variables, расщепление помогает уменьшить давление в регистре/стеке, а оптимизатор превращает его в более качественный машинный код
• функции, которые вы используете для удаления кэша команд L1, так что кеш загружается на каждой итерации, а путем разделения вы управляете загрузкой его один раз (только) на первой итерации каждого цикла

Эти списки, безусловно, не является исчерпывающим, но уже вы можете почувствовать, что существует противоречие между кодом и данных. Поэтому нам трудно воспринимать образованное/дикое предположение, когда мы не знаем ни того, ни другого.

Сопротивление: профиль. Используйте callgrind, проверьте промахи кэша в каждом случае, проверьте количество выполненных инструкций. Измерьте потраченное время.

Answer 2

насколько большой о сложности, то, это не делает разницы, если 1 цикл О (п), то и решение 2 петли.
As в отличие от микро-оптимизации, трудно сказать. Стоимость цикла довольно мала, мы не знаем, какие затраты на доступ к вашим объектам (если они находятся в векторе, то это тоже должно быть довольно мало) , но есть много, чтобы рассмотреть вопрос о том, чтобы дать полезный ответ.

Answer 3

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

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

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

Answer 4

С точки зрения алгоритмической сложности разбиение петель не имеет значения.

С точки зрения реального мира производительность разделения петель может повысить производительность, ухудшить производительность или не иметь никакого значения - это зависит от ОС, аппаратного обеспечения и, конечно, - то, что statement 1 и statement 2 есть.

Answer 5

С двумя петлями вы будете платить за:

• увеличил генерируемый размер кода
• 2x, как многие ветви предсказывает
• в зависимости, что расположение данных утверждения 1 и 2, вы можете быть перегрузка данных в кеш.

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

Answer 6

Как уже отмечалось, сложность остается.

Но в реальном мире мы не можем предсказать, какая версия работает быстрее. Ниже перечислены факторы, которые играют роль, огромные из них:

• кэширование данных
• кэширование Инструкции
• Спекулятивного исполнение
• прогнозирование отделения
• целевого Отделение буфера
• Количества доступных регистров на процессоре
• Размер кэш-памяти

(примечание: над всеми ними есть дамоклов меч неправильного предсказания; все являются wikipedizable и googlable)

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

Решения:

• Пусть ваш компилятор сделать работу преобразования цикла. Современные g ++ в этой дисциплине довольно хороши. Другая дисциплина, в которой g ++ хороша, - это автоматическая векторизация. Имейте в виду, что компиляторы знают больше об архитектуре компьютера, чем почти все люди.
• Корабль различных двоичных файлов и диспетчера.
• Используйте cache-oblivious data structures/layouts and algorithms, которые адаптируются к целевому кешу.

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

Литература: * Agner Fog's Guides * Intel's Guides