Runtime: API: long Math.BigMul(long, long, out long)

[benaadams]

API Shape

To return 128 bit result (as per long BigMul(int a, int b))

partial class Math
{
    ulong BigMul(ulong a, ulong b, out ulong low);
    long BigMul(long a, long b, out long low);
}

Use case

Manual multiply high is now being used for Dictionary

Which looks like

(uint)((((ulong)(uint)left * right >> 32) + (left >> 32) * right) >> 32)

When ideally it would be

(uint)Math.BigMul(left, right, out _)

Other langs

While it is what the asm does (i.e. RDX:RAX ← RAX ∗ SRC) the apis either use a 128bit value or the split pair.

MSVC:

__int64 _mul128(__int64 Multiplier, __int64 Multiplicand, __int64 *HighProduct)
__int64 __mulh(__int64 a, __int64 b)

Others use * overloading on a __uint128_t type

[EgorBo]

@benaadams it already exists in System.Runtime.Intrinsics.BMI2: https://github.com/dotnet/coreclr/blob/master/src/System.Private.CoreLib/shared/System/Runtime/Intrinsics/X86/Bmi2.cs#L48

[benaadams]

Technically MultiplyNoFlags is different (_mulx_u64), but I'll take it 😄

[EgorBo]

It's also supported in Mono-LLVM (and doesn't use mulx directly - instead, it uses Int128): https://github.com/mono/mono/pull/17031

[benaadams]

Nice!

[tannergooding]

@benaadams, is this not something you still want more generally (and on hardware without BMI2 support)?

(e.g. should it return a 128bit type Vector128)

There is a proposal to expose Int128/UInt128, but there hasn't been enough need/request for it yet to warrant the work on the language side.

[benaadams]

On example is using the high 64 bits from a 64bit * 64bit => 128bit multiplication and then could avoid modulo from Dictionary by adding a long to it:

ulong modAdjust = ...; // 0xFFFFFFFFFFFFFFFFuL / prime + 1

uint FastMod(uint hash, uint prime) 
{
    ulong lowbits = modAdjust * hash;
    return Math.MultHigh(lowbits, prime); 
}

https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/

[benaadams]

Updated the dictionary PR to use this approach https://github.com/dotnet/coreclr/pull/27299#issuecomment-545681159

[tannergooding]

If we mirrored the C/C++ intrinsics, they would be something like:

long MultiplyHigh(long left, long right);
long Multiply128(long left, long right, out long highProduct);

[tannergooding]

Ah, that's basically what is proposed in the OP, but with different names and I just misread them.

I'm not a fan of shortening multiply to mult and I don't think Big accurately describes the type of multiplication being done (but there is prior art with long BigMul(int a, int b)).

So, for consistency, I think sticking with BigMul is probably the way to go for Multiply128... I'm not sure of a good name for Multiply and get High bits that also fits in with the existing names we have....

Once we come up with some decent names, I think we can mark as ready-for-review...

I would think it would also be desirable to expose the following for parity:

int MultiplyHigh(int left, int right); // or w/e name is decided

[benaadams]

Updated.

A side point... Bmi is low rather than high

ulong MultiplyNoFlags(ulong left, ulong right, ulong* low)

[tannergooding]

A side point... Bmi is low rather than high

Ah, right. We changed that in https://github.com/dotnet/corefx/issues/33615 due to customer feedback and ease of implementation in the JIT (it also makes it a natural extension to MultiplyHigh).

[benaadams]

Happy with either for the ready-for-review 😉

[tannergooding]

Happy with either for the ready-for-review 😉

If you could update so that it matches Bmi (return high, out low) and uses Mul rather than Mult as the name, I think I'd be happy enough to mark it as such 😄

[benaadams]

Done :)

[benaadams]

Manual multiply high is now being used for Dictionary

Which looks like

(uint)((((ulong)(uint)left * right >> 32) + (left >> 32) * right) >> 32)

When ideally it would be

(uint)Math.MultiplyHigh(left, right)

[jkotas]

Do we need really need the MultiplyHigh versions? It would expect it to be easy for the JIT to tell that the low part is unused for BigMul.

[benaadams]

Suppose not as discards make it not very onerous

ulong high = BigMul(a, b, out _);

[jkotas]

Naming nit: BigMul -> Mul. There is nothing Big (as in BigInteger) about it.

[tannergooding]

Naming nit: BigMul -> Mul. There is nothing Big (as in BigInteger) about it.

I had the same initial concern, but it matches the naming (and effective functionality) of the existing long BigMul(int, int) function we've had since .NET 1.1

[benaadams]

Naming is from the prior api static long BigMul(int a, int b) https://docs.microsoft.com/en-us/dotnet/api/system.math.bigmul?view=netframework-4.8 😢

Updated summary to drop MultiplyHigh

[pentp]

There is some related discussion in dotnet/runtime#27292

[terrajobst]

Video

• Looks good as proposed

C# namespace System { public partial class Math { public ulong BigMul(ulong a, ulong b, out ulong low); public long BigMul(long a, long b, out long low); } }

[stephentoub]

Implemented in https://github.com/dotnet/runtime/pull/35975