Tracking Issue for signed bigint helper methods

[nickkuk]

View all comments

Feature gate: #![feature(signed_bigint_helpers)]

This issue continues discussion #85532 with the following methods on integers:

• uN::carrying_mul_add_signed
• iN::overflowing_add_carry
• iN::overflowing_sub_borrow
• iN::carrying_mul
• iN::carrying_mul_add
• iN::carrying_mul_add_unsigned

impl uN {
    /// `add += self * rhs + carry`, covers full `i2N` range exactly
    fn carrying_mul_add_signed(self, rhs: iN, carry: Self, add: iN) -> (Self, iN);
}

impl iN {
    /// Returns `self + rhs + carry` and (signed) overflow flag;
    /// should be used for most significant limb only; shouldn't be chained
    fn overflowing_add_carry(self, rhs: Self, carry: bool) -> (Self, bool);
    
    /// Returns `self - rhs - borrow` and (signed) overflow flag;
    /// should be used for most significant limb only; shouldn't be chained
    fn overflowing_sub_borrow(self, rhs: Self, borrow: bool) -> (Self, bool);
    
    /// `self * rhs + carry`
    fn carrying_mul(self, rhs: Self, carry: Self) -> (uN, Self);
    
    /// `add += self * rhs + carry`, fits `i2N` range, but doesn't cover it fully
    fn carrying_mul_add(self, rhs: Self, carry: Self, add: Self) -> (uN, Self);
    
    /// `add += self * rhs + carry`, covers full `i2N` range exactly
    fn carrying_mul_add_unsigned(self, rhs: uN, carry: Self, add: uN) -> (uN, Self);
}

[nickkuk]

I found that addition of carrying_mul_unsigned_add with carry: uN looks natural.

1. We want it to be optimized correctly, because as mentioned by @tspiteri and @programmerjake simple

pub fn widemul_u64_i64(a: u64, b: i64) -> i128 {
    (a as i128) * (b as i128)
}

is better for RISC-V: godbolt, but is not enough for good x86_64 assembly and this should be used instead: godbolt.

@tspiteri noted this LLVM mis-optimization some time ago: llvm/llvm-project#57549, but its fix was abandoned.

2. Its result range is natural: e.g., for base b = 2^64 we have

• lower bound -b/2 * (b - 1) - b/2 = -b²/2;
• and upper bound (b/2 - 1) * (b - 1) + b/2 - 1 + b - 1 = b²/2 - 1,

which are exactly the bounds of i128 type.

3. Here is recursive implementation without any other methods: gist.

[nickkuk]

I believe that implementing analog of @scottmcm's generic quadratic loop is also possible, but need to compute multiplications in a bit different order and take into account different result types u64 vs i64.

/// Multiply two signed integers, first is `x` has two limbs, second is `y` with three limbs.
pub fn mul_2x3(x: ([u64; 1], i64), y: ([u64; 2], i64)) -> ([u64; 4], i64) {
    let (r0, r1) = u64_carrying_mul_add(x.0[0], y.0[0], 0, 0);
    let (r1, r2) = u64_carrying_mul_add(x.0[0], y.0[1], r1, 0);
    let (r2a, r3a) = u64_carrying_mul_signed_add(x.0[0], y.1, r2, 0);
    let (r1, r2b) = i64_carrying_mul_unsigned_add(x.1, y.0[0], r1, 0);
    let (r2, r3b) = i64_carrying_mul_unsigned_add(x.1, y.0[1], r2a, r2b);
    let (r3, r4) = i64_carrying_mul_add(x.1, y.1, r3a, r3b);
    ([r0, r1, r2, r3], r4)
}

functions

pub fn u64_carrying_mul_add(x: u64, y: u64, z: u64, w: u64) -> (u64, u64) {
    x.carrying_mul_add(y, z, w)
}

pub fn i64_carrying_mul_add(x: i64, y: i64, z: i64, w: i64) -> (u64, i64) {
    let r = i128::from(x)
        .wrapping_mul(i128::from(y))
        .wrapping_add(i128::from(z))
        .wrapping_add(i128::from(w));
    (r as u64, (r >> 64) as i64)
}

pub fn i64_carrying_mul_unsigned_add(x: i64, y: u64, z: u64, w: i64) -> (u64, i64) {
    let y = y.cast_signed();
    // if y has become negative, we need to add 2^64 * x to the answer
    let correction = if y.is_negative() {
        i128::from(x) << 64
    } else {
        0
    };
    let r = i128::from(x)
        .wrapping_mul(i128::from(y))
        .wrapping_add(correction)
        .wrapping_add(i128::from(z))
        .wrapping_add(i128::from(w));
    (r as u64, (r >> 64) as i64)
}

pub fn u64_carrying_mul_signed_add(x: u64, y: i64, z: u64, w: i64) -> (u64, i64) {
    i64_carrying_mul_unsigned_add(y, x, z, w)
}

[Krishna-js45]

Thanks for continuing the discussion here.

The range analysis for carrying_mul_unsigned_add returning (uN, Self)
makes sense, and the LLVM mis-optimization context is especially useful.
I’ll follow the implementation progress and test once available.

[programmerjake]

but is not enough for good x86_64 assembly and this should be used instead: godbolt.

did you actually benchmark them? the "fixed" version looks like it probably has higher latency so could perform worse than the code generated by using i128 multiply.

[nickkuk]

@programmerjake yeah, sorry, maybe you are right. Right now I can't get anything useful from my x86_64 with such small test.

Initially I was surprised by 2x amount of mul's when we discussed this for @tspiteri's library here.

Do you think your prediction still correct for i128 widemul for my variant vs current nightly Rust std (i.e. 4 muls vs 8)? https://godbolt.org/z/YfsxcddcW

[programmerjake]

Do you think your prediction still correct for i128 widemul for my variant vs current nightly Rust std (i.e. 4 muls vs 8)? https://godbolt.org/z/YfsxcddcW

that's enough code that I'm not going to manually calculate instruction dependency chains, sorry. you can try using llvm-mca (in the tools menu) and look at the predicted cycle count, though you do have to make sure the output only has one function (so #[cfg(...)] disable the other) without any branches since llvm-mca will assume all provided assembly is one loop and ignore returns and branches.

[nickkuk]

If I'm using llvm-mca correctly (directly right in godbolt), then both i64-u64 mul variants for my version returns almost the same

Iterations:        100
Instructions:      6600
Total Cycles:      2217
Total uOps:        8500

Variant with

i128::from(self).wrapping_mul(i128::from(rhs)).wrapping_add(i128::from(carry)).wrapping_add(i128::from(add))

even a bit better by 100 total uOps.

In this case something else is wrong for current nightly Rust i128::carrying_mul_add:

Iterations:        100
Instructions:      8000
Total Cycles:      3019
Total uOps:        10600

[scottmcm]

In this case something else is wrong for current nightly Rust i128::carrying_mul_add:

Note that that one we emit as just i256 operations to LLVM, see https://rust.godbolt.org/z/4EaYqE4xG

  %0 = sext i128 %a to i256
  %1 = sext i128 %b to i256
  %2 = sext i128 %c1 to i256
  %3 = sext i128 %c2 to i256
  %4 = mul nsw i256 %0, %1
  %5 = add nsw i256 %4, %2
  %6 = add nsw i256 %5, %3
  %7 = trunc i256 %6 to i128
  %8 = lshr i256 %6, 128
  %9 = trunc i256 %8 to i128

So if it's suboptimal, consider filing a bug on LLVM, as the same thing would probably happen with _BitInt(256) in C.

[clarfonthey]

Also worth pointing out that pretty much all of these methods are done via intrinsics to ensure we can control codegen as much as possible. So, there is always the option of doing that for any new methods that don't perform optimally.

Personally, I think trying to replicate the examples in the docs (which I think were all written by @scottmcm?) for any new methods would be the best way of ensuring that they feel natural to use. Ultimately, the types of operands matters less to the codegen and more toward how people use and understand them, and AFAIK that latter part is what's the biggest struggle at the moment.

Also, if you find any suboptimal codegen and find a way to fix it, be sure to add codegen tests!

[scottmcm]

Ultimately, the types of operands matters less to the codegen and more toward how people use and understand them, and AFAIK that latter part is what's the biggest struggle at the moment.

Absolutely this. uN::carrying_mul_add turned out really nicely (despite me not liking it at first) in part because it fits the range perfectly. iN::carrying_mul_add doesn't work like that at all, so might be best working materially differently. Similarly I understand what the carry means in uN::carrying_add, but for iN::carrying_add seeing a bool is very non-obvious (to me at least) since adding signed numbers could carry both positively or negatively.

So it needs a holistic story about what these are for and how they should work. We can always tune the implementation details later.