.NET 7 interface INumberBuilder

[c-ohle]

.NET7 C# INumberBuilder

To improve and to keep the .NET 7 API simple, in discussion with dotnet devs we came back to an old problem.
To implement numeric types in C# with numeric- and conversion operators is great - so long the type is simple, has fixed size and don’t need normalization.

But if it starts with numerics eg. arbitrary size types, there is a problem.
Let’s take as example - the well known type System.Numerics.BigInteger.
A simple expressions like x = a * b; is no problem.
But in practice we have expressions like x = (a * b + c * d) / e;
The compiler generates a sequence of operator calls but the operator has no hint if this is for a final result or for a intermediate result only. In result, it leads to memory allocation for each temporary individual intermediate result and for more complex types, eg. rational numbers, to unnecessary performance costs for normalizations etc.

The System.Numerics devs plan at this point to provide a special public class BigIntegerBuilder similar to other NET Builder solutions, to at least give the user the opportunity to code more memory-efficient and better-performing solutions.

• My proposal is: an interface System.Numerics.INumberBuilder supporting System.Numerics.INumber<T>.

I would prefer a stack-like instruction set, but I know other ideas from discussions and there are many different implementations thinkable based on different systems and with different priorities.

• Therefore, a final interface specification is a point of discussion.
  But it should support System.Numerics.INumber<T>, which Builder and INumber-based templates can benefit from.

The 3 aspects for the solution

1. Performance for custom types that have no hardware support or not on the current platform but need normalization what for most types is the half of computation time.
2. To avoid unnecessary memory allocations for arbitrary-precision types, and this doesn't just apply to BigInteger or BigRational. This also applies to subtypes based on it, eg Complex, Quaternion, Vector, Matrices, Sparse and Tensor types. For struct types there is actually no way to solve this with shared memory. For class types it's a enormus effort (example), but so they would get a chance to manage here caches fast, efficiently and determined. Reduce allocation is finally performance, the GC would say.
3. Precision. A bad but illustrative example: A floating point 3D plane, quickly computed by cross product. However, the normalized form requires a sqrt and this results in less accuracy. Calculating a final intersection is not only faster, but also more accurate without these unecessary normalization.

A full working test implementation for a minimalistic interface already exists. (interface) (implementation)
Test project is available (GitHub) and can be used to check and debug. (requires compilation with Target framework .NET 7.0.)

API Proposal

  // This is just an outline for a stack-like approach
  // only a minimum of standard operations.
  public interface INumberBuilder
  {
    void Push<Number>(Number value) where Number : INumber<Number>;
    Number Pop<Number>() where Number : INumber<Number>;
    void Pop();
    // binary operations
    void Add();
    void Subtract();
    void Multiply();
    void Divide();
    // unary operations
    void Negate();
    void Sqr();
  }

API Usage

    static void test_INumberBuilder()
    {
      var builder = (INumberBuilder)new MyNumberBuilder();

      // 2 * 3 + 4 * 5
      builder.Push(2.0f);
      builder.Push(3.0m);
      builder.Multiply();
      builder.Push(4UL);
      builder.Push(5L);
      builder.Multiply();
      builder.Add();
      var intval = builder.Pop<Int128>();

      // PI * 10^10000
      builder.Push(Math.PI);
      builder.Push(BigInteger.Pow(10, 10000));
      builder.Multiply();
      var ratval = builder.Pop<BigRational>();

      // result / 10^10000
      builder.Push(ratval);
      builder.Push(BigRational.Pow(10, 10000));
      builder.Divide();
      var dblval = builder.Pop<double>();
    }

[huoyaoyuan]

This is out of scope for now.
The INumber<T> interface is currently focused on primitive numeric types which are struct and immutable. I can see the desire for a builder for BigInteger, but there is no public type for BigIntegerBuilder yet.

[c-ohle]

@huoyaoyuan it works for all system types, BigInteger for example in a formula x = (a * b + c * d) / e; can be compted 2x faster.
longer BigInter expression many times faster.

[c-ohle]

@huoyaoyuan There are benchmarks public with code to reproduce.

[huoyaoyuan]

There are benchmarks public with code to reproduce.

Before discussing the interface, we should discuss about adding the builder into the framework first.
Your implementation is good. But according to the guideline, interfaces should have implementation within the framework to verify the design.

[c-ohle]

@huoyaoyuan it was not my idea. It was the idea from someone from the devs. He wanted a solution, a Builder solution. I presented all together 5 different solution for an UI. Only two with stack-aspect. It's all public. But nothing was good enough. Therfore I guess it's a good idea to discuss this and maybe someone else has good solution.

[c-ohle]

@huoyaoyuan For every solution is test code available, (type 1), (type 2), (type 3), (type 4) every approach works with better performance and memory usage but with pro and cons regarding the interface. They want a solution that works also on the base of the current BigInteger calculation core (BigIntegerCalculator). I also presented a theoretical solution with a swap buffer for this. The simulation works but such a simple approach has many limits. This is the situation.

[Clockwork-Muse]

....so, here's the thing.
Unless the calculator is doing some equivalent of deep stack analysis of the calculation to eliminate/condense operations (which probably is a better fit for a third party library)...
What you're going to end up with practically is going to be MutableBigInteger (or MutableWhatever, you get the idea). Your current example API doesn't appear to have any advantages over a mutable representation, for example.

There ends up being this spectrum between where the operations are (relatively) few enough between needed results you don't want/need the stack analysis (but maybe you want a mutable version), or you get expression trees large enough that performing the extra analysis is valuable time spent - especially if you could "compile" them to run over arbitrary input. It's this latter end of things that's likely better served by a third party package. (And one that may benefit by writing them into source generators - because the compiler/JIT isn't likely to be able to perform that deep an analysis on its own for an arbitrary type like that)

[c-ohle]

@Clockwork-Muse thanks for reply, the nature of standard syntax expressions (a * b + c * d) is a tree. What the syntax parser is doing at compile time is to create a always flat sequence of op_xxx calls. For this example op_Multiply, op_Multiply, op_Addition. We can reley on this, its per definition and logical since the parser don't know what happens in the operators. For complex types, vectors, matrices, sparse matrix types, variable exponent types etc.
Many types, also simple struct, there is always a fast computation version working without normalization and the need for a normalized final result, needed to get unique comperable results.
The one and only problem is that the numeric operator not know if a final result is needed or a temp value. It would be helpful to have a optional unary op_Assign (=) operator called at the end of a operator sequence where the number type could perform a normalization - but they decided 20 years before that this is not necessary for CLI.
And thats why a Builder solution is currently the only way to allow more performant calculations for such types. Because the last call for a Builder is something like ToResult() or ToResult<T>() for a assign. That not every type has to implement something new, at this point INumber<T> is helpful, but also numeric templates can not solve the problem with the missing op_Assign. But by using INumber<T> in combination with a INumber<T> based builder interface is a powerful combination. For both sides. If at some point it also works with the inline.

[c-ohle]

Solution found using standard arithmetic expressions (using operators) that makes the builder approach obsolete.

Sample code, benchmarks and case studies for several number types can be found in the Test app if compiled for .NET 7.0.
Also BigInteger could use the approach, which would solve at least the memory waste problem.
Measured only 2% performance overhead to an ideal builder solution.
A detailed explanation of how it works will follow shortly in the BigRational Proposal discussion.