Смещение цикла в приложении С#

Мы работаем над приложением для обработки видео с использованием EmguCV и недавно должны были выполнить некоторую операцию с пиксельным уровнем. Сначала я написал петли, чтобы просмотреть все пиксели изображения следующим образом:

for (int j = 0; j < Img.Width; j++ )
{
    for (int i = 0; i < Img.Height; i++)
    {
        // Pixel operation code
    }
}

Время выполнения циклов было довольно плохим. Затем я опубликовал на форуме EmguCV и получил предложение переключить петли следующим образом:

for (int j = Img.Width; j-- > 0; )
{
    for (int i = Img.Height; i-- > 0; )
    {
        // Pixel operation code
    }
}

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

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

Ответы

Ответ 1

Разница заключается не в стоимости ветвления, а в том, что вы извлекаете свойство объекта Img.Width и Img.Height во внутренний цикл. Оптимизатор не знает, что это константы для целей этого цикла.

Вы должны получить такое же ускорение производительности, выполнив это.

const int Width = Img.Width;
const int Height = Img.Height;
for (int j = 0; j < Width; j++ )
{
    for (int i = 0; i < Height; i++)
    {
        // Pixel operation code
    }
}

Изменить:

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

const int Width = Img.Width;
const int Height = Img.Height;
for (int i = 0; i < Height; i++)
{
    for (int j = 0; j < Width; j++ )
    {
        // Pixel operation code
    }
}

Ответ 2

Я предполагаю, что вы используете класс System.Drawing.Image? Глядя на реализацию .Width и .Height, я вижу, что они выполняют вызов функции в GDI + (GdipGetImageHeight и GdipGetImageWidth в gdiplus.dll), что кажется довольно дорогостоящим.

Отправляясь назад, вы делаете этот вызов один раз, а не на каждой итерации.

Ответ 3

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

Ответ 4

Это потому, что процессоры похожи на хоккеистов, они идут быстрее, когда идут назад, -)

Более серьезно:
Это никак не связано с направлением цикла, а скорее из-за того, что в исходной конструкции условия управления циклом подразумевали разыменование объекта Img для индексации его свойства Width или Height (для каждой и одной итерации в петли), при этом вторая конструкция оценивает эти свойства только один раз.
Кроме того, тот факт, что новое условие проверяет значение 0, сохраняет даже загрузку немедленного значения. Вероятно, это объясняет разницу (при условии, что работа, выполняемая внутри внутреннего, была относительно минимальной, т.е. +/- то же самое, что и работа над тестированием объекта Object.Property, поскольку вы указываете прирост примерно на 50%).

Edit:
см. ответ Майкла Штума, который указывает, что ссылка Img.Width/Height является еще более дорогостоящей, чем мысль. Как это иногда бывает со свойствами, реализация объекта может запускать значительный объем кода для создания значения (например, он может делать кучу математики, чтобы каждый раз получать ширину, а не как-то кэшировать ее и т.д.). Это похоже на этот объект Img, поэтому интерес сделать это нужно только один раз (если вы уверены, что значение останется постоянным на протяжении всей логики цикла).