Сообщение 2D-Linq и оптимизация цифровых фильтров - 3 от 29.06.2018 12:40
Изменено 29.06.2018 12:41 Sinclair
2D-Linq и оптимизация цифровых фильтров - 3
Ну, вот и пятница.
Для начала, напустим интриги:
Вот код метода UnsafeLinq:
Всё то же самое!
Чёрт возьми, Холмс, как? Linq оказался вдвое быстрее "идеального варианта"...
А вот, примерно, так:
Внимательный взгляд, конечно же, увидит, что у делегатов Filter и Kernel теперь появилось два параметра. Это отражение развития, которое идёт в параллельной ветке обсуждения, где тип выходного массива не обязательно совпадает с типом входного.
Кроме того, в отличие от GenerateFilter, новая версия метода уже не-generic. В той версии C#, которая у меня, невозможно выразить констреинт "тип, от которого можно взять managed pointer", поэтому пришлось гвоздями прибить метод к int-у.
Тем не менее, с задачей с4-фильтрации исходного массива метод справился на ура.
Мы добавляем немного чёрной магии при помощи pinned переменных — результат сразу сохраняется в такой переменной, а входные данные приходится скопировать из arg.1 в переменную source.
В цикле — развлекаемся адресной арифметикой, зная внутреннее устройство двумерных массивов в CLR.
Таким образом, мы избегаем проверок на выход за границы массива, которые, судя по показаниям профайлера, съедают примерно 50% времени работы "безопасной" версии метода.
Что характерно, пользовательский код остаётся вполне себе Safe — всё вуду происходит только "под капотом".
Замена вызова при инлайне происходит тоже чуточку посложнее:
Понятно, что программист-фанатик может написать версию этого кода и на C#, но это — скользкий путь: в коде всё меньше остаётся от исходной задачи, и всё больше добавляется подробностей реализации.
Всё больше шансов запороть программу, внося изменения (например, меняя ядро фильтра), всё больше опасность разрушить память, вылетая за границы массива.
Итак, принципиальная возможность "обогнать" ручное выпиливание циклов при помощи красивого Linq — продемонстрирована.
Для начала, напустим интриги:
BenchmarkDotNet=v0.10.14, OS=Windows 10.0.15063.1155 (1703/CreatorsUpdate/Redstone2)
Intel Core i7-6600U CPU 2.60GHz (Skylake), 1 CPU, 4 logical and 2 physical cores
Frequency=2742189 Hz, Resolution=364.6722 ns, Timer=TSC
[Host] : .NET Framework 4.6.1 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2671.0
LegacyJitX86 : .NET Framework 4.6.1 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.2671.0
Job=LegacyJitX86 Jit=LegacyJit Platform=X86
Runtime=Clr
Method | Mean | Error | StdDev | Scaled | Gen 0 | Gen 1 | Gen 2 | Allocated |
----------- |---------:|----------:|----------:|-------:|---------:|---------:|---------:|----------:|
UnsafeLinq | 4.256 ms | 0.0849 ms | 0.0978 ms | 0.43 | 570.3125 | 375.0000 | 375.0000 | 3.83 MB |
Perfect | 9.989 ms | 0.1198 ms | 0.1120 ms | 1.00 | 156.2500 | 156.2500 | 156.2500 | 3.81 MB |Вот код метода UnsafeLinq:
public int[,] UnsafeLinq() => from d in data select (d[-1, 0] + d[1, 0] + d[0, -1] + d[0, 1]) / 4;Всё то же самое!
Чёрт возьми, Холмс, как? Linq оказался вдвое быстрее "идеального варианта"...
А вот, примерно, так:
public static Filter<int, int> GenerateUnsafeFilter(Kernel<int, int> kernel)
{
var km = KernelMeasure.Measure(kernel);
var ab = AssemblyBuilder.DefineDynamicAssembly(new AssemblyName("FixedTest"), AssemblyBuilderAccess.RunAndCollect);
var tb = ab.DefineDynamicModule("FixedTest", "FixedTest.dll").DefineType("Filter." + kernel.Method.Name, TypeAttributes.Class | TypeAttributes.Public);
var dm = tb.DefineMethod("Filter", MethodAttributes.HideBySig | MethodAttributes.Public | MethodAttributes.Static, typeof(int[,]), new Type[] { typeof(object), typeof(int[,]) });
var ilg = dm.GetILGenerator();
var target = ilg.DeclareLocal(typeof(int[,]), true);
var source = ilg.DeclareLocal(typeof(int[,]), true); // a replica of the arg1, to force the GC pinning
var psource = ilg.DeclareLocal(typeof(int*));
var ptarget = ilg.DeclareLocal(typeof(int*));
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));
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(int[,]).GetMethod("GetLength", new Type[] { typeof(int) }));
ilg.Emit(OpCodes.Stloc, h_var);
ilg.Emit(OpCodes.Ldarg_1); // source
ilg.Emit(OpCodes.Ldc_I4_1);// 0
ilg.Emit(OpCodes.Call, typeof(int[,]).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(int[,]).GetConstructor(new Type[] { typeof(int), typeof(int) }));
ilg.Emit(OpCodes.Stloc, target);
ilg.Emit(OpCodes.Ldloc, w_var);
ilg.Emit(OpCodes.Stloc, W_var);
ilg.EmitIncrease(h_var, -km.ymax);
ilg.EmitIncrease(w_var, -km.xmax);
ilg.Emit(OpCodes.Ldarg_1);
ilg.Emit(OpCodes.Stloc_S, source); // pinning the source array
ilg.EmitFor(i_var, 0 - km.xmin, h_var, () =>
{
ilg.Emit(OpCodes.Ldloc, source);
ilg.Emit(OpCodes.Ldloc, i_var);
ilg.Emit(OpCodes.Ldc_I4, -km.ymin);
ilg.Emit(OpCodes.Call, _arrayAddressGetter);
ilg.Emit(OpCodes.Conv_U);
ilg.Emit(OpCodes.Stloc, psource); // psource = &source[i, lb];
ilg.Emit(OpCodes.Ldloc, target);
ilg.Emit(OpCodes.Ldloc, i_var);
ilg.Emit(OpCodes.Ldc_I4, -km.ymin);
ilg.Emit(OpCodes.Call, _arrayAddressGetter);
ilg.Emit(OpCodes.Conv_U);
ilg.Emit(OpCodes.Stloc, ptarget); // ptarget = &target[i, lb]
ilg.EmitFor(j_var, 0 - km.ymin, w_var, () =>
{
ilg.Emit(OpCodes.Ldloc_S, ptarget); // :ptarget
var usilv = new UnsafeInliningILInstructionVisitor(ilg, i_var, j_var, psource, W_var);
new ILReader(kernel.Method).Accept(usilv);
//EmitDebug<int>(ilg);
ilg.Emit(OpCodes.Stind_I4);
ilg.EmitIncrease(psource, 4); // psource++
ilg.EmitIncrease(ptarget, 4); // ptarget++
});
});
ilg.Emit(OpCodes.Ldloc, target);
ilg.Emit(OpCodes.Ret);
var type = tb.CreateType();
var mi = type.GetMethod("Filter");
var inlined = (Func<object, int[,], int[,]>)mi.CreateDelegate(typeof(Func<object, int[,], int[,]>));
int[,] filter(int[,] data) => inlined(kernel.Target, data);
return filter;
}Внимательный взгляд, конечно же, увидит, что у делегатов Filter и Kernel теперь появилось два параметра. Это отражение развития, которое идёт в параллельной ветке обсуждения, где тип выходного массива не обязательно совпадает с типом входного.
Кроме того, в отличие от GenerateFilter, новая версия метода уже не-generic. В той версии C#, которая у меня, невозможно выразить констреинт "тип, от которого можно взять managed pointer", поэтому пришлось гвоздями прибить метод к int-у.
Тем не менее, с задачей с4-фильтрации исходного массива метод справился на ура.
Мы добавляем немного чёрной магии при помощи pinned переменных — результат сразу сохраняется в такой переменной, а входные данные приходится скопировать из arg.1 в переменную source.
В цикле — развлекаемся адресной арифметикой, зная внутреннее устройство двумерных массивов в CLR.
Таким образом, мы избегаем проверок на выход за границы массива, которые, судя по показаниям профайлера, съедают примерно 50% времени работы "безопасной" версии метода.
Что характерно, пользовательский код остаётся вполне себе Safe — всё вуду происходит только "под капотом".
Замена вызова при инлайне происходит тоже чуточку посложнее:
protected override void EmitSourceAccessCode()
{
// Opcode Stack state (head left)
// dy, dx, psource, ...
Target.Emit(OpCodes.Ldloc, _w); // w, dy, dx, psource
Target.Emit(OpCodes.Mul); // w*dy, dx, psource, ...
Target.Emit(OpCodes.Add); // w*dy+dx, psource, ...
Target.Emit(OpCodes.Ldc_I4_4); // 4, dy + w*dx, psource, ...
Target.Emit(OpCodes.Mul); // 4 * (w*dy + dx), psource, ...
Target.Emit(OpCodes.Add); // psource + 4 * dy + 4*w*dx, ...
Target.Emit(OpCodes.Ldind_I4); // psource[dy*w+dx]
}Понятно, что программист-фанатик может написать версию этого кода и на C#, но это — скользкий путь: в коде всё меньше остаётся от исходной задачи, и всё больше добавляется подробностей реализации.
Всё больше шансов запороть программу, внося изменения (например, меняя ядро фильтра), всё больше опасность разрушить память, вылетая за границы массива.
Итак, принципиальная возможность "обогнать" ручное выпиливание циклов при помощи красивого Linq — продемонстрирована.
2D-Linq и оптимизация цифровых фильтров - 3
Ну, вот и пятница.
Для начала, напустим интриги:
Вот код метода UnsafeLinq:
Всё то же самое!
Чёрт возьми, Холмс, как? Linq оказался вдвое быстрее "идеального варианта"...
А вот, примерно, так:
Внимательный взгляд, конечно же, увидит, что у делегатов Filter и Kernel теперь появилось два параметра. Это отражение развития, которое идёт в параллельной ветке обсуждения, где тип выходного массива не обязательно совпадает с типом входного.
Кроме того, в отличие от GenerateFilter, новая версия метода уже не-generic. В той версии C#, которая у меня, невозможно выразить констреинт "тип, от которого можно взять managed pointer", поэтому пришлось гвоздями прибить метод к int-у.
Тем не менее, с задачей с4-фильтрации исходного массива метод справился на ура.
Мы добавляем немного чёрной магии при помощи pinned переменных — результат сразу сохраняется в такой переменной, а входные данные приходится скопировать из arg.1 в переменную source.
В цикле — развлекаемся адресной арифметикой, зная внутреннее устройство двумерных массивов в CLR.
Таким образом, мы избегаем проверок на выход за границы массива, которые, судя по показаниям профайлера, съедают примерно 50% времени работы "безопасной" версии метода.
Что характерно, пользовательский код остаётся вполне себе Safe — всё вуду происходит только "под капотом".
Замена вызова при инлайне происходит тоже чуточку посложнее:
Понятно, что программист-фанатик может написать версию этого кода и на C#, но это — скользкий путь: в коде всё меньше остаётся от исходной задачи, и всё больше добавляется подробностей реализации.
Всё больше шансов запороть программу, внося изменения (например, меняя ядро фильтра), всё больше опасность разрушить память, вылетая за границы массива.
Итак, принципиальная возможность "обогнать" ручное выпиливание циклов при помощи красивого Linq — продемонстрирована.
В следующей серии я попробую показать, как Linq офигенен для решения более сложных задач
Для начала, напустим интриги:
BenchmarkDotNet=v0.10.14, OS=Windows 10.0.15063.1155 (1703/CreatorsUpdate/Redstone2)
Intel Core i7-6600U CPU 2.60GHz (Skylake), 1 CPU, 4 logical and 2 physical cores
Frequency=2742189 Hz, Resolution=364.6722 ns, Timer=TSC
[Host] : .NET Framework 4.6.1 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2671.0
LegacyJitX86 : .NET Framework 4.6.1 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.2671.0
Job=LegacyJitX86 Jit=LegacyJit Platform=X86
Runtime=Clr
Method | Mean | Error | StdDev | Scaled | Gen 0 | Gen 1 | Gen 2 | Allocated |
----------- |---------:|----------:|----------:|-------:|---------:|---------:|---------:|----------:|
UnsafeLinq | 4.256 ms | 0.0849 ms | 0.0978 ms | 0.43 | 570.3125 | 375.0000 | 375.0000 | 3.83 MB |
Perfect | 9.989 ms | 0.1198 ms | 0.1120 ms | 1.00 | 156.2500 | 156.2500 | 156.2500 | 3.81 MB |Вот код метода UnsafeLinq:
public int[,] UnsafeLinq() => from d in data select (d[-1, 0] + d[1, 0] + d[0, -1] + d[0, 1]) / 4;Всё то же самое!
Чёрт возьми, Холмс, как? Linq оказался вдвое быстрее "идеального варианта"...
А вот, примерно, так:
public static Filter<int, int> GenerateUnsafeFilter(Kernel<int, int> kernel)
{
var km = KernelMeasure.Measure(kernel);
var ab = AssemblyBuilder.DefineDynamicAssembly(new AssemblyName("FixedTest"), AssemblyBuilderAccess.RunAndCollect);
var tb = ab.DefineDynamicModule("FixedTest", "FixedTest.dll").DefineType("Filter." + kernel.Method.Name, TypeAttributes.Class | TypeAttributes.Public);
var dm = tb.DefineMethod("Filter", MethodAttributes.HideBySig | MethodAttributes.Public | MethodAttributes.Static, typeof(int[,]), new Type[] { typeof(object), typeof(int[,]) });
var ilg = dm.GetILGenerator();
var target = ilg.DeclareLocal(typeof(int[,]), true);
var source = ilg.DeclareLocal(typeof(int[,]), true); // a replica of the arg1, to force the GC pinning
var psource = ilg.DeclareLocal(typeof(int*));
var ptarget = ilg.DeclareLocal(typeof(int*));
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));
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(int[,]).GetMethod("GetLength", new Type[] { typeof(int) }));
ilg.Emit(OpCodes.Stloc, h_var);
ilg.Emit(OpCodes.Ldarg_1); // source
ilg.Emit(OpCodes.Ldc_I4_1);// 0
ilg.Emit(OpCodes.Call, typeof(int[,]).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(int[,]).GetConstructor(new Type[] { typeof(int), typeof(int) }));
ilg.Emit(OpCodes.Stloc, target);
ilg.Emit(OpCodes.Ldloc, w_var);
ilg.Emit(OpCodes.Stloc, W_var);
ilg.EmitIncrease(h_var, -km.ymax);
ilg.EmitIncrease(w_var, -km.xmax);
ilg.Emit(OpCodes.Ldarg_1);
ilg.Emit(OpCodes.Stloc_S, source); // pinning the source array
ilg.EmitFor(i_var, 0 - km.xmin, h_var, () =>
{
ilg.Emit(OpCodes.Ldloc, source);
ilg.Emit(OpCodes.Ldloc, i_var);
ilg.Emit(OpCodes.Ldc_I4, -km.ymin);
ilg.Emit(OpCodes.Call, _arrayAddressGetter);
ilg.Emit(OpCodes.Conv_U);
ilg.Emit(OpCodes.Stloc, psource); // psource = &source[i, lb];
ilg.Emit(OpCodes.Ldloc, target);
ilg.Emit(OpCodes.Ldloc, i_var);
ilg.Emit(OpCodes.Ldc_I4, -km.ymin);
ilg.Emit(OpCodes.Call, _arrayAddressGetter);
ilg.Emit(OpCodes.Conv_U);
ilg.Emit(OpCodes.Stloc, ptarget); // ptarget = &target[i, lb]
ilg.EmitFor(j_var, 0 - km.ymin, w_var, () =>
{
ilg.Emit(OpCodes.Ldloc_S, ptarget); // :ptarget
var usilv = new UnsafeInliningILInstructionVisitor(ilg, i_var, j_var, psource, W_var);
new ILReader(kernel.Method).Accept(usilv);
//EmitDebug<int>(ilg);
ilg.Emit(OpCodes.Stind_I4);
ilg.EmitIncrease(psource, 4); // psource++
ilg.EmitIncrease(ptarget, 4); // ptarget++
});
});
ilg.Emit(OpCodes.Ldloc, target);
ilg.Emit(OpCodes.Ret);
var type = tb.CreateType();
var mi = type.GetMethod("Filter");
var inlined = (Func<object, int[,], int[,]>)mi.CreateDelegate(typeof(Func<object, int[,], int[,]>));
int[,] filter(int[,] data) => inlined(kernel.Target, data);
return filter;
}Внимательный взгляд, конечно же, увидит, что у делегатов Filter и Kernel теперь появилось два параметра. Это отражение развития, которое идёт в параллельной ветке обсуждения, где тип выходного массива не обязательно совпадает с типом входного.
Кроме того, в отличие от GenerateFilter, новая версия метода уже не-generic. В той версии C#, которая у меня, невозможно выразить констреинт "тип, от которого можно взять managed pointer", поэтому пришлось гвоздями прибить метод к int-у.
Тем не менее, с задачей с4-фильтрации исходного массива метод справился на ура.
Мы добавляем немного чёрной магии при помощи pinned переменных — результат сразу сохраняется в такой переменной, а входные данные приходится скопировать из arg.1 в переменную source.
В цикле — развлекаемся адресной арифметикой, зная внутреннее устройство двумерных массивов в CLR.
Таким образом, мы избегаем проверок на выход за границы массива, которые, судя по показаниям профайлера, съедают примерно 50% времени работы "безопасной" версии метода.
Что характерно, пользовательский код остаётся вполне себе Safe — всё вуду происходит только "под капотом".
Замена вызова при инлайне происходит тоже чуточку посложнее:
protected override void EmitSourceAccessCode()
{
// Opcode Stack state (head left)
// dy, dx, psource, ...
Target.Emit(OpCodes.Ldloc, _w); // w, dy, dx, psource
Target.Emit(OpCodes.Mul); // w*dy, dx, psource, ...
Target.Emit(OpCodes.Add); // w*dy+dx, psource, ...
Target.Emit(OpCodes.Ldc_I4_4); // 4, dy + w*dx, psource, ...
Target.Emit(OpCodes.Mul); // 4 * (w*dy + dx), psource, ...
Target.Emit(OpCodes.Add); // psource + 4 * dy + 4*w*dx, ...
Target.Emit(OpCodes.Ldind_I4); // psource[dy*w+dx]
}Понятно, что программист-фанатик может написать версию этого кода и на C#, но это — скользкий путь: в коде всё меньше остаётся от исходной задачи, и всё больше добавляется подробностей реализации.
Всё больше шансов запороть программу, внося изменения (например, меняя ядро фильтра), всё больше опасность разрушить память, вылетая за границы массива.
Итак, принципиальная возможность "обогнать" ручное выпиливание циклов при помощи красивого Linq — продемонстрирована.
В следующей серии я попробую показать, как Linq офигенен для решения более сложных задач
Автор: Pavel Dvorkin
Дата: 29.06.18
, несмотря на сомнения скептиков.Дата: 29.06.18