Re[9]: IEqualityComparer<T> - .NET

Здравствуйте, Qbit86, Вы писали:

Q>Полезность новой фичи я не обсуждал. Меня триггернул тезис с позиции wannabe-прагматика: «моноиды ваши заумные не нужны, потому что монады это сложно»

Вы отвечаете в какой-то не той ветке. Где я писал, что монады это сложно?

Q>Я бы тоже делал аналогичную презентцию с моноидом по умолчанию — просто мне это кажется самым простым и инструктивным примером (безотносительно видео Мэдса, это частый пример). Но сегодняшний тред пошатнул мою веру в рациональность аудитории. Так что в виду моды на M-фобию можно было заменить IMonoid<T> на IEqualityComparer<T> — всё то же самое, только без страха, что вот-вот сотни вложенных bind/apply заполонят код и сожрут всю память, гроб, отладка, кладбище, монада.

Здравствуйте, Qbit86, Вы писали:

Q>Зд
Q>Внезапно, код с моноидом в стиле как на видео будет быстрее, чем стандартная лапша с делегатами : )

Q>Рассмотрим моноид из видео (C# пятилетней давности подойдёт, ничего нового из превью 9.0). Осторожно, возможна интоксикация жутким хтоническим матаном в мозг!

Q>Бенчмарк можно взять отсюда и убедиться самостоятельно.
Простите, коллега, но этот аргумент ничтожен.
Во-первых, вы что, всерьёз предлагаете чинить проблемы перформанса рантайма при помощи ажно новой фичи языка?
Да, мы все в курсе, что вызов делегата — ещё хуже, чем косвенный вызов через интерфейс. Ну так это надо чинить там, где сломано — во-первых, нужно вернуть обратно выкинутую в первой версии поддержку single-cast делегатов, а во-вторых, наконец вынуть голову из того места, где она сейчас, и прикрутить спекулятивные оптимизации. Если вам непонятно, что именно я имею в виду — напишите, я расшифрую пошагово.
Почему этот способ лучше? Да потому, что он улучшит работу всего существующего кода, в частности весь linq 2 objects. А не только тех полуторых тысяч гипотетических строк кода, которые будут написаны с использованием новых фич C#10.

Во-вторых, не смешите мои тапочки. Если вы уж взялись рассуждать о производительности, за baseline надо брать не моноид, а простой прямолинейный код:

public int AddIntegers(int[] ints)
{
  int result=0;
  foreach(var i in ints)
    result+=i;
  return result
}

Вот к такой производительности надо стремиться. Заменять одну тормозную абстракцию на чуть-чуть менее тормозную — это даже не паллиатив, а профанация.
Я могу написать код, который делает обобщённый static T Reduce<T, TMonoid>(this IEnumerable<T> items, TMonoid monoid) быстрее, чем AddIntegers выше (без учёта времени прогрева), но это упраженение, которое я бы не стал заставлять делать каждого гражданского разработчика.

Здравствуйте, Sinclair, Вы писали:

S>Во-первых, вы что, всерьёз предлагаете чинить проблемы перформанса рантайма при помощи ажно новой фичи языка?

Нет, я просто отвечаю на комментарий: «Когда дело доходить до оптимизации производительности или потребления памяти — часто проще всю монадную магию выкинуть и переписать с нуля на чистой императивщине.»

S>Если вы уж взялись рассуждать о производительности, за baseline надо брать не моноид, а простой прямолинейный код:

Такой опции попросту нет. У меня алгоритмы складывают не int'ы или double'ы. А TWeight'ы и TDistance'ы.

Здравствуйте, Sinclair, Вы писали:

S>Вы отвечаете в какой-то не той ветке.

Нет, ты :)

S>Где я писал, что монады это сложно?

Про тебя речи вообще не идёт :) Я отвечал gandjustas'у, ссылаясь на комментарий hi_octane.

Здравствуйте, Sinclair, Вы писали:

S>Не, никакой бури не вызывает.

Это у тебя не вызывает, а я говроил не про тебя. В соседней ветке ещё как вызывает.

S>Я говорю о том, что предлагаемый вариант ролей не шибко помогает.

Согласен. Просто вся ветка перешла от обсуждения полезности «ролей», к обсуждению полезности абстракции моноида.

S>Рулится прямо сейчас:

Всё так.

S>

var m = new M();

S>С учётом того, что статические интерфейсы ты ничем не параметризуешь, дефолтного конструктора вполне достаточно.

Даже конструктор не нужен (его констрейнт и вызов), достаточно default(M) с констрейнтом struct. В той статье «Concept C#: Type Classes for the Masses» именно такой подход рассматривался.

S>Вся разница — код работает прямо сейчас, не дожидаясь C# 12.

Всё верно! (Только я в своих API предпочитаю по старинке протаскивать такие policies явно — более гибко. Но действительно, можно и не параметром метода, а параметром дженерика с самостоятельным инстанцированием через default(T).)

S>С моей точки зрения, для обобщённой операции сложения использовать оператор "+" — баловство.

Категорически согласен.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Serginio1, Вы писали:

S>>Я вот только не понял зачем IntMulMonoid, IntAddMonoid
S>

S>interface IMonoid<T>
S>{
S>static T Zero{get;}
S>static T operator+(T t1, T t2)
S>static T operator*(T t1, T t2)
S>}
S>

S>Про это я писал — это не IMonoid, а IRing.
S>Плохо то, что в нём мы не можем повторно использовать IntAddMonoid и IntMulMonoid.
Ну IMonoid или IRing это просто название интерфейса.
Прелесть в том, что мы можем использовать op перегрузку операторов типа.
И при этом не нужно делать свои специализации в 99% тах случаев

Та же сортировка на перегрузке ==, !=, <, >, <=, >=
Шаблоны C++ прекрасно с ними живут. Правда долго компилируются

Здравствуйте, Qbit86, Вы писали:

Q>Нет, я просто отвечаю на комментарий: «Когда дело доходить до оптимизации производительности или потребления памяти — часто проще всю монадную магию выкинуть и переписать с нуля на чистой императивщине.»
Ну так он же справедлив. В конце концов мы выкидываем не только делегатов, но и интерфейсы, сворачивая цепочку map/reduce в конкретный метод, который вычисляет конкретное замыкание над конкретной коллекцией.

S>>Если вы уж взялись рассуждать о производительности, за baseline надо брать не моноид, а простой прямолинейный код:

Q>Такой опции попросту нет. У меня алгоритмы складывают не int'ы или double'ы. А TWeight'ы и TDistance'ы.
И в чём проблема? Судя по названию — это просто обёртки для соответствующих value-типов, для которых определены те же арифметические операторы, и возможен точно такой же код, как для интов.
Если вас беспокоит производительность, то стремиться надо к тому, чтобы в tight loops бегал обычный нативный код сложения и умножения, а не abstraction penalty с боксингами и косвенными вызовами.

Здравствуйте, Qbit86, Вы писали:

S>>

var m = new M();

S>>С учётом того, что статические интерфейсы ты ничем не параметризуешь, дефолтного конструктора вполне достаточно.

Q>Даже конструктор не нужен (его констрейнт и вызов), достаточно default(M) с констрейнтом struct. В той статье «Concept C#: Type Classes for the Masses» именно такой подход рассматривался.
Тот же конструктор, вид в профиль — построен на автоматической доступности default constructor для структур.

Q>Всё верно! (Только я в своих API предпочитаю по старинке протаскивать такие policies явно — более гибко. Но действительно, можно и не параметром метода, а параметром дженерика с самостоятельным инстанцированием через default(T).)

S>>С моей точки зрения, для обобщённой операции сложения использовать оператор "+" — баловство.

Q>Категорически согласен.
Ну, вот поэтому я не вижу особой пользы именно от ролей. То, чего я хочу от шейпов/екстеншнов, они не дают. То, что они дают, выглядит не очень-то нужным.

Здравствуйте, Sinclair, Вы писали:

Q>>Такой опции попросту нет. У меня алгоритмы складывают не int'ы или double'ы. А TWeight'ы и TDistance'ы.
S>И в чём проблема? Судя по названию — это просто обёртки для соответствующих value-типов

Нет, это параметеры дженерика. В пользовательском графе веса рёбер могут быть int'ами, decimal'ами, Complex'ами, кастомными типами — чем угодно, заранее неизвестно. Мне нужно абстрагироваться от мономорфных плюсиков.

S>Ну так он же справедлив. В конце концов мы выкидываем не только делегатов, но и интерфейсы, сворачивая цепочку map/reduce в конкретный метод, который вычисляет конкретное замыкание над конкретной коллекцией.

Так ведь нет конкретной коллекции. Речь про написание библиотечного кода, который работает с любыми типами. В момент написания кода ещё не известны типы конечного пользователя. Нет такой альтернативы как «обычный нативный код сложения и умножения».

Здравствуйте, Serginio1, Вы писали:
S>Прелесть в том, что мы можем использовать op перегрузку операторов типа.
Толку-то?
S>И при этом не нужно делать свои специализации в 99% тах случаев
Роли в этом не помогают. В тех самых 99%, роль для IRing<T> будет сводиться к "переопределению" умножения в умножение, а сложения — в сложение. Ну и нафига козе баян?
Я могу переопределить умножение, чтобы в обобщённом коде я мог использовать для умножения умножение? Офигеть как круто.
Единственный осмысленный пример — это возможность переопределить сложение через умножение, чтобы получить перемножение элементов. Ценность — близка к нулю. Если мы дизайним компонент, который пользуется "обобщённым сложением", то совершенно незачем фокусироваться на использовании для него именно инфиксного оператора +, вместо честного (статического) метода Combine().

Здравствуйте, Qbit86, Вы писали:

Q>Нет, это параметеры дженерика. В пользовательском графе веса рёбер могут быть int'ами, decimal'ами, Complex'ами, кастомными типами — чем угодно, заранее неизвестно. Мне нужно абстрагироваться от мономорфных плюсиков.
Ну вот я ровно об этом вам и говорю — то, чего мы хотим, так это чтобы AddAll(TWeight<double>[] weights) работал не хуже, чем AddAll(double[] weights).
Не имеет никакого смысла рассуждать о том, что AddAll(TWeight<double>[] weights, Func<TWeight<double>, TWeight<double>, TWeight<double>> add, TWeight<double> zero) работает хуже, чем AddAll(TWeight<double>[] weights, IMonoid<TWeight<double>> add). Если нас беспокоит производительность, то оба — отстой. Если не беспокоит, то и первого достаточно.

S>>Ну так он же справедлив. В конце концов мы выкидываем не только делегатов, но и интерфейсы, сворачивая цепочку map/reduce в конкретный метод, который вычисляет конкретное замыкание над конкретной коллекцией.
Q>Так ведь нет конкретной коллекции. Речь про написание библиотечного кода, который работает с любыми типами. В момент написания кода ещё не известны типы конечного пользователя. Нет такой альтернативы как «обычный нативный код сложения и умножения».
Вот именно об этом и речь. У нас есть чудесная библиотека, которая описывает поиск минимального пути на графе в терминах другой чудесной библиотеки универсальной агрегации и удачно описанных моноидов.
И это чудесно работает в proof of concept. А при переезде в продакшн конечные пользователи чертыхаются и заменяют всю эту кунсткамеру на плоский FindShortestPath с double и встроенными операциями; а потом ещё и переписывают на SIMD.
Потому что у них-то типы уже известны. Проблема как раз в том, что рантайм и язык плохо выполняют специализацию и её приходится выполнять вручную.

Здравствуйте, Sinclair, Вы писали:

S>Ну вот я ровно об этом вам и говорю — то, чего мы хотим, так это чтобы AddAll(TWeight<double>[] weights) работал не хуже, чем AddAll(double[] weights).

Ещё раз, TWeight — это не обёртка над double, это и есть double. Или int. Или что там ещё у пользователя. Скорее всего это обычный примитивный тип, просто неизвестный заранее. Ровно как тип элементов коллекции в Linq Aggregate(). Может и кастомный MyWeight, это уже как угодно.

S>Потому что у них-то типы уже известны. Проблема как раз в том, что рантайм и язык плохо выполняют специализацию и её приходится выполнять вручную.

А чё сразу плохо-то? Произойдёт мономорфизация, исчезнут callvirt'ы, в простых случаях даже инлайнинг будет. Это ж не делегаты с гарантированной косвенностью. Мы ж передаём не IMonoid<T>, а TMonoid where TMonoid : IMonoid<T>.

Здравствуйте, Sinclair, Вы писали:

S>Если вы уж взялись рассуждать о производительности, за baseline надо брать не моноид, а простой прямолинейный код:
S>...
S>Проблема как раз в том, что рантайм и язык плохо выполняют специализацию и её приходится выполнять вручную.

Добавил вариант для int (вначале повторю вариант для T для сравнения):

internal static T Reduce<T, TMonoid>(this IEnumerable<T> items, TMonoid monoid)
    where TMonoid : IMonoid<T>
{
    if (items is null)
        throw new ArgumentNullException(nameof(items));

    T result = monoid.Identity;
    foreach (T item in items)
        result = monoid.Combine(result, item);

    return result;
}

internal static int ReduceInt32(this IEnumerable<int> items)
{
    if (items is null)
        throw new ArgumentNullException(nameof(items));

    int result = 0;
    foreach (int item in items)
        result += item;

    return result;
}

Методы бенчмарка:

[Benchmark(Baseline = true)]
public int ReduceIntegersBaseline() => s_integers.ReduceInt32();

[Benchmark]
public int ReduceIntegers() => s_integers.Reduce(default(AdditiveInt32Monoid));

...

Результат (правда, на малом числе итераций):

|                 Method |      Mean |     Error |   StdDev | Ratio | RatioSD |
|----------------------- |----------:|----------:|---------:|------:|--------:|
| ReduceIntegersBaseline |  66.76 ns |  4.584 ns | 0.251 ns |  1.00 |    0.00 |
|         ReduceIntegers |  65.82 ns |  8.648 ns | 0.474 ns |  0.99 |    0.01 |
|      AggregateIntegers |  81.74 ns |  2.121 ns | 0.116 ns |  1.22 |    0.00 |
|         ReduceDecimals | 157.94 ns |  8.341 ns | 0.457 ns |  2.37 |    0.02 |
|      AggregateDecimals | 169.61 ns | 20.494 ns | 1.123 ns |  2.54 |    0.02 |

Здравствуйте, Qbit86, Вы писали:
Q>Методы бенчмарка:
Q>[cs][Benchmark(Baseline = true)]
Q>public int ReduceIntegersBaseline() => s_integers.ReduceInt32();

Надо не IEnumerable, а int[] items. Там 50% времени — это вызовы в GetNext.

Здравствуйте, Qbit86, Вы писали:
Q>Ещё раз, TWeight — это не обёртка над double, это и есть double. Или int. Или что там ещё у пользователя. Скорее всего это обычный примитивный тип, просто неизвестный заранее. Ровно как тип элементов коллекции в Linq Aggregate(). Может и кастомный MyWeight, это уже как угодно.
Ну, это хоть совой об пенёк, хоть пнём об сову. Всё равно всё упирается в возможность вызывать встроенные операторы без полиморфизма.

S>>Потому что у них-то типы уже известны. Проблема как раз в том, что рантайм и язык плохо выполняют специализацию и её приходится выполнять вручную.
Q>А чё сразу плохо-то? Произойдёт мономорфизация, исчезнут callvirt'ы, в простых случаях даже инлайнинг будет. Это ж не делегаты с гарантированной косвенностью. Мы ж передаём не IMonoid<T>, а TMonoid where TMonoid : IMonoid<T>.
Ну, если так-то конечно почему бы и нет.
Можно проверить, получится ли это сделать сейчас — если передать struct Monoid как параметр шаблона, то по идее это должно вызвать принудительную специализацию, и все абстрактные методы будут проинлайнены.

В целом я как раз за extensions в том виде, как их описал Мэдс — я только не понял, будут ли подхватываться существующие методы. Так-то берёшь себе, описываешь Zero и One для десятка встроенных типов — и оппа, вот тебе возможность делать where T: IArithmetic<T> с любым из них. Да и Zero-то описывать надо только для разве что string, потому что нулями всех остальных совершенно случайно являются default(T).

Здравствуйте, Sinclair, Вы писали:

S>Надо не IEnumerable, а int[] items. Там 50% времени — это вызовы в GetNext.

Эта уловка называется «moving the goalspots» [1] [2]
Алгоритмы-то всё-таки пишутся не только над массивами, а над произвольными структурами (деревья, графы общего вида, etc).

Но ладно! Начав писать бенчмарки, сложно остановиться.

internal static T Reduce<T, TMonoid>(this T[] items, TMonoid monoid)
    where TMonoid : IMonoid<T>
{
    if (items is null)
        throw new ArgumentNullException(nameof(items));

    T result = monoid.Identity;
    for (int i = 0; i != items.Length; ++i)
        result = monoid.Combine(result, items[i]);

    return result;
}

internal static int ReduceInt32(this int[] items)
{
    if (items is null)
        throw new ArgumentNullException(nameof(items));

    int result = 0;
    for (int i = 0; i != items.Length; ++i)
        result += items[i];

    return result;
}

|                 Method |       Mean |     Error |    StdDev | Ratio | RatioSD | Code Size |
|----------------------- |-----------:|----------:|----------:|------:|--------:|----------:|
| ReduceIntegersBaseline |   7.737 ns | 0.4087 ns | 0.0224 ns |  1.00 |    0.00 |     139 B |
|         ReduceIntegers |   7.409 ns | 0.4154 ns | 0.0228 ns |  0.96 |    0.00 |     162 B |
|      AggregateIntegers |  85.019 ns | 4.5889 ns | 0.2515 ns | 10.99 |    0.04 |     419 B |
|         ReduceDecimals | 132.324 ns | 9.0149 ns | 0.4941 ns | 17.10 |    0.07 |     314 B |
|      AggregateDecimals | 171.322 ns | 4.9471 ns | 0.2712 ns | 22.14 |    0.07 |     595 B |

Здравствуйте, Sinclair, Вы писали:

S>Всё равно всё упирается в возможность вызывать встроенные операторы без полиморфизма.
Q>>Произойдёт мономорфизация, исчезнут callvirt'ы, в простых случаях даже инлайнинг будет. Это ж не делегаты с гарантированной косвенностью. Мы ж передаём не IMonoid<T>, а TMonoid where TMonoid : IMonoid<T>.
S>Ну, если так-то конечно почему бы и нет.
S>Можно проверить, получится ли это сделать сейчас — если передать struct Monoid как параметр шаблона, то по идее это должно вызвать принудительную специализацию, и все абстрактные методы будут проинлайнены.

Так он уже параметр шаблона. Проверить можно — я подрубил к бенчмарку DisassemblyDiagnoser. (Сам-то я не шарю в CIL; но на вид генерируемый код такой же.)

S>Да и Zero-то описывать надо только для разве что string, потому что нулями всех остальных совершенно случайно являются default(T).

Кроме, например, мультипликативных моноидов, где нейтральным элементом будет единица.

Здравствуйте, Qbit86, Вы писали:

Q>

public interface IGenericAggregationControllerManager<T>
Q>{
Q>    T Identity { get; }
Q>    T Combine(T left, T right);
Q>}

Надо сразу идти дальше

public interface IGenericAggregationControllerManager2<T> : IGenericAggregationControllerManager<T>
{
    T Combine(T[] items);
}

Здравствуйте, Qbit86, Вы писали:

S>>Можно проверить, получится ли это сделать сейчас — если передать struct Monoid как параметр шаблона, то по идее это должно вызвать принудительную специализацию, и все абстрактные методы будут проинлайнены.
Q>Так он уже параметр шаблона. Проверить можно — я подрубил к бенчмарку DisassemblyDiagnoser. (Сам-то я не шарю в CIL; но на вид генерируемый код такой же.)

S>>Да и Zero-то описывать надо только для разве что string, потому что нулями всех остальных совершенно случайно являются default(T).

Q>Кроме, например, мультипликативных моноидов, где нейтральным элементом будет единица.
А вам обычно мультипликативный моноид и не нужен. Вам обычно нужно умение вызывать встроенный оператор *.
Ну, вот как в примере про умножение матриц — там нафиг не нужна единица, нужно собственно умножение, сложение, и zero, он же default.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Serginio1, Вы писали:
S>>Прелесть в том, что мы можем использовать op перегрузку операторов типа.
S>Толку-то?
S>>И при этом не нужно делать свои специализации в 99% тах случаев
S>Роли в этом не помогают. В тех самых 99%, роль для IRing<T> будет сводиться к "переопределению" умножения в умножение, а сложения — в сложение. Ну и нафига козе баян?
S>Я могу переопределить умножение, чтобы в обобщённом коде я мог использовать для умножения умножение? Офигеть как круто.
S>Единственный осмысленный пример — это возможность переопределить сложение через умножение, чтобы получить перемножение элементов. Ценность — близка к нулю. Если мы дизайним компонент, который пользуется "обобщённым сложением", то совершенно незачем фокусироваться на использовании для него именно инфиксного оператора +, вместо честного (статического) метода Combine().

Берем QuikSort и ничего там переопределять вообще не нужно.
И куча алгоритмов для арифметических типов переопределять не надо. Написал для инта проверил, и все остальное для всех алгеброических типов идет.

Суть то ролей в том, что бы ты использовал текущую перегрузку опрераторов. Не хочешь действуй как и раньше только вместо
Equality в role сделай перегрузку == и !=
Обычно для каждого типа они есть.

В твоем примере можно использовать текущие перегрузки операторов.

От:	Sinclair	https://github.com/evilguest/
Дата:	09.06.20 02:54
Оценка:

От:	Sinclair	https://github.com/evilguest/
Дата:	09.06.20 03:19
Оценка:	+5

От:	Qbit86	https://twitter.com/qbit86
Дата:	09.06.20 06:10
Оценка:

От:	Qbit86	https://twitter.com/qbit86
Дата:	09.06.20 06:15
Оценка:

От:	Qbit86	https://twitter.com/qbit86
Дата:	09.06.20 06:43
Оценка:	+1

От:	Serginio1	https://habrahabr.ru/users/serginio1/topics/
Дата:	09.06.20 06:57
Оценка: