Продолжаем размышления

Автор: Sinclair
Дата: 25.06.18

.
По факту, в прошлый раз мы получили только первую половину заголовка — 2D-Linq.
Теперь поговорим об оптимизации.
Отставание в 2.3 — 2.7 раза вызвано, судя по всему, наличием косвенного вызова. Как хорошо известно, вызовы делегатов инлайнингу не подлежат.
Мотивация для этого устарела примерно лет десять назад, но ограничения, с которыми сталкивается JIT, всё те же.
Поэтому внутри нашего плотного цикла идут постоянные косвенные вызовы всё одного и того же kernel, переданного нам снаружи.
В отличие от JIT и C#, мы точно знаем, сколько раз будет исполняться этот один и тот же делегат; нам может оказаться выгодным динамически построить код, похожий на наш PerfectFourNeighborAverage, и исполнить его.
Сказано — сделано.

Опытные джедаи наверняка бы заменили сигнатуру метода Select так, чтобы она принимала Expression<Kernel<T>> вместо делегата, и на лету собрали бы код итерирования из циклов и выражений.
К сожалению, моей квалификации на это не хватило, поэтому работать мы будем на уровне MSIL.
Оболочка решения — метод GenerateFilter():

public static Filter<T> GenerateFilter<T>(Kernel<T> kernel)
{
  var km = KernelMeasure.Measure(kernel);

  DynamicMethod dm = new DynamicMethod("Filter"+kernel.Method.Name, typeof(T[,]), new Type[] { typeof(object), typeof(T[,]) });

  var ilg = dm.GetILGenerator();

  var result_var = ilg.DeclareLocal(typeof(T[,]));
  var i_var = ilg.DeclareLocal(typeof(int));
  var j_var = ilg.DeclareLocal(typeof(int));
  var h_var = ilg.DeclareLocal(typeof(int));
  var w_var = ilg.DeclareLocal(typeof(int));

  ilg.Emit(OpCodes.Ldarg_1); // source
  ilg.Emit(OpCodes.Ldc_I4_0);// 0
  ilg.Emit(OpCodes.Call, typeof(T[,]).GetMethod("GetLength", new Type[] { typeof(int) }));
  ilg.Emit(OpCodes.Stloc, h_var);


  ilg.Emit(OpCodes.Ldarg_1); // source
  ilg.Emit(OpCodes.Ldc_I4_1);// 1
  ilg.Emit(OpCodes.Call, typeof(T[,]).GetMethod("GetLength", new Type[] { typeof(int) }));
  ilg.Emit(OpCodes.Stloc, w_var);

  ilg.Emit(OpCodes.Ldloc, h_var);
  ilg.Emit(OpCodes.Ldloc, w_var);
  ilg.Emit(OpCodes.Newobj, typeof(T[,]).GetConstructor(new Type[] { typeof(int), typeof(int) }));
  ilg.Emit(OpCodes.Stloc, result_var);

  ilg.EmitIncrease(h_var, -km.ymax);
  ilg.EmitIncrease(w_var, -km.xmax);

  ilg.EmitFor(i_var, 0-km.xmin, h_var, () =>
  {
    ilg.EmitFor(j_var, 0-km.ymin, w_var, () =>
    {
      ilg.Emit(OpCodes.Ldloc, result_var);
      ilg.Emit(OpCodes.Ldloc, i_var);
      ilg.Emit(OpCodes.Ldloc, j_var);
      var ki = new KernelInliningILInstructionVisitor<T>(ilg, i_var, j_var); // самое интересное - вот тут!
      new ILReaderkernel.Method).Accept(ki);

      ilg.Emit(OpCodes.Call, typeof(T[,]).GetMethod("Set", new Type[] { typeof(int), typeof(int), typeof(T) }));
    });
  });

  ilg.Emit(OpCodes.Ldloc, result_var);
  ilg.Emit(OpCodes.Ret);

  var inlined = (Func<object, T[,], T[,]>)dm.CreateDelegate(typeof(Func<object, T[,], T[,]>));
  return (data) => inlined(kernel.Target, data);
}

В целом — ничего военного: метод просто порождает примерно такой же MSIL-код, который генерирует для PerfectFourNeighborAverage() компилятор C#:
— вычисляем размеры исходного массива
— создаём целевой массив такого же размера
— уменьшаем переменные "ширины" и "высоты" на соответствующие размеры ядра фильтра
— строим два вложенных цикла.
Для упрощения порождения кода написан класс ILWriter с парой хелпер-методов вроде EmitFor и EmitIncrease, которые прячут под капот рутинную работу по назначению меток и типовым последовательностям загрузки переменной/загрузки слагаемого/сложению/сохранению.

Интересная часть — встраивание кода ядра в код нашего метода:

      var ki = new KernelInliningILInstructionVisitor<T>(ilg, i_var, j_var); 
      new ILReader(kernel.Method).Accept(ki);

Она основана на пакете ILReader, который позволяет выполнять обход инструкций MSIL-потока.
Класс KernelInliningILInstructionVisitor реализует следующую стратегию обхода:

1. Все инструкции копируются в переданный ему ILGenerator.
   
2. Каждая скопированная инструкция снабжается меткой (ilg.MarkLabel()), и её смещение запоминается во внутренней таблице. Сделано это для того, чтобы аккуратно скопировать различные branch-инструкции: при чтении потока меток нет, есть только смещения.
   
3. Инструкция ret выбрасывается при копировании; результат метода просто остаётся на стеке — в точности так, как было бы после реального вызова
   
4. Делается ещё один трюк: замена операции.
   В первоначальном варианте кода метода Select в kernel передавалась ссылка на IRelativeAccess2d. В принципе, можно было бы её так и оставить — сконструировать локальную переменную, обновлять её поля на каждой итерации, и заменить все инструкции ldard.1 на соответствующий ldloc. Пусть дальше JIT разбирается.
   Но из врождённой паранойи и недоверию к JIT, я заменяю вызовы метода IRelativeAccess2d<T>.get_Item на вызовы метода T[,].Get().

При этом нам известно, что в момент вызова у нас в стеке лежат значения arg.1, dx, dy. Перед вызовом их надо заменить на data, i+dx, j+dy.
Волшебным образом data у нас как раз лежит в arg.1 генерируемого метода, поэтому его можно не трогать. А для того, чтобы заменить аргументы на стеке, в метод эмиттится следующая последовательность инструкций:

Target.Emit(OpCodes.Stloc, dy); // заводим ещё одну переменную для временного хранения dy. стек после операции: [data, dx].
Target.Emit(OpCodes.Ldloc, i); // [data, dx, i]
Target.Emit(OpCodes.Add);      // [data, i+dx]
Target.Emit(OpCodes.Ldloc, j); // [data, i+dx, j]
Target.Emit(OpCodes.Ldloc, dy); // [data, i+dx, j, dy]
Target.Emit(OpCodes.Add);       // [data, i+dx, j+dy]
Target.Emit(OpCodes.Call, _arrGetter); // [data[i+dx, j+dy]]

Последнее упражнение — привязка к контексту. Метод в kernel может быть любым, в том числе и методом экземпляра (в нашем случае так и есть, несмотря на то, что замыкать нечего). Его код запросто может обратиться к this, поэтому нельзя просто встроить его as is. Поэтому у порождаемого DynamicMethod не один параметр, а два — первым выступает Target делегата, переданного в Kernel. Поэтому из GenerateFilter возвращается не сам DynamicMethod, а локальная функция, добавляющая к data оригинальный Target:

  return (data) => inlined(kernel.Target, data);

Теперь метод Select выглядит до неприличия простым:

public static T[,] Select<T>(this T[,] source, Kernel<T> kernel) => GenerateFilter(kernel)(source);

Ну, а теперь — к десерту:

// * Summary *
BenchmarkDotNet=v0.10.14, OS=Windows 10.0.15063.1088 (1703/CreatorsUpdate/Redstone2)
Intel Core i7-6600U CPU 2.60GHz (Skylake), 1 CPU, 4 logical and 2 physical cores
Frequency=2742190 Hz, Resolution=364.6720 ns, Timer=TSC
  [Host]       : .NET Framework 4.6.1 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2650.0
  LegacyJitX86 : .NET Framework 4.6.1 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.2650.0

Job=LegacyJitX86  Jit=LegacyJit  Platform=X86
Runtime=Clr

   Method |     Mean |     Error |    StdDev | Scaled | ScaledSD |     Gen 0 |    Gen 1 |    Gen 2 | Allocated |
--------- |---------:|----------:|----------:|-------:|---------:|----------:|---------:|---------:|----------:|
  Perfect | 10.42 ms | 0.2342 ms | 0.2505 ms |   1.00 |     0.00 |  156.2500 | 156.2500 | 156.2500 |   3.81 MB |
 SafeLinq | 10.50 ms | 0.2057 ms | 0.2368 ms |   1.01 |     0.03 |  156.2500 | 156.2500 | 156.2500 |   3.81 MB |
     Linq | 30.95 ms | 0.6184 ms | 1.0160 ms |   2.97 |     0.12 | 9687.5000 | 250.0000 | 250.0000 |  22.81 MB |

Итого, быстродействие порождённого метода — в пределах стат.погрешности по отношению к "идеальному" варианту!
Даже кэшировать порождённый динамический метод нам не нужно — при таких размерах массивов генерация и JIT занимает пренебрежимо малое время.

Но стоит ли останавливаться на достигнутом? В следующей серии мы посмотрим, можно ли выполнить from d in data select (d[-1, 0] + d[1, 0] + d[0, 1] + d[0, -1]) / 4 быстрее, чем "простейший двойной цикл с одним оператором внутри", который "Пишется "на автомате", почти не думая, так как подобное любой опытный программист писал много раз."