System.Numerics.BigInteger: use LastIndexOfAnyExcept (when relevant)

[speshuric]

Description

System.Numerics.BigInteger has a number of methods that look for the first zero (or first non-zero) element. This is usually done by looping through the span/array. It seems that most of them can be rewritten by Span.LastIndexOfAnyExcept() (or similar methods) - this method can be faster than plain loop. Isolated tests show improvement up to 8 times on modern x64 (but any distinct case need clarification).

Click here to expand and show examples

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 424 to 427 in bed0ec0

	// Pack _bits to remove any wasted space after the twos complement
	int len = val.Length - 1;
	while (len >= 0 && val[len] == 0) len--;
	len++;

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 503 to 505 in bed0ec0

	// Try to conserve space as much as possible by checking for wasted leading span entries
	// sometimes the span has leading zeros from bit manipulation operations & and ^
	for (len = value.Length; len > 0 && value[len - 1] == 0; len--);

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 544 to 545 in bed0ec0

	// Try to conserve space as much as possible by checking for wasted leading span entries
	while (dwordCount > 0 && value[dwordCount - 1] == 0) dwordCount--;

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 589 to 591 in bed0ec0

	// Pack _bits to remove any wasted space after the twos complement
	int len = value.Length;
	while (len > 0 && value[len - 1] == 0) len--;

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 641 to 645 in bed0ec0

	while (--iu >= 0)
	{
	if (_bits[iu] != 0)
	return false;
	}

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 1387 to 1390 in bed0ec0

	while (bits[nonZeroDwordIndex] == 0U)
	{
	nonZeroDwordIndex++;
	}

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 1545 to 1550 in bed0ec0

	// Find highest significant byte and ensure high bit is 0 if positive, 1 if negative
	int msb = buffer.Length - 2;
	while (msb > 0 && buffer[msb] == highDWord)
	{
	msb--;
	}

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 3093 to 3101 in bed0ec0

	// Check the rest of the bits (if present)
	for (int i = bitsArrayLength - 2; i >= 0; i--)
	{
	// bits array is always non-null when bitsArrayLength >= 2
	if (bits![i] == 0)
	continue;
	return bitLength;
	}

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 3540 to 3544 in bed0ec0

	for (int i = 1; (part == 0) && (i < value._bits.Length); i++)
	{
	part = value._bits[i];
	result += (sizeof(uint) * 8);
	}

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 3599 to 3606 in bed0ec0

	for (int index = 0; index < bits.Length - 1; index++)
	{
	if (bits[index] != 0)
	{
	part -= 1;
	break;
	}
	}

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 3840 to 3847 in bed0ec0

	for (int index = 0; index < bits.Length - 1; index++)
	{
	if (bits[index] != 0)
	{
	part -= 1;
	break;
	}
	}

May be I miss some of them. May be some of them shouldn't use span memory extension methods.

Configuration

Current main branch

Regression?

No

Data

Will be provided

Analysis

Will be provided

Tagging subscribers to this area: @dotnet/area-system-numerics
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

System.Numerics.BigInteger has a number of methods that look for the first zero (or first non-zero) element. This is usually done by looping through the span/array. It seems that most of them can be rewritten by Span.LastIndexOfAnyExcept() (or similar methods) - this method can be faster than plain loop. Isolated tests show improvement up to 8 times on modern x64 (but any distinct case need clarification).

Click here to expand and show examples

https://github.com/dotnet/runtime/blob/bed0ec0d196c9f85b9154d71e2e164bc46b7b0a5/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs#L424-L427

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 503 to 505 in bed0ec0

	// Try to conserve space as much as possible by checking for wasted leading span entries
	// sometimes the span has leading zeros from bit manipulation operations & and ^
	for (len = value.Length; len > 0 && value[len - 1] == 0; len--);

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 544 to 545 in bed0ec0

	// Try to conserve space as much as possible by checking for wasted leading span entries
	while (dwordCount > 0 && value[dwordCount - 1] == 0) dwordCount--;

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 589 to 591 in bed0ec0

	// Pack _bits to remove any wasted space after the twos complement
	int len = value.Length;
	while (len > 0 && value[len - 1] == 0) len--;

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 641 to 645 in bed0ec0

	while (--iu >= 0)
	{
	if (_bits[iu] != 0)
	return false;
	}

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 1387 to 1390 in bed0ec0

	while (bits[nonZeroDwordIndex] == 0U)
	{
	nonZeroDwordIndex++;
	}

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 1545 to 1550 in bed0ec0

	// Find highest significant byte and ensure high bit is 0 if positive, 1 if negative
	int msb = buffer.Length - 2;
	while (msb > 0 && buffer[msb] == highDWord)
	{
	msb--;
	}

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 3093 to 3101 in bed0ec0

	// Check the rest of the bits (if present)
	for (int i = bitsArrayLength - 2; i >= 0; i--)
	{
	// bits array is always non-null when bitsArrayLength >= 2
	if (bits![i] == 0)
	continue;
	return bitLength;
	}

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 3540 to 3544 in bed0ec0

	for (int i = 1; (part == 0) && (i < value._bits.Length); i++)
	{
	part = value._bits[i];
	result += (sizeof(uint) * 8);
	}

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 3599 to 3606 in bed0ec0

	for (int index = 0; index < bits.Length - 1; index++)
	{
	if (bits[index] != 0)
	{
	part -= 1;
	break;
	}
	}

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 3840 to 3847 in bed0ec0

	for (int index = 0; index < bits.Length - 1; index++)
	{
	if (bits[index] != 0)
	{
	part -= 1;
	break;
	}
	}

May be I miss some of them. May be some of them shouldn't use span memory extension methods.

Configuration

Current main branch

Regression?

No

Data

Will be provided

Analysis

Will be provided

Author:	speshuric
Assignees:	-
Labels:	area-System.Numerics, tenet-performance, untriaged
Milestone:	-

[tannergooding]

General perf optimization. Contributions welcome anytime

[tommysor]

@speshuric @tannergooding I made an attempt with the first example given by @speshuric.
Edit: Info in this post is obsolete, see conclusion in pr #90960

Edit: this is the original post

Turns out there is a question of what cases should this be optimized for?
Edit: Potentially worth it to add special cases for a few more elements.
Edit2: I may have answered my own question in next post.

Case: Array contains no zero elements at end => equal between Current and proposed.
Case: Array contains between 1 and 3 zero elements at end => Current is faster.
Case: Array contains 4 zero elements at end => equal between Current and proposed.
Case: Array contains 5 or more zero elements at end => proposed is faster (increasing advantage with more zero elements).

"proposed" in previous paragraph benchmarked as "SpanIndexOfOpt" (using LastIndexOfAnyExcept with a special case for "last element is not zero").
Proposed matches performance when nothing should change (assumed most common case).
Sacrifice ~1ns and decreasing on low number of zeroes (assumed common).
Gain ever more on higher number of zeroes (assumed ever decreasing probability).
Note: I don't have a solid basis for how common the cases are. I generally assume 0 is more common than 1, which is more common than 2, and so on.

Methods benchmarked:

    // Benchmarked as "Current"
    public static int Current(uint[] val)
    {
        int len = val.Length - 1;
        while (len >= 0 && val[len] == 0) len--;
        len++;
        return len;
    }
    // Benchmarked as "SpanIndexOf"
    public static int UsingLastIndexOfAnyExcept(uint[] val)
    {
        int len = val.AsSpan().LastIndexOfAnyExcept((uint)0);
        len++;
        return len;
    }
    // Benchmarked as "SpanIndexOfOpt"
    public static int UsingLastIndexOfAnyExcept_WithOptimizedNoZeroes(uint[] val)
    {
        int len = val.Length;
        if (val[len - 1] == 0)
        {
            len = val.AsSpan().LastIndexOfAnyExcept((uint)0);
            len++;
        }
        return len;
    }

Details about benchmarks

Benchmarks have been run in Github Codespace (so not ideal, but seems mostly consistent between runs with a few weird ones each run).
Speed determined by number of zero elements at end, array length irrelevant (at least up to array length 256 8192).
Benchmark code available in my fork: tommysor#1

BenchmarkDotNet=v0.13.5, OS=ubuntu 22.04 (container)
AMD EPYC 7763, 1 CPU, 4 logical and 2 physical cores
.NET SDK=8.0.100-preview.7.23376.3
  [Host]     : .NET 8.0.0 (8.0.23.37506), X64 RyuJIT AVX2
  DefaultJob : .NET 8.0.0 (8.0.23.37506), X64 RyuJIT AVX2

Method	NumberOfZeroElements	Mean	Error	StdDev	Median	Ratio	RatioSD	Allocated	Alloc Ratio
Current	0	0.3356 ns	0.0261 ns	0.0244 ns	0.3308 ns	1.00	0.00	-	NA
SpanIndexOf	0	2.1166 ns	0.0161 ns	0.0135 ns	2.1201 ns	6.35	0.36	-	NA
SpanIndexOfOpt	0	0.3846 ns	0.0234 ns	0.0207 ns	0.3780 ns	1.14	0.11	-	NA
Current	1	1.2683 ns	0.0322 ns	0.0302 ns	1.2552 ns	1.00	0.00	-	NA
SpanIndexOf	1	2.1783 ns	0.0754 ns	0.0705 ns	2.1786 ns	1.72	0.05	-	NA
SpanIndexOfOpt	1	2.4456 ns	0.0527 ns	0.0440 ns	2.4341 ns	1.93	0.05	-	NA
Current	2	1.5833 ns	0.0234 ns	0.0207 ns	1.5852 ns	1.00	0.00	-	NA
SpanIndexOf	2	2.1301 ns	0.0361 ns	0.0301 ns	2.1251 ns	1.35	0.02	-	NA
SpanIndexOfOpt	2	2.4193 ns	0.0268 ns	0.0237 ns	2.4154 ns	1.53	0.03	-	NA
Current	4	2.4688 ns	0.0624 ns	0.0553 ns	2.4572 ns	1.00	0.00	-	NA
SpanIndexOf	4	2.1418 ns	0.0470 ns	0.0417 ns	2.1334 ns	0.87	0.03	-	NA
SpanIndexOfOpt	4	2.4967 ns	0.0658 ns	0.0583 ns	2.4825 ns	1.01	0.04	-	NA
Current	5	2.7909 ns	0.0225 ns	0.0188 ns	2.7849 ns	1.00	0.00	-	NA
SpanIndexOf	5	2.1674 ns	0.0619 ns	0.0579 ns	2.1833 ns	0.77	0.02	-	NA
SpanIndexOfOpt	5	2.4543 ns	0.0379 ns	0.0355 ns	2.4488 ns	0.88	0.02	-	NA
Current	32	17.3713 ns	0.3158 ns	0.2800 ns	17.2381 ns	1.00	0.00	-	NA
SpanIndexOf	32	4.7153 ns	0.0524 ns	0.0514 ns	4.6984 ns	0.27	0.00	-	NA
SpanIndexOfOpt	32	4.3488 ns	0.0542 ns	0.0423 ns	4.3512 ns	0.25	0.00	-	NA
Current	64	31.5755 ns	0.4968 ns	0.4404 ns	31.4325 ns	1.00	0.00	-	NA
SpanIndexOf	64	8.0636 ns	0.3448 ns	1.0165 ns	7.3931 ns	0.24	0.02	-	NA
SpanIndexOfOpt	64	6.6606 ns	0.0644 ns	0.0603 ns	6.6317 ns	0.21	0.00	-	NA

Weirdness in this particular run:
NumberOfZeroElements of 32 and 64 taking less time for SpanIndexOfOpt than SpanIndexOf despite doing the exact same thing with an additional check.

[tommysor]

Edit: Info in this post is obsolete, see conclusion in pr #90960

Edit: this is the original post

For the first example, based on the unit tests (most use random byte arrays), it seems "no zeroes" or "one zero" are much more common than the rest. A tail of a few cases each up to 24 zeroes and a single example with 136 zeroes.

For that case, new proposed would be optimized for the "no zeroes" and "1 zero" cases.
Case of "no zeroes" being equally fast as current (diff in benchmark below is an artifact of this specific run).
Case of "1 zero" being slightly faster than current (diff is less than in benchmark below, estimate real ratio of ~0.8).
Using the Span method to speed up the tail methods.
2-4 zeroes slower, 5+ zeroes progressively faster (greater advantage over current).

    // Benchmarked as "SpanIndexOfOpt1"
    public static int UsingLastIndexOfAnyExcept_WithOptimizedUpTo1Zeroes(uint[] val)
    {
        int len = val.Length;
        if (val[len - 1] == 0)
        {
            len--;
            if (len > 0 && val[len - 1] == 0)
            {
                len = val.AsSpan().LastIndexOfAnyExcept((uint)0);
                len++;
            }
        }
        return len;
    }

Details about benchmarks and frequency of zeroes

Frequency of zeroes

Out of 10,000,000 random byte arrays, not a single one had more than 1 zero (no zeroes most common by far).

In unit tests they are much more common, either intentionally for tests or when involved in multiplication.
And (I think) when picking a number close to a power of 2 (lots of 1 bits in a row, or lots of 0 bits in a row).

For frequency in unit tests I modified the code to fail the test if the number of zeroes was equal to X.
Number of zeroes to number of tests

• 0 => failed="321"
• 1 => failed="211"
• 2 => failed="2"
• 3 => failed="3"
• 4 => failed="7"
• 5 => failed="5"
• 6 => failed="7"
• 7 => failed="3"
• 8 => failed="1"
• 9 => failed="7"
• 10 => failed="2"
• 11 => failed="4"
• 12 => failed="4"
• 13 => failed="2"
• 14 => failed="6"
• 15 => failed="1"
• 16 => failed="5"
• 17 => failed="5"
• 18 => failed="3"
• 19 => failed="3"
• 20 => failed="7"
• 21 => failed="6"
• 22 => failed="1"
• 23 => failed="4"
• 24 => failed="2"
• more than 24 => failed="1" (136 zeroes)

Benchmark new proposed

BenchmarkDotNet=v0.13.5, OS=ubuntu 22.04 (container)
AMD EPYC 7763, 1 CPU, 4 logical and 2 physical cores
.NET SDK=8.0.100-preview.7.23376.3
  [Host]     : .NET 8.0.0 (8.0.23.37506), X64 RyuJIT AVX2
  DefaultJob : .NET 8.0.0 (8.0.23.37506), X64 RyuJIT AVX2

Method	NumberOfZeroElements	Mean	Error	StdDev	Median	Ratio	RatioSD	Allocated	Alloc Ratio
Current	0	0.4317 ns	0.0287 ns	0.0255 ns	0.4226 ns	1.00	0.00	-	NA
SpanIndexOfOpt1	0	0.3327 ns	0.0341 ns	0.0302 ns	0.3211 ns	0.77	0.09	-	NA
Current	1	1.2739 ns	0.0507 ns	0.0450 ns	1.2651 ns	1.00	0.00	-	NA
SpanIndexOfOpt1	1	0.6671 ns	0.0299 ns	0.0265 ns	0.6687 ns	0.52	0.03	-	NA
Current	2	1.6342 ns	0.0643 ns	0.0836 ns	1.6175 ns	1.00	0.00	-	NA
SpanIndexOfOpt1	2	2.7661 ns	0.0580 ns	0.0514 ns	2.7485 ns	1.70	0.10	-	NA
Current	3	1.9835 ns	0.0708 ns	0.0727 ns	1.9864 ns	1.00	0.00	-	NA
SpanIndexOfOpt1	3	2.7824 ns	0.0598 ns	0.0530 ns	2.7919 ns	1.40	0.06	-	NA
Current	4	2.5026 ns	0.0798 ns	0.0666 ns	2.4757 ns	1.00	0.00	-	NA
SpanIndexOfOpt1	4	2.9106 ns	0.0918 ns	0.2268 ns	2.8355 ns	1.22	0.15	-	NA
Current	5	2.8263 ns	0.0749 ns	0.0625 ns	2.8155 ns	1.00	0.00	-	NA
SpanIndexOfOpt1	5	2.7813 ns	0.0749 ns	0.0625 ns	2.7813 ns	0.98	0.02	-	NA
Current	6	3.4840 ns	0.1021 ns	0.1135 ns	3.4294 ns	1.00	0.00	-	NA
SpanIndexOfOpt1	6	2.8140 ns	0.0890 ns	0.1093 ns	2.7808 ns	0.81	0.04	-	NA
Current	7	3.8893 ns	0.1014 ns	0.0899 ns	3.8689 ns	1.00	0.00	-	NA
SpanIndexOfOpt1	7	2.7446 ns	0.0482 ns	0.0427 ns	2.7490 ns	0.71	0.02	-	NA
Current	8	4.4150 ns	0.1131 ns	0.1003 ns	4.3772 ns	1.00	0.00	-	NA
SpanIndexOfOpt1	8	3.1855 ns	0.0733 ns	0.0649 ns	3.1672 ns	0.72	0.02	-	NA
Current	16	9.1404 ns	0.1010 ns	0.0895 ns	9.1174 ns	1.00	0.00	-	NA
SpanIndexOfOpt1	16	3.7654 ns	0.1053 ns	0.1369 ns	3.7446 ns	0.42	0.02	-	NA
Current	24	12.9521 ns	0.1947 ns	0.1726 ns	12.9232 ns	1.00	0.00	-	NA
SpanIndexOfOpt1	24	4.1487 ns	0.0877 ns	0.0820 ns	4.1530 ns	0.32	0.01	-	NA

[tommysor]

@adamsitnik @tannergooding
Should this issue be closed or changed based the conclusion in pr #90960 ?
I only looked at the first example given in the original post. But my basic assumption would be that the conclusion holds for the other examples as well.