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

Question

Good Day,

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

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

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

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

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

cds.update(objectlist);

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

Answer 1

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

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

Answer 2

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

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

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

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

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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

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

Решения:

• Пусть ваш компилятор выполняет работу по преобразованию цикла. Современные g ++ довольно хороши в этой дисциплине. Еще одна дисциплина, в которой хорошо работает g ++ - автоматическая векторизация. Помните, что компиляторы знают больше о компьютерной архитектуре, чем почти все люди.
• Отправляем разные двоичные файлы и диспетчер.
• Использовать структуры / схемы и алгоритмы не учитывающие кэш данных , которые адаптируются к целевому кешу.

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

Литература: * Гид Агнера Тумана * Руководства Intel

Answer 5

Что касается сложности big-o, это не имеет значения, если 1 цикл равен O (n), то же самое относится и к решению с 2 циклами.
Что касается микрооптимизации, то сказать сложно. Стоимость цикла довольно мала, мы не знаем, какова стоимость доступа к вашим объектам (если они в векторе, то он тоже должен быть довольно мал), но есть много вещей, которые нужно учитывать, чтобы дать полезный ответить.

Answer 6

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

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

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