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 pinningvar 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); // :ptargetvar 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 — всё вуду происходит только "под капотом".
Замена вызова при инлайне происходит тоже чуточку посложнее:
Понятно, что программист-фанатик может написать версию этого кода и на C#, но это — скользкий путь: в коде всё меньше остаётся от исходной задачи, и всё больше добавляется подробностей реализации.
Всё больше шансов запороть программу, внося изменения (например, меняя ядро фильтра), всё больше опасность разрушить память, вылетая за границы массива.
Итак, принципиальная возможность "обогнать" ручное выпиливание циклов при помощи красивого Linq — продемонстрирована.
В следующей серии я попробую показать, как Linq офигенен для решения более сложных задач
Здравствуйте, Sinclair, Вы писали:
S>Итак, принципиальная возможность "обогнать" ручное выпиливание циклов при помощи красивого Linq — продемонстрирована. S>В следующей серии я попробую показать, как Linq офигенен для решения более сложных задач
Я лениво слежу за этой серией постов и комментариев про linq и фильтры, но не могу понять, причем здесь linq? Вся суть оптимизаций в том, что вручную генерится более производительный il-код без
избыточных проверок + некоторая микрооптимизация. Для чего здесь принципиально нужен linq?
Кодом людям нужно помогать!
Re[2]: 2D-Linq и оптимизация цифровых фильтров - 3
Здравствуйте, Sharov, Вы писали: S>Я лениво слежу за этой серией постов и комментариев про linq и фильтры, но не могу понять, причем здесь linq? Вся суть оптимизаций в том, что вручную генерится более производительный il-код без S>избыточных проверок + некоторая микрооптимизация. Для чего здесь принципиально нужен linq?
Для того, чтобы программист-прикладник не занимался микрооптимизациями.
Чтобы он мог писать понятный код вместо лапши.
Лапшу оправдывают обычно тем, что "ну так нам же производительность важна".
Показываем — нет, производительность у лапши не лучше.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Для того, чтобы программист-прикладник не занимался микрооптимизациями. S>Чтобы он мог писать понятный код вместо лапши. S>Лапшу оправдывают обычно тем, что "ну так нам же производительность важна". S>Показываем — нет, производительность у лапши не лучше.
Я еще больше с целью этих постов запутался, ибо выше лапша и есть. Это вероятно и подразумевалось, т.е. и было целью топиков....
Если я опять же не ошибаюсь, то судя по таблице выше, у лапши производительность в два раза лучше, это, по-моему, стоит микрооптимизаций, даже если оне ведут к лапше.
Кодом людям нужно помогать!
Re[4]: 2D-Linq и оптимизация цифровых фильтров - 3
Здравствуйте, Sharov, Вы писали: S>Я еще больше с целью этих постов запутался, ибо выше лапша и есть. Это вероятно и подразумевалось, т.е. и было целью топиков....
Вижу, я плохо объясняю.
Вся "лапша" — в моём коде.
В коде прикладного программиста ничего этого нет.
У него — просто
from d in data select (d[-1, 0] + d[1, 0] + d[0, -1] + d[0, 1]) / 4;
Вся чёрная магия делается в недрах библиотеки Array2d.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: 2D-Linq и оптимизация цифровых фильтров - 3
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Sharov, Вы писали: S>>Я еще больше с целью этих постов запутался, ибо выше лапша и есть. Это вероятно и подразумевалось, т.е. и было целью топиков.... S>Вижу, я плохо объясняю. S>Вся "лапша" — в моём коде. S>В коде прикладного программиста ничего этого нет. S>У него — просто S>
S>from d in data select (d[-1, 0] + d[1, 0] + d[0, -1] + d[0, 1]) / 4;
S>
S>Вся чёрная магия делается в недрах библиотеки Array2d.
Значит я все правильно понял. Лапша оправдана, ибо дает 2x производительности и если производительность критична.
Кодом людям нужно помогать!
Re[6]: 2D-Linq и оптимизация цифровых фильтров - 3
S>Значит я все правильно понял. Лапша оправдана, ибо дает 2x производительности и если производительность критична.
Ровно наоборот
Лапша — это тот код, который мне привели в качестве образца универсальности и производительности.
Потому что там решение задачи замусорено деталями исполнения.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, gandjustas, Вы писали:
G>А как насчет Span<T> и Memory<T><br />
<span class='lineQuote level1'>G></span>
Ну, единственное, чем может помочь Span<T> — это потенциальным устраненим проверок выхода за пределы строки во внутреннем цикле. В экспериментальных билдах эта оптимизация есть.
Остаётся найти, в каком месте Span<T> можно проинициализировать в адрес i-той строки массива. Проверкой выхода за границы в этом случае можно пренебречь — у нас проверок станет O(N) вместо O(N*M), причём для интересующих нас случаев M лежит в диапазоне 500-4000.
Сходу — не нашёл.
В принципе, если совместить Span<T> с инлайнингом експрешшнов (TBD), то можно получить вполне приемлемый gain.
Но тут Павел подкинул задачку
на порядок интереснее:
1. Во-первых, не один массив, а два
2. Во-вторых, есть подзадача с рекуррентным определением. Она сулит феерические впечатления при поисках возможности параллелизации.
Пока что нахожусь на этапе мучительных поисков синтаксиса.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: 2D-Linq и оптимизация цифровых фильтров - 3
Здравствуйте, Sinclair, Вы писали:
S>Вся "лапша" — в моём коде. S>В коде прикладного программиста ничего этого нет. S>У него — просто S>from d in data select (d[-1, 0] + d[1, 0] + d[0, -1] + d[0, 1]) / 4;
Не совсем понял, как это будет вызываться. Что тут data?
Вы сделаете кучу оптимизированных методов, которые будут использоваться "прикладными" программистами? Или кто будет писать эти методы с лапшой? Где будет находится валидация, что если я, прикладной, напишу d[-2,0]?
Я так понял, что вы добились в 2 раза большей производительности. Но я пока не понимаю как (в IL ни бум бум). Скажите, эта оптимизация возможна только для linq? Или linq используется только для читаемости? У меня просто подозрение, что заголовок желтый и к linq это никакого отношения не имеет.
---
ПроГLамеры объединяйтесь..
Re[6]: 2D-Linq и оптимизация цифровых фильтров - 3
Здравствуйте, Sinatr, Вы писали:
S>Здравствуйте, Sinclair, Вы писали:
S>>Вся "лапша" — в моём коде. S>>В коде прикладного программиста ничего этого нет. S>>У него — просто S>>from d in data select (d[-1, 0] + d[1, 0] + d[0, -1] + d[0, 1]) / 4;
S>Не совсем понял, как это будет вызываться. Что тут data?
примерно так:
var data = new int[3000, 4000];
// init data with the contentvar filtered = from d in data select (d[-1, 0] + d[1, 0] + d[0, -1] + d[0, 1]) / 4; // C4-filtering
S>Вы сделаете кучу оптимизированных методов, которые будут использоваться "прикладными" программистами? Или кто будет писать эти методы с лапшой? Где будет находится валидация, что если я, прикладной, напишу d[-2,0]?
Валидация выполняется внутри кода метода Select. Если передать внутри выражения ядра d[-2,0], то вызываться ядро будет начиная с третьей строки исходного массива (см. KernelMeasure.Measure(kernel) ). S>Я так понял, что вы добились в 2 раза большей производительности. Но я пока не понимаю как (в IL ни бум бум). Скажите, эта оптимизация возможна только для linq? Или linq используется только для читаемости? У меня просто подозрение, что заголовок желтый и к linq это никакого отношения не имеет.
Linq используется для того, чтобы разделить стратегю исполнения и сам "запрос".
Если я напишу вручную двойной цикл, то валидацию размеров фильтра и оптимизацию исполнения мне тоже придётся писать вручную.
А если я пишу его в стиле Linq, то за меня всё это делает библиотека.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[2]: 2D-Linq и оптимизация цифровых фильтров - 3
Здравствуйте, Sharov, Вы писали:
S>Я лениво слежу за этой серией постов и комментариев про linq и фильтры, но не могу понять, причем здесь linq? Вся суть оптимизаций в том, что вручную генерится более производительный il-код
Генерится не более производительный, а такой же, а весь этот трюк для обхода делегата.
S>Для чего здесь принципиально нужен linq?
Судя по длине показанных костылей даже для простейших случаев, Linq не нужен. ))
Для чего-то более-менее сложного показанный подход не применим в принципе, т.е. все приведённые рассуждения превращаются в тыкву.
Re[7]: 2D-Linq и оптимизация цифровых фильтров - 3
Здравствуйте, Sinclair, Вы писали:
S>Если я напишу вручную двойной цикл, то валидацию размеров фильтра и оптимизацию исполнения мне тоже придётся писать вручную. S>А если я пишу его в стиле Linq, то за меня всё это делает библиотека.
Напиши один раз "библиотечный" индексер и пользуйся.
Технология Linq тут не при чём.
Заголовок желтушный.
Re[8]: 2D-Linq и оптимизация цифровых фильтров - 3
Здравствуйте, vdimas, Вы писали: V>Напиши один раз "библиотечный" индексер и пользуйся.
Жду пример кода C4 фильтрации на основе "библиотечного" индексера.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[9]: 2D-Linq и оптимизация цифровых фильтров - 3
Здравствуйте, Sinclair, Вы писали: V>>Напиши один раз "библиотечный" индексер и пользуйся. S>Жду пример кода C4 фильтрации на основе "библиотечного" индексера.
А самому уже не?
Эмуляция 2D массива через 1D
using System;
using System.Diagnostics;
namespace ConsoleApp1
{
interface IArray2dD<T>
{
T this[int dx, int dy] { get; set; }
int dx { get; }
int dy { get; }
}
struct Array2D<T> : IArray2dD<T>
{
private readonly T[,] _array;
public Array2D(int dx, int dy) { _array = new T[dx, dy]; }
public T this[int x, int y]
{
get => _array[x, y];
set => _array[x, y] = value;
}
public int dx { get { return _array.GetLength(0); } }
public int dy { get { return _array.GetLength(1); } }
}
struct Array2DEmu<T> : IArray2dD<T>
{
private readonly T[] _array;
public int dx { get; }
public int dy { get; }
public Array2DEmu(int dx, int dy)
{
this.dx = dx;
this.dy = dy;
_array = new T[dx * dy];
}
public T this[int x, int y]
{
get => _array[dx * y + x];
set => _array[dx * y + x] = value;
}
}
interface IFactory<T>
{
T create();
}
class Program
{
static void Test<T, TFactory>()
where T : struct, IArray2dD<int>
where TFactory : struct, IFactory<T>
{
T array = default(TFactory).create();
int sum = 0;
var rnd = new Random((int)DateTime.Now.TimeOfDay.Ticks);
for (int x = 0; x < array.dx; x++)
for (int y = 0; y < array.dy; y++)
array[x, y] = rnd.Next();
Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 0; i < 1000; i++)
{
for (int x = 0, dx = array.dx; x < dx; x++)
for (int y = 0, dy= array.dy; y < dy; y++)
sum += array[x, y];
}
sw.Stop();
Console.WriteLine("Elapsed(ms)={0}", sw.Elapsed);
}
struct NativeArrayFactory<T> : IFactory<Array2D<T>>
{
public Array2D<T> create()
{
return new Array2D<T>(1000, 1000);
}
}
struct ArrayEmuFactory<T> : IFactory<Array2DEmu<T>>
{
public Array2DEmu<T> create()
{
return new Array2DEmu<T>(1000, 1000);
}
}
static void Main(string[] args)
{
Console.Write("Native 2D array: ");
Test<Array2D<int>, NativeArrayFactory<int>>();
Console.Write("Emulated 2D array: ");
Test<Array2DEmu<int>, ArrayEmuFactory<int>>();
}
}
}
Здравствуйте, Qbit86, Вы писали:
V>>Native 2D array: Elapsed(ms)=00:00:00.7817720 V>>Emulated 2D array: Elapsed(ms)=00:00:00.6798358 Q>Безотносительно к топику: в 2k18 микробенчмаркать через Stopwatch уже моветон...
Через Stopwatch было моветоном бенчмаркать с самого начала и я подробно объяснял — почему.
Использование PerformanceCounter-ов — это же само по себе уже признак глубокого нубства.
Но некоторые особо упоротые из здешней тусовки не поняли и половины, как обычно.
Бо религия.
Поэтому — лично мне до фени.
Запусти тесты по кругу, сними статистику, если тебе это интересно.
Re[9]: 2D-Linq и оптимизация цифровых фильтров - 3
Здравствуйте, Sinclair, Вы писали: S>Здравствуйте, vdimas, Вы писали: V>>Напиши один раз "библиотечный" индексер и пользуйся. S>Жду пример кода C4 фильтрации на основе "библиотечного" индексера.
Вдогонку, расширил пример на новомодный Span (который сам по себе уже абстрактный индексер).
Заодно из Span<T> легко получить unsafe, поэтому прогнал и его тоже.
Выходит, он удобен сугубо для получения slice-ов из произвольного участка managed или unmanaged памяти, разве что с последующим приведением к unsafe. ))
Дополнительный код
unsafe readonly ref struct SpanIndexer2D<T>
{
public Span<T> array { get; }
public int dx { get; }
public int dy { get; }
public SpanIndexer2D(int dx, int dy)
{
this.dx = dx;
this.dy = dy;
array = new T[dx * dy];
}
public T this[int x, int y]
{
get => array[dx * y + x];
set => array[dx * y + x] = value;
}
}
unsafe readonly ref struct UnsafeIntArray2D
{
private readonly int* _array;
public int dx { get; }
public int dy { get; }
public UnsafeIntArray2D(int* array, int dx, int dy)
{
this.dx = dx;
this.dy = dy;
_array = array;
}
public int this[int x, int y]
{
get => _array[dx * y + x];
set => _array[dx * y + x] = value;
}
}
//...static void SpanTest()
{
int dx = 1000, dy = 1000;
var array = new SpanIndexer2D<int>(dx, dy);
int sum = 0;
var rnd = new Random((int)DateTime.Now.TimeOfDay.Ticks);
for (int x = 0; x < array.dx; x++)
for (int y = 0; y < array.dy; y++)
array[x, y] = rnd.Next();
Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 0; i < 1000; i++)
{
for (int x = 0; x < dx; x++)
for (int y = 0; y < dy; y++)
sum += array[x, y];
}
sw.Stop();
Console.WriteLine("Elapsed(ms)={0}", sw.Elapsed);
}
static unsafe void UnsafeTest()
{
int dx = 1000, dy = 1000;
var indexer = new SpanIndexer2D<int>(dx, dy);
fixed (int* intArray = indexer.array)
{
var array = new UnsafeIntArray2D(intArray, dx, dy);
int sum = 0;
var rnd = new Random((int)DateTime.Now.TimeOfDay.Ticks);
for (int x = 0; x < array.dx; x++)
for (int y = 0; y < array.dy; y++)
array[x, y] = rnd.Next();
Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 0; i < 1000; i++)
{
for (int x = 0; x < dx; x++)
for (int y = 0; y < dy; y++)
sum += array[x, y];
}
sw.Stop();
Console.WriteLine("Elapsed(ms)={0}", sw.Elapsed);
}
}
Если бы для бенчмарка использовал нормальную тулзу вместо Stopwatch курильщика, она хотя бы вывела в репорте окружение, в котором бенчмаркалось. (У Stopwatch, кстати, есть статический метод Start или StartNew.)