Implement type constraints like in C #

In the development of C # port of AtCoderLibrary Class <arbitrary numeric type I have the intention of realizing a type like> , and I will describe the result of the examination.

As an example for explanation, consider the following program that calculates the greatest common divisor.

class Program
{
    static void Main()
    {
        System.Console.WriteLine(new Gcder(30030).Calc(42)); // → 42
        System.Console.WriteLine(new Gcder(120).Calc(119)); // → 1
    }
}
class Gcder
{
    static int Gcd(int a, int b) => b > a ? Gcd(b, a) : (b == 0 ? a : Gcd(b, a % b));
    public int a;
    public Gcder(int a) { this.a = a; }
    public int Calc(int b) => Gcd(a, b);
}

Problem: Numerical calculation cannot be made Generic

If you try to make this generic, it will not be straightforward.

This is because b> a, b == 0, ʻa% b`, etc. are undefined.

class Program
{
    static void Main()
    {
        System.Console.WriteLine(new Gcder<int>(30030).Calc(42));
        System.Console.WriteLine(new Gcder<ulong>(30030).Calc(42));
    }
}
class Gcder<T> where T : struct
{
    static T Gcd(T a, T b) => b > a ? Gcd(b, a) : (b == 0 ? a : Gcd(b, a % b)); //This line cannot be compiled
    public T a;
    public Gcder(T a) { this.a = a; }
    public T Calc(T b) => Gcd(a, b);
}

Realization in C ++

In C ++, it can be expressed using the conditional expression of template.

#include <type_traits>
#include <iostream>

template <class T>
auto gcd(T a, T b) -> typename std::enable_if<std::is_integral<T>::value, T>::type
{
  return b > a ? gcd(b, a) : (b == 0 ? a : gcd(b, a % b));
}

int main()
{
  std::cout << gcd(120, 96) << std::endl;
  std::cout << gcd(120ULL, 96ULL) << std::endl;
  // std::cout << gcd("120", 96) << std::endl; // Compilation error
}

Solution: Interface for numerical calculation

interface definition

It is good to prepare an interface for numerical calculation.

public interface INumOperator<T> : IEqualityComparer<T>, IComparer<T> where T : struct
{
        T MinValue { get; }
        T MaxValue { get; }
    T Add(T x, T y);
    T Subtract(T x, T y);
    T Multiply(T x, T y);
    T Divide(T x, T y);
    T Modulo(T x, T y);
    bool GreaterThan(T x, T y);
    bool GreaterThanOrEqual(T x, T y);
    bool LessThan(T x, T y);
    bool LessThanOrEqual(T x, T y);
}
public readonly struct IntOperator : INumOperator<int>
{
    public int MinValue => int.MinValue;
    public int MaxValue => int.MaxValue;
    public int Add(int x, int y) => x + y;
    public int Subtract(int x, int y) => x - y;
    public int Multiply(int x, int y) => x * y;
    public int Divide(int x, int y) => x / y;
    public int Modulo(int x, int y) => x % y;
    public bool GreaterThan(int x, int y) => x > y;
    public bool GreaterThanOrEqual(int x, int y) => x >= y;
    public bool LessThan(int x, int y) => x < y;
    public bool LessThanOrEqual(int x, int y) => x <= y;
    public int Compare(int x, int y) => x.CompareTo(y);
    public bool Equals(int x, int y) => x == y;
    public int GetHashCode(int obj) => obj.GetHashCode();
}
// LongOperator, UIntOperator,ULongOperator etc. are defined in the same way

The point here is that ʻIntOperator is struct`. Details will be described later.

Completed form

class Program
{
    static void Main()
    {
        System.Console.WriteLine(new Gcder<int, IntOperator>(30030).Calc(42));
        System.Console.WriteLine(new Gcder<ulong, ULongOperator>(30030).Calc(42));
        System.Console.WriteLine(new Gcder<int, IntOperator>(120).Calc(119));
        System.Console.WriteLine(new Gcder<ulong, ULongOperator>(120).Calc(119));
    }
}
class Gcder<T, TOp> where T : struct where TOp : struct, INumOperator<T>
{
    static readonly TOp op;
    static T Gcd(T a, T b) => op.GreaterThan(b, a) ? Gcd(b, a) : (op.Equals(b, default) ? a : Gcd(b, op.Modulo(a, b)));
    public T a;
    public Gcder(T a) { this.a = a; }
    public T Calc(T b) => Gcd(a, b);
}

Now, ʻint is also genericized for ʻulong.

Consideration

Reasons to implement a math interface in a struct

There are two main reasons to implement a math interface in a struct.

–struct is non-nullable
–When a struct enters a type argument, the type is expanded and fast

The former is easy because you can just use static readonly TOp op; without initializing it.

The latter is important.

If the arithmetic type is class, calls like ʻop.GreaterThan (b, a) are virtualized and will never be JIT optimized. On the other hand, in the case of struct, ʻop.GreaterThan (b, a) can be expanded by JIT optimization. Therefore, it will operate at high speed.

Benchmarks

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.18363.1082 (1909/November2018Update/19H2)
Intel Core i7-4790 CPU 3.60GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.1.401
[Host] : .NET Core 3.1.7 (CoreCLR 4.700.20.36602, CoreFX 4.700.20.37001), X64 RyuJIT
DefaultJob : .NET Core 3.1.7 (CoreCLR 4.700.20.36602, CoreFX 4.700.20.37001), X64 RyuJIT

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
DirectInt	1.173 s	0.0046 s	0.0038 s	-	-	-	304 B
GenericInt	1.292 s	0.0054 s	0.0048 s	-	-	-	2112 B
GenericClassInt	2.361 s	0.0463 s	0.0747 s	-	-	-	304 B

Code</summary><div>

class Program
{
    static void Main()
    {
        BenchmarkRunner.Run<AclBench>(DefaultConfig.Instance.AddDiagnoser(MemoryDiagnoser.Default));
    }
}
class GcderInt
{
    static int Gcd(int a, int b) => b > a ? Gcd(b, a) : b == default ? a : Gcd(b, a % b);
    public int a;
    public GcderInt(int a) { this.a = a; }
    public int Calc(int b) => Gcd(a, b);
}
class Gcder<T, TOp> where T : struct where TOp : INumOperator<T>, new()
{
    static readonly TOp op = new TOp();
    static T Gcd(T a, T b) => op.GreaterThan(b, a) ? Gcd(b, a) : (op.Equals(b, default) ? a : Gcd(b, op.Modulo(a, b)));
    public T a;
    public Gcder(T a) { this.a = a; }
    public T Calc(T b) => Gcd(a, b);
}
public class ClassIntOperator : INumOperator<int>
{
    public int MinValue => int.MinValue;
    public int MaxValue => int.MaxValue;
    public int Add(int x, int y) => x + y;
    public int Subtract(int x, int y) => x - y;
    public int Multiply(int x, int y) => x * y;
    public int Divide(int x, int y) => x / y;
    public int Modulo(int x, int y) => x % y;
    public bool GreaterThan(int x, int y) => x > y;
    public bool GreaterThanOrEqual(int x, int y) => x >= y;
    public bool LessThan(int x, int y) => x < y;
    public bool LessThanOrEqual(int x, int y) => x <= y;
    public int Compare(int x, int y) => x.CompareTo(y);
    public bool Equals(int x, int y) => x == y;
    public int GetHashCode(int obj) => obj.GetHashCode();
}
public class AclBench
{
    const int N = 10_000_000;

    [Benchmark]
    public long DirectInt()
    {
        var rnd = new System.Random(42);
        long sum = 0;
        var gcder = new GcderInt(2 * 3 * 5 * 7 * 9 * 11 * 13 * 17 * 19 * 23);
        for (int i = 0; i < N; i++)
        {
            sum += gcder.Calc(rnd.Next());
        }
        return sum;
    }

    [Benchmark]
    public long GenericInt()
    {
        var rnd = new System.Random(42);
        long sum = 0;
        var gcder = new Gcder<int, IntOperator>(2 * 3 * 5 * 7 * 9 * 11 * 13 * 17 * 19 * 23);
        for (int i = 0; i < N; i++)
        {
            sum += gcder.Calc(rnd.Next());
        }
        return sum;
    }

    [Benchmark]
    public long GenericClassInt()
    {
        var rnd = new System.Random(42);
        long sum = 0;
        var gcder = new Gcder<int, ClassIntOperator>(2 * 3 * 5 * 7 * 9 * 11 * 13 * 17 * 19 * 23);
        for (int i = 0; i < N; i++)
        {
            sum += gcder.Calc(rnd.Next());
        }
        return sum;
    }
}
public interface INumOperator<T> : System.Collections.Generic.IEqualityComparer<T>, System.Collections.Generic.IComparer<T> where T : struct
{
    T MinValue { get; }
    T MaxValue { get; }
    T Add(T x, T y);
    T Subtract(T x, T y);
    T Multiply(T x, T y);
    T Divide(T x, T y);
    T Modulo(T x, T y);
    bool GreaterThan(T x, T y);
    bool GreaterThanOrEqual(T x, T y);
    bool LessThan(T x, T y);
    bool LessThanOrEqual(T x, T y);
}
public readonly struct IntOperator : INumOperator<int>
{
    public int MinValue => int.MinValue;
    public int MaxValue => int.MaxValue;
    public int Add(int x, int y) => x + y;
    public int Subtract(int x, int y) => x - y;
    public int Multiply(int x, int y) => x * y;
    public int Divide(int x, int y) => x / y;
    public int Modulo(int x, int y) => x % y;
    public bool GreaterThan(int x, int y) => x > y;
    public bool GreaterThanOrEqual(int x, int y) => x >= y;
    public bool LessThan(int x, int y) => x < y;
    public bool LessThanOrEqual(int x, int y) => x <= y;
    public int Compare(int x, int y) => x.CompareTo(y);
    public bool Equals(int x, int y) => x == y;
    public int GetHashCode(int obj) => obj.GetHashCode();
}

</div></details>

Digression

It seems that the function called Type Classes, which is targeted at C # 10.0, is exactly like this.

https://github.com/dotnet/csharplang/issues/110