Динамическое разворачивание циклов

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

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

 

int result = 0;

for (int i = 1; i <= valMax; i++)

result += i;

 

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

Для решения этой задачи используется простейший цикл с верхней границей valMax. Величина valMax является параметром этого алгоритма и может меняться от одного запуска алгоритма к другому.

То, что valMax является величиной переменной, играет важную роль для оптимизации этого цикла. Дело в том, что если бы в задаче требовалось провести вычисления только для одного значения valMax, можно было бы обойтись без цикла. Например, для valMax = 20 код выглядел бы вот так.

 

int result = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10

+ 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20;

 

Какой смысл в таком преобразовании кода? Убедительнее всего будет вам произвести замер скорости выполнения двух вариантов суммирования. Вы убедитесь, что вариант с циклом проигрывает по скорости второму варианту в несколько раз! Надо сказать, что разработчики компиляторов прекрасно осведомлены в этом вопросе и давно используют приём разворачивания циклов при трансляции кода циклов.

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

Но ведь технология Reflection. Emit позволяет генерировать код во время исполнения программы. Это значит, что мы можем отложить генерирование кода цикла до того момента, когда количество необходимых повторений станет известным. В этот момент мы можем " на лету " сгенерировать код развёрнутого цикла и получить огромный выигрыш в скорости!

Динамическое разворачивание цикла:

 

using System;

using System.Reflection;

using System.Reflection.Emit;

 

namespace DynUnloop

{ // Суммирование в цикле

class SumLooping

{ public int Summ(int valMax)

{ int result = 0;

for (int i = 0; i <= valMax; i++)

result += i;

return result;

}

}

 

// Плоское суммирование

class SumFlat

{ interface ISumCode

{ int ComputeSumm(int valMax);

}

void WriteCode(int valMax)

{ AssemblyName assemblyName = new AssemblyName();

assemblyName.Name = "SumFlatAssembly";

 

AssemblyBuilder assemblyBuilder =

AppDomain.CurrentDomain.DefineDynamicAssembly(

assemblyName, AssemblyBuilderAccess.Run);

 

ModuleBuilder moduleBuilder =

assemblyBuilder.DefineDynamicModule("SumFlatModule");

 

TypeBuilder typeBuilder =

moduleBuilder.DefineType("SumFlatClass"

, TypeAttributes.Public);

 

typeBuilder.AddInterfaceImplementation(typeof(ISumCode));

 

/// Задаём возвращаемое зачение и параметр

Type[] paramTypes = { typeof(int) };

Type returnType = typeof(int);

 

MethodBuilder methodBuilder =

typeBuilder.DefineMethod("ComputeSumm"

, MethodAttributes.Public

| MethodAttributes.Virtual

, returnType, paramTypes);

 

ILGenerator il = methodBuilder.GetILGenerator();

 

// Генерируем плоский код.

il.Emit(OpCodes.Ldc_I4, 0);

for (int i = 1; i <= valMax; i++)

{ il.Emit(OpCodes.Ldc_I4, i);

il.Emit(OpCodes.Add);

}

il.Emit(OpCodes.Ret);

 

// Перекрываем метод ComputeSumm и создаём тип SumFlatClass.

MethodInfo methodInfo =

typeof(ISumCode).GetMethod("ComputeSumm");

typeBuilder.DefineMethodOverride(methodBuilder, methodInfo);

typeBuilder.CreateType();

 

/// Код готов, создаём объект и берем его интерфейс.

code = (ISumCode)assemblyBuilder.CreateInstance("SumFlatClass");

}

 

public int Summ(int val)

{ if (this.code == null)

WriteCode(val);

return this.code.ComputeSumm(val);

}

 

ISumCode code;

}

 

class Test

{ static void Main()

{ const int valMax = 3000;

const int countIterations = 200000;

 

////////////////////////////////////////////

 

SumLooping sumLoop = new SumLooping();

DateTime start = DateTime.Now;

 

int sum = 0;

for (int it = 0; it < countIterations; it++)

sum = sumLoop.Summ(valMax);

 

TimeSpan span = DateTime.Now - start;

Console.WriteLine("Sum Looping. Sum = {0}, Elapsed msec= {1}"

, sum, span.TotalMilliseconds);

 

///////////////////////////////////////////

 

SumFlat sumFlat = new SumFlat();

DateTime start2 = DateTime.Now;

 

int sum2 = 0;

for (int it = 0; it < countIterations; it++)

sum2 = sumFlat.Summ(valMax);;

 

TimeSpan span2 = DateTime.Now - start2;

Console.WriteLine("Sum Flat. Sum = {0}, Elapsed msec= {1}"

, sum2, span2.TotalMilliseconds);

 

Console.ReadLine();

}

}

}

 

Вот такой получается результат:

 

Sum Looping. Sum = 4501500, Elapsed msec= 4967,1424

Sum Flat. Sum = 4501500, Elapsed msec= 731,0512

 

Выигрыш от разворачивания цикла – в 4-7 раз.

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

Результат, получился убедительным, но вот способ получения его результата, привёл некоторых в смущение. Всё-таки генерирование Op-кодов MSIL, да ещё динамическое, при помощи методов Reflection. Emit – это занятие непростое и трудоёмкое. А нельзя ли применить обычные языки среды.NET для динамического программирования? C#, например? Можно.

Атрибуты

Атрибут - это некоторая дополнительная информация о любом элементе программы – классах, методах, параметрах и т.д. Эта информация может быть приписана к различным элементам языка - типам (классам, перечислениям и т.п.), полям, методам, свойствам и некоторым другим конструкциям языка. Атрибуты помещаются в исполняемый файл и могут оттуда при необходимости извлекаться.

Атрибут является специальным видом класса, являющимся наследниками класса System.Attribute.

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

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

Атрибут это класс

Все атрибуты.NET являются классами - потомками класса System.Attribute.

Класс Attribute пространства имен System предоставляет следующие члены класса:

- GetType - получает объект типа Type текущего экземпляра;

- ToString - возвращает строку, описывающую данный объект;

- IsDefined - определяет, существует ли атрибуты заданного типа, назначенные указываемому члену класса;

- GetCustomAttribute - запрашивает атрибут заданного типа для указанного члена класса.

Для класса Attribute определено свойство TypeId, определяющее уникальный идентификатор атрибута.

Класс атрибута всегда должен иметь модификатор доступа public.

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

Атрибут указывается в квадратных скобках перед элементом, которому он назначается. Например:

 

[ObsoleteAttribute("Hallow World")]

 

Язык С# при назначении атрибута позволяет не указывать суффикс Attribute. Так, вместо

 

[ObsoleteAttribute("Hallow World")]

 

можно записать

 

[Obsolete ("Hallow World")]

 

Атрибуты делятся на предопределенные (встроенные) и пользовательские, которые пишет программист.

Простейший пример встроенного атрибута указывает, что класс подлежит сериализации:

 

[Serializable]

Class Student

{string Name;

int age

}

 

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

- использовать существующий класс атрибута из библиотеки.NET Framework;

- определить новый класс атрибута.

Атрибуты в программном коде используются следующим образом:

1. Определяется новый или берется существующий в.NET Framework атрибут;

2. Инициализируется конкретный экземпляр атрибута с помощью вызова конструктора атрибута.

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

Еще одним примером применения атрибутов являются компоненты, которые вы располагаете на форме. Кнопки, метки и т.п. имеют некоторый набор свойств - шрифт, местоположение, видимость и т.д. В IDE Visual Studio вы можете выбрать в окне Properties один из двух способов расположения этих свойств - по алфавиту или по категориям. Так вот, в какую категорию попадет то или иное свойство, определяется специальным встроенным атрибутом.