Реверсирование цикла в C# Ускоряет приложение
Мы работаем над использованием приложения обработки видеоданных 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
}
}
Я был очень удивлен найти что код выполняемый в половину времени!
Единственной вещью, о которой я могу думать, является сравнение, которое происходит в циклах, каждый раз получает доступ к свойству, к которому это больше не имеет. Действительно ли это - причина скорости? Или есть ли что-то еще? Я был взволнован для наблюдения этого улучшения. И любил бы его, если кто-то мог бы разъяснить причину этого.
4 ответа
Разница не в стоимости ветвления, а в том, что вы получаете свойство объекта 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
}
}
Редактировать:
Как предлагает Джошуа, установка Width во внутренний цикл заставит вас последовательно проходить через память, что будет лучше согласованно кешировать и может быть быстрее. (зависит от размера вашего растрового изображения).
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
}
}
Я полагаю, вы используете класс System.Drawing.Image? Посмотрев на реализацию .Width и .Height, я вижу, что они выполняют вызов функции в GDI+ (GdipGetImageHeight и GdipGetImageWidth в gdiplus.dll), что кажется довольно дорогим.
При движении назад вы делаете этот вызов один раз, а не в каждой итерации.
Это потому что процессоры как хоккеисты, они идут быстрее, когда идут назад ;-)
Более серьезно:
Это никак не связано с направлением цикла, а скорее с тем, что в оригинальной конструкции условия управления циклом подразумевали разыменование объекта Img для индексации его свойства Width или Height (для каждой и единственной итерации в циклах), тогда как вторая конструкция оценивает эти свойства только один раз.
Кроме того, тот факт, что новое условие проверяется на значение 0, экономит даже загрузку непосредственного значения.
Это, вероятно, объясняет разницу (если предположить, что работа, проделанная внутри inner, была относительно минимальной, т.е. +/- такой же, как работа по проверке Object.Property, поскольку вы указываете примерно 50% выигрыш).
Edit:
см. ответ Michael Stum, который показывает, что ссылка Img.Width/Height еще более затратная, чем предполагалось. Как это иногда случается со свойствами, реализация объекта может выполнять значительный объем кода для получения значения (например, она может выполнять кучу математических вычислений, чтобы получить ширину каждый раз, вместо того, чтобы каким-то образом кэшировать ее и т.д.). Похоже, что это относится к данному объекту Img, отсюда и интерес сделать это только один раз (если вы уверены, что значение будет оставаться постоянным на протяжении всей логики цикла).
Дело не в обратном цикле, который ускоряет работу, а в том, что вы обращаетесь к свойствам Width и Height гораздо меньше раз.