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

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

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

int result = 0;for (int i = 1; i <= valMax; i++) result += i;
ПРЕДУПРЕЖДЕНИЕ Нас интересует именно непосредственное суммирование, т.е. мы не хотим пользоваться общеизвестной формулой нахождения суммы арифметической прогрессии. Представьте себе, что наша задача как раз и состоит в проверке правильности этой формулы! 8-)

Для решения этой задачи используется простейший цикл с верхней границей 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,1424Sum Flat. Sum = 4501500, Elapsed msec= 731,0512

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

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

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