System.UInt64.TryMultiply to check for overflow without throwing exceptions

[verelpode]

@tannergooding, @pgovind
What do you guys think of the idea of adding the following TryMultiply methods to System.UInt64 or System.Math? They return null if the multiplication would overflow:

namespace System
{
	public struct UInt64  // Alternatively System.Math
	{
		public static unsafe UInt64? TryMultiply(UInt64 a, UInt64 b)
		{
			unchecked {
				if (System.Runtime.Intrinsics.X86.Bmi2.X64.IsSupported)
				{
					uint64 low;
					if (System.Runtime.Intrinsics.X86.Bmi2.X64.MultiplyNoFlags(a, b, &low) == 0)
						return low;
					return null;
				}
				if (b == 0 || a <= (UInt64.MaxValue / b)) return a * b;
				return null;
			}
		}

		// And for System.UInt32.TryMultiply or System.Math.TryMultiply(UInt32, UInt32):
		[MethodImplAttribute(MethodImplOptions.AggressiveInlining)]
		public static UInt32? TryMultiply(UInt32 a, UInt32 b)
		{
			unchecked {
				UInt64 product64 = (UInt64)a * b;
				UInt32 product32 = (UInt32)product64;
				if (product32 == product64) return product32;
				return null;
			}
		}
		
		[MethodImplAttribute(MethodImplOptions.AggressiveInlining)]
		public static UInt64? TryAdd(UInt64 a, UInt64 b)
		{
			UInt64 result = unchecked(a + b);
			return (result >= a) ? result : default(UInt64?);
		}

	}
}

These methods intentionally do not use checked(a * b) because they're intended for scenarios where the high cost of throwing exceptions is unacceptable.

Maybe you know, and could answer, the question of whether my TryMultiply implementations above are the best-possible implementations. Because of gaps in my knowledge of Intel processors, I'm unsure whether the above are the best implementations. I wonder whether or not it would be beneficial to add a few more intrinsics/methods to System.Runtime.Intrinsics.X86 in order to gain the ability to read the carry and/or overflow flags -- if necessary. I don't know enough CPU detail to say whether or not the x86-64 carry and/or overflow flags should be used, versus whether the above implementations are already the best overall. Maybe someone with detailed CPU knowledge could answer this question.

In any event, regardless of whether the above implementations are the best-possible, they're already at least good implementations that could be added to NETFW 5.x immediately, and later further optimized if necessary.

See also issue #13026 where @RobertBouillon suggests new CIL instructions. Although I like his idea, it's far more work than the alternative of TryMultiply etc methods such as the above. The above TryMultiply etc methods could provide the desired functionality very soon, unlike the complexity and politics of creating new CIL instructions.

[Dotnet-GitSync-Bot]

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

Tagging subscribers to this area: @tannergooding, @pgovind
See info in area-owners.md if you want to be subscribed.

Issue Details

---

@tannergooding, @pgovind
What do you guys think of the idea of adding the following TryMultiply methods to System.UInt64 or System.Math? They return null if the multiplication would overflow:

namespace System
{
	public struct UInt64  // Alternatively System.Math
	{
		public static unsafe UInt64? TryMultiply(UInt64 a, UInt64 b)
		{
			unchecked {
				if (System.Runtime.Intrinsics.X86.Bmi2.X64.IsSupported)
				{
					uint64 low;
					if (System.Runtime.Intrinsics.X86.Bmi2.X64.MultiplyNoFlags(a, b, &low) == 0)
						return low;
					return null;
				}
				if (b == 0 || a <= (UInt64.MaxValue / b)) return a * b;
				return null;
			}
		}

		// And for System.UInt32.TryMultiply or System.Math.TryMultiply(UInt32, UInt32):
		[MethodImplAttribute(MethodImplOptions.AggressiveInlining)]
		public static UInt32? TryMultiply(UInt32 a, UInt32 b)
		{
			unchecked {
				UInt64 product64 = (UInt64)a * b;
				UInt32 product32 = (UInt32)product64;
				if (product32 == product64) return product32;
				return null;
			}
		}
		
		[MethodImplAttribute(MethodImplOptions.AggressiveInlining)]
		public static UInt64? TryAdd(UInt64 a, UInt64 b)
		{
			UInt64 result = unchecked(a + b);
			return (result >= a) ? result : default(UInt64?);
		}

	}
}

These methods intentionally do not use checked(a * b) because they're intended for scenarios where the high cost of throwing exceptions is unacceptable.

Maybe you know, and could answer, the question of whether my TryMultiply implementations above are the best-possible implementations. Because of gaps in my knowledge of Intel processors, I'm unsure whether the above are the best implementations. I wonder whether or not it would be beneficial to add a few more intrinsics/methods to System.Runtime.Intrinsics.X86 in order to gain the ability to read the carry and/or overflow flags -- if necessary. I don't know enough CPU detail to say whether or not the x86-64 carry and/or overflow flags should be used, versus whether the above implementations are already the best overall. Maybe someone with detailed CPU knowledge could answer this question.

In any event, regardless of whether the above implementations are the best-possible, they're already at least good implementations that could be added to NETFW 5.x immediately, and later further optimized if necessary.

See also issue #13026 where @RobertBouillon suggests new CIL instructions. Although I like his idea, it's far more work than the alternative of TryMultiply etc methods such as the above. The above TryMultiply etc methods could provide the desired functionality very soon, unlike the complexity and politics of creating new CIL instructions.

Author:	verelpode
Assignees:	-
Labels:	api-suggestion, area-System.Numerics, untriaged
Milestone:	-

[GrabYourPitchforks]

FWIW I've also encountered scenarios where TryAdd or similar would've been useful. Sometimes I need the value of the carry or overflow flag in addition to the sum.

[jkotas]

Should these method take nullables too so that you can write expressions without checking the result after each operation?

class SafeMath
{
    static int? Add(int? x, int? y);
    static int? Sub(int? x, int? y);
    static int? Mul(int? x, int? y);
...
}

https://docs.microsoft.com/en-us/cpp/safeint/safeint-class is a prior art for this in C++.

[verelpode]

@jkotas -- That's a nice idea. I see what you mean. The methods could be overloaded -- both nullable and non-nullable versions. For the overloads with nullable parameters, they operate with a principle akin to System.Double.NaN. In this case, the result is null if either parameter is null or overflow would occur. Likewise with floating-point, the result is NaN when either parameter is NaN.

[MethodImplAttribute(MethodImplOptions.AggressiveInlining)]
public static UInt64? TryAdd(UInt64? a, UInt64? b)
{
	UInt64 result = unchecked(a.GetValueOrDefault() + b.GetValueOrDefault());
	return (result >= a & a.HasValue & b.HasValue) ? result : default(UInt64?);
}

public static Int64? TryAdd(Int64? a, Int64? b)
{
	Int64 result = unchecked(a.GetValueOrDefault() + b.GetValueOrDefault());
	return (unchecked((UInt64)((result ^ a) & (result ^ b)) >> 63) == 0 & a.HasValue & b.HasValue) ? result : default(Int64?);
}

Therefore, like you said, you can perform multiple math operations, and instead of checking for null after every operation, you can check for null once at the end. Likewise the technique of "check once at the end" works with NaN.

Int64? x = Int64.TryAdd(a, b);
x = Int64.TryAdd(x, q);
var z = Int64.TryMultiply(x, t);
if (!z.HasValue) OverflowOccurred();

The equivalent with NaN is:

double x = a + b;
x = x + q;
double z = x * t;
if (double.IsNaN(z)) AnyOfTheVariablesWasNaN();

[verelpode]

@GrabYourPitchforks

Sometimes I need the value of the carry or overflow flag in addition to the sum.

What do you think of possibly supporting that by adding one more constructor to Nullable<T> like following?

public partial struct Nullable<T> where T : struct
{
	private readonly bool hasValue;
	internal T value; 

	public Nullable(T inValue, bool inHasValue)
	{
		this.value = inValue;
		this.hasValue = inHasValue;
	}

	public Nullable(T inValue)
	{
		this.value = inValue;
		this.hasValue = true;
	}
	
	public readonly T GetValueOrDefault() => hasValue ? this.value : default(T);
	
	public readonly T GetValueOrDefault(T defaultValue) => hasValue ? this.value : defaultValue;
	
	public readonly bool ValueUnchecked { get => this.value; }
	
	public readonly T Value { get { if (!hasValue) throw xxxx; return this.value; } }
}

With such an additional constructor for Nullable<T>, the TryAdd methods would be like this:

[MethodImplAttribute(MethodImplOptions.AggressiveInlining)]
public static UInt64? TryAdd(UInt64 a, UInt64 b)
{
	UInt64 result = unchecked(a + b);
	return new Nullable<UInt64>(result, result >= a);
}

[MethodImplAttribute(MethodImplOptions.AggressiveInlining)]
public static UInt64? TryAdd(UInt64? a, UInt64? b)
{
	UInt64 result = unchecked(a.GetValueOrDefault() + b.GetValueOrDefault());
	// OR if ValueUnchecked exists:  UInt64 result = unchecked(a.ValueUnchecked + b.ValueUnchecked);
	return new Nullable<UInt64>(result, result >= a & a.HasValue & b.HasValue);
}

Would it cause any bad side-effects if the field Nullable<T>.value is allowed to contain a value other than default(T) when HasValue is false? At the moment I can't think of any problems with it, but I'm unsure. This isn't a change in behavior to all nullables, rather it's only a change in behavior to special cases such as nullables produced by TryAdd.

The above example code preserves the preexisting behavior for Nullable<T>.GetValueOrDefault() and for the property Nullable<T>.Value, meaning the new payload in the field Nullable<T>.value is completely invisible via the preexisting members of Nullable<T>, thus externally it appears to operate unchanged. To get access to the value when HasValue is false, a new property could be added, such as the Nullable<T>.ValueUnchecked property that you can see above.

The above example takes a conservative (but possibly unnecessary) approach of changing the implementation of Nullable<T>.GetValueOrDefault() to check the hasValue:

public readonly T GetValueOrDefault() => hasValue ? this.value : default(T);

But it might still be satisfactory to leave the implementation of GetValueOrDefault() unchanged:

public readonly T GetValueOrDefault() => this.value;

...considering that we're not talking about a change to all nullables, rather the change only affects nullables produced by special methods such as TryAdd that use the special additional constructor to allow payload even when HasValue is false.

i.e. if a caller of TryAdd is willing to call TryAdd at all, then he/she should be willing to accept and deal with the fact that the documentation for TryAdd may state that TryAdd produces nullables that contain payload even when HasValue is false, and that this might or might not affect Nullable<T>.GetValueOrDefault() depending on whether the implementation of GetValueOrDefault() is left unchanged or not.

[jkotas]

The above example code preserves the preexisting behavior for Nullable.GetValueOrDefault()

It does not preserve the performance characteristics. This change would be performance regression for number of current uses of Nullable<T>.

[verelpode]

@GrabYourPitchforks

Sometimes I need the value of the carry or overflow flag in addition to the sum.

Neat, even in cases where both the flag and sum are NOT needed, if both are returned anyway, then it has a nice little side-effect of making TryAdd become branch-free. Check out the following 2 alternative implementations of TryAdd -- the first has one branch, whereas the second implementation (the one that returns both carry flag and sum) is branch-free.

public static Int64? TryAdd__NormalNullable(Int64? a, Int64? b)
{
	Int64 result = unchecked(a.GetValueOrDefault() + b.GetValueOrDefault());
	return (unchecked((UInt64)((result ^ a) & (result ^ b)) >> 63) == 0 & a.HasValue & b.HasValue) ? result : default(Int64?);
}

public static Int64? TryAdd__NullableWithPayload(Int64? a, Int64? b)
{
	Int64 result = unchecked(a.ValueUnchecked + b.ValueUnchecked);
	return new Nullable<Int64>(result, unchecked((UInt64)((result ^ a) & (result ^ b)) >> 63) == 0 & a.HasValue & b.HasValue);
}

So in this case returning more information is actually slightly better for performance.

[verelpode]

It does not preserve the performance characteristics. This change would be performance regression for number of current uses of Nullable.

OK, in that case, it sounds like the better option might be to leave Nullable<T>.GetValueOrDefault() unchanged, and just put a note in the documentation for TryAdd that TryAdd(a,b).GetValueOrDefault() does not return default(T) or zero, rather it returns the equivalent of unchecked(a + b).

Additionally also still add the Nullable<T>.ValueUnchecked property anyway, regardless of the fact that ValueUnchecked and GetValueOrDefault() would have identical implementations of simplying returning the value field unchanged. Callers of TryAdd etc can use Nullable<T>.ValueUnchecked to help minimize any confusion relating to the fact that TryAdd(a,b).GetValueOrDefault() does not return default(T).

Anyway I never liked the fact that GetValueOrDefault() is a method, so it'd be nice to have a property with a short-ish name that simply returns the value field unchanged. In practice, I use Nullable<T>.GetValueOrDefault() far far more often than the exception-throwing property Nullable<T>.Value.

[jkotas]

put a note in the documentation for TryAdd that TryAdd(a,b).GetValueOrDefault() does not return default(T)

This note would really have to say that you cannot pass this Nullable to other methods that take Nullable. It would be less confusing to create a completely new type that has conversion to proper Nullable.

[tannergooding]

I've not given this a proper lookover yet due to the holidays. But my initial thought is that this is very different to how .NET exposes "try" APIs and I'd wonder if the JIT could have efficient codegen with it and if it would be useable with common overflow patterns.

For example, _addcarry_u32 in C/C++ is exposed as effectively bool AddCarry(bool inputFlag, uint left, uint right, out uint result). This allows you to write code similar to (https://godbolt.org/z/zb6zKo):

#include <stdint.h>
#include <intrin.h>

struct UInt128 { uint64_t lo, hi; };

UInt128 Test(UInt128 left, UInt128 right)
{
    UInt128 result;

    auto carry = _addcarry_u64(false, left.lo, right.lo, &result.lo);
    carry = _addcarry_u64(carry, left.hi, right.hi, &result.hi);

    return result;
}

This works well because the overflow is generally represented via a CPU flag and integrates easily with an Add w/ Carry chain or with other comparison ops like jcc, cmovcc, setcc, etc. The same goes for equivalents on ARM32/ARM64.

I wonder if it would be better to mirror the general API style or if returning a (bool overflow, ulong) result would be better (given this is the approach being taken for other "multi value returns" for intrinsics). The latter would also handle the issue with not being convertible to nullable and ideally the JIT could correctly handle that bool is actually a CPU flag and doesn't need a register for many cases.

We already handle bool returns being used as jcc, ``cmovcc, and setcc` in a few other places for HWIntrinsics; so I wouldn't expect this to be very difficult to support. I just don't know of any "gotchas" around doing that with a value tuple (or nullable) return

[verelpode]

Ahhhh! Lightbulb! After reading what @tannergooding and @jkotas wrote, I see that apparently the best design is:

• A TryMultiply method should NOT return the high half of the product, because for that purpose a different method already exists (System.Math.BigMul). A TryMultiply should only return a boolean and an integer the same size as the inputs, meaning a normal Nullable<T>.
• A TryMultiply method should NOT return the truncated/low half of a product that overflows. Again for that purpose a different method already exists (unchecked(a*b) or again System.Math.BigMul).
• A TryAdd method should NOT return the truncated sum when overflow occurs, because for that purpose a different method or class is better suited. Although System.Math.BigAdd doesn't exist, it could easily be created, but that's actually a different topic/purpose than I originally raised in this issue.
• The AddCarry method in the form that @tannergooding described apparently does work well for that purpose, therefore that purpose is better served by AddCarry and a TryAdd method should not be used for that purpose.
• TryAdd is the best design for one purpose whereas AddCarry is the best design for a different purpose.

This discussion has revealed an interesting key point. I see now why this fundamental "basics" issue (overflow checking) wasn't already completed long ago. I now understand that there are 2 different goals that have been disrupting each other and being interchanged:

1. Checking for overflow, NOT for larger-integer purposes such as producing a 128-bit integer from two 64-bit integers.
2. Checking for a carry bit including larger-integer purposes such as a 128-bit integer.

I see now the reason why these 2 different issues have been forever interchanged is that the addition carry bit happens to be exactly the same size (1 bit) as an overflow flag, thus it's so easy to interchange these 2 different issues, or to get seduced by the goal of hitting 2 birds with 1 stone.

Apparently, in this particular case, if we try to make one hammer that hits both of those goals, then it ends up being a weak hammer that works (albeit poorly) for both goals. Therefore apparently the goals need to be separated, and two different hammers created.

Therefore it would be best to first focus on multiplication, because multiplication makes it apparent that 2 different goals exist, whereas addition causes confusion because an overflow flag and an addition carry flag happen to be the same size (1 bit).

Multiplication makes it clear because the multiplication "carry" is not a carry bit, flag, or boolean, rather it's the high and low halves of the product -- not a boolean!

Thus a TryMultiply method can never support the idea of returning both a boolean AND the high half of the product. Obviously it'd be nonsense to make:

UInt64? TryMultiply(UInt64 a, UInt64 b, out UInt64 highHalf);
// or
UInt64 TryMultiply(UInt64 a, UInt64 b, out UInt64 highHalf, out bool isOverflow);

That'd be nonsense because obviously the overflow boolean or HasValue boolean is unnecessary/useless because it's simpler to check whether highHalf is zero, and the method System.Math.BigMul already exists:

public static ulong BigMul (ulong a, ulong b, out ulong low);

Thus in cases where the goal is #2 (larger-integer purposes such as a 128-bit integer), it'd be nonsense to use Nullable<UInt64> because it'd be better to use the preexisting System.Math.BigMul and an AddCarry in the form described by @tannergooding. But that's a different purpose.

The water becomes murky when you think about addition instead of multiplication, because in multiplication, the highHalf is 64 bits as shown above, whereas in addition, the "high part" consists of only one single bit called the "carry bit", and this "carry bit" is easy to interchange/confuse with an overflow flag. This interchange/confusion is the reason why non-throwing overflow-checking wasn't already completed long ago.