Trimming zeroes in BigInteger

[sakno]

#35565 is finally closed and we can move forward to the next series of optimizations. This time I would like to propose the optimization for trimming operation. When arithmetic operation occurred, every time we need to trim leading elements of type uint from the result to reduce the space. It happens in several places:

• ActualLength method called in the end of almost every arithmetic operation
• In ctors: here and here

#41495 is another proposal but I would not consider it as a part of this change.

I did some research and here is the results:

Benchmark

[SimpleJob(runStrategy: RunStrategy.Throughput, launchCount: 1)]
    [Orderer(SummaryOrderPolicy.Declared)]
    public class TrimLeadingZeroesBenchmark
    {
        public readonly struct ArrayParam
        {
            private readonly uint[] _array;
            private readonly string _text;

            internal ArrayParam(string text, uint[] array)
            {
                _array = array;
                _text = text;
            }

            public Span<uint> Value => _array.AsSpan();

            public override string ToString() => _text;
        }

        [ParamsSource(nameof(Arrays))]
        public ArrayParam array;

        public static IEnumerable<ArrayParam> Arrays
        {
            get
            {
                yield return new("No leading zeroes", new uint[] { 1U, 2U, 3U, 4U, 5U, 6U, 7U, 8U, 9U, 10U, 11U, 12U, 13U, 14U, 15U, 16U, 17U, 18U });
                yield return new("One leading zero", new uint[] { 1U, 2U, 3U, 4U, 5U, 6U, 7U, 8U, 9U, 10U, 11U, 12U, 13U, 14U, 15U, 16U, 17U, 0U });
                yield return new("Four leading zeroes", new uint[] { 1U, 2U, 3U, 4U, 5U, 6U, 7U, 8U, 9U, 10U, 11U, 12U, 13U, 14U, 0U, 0U, 0U, 0U });
                yield return new("Eight leading zeroes", new uint[] { 1U, 2U, 3U, 4U, 5U, 6U, 7U, 8U, 9U, 10U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U });
                yield return new("Nine leading zeroes", new uint[] { 1U, 2U, 3U, 4U, 5U, 6U, 7U, 8U, 9U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U });
            }
        }

        [Benchmark(Baseline = true, Description = "Loop")]
        public Span<uint> TrimUsingLoop()
        {
            Span<uint> span = array.Value;

            int length = span.Length;

            while (length > 0 && span[length - 1] == 0)
                --length;

            return span.Slice(0, length);
        }

        [Benchmark(Description = "MemoryExtensions.TrimEnd")]
        public Span<uint> TrimUsingMethod()
            => array.Value.TrimEnd(0U);

        [Benchmark(Description = "Vector + unsafe code")]
        public Span<uint> TrimUsingVectorUnsafe()
        {
            Span<uint> span = array.Value;

            int length = span.Length;

            while (length > Vector<uint>.Count)
            {
                int offset = length - Vector<uint>.Count;
                ref uint ptr = ref Unsafe.Add(ref MemoryMarshal.GetReference(span), offset);
                Vector<uint> vec = Unsafe.As<uint, Vector<uint>>(ref ptr);
                if (vec != Vector<uint>.Zero)
                    break;

                length = offset;
            }

            while (length > 0 && span[length - 1] == 0)
                --length;

            return span.Slice(0, length);
        }

        [Benchmark(Description = "Vector")]
        public Span<uint> TrimUsingVector()
        {
            Span<uint> span = array.Value;

            int length = span.Length;

            while (length > Vector<uint>.Count)
            {
                int offset = length - Vector<uint>.Count;
                Vector<uint> vec = new(span.Slice(offset, Vector<uint>.Count));
                if (vec != Vector<uint>.Zero)
                    break;

                length = offset;
            }

            while (length > 0 && span[length - 1] == 0)
                --length;

            return span.Slice(0, length);
        }
    }

Method	array	Mean	Error	StdDev	Ratio	RatioSD
Loop	Eight leading zeroes	7.035 ns	0.0849 ns	0.0753 ns	1.00	0.00
MemoryExtensions.TrimEnd	Eight leading zeroes	9.164 ns	0.0420 ns	0.0372 ns	1.30	0.02
'Vector + unsafe code'	Eight leading zeroes	2.683 ns	0.0167 ns	0.0148 ns	0.38	0.00
Vector	Eight leading zeroes	3.627 ns	0.0206 ns	0.0182 ns	0.52	0.01
Loop	Four leading zeroes	4.267 ns	0.0224 ns	0.0209 ns	1.00	0.00
MemoryExtensions.TrimEnd	Four leading zeroes	5.618 ns	0.0382 ns	0.0339 ns	1.32	0.01
'Vector + unsafe code'	Four leading zeroes	5.862 ns	0.0543 ns	0.0508 ns	1.37	0.01
Vector	Four leading zeroes	4.917 ns	0.0352 ns	0.0330 ns	1.15	0.01
Loop	Nine leading zeroes	7.953 ns	0.1579 ns	0.1399 ns	1.00	0.00
MemoryExtensions.TrimEnd	Nine leading zeroes	10.097 ns	0.0486 ns	0.0430 ns	1.27	0.02
'Vector + unsafe code'	Nine leading zeroes	3.397 ns	0.0597 ns	0.0558 ns	0.43	0.01
Vector	Nine leading zeroes	3.997 ns	0.0110 ns	0.0086 ns	0.50	0.01
Loop	No leading zeroes	1.445 ns	0.0215 ns	0.0190 ns	1.00	0.00
MemoryExtensions.TrimEnd	No leading zeroes	2.694 ns	0.0235 ns	0.0208 ns	1.86	0.03
'Vector + unsafe code'	No leading zeroes	2.486 ns	0.0185 ns	0.0173 ns	1.72	0.03
Vector	No leading zeroes	2.324 ns	0.0116 ns	0.0103 ns	1.61	0.02
Loop	One leading zero	2.426 ns	0.0429 ns	0.0401 ns	1.00	0.00
MemoryExtensions.TrimEnd	One leading zero	3.280 ns	0.0158 ns	0.0140 ns	1.35	0.02
'Vector + unsafe code'	One leading zero	3.066 ns	0.0215 ns	0.0190 ns	1.27	0.02
Vector	One leading zero	2.966 ns	0.0275 ns	0.0257 ns	1.22	0.02

Vector gives the most significant benefit when the array contains a lot of leading zeroes. And small overhead when the number of zeroes doesn't fit to vector size. However, this is constant price that do not depend on the number elements.

Before I can start this work, it would be great to hear the opinion.

/cc @jeffhandley , @tannergooding , @danmoseley , @GrabYourPitchforks

[tannergooding]

Thanks for the consideration here @sakno.

I think its best if we hold off on this change at the moment. I'm currently looking at a more general refactoring/potential rewrite of BigInteger to just store and do everything as two's complement directly.

This refactoring is being considered for many reasons, including that most of the current bugs stem from it being (since the original implementation from 2010) stored as sign + magnitude. The current approach also leads to other problems, such as the implementation being overall less performant (which prevented its usage for floating-point parsing/formatting and is why we have a separate: https://source.dot.net/#System.Private.CoreLib/Number.BigInteger.cs,bfb80448fa83ac98), it requiring inline conversion to/from two's complement for many operations, and it not being inline with any of the perf oriented whitepapers involving "fast big integer arithmetic" (which can hinder optimizations around utilizing the underlying hardware).

If you're interested in being involved in such a refactoring; then we'd be happy to coordinate; but that is likely going to require me completing some initial investigations and doing a write-up on the intended roadmap for such an undertaking (which will probably happen in early November at the moment).

[sakno]

Sure, I'm in.