Combined `div_rem` function (and variants) for ints and uints

[Apersoma]

Proposal

Adding a combined division remainder function to integral types.

Problem statement

There is currently no function to do this and computing them together can be done more efficiently than doing them separately.

Motivating examples or use cases

Splitting things into n groups and figuring out how many groups need to have an extra member.
Finding the position of the nth element of a 2d array.
Formatting numbers in different bases.

Solution sketch

// ints & uints
fn div_rem(self, rhs: Self) -> (Self, Self) {
    let div = self / rhs;
    let rem = self - div*rhs;
    (div, rem)
}
// ints & uints
fn checked_div_rem(self, rhs: Self) -> Option<(Self, Self)>;
// ints & uints
unsafe fn unchecked_div_rem(self, rhs: Self) -> (Self, Self);
// ints
fn wrapping_div_rem(self, rhs: Self) -> (Self, Self);
// ints
fn overflowing_div_rem(self, rhs: Self) -> (Self, Self, bool);
// ints
fn strict_div_rem(self, rhs: Self) -> (Self, Self);

Note that saturating is intentionally left out. This is because what the remainder of -256/-1 when the quotient is 255 is either 1 and it is not less than |divisor| or it is 0 and not dividend - quotient*divisor. Wrapping division doesn't run into the issue because the true remainder is 0, and dividend - quotient*divisor is 0 if you let it wrap, which is appropriate for wrapping division.

Unresolved Questions

Should there be variations for div_euclid and div_floor? div_ceil wouldn't be very useful but what about it?
Should Wrapping<N> have div_rem? Saturating<T> shouldn't for the previously mentioned reasons.

Alternatives

Manual implementations of this. Probably some library that has this.

Links and related work

#526
#775
rust-lang/rfcs#914

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[programmerjake]

That should probably just be:

fn div_rem(self, rhs: Self) -> (Self, Self) {
    (self / rhs, self % rhs)
}

LLVM does optimize that into a combined div&rem instruction where that's available.

[cuviper]

LLVM does optimize that into a combined div&rem instruction where that's available.

Not always -- https://rust.godbolt.org/z/dsKnWzYKP

• u32 looks good
• u64 looks like it's trying to use a 32-bit div when possible, but either way it only executes one combined op.
• u128 is calling __udivti3 and then multiplying and subtracting for the remainder. I have no idea why it doesn't use __udivmodti4 to combine this.

Signed is similar, just with extra checks for MIN overflow.

Efficiencies aside, I also find that div_rem is more convenient if either of the args is a computed expression, rather than manually saving a temp and doing separate ops.

[Apersoma]

I looked at unchecked, wrapping, strict for signed and for the unchecked variants they are typically quite similar but the rest vary a lot and the amount of variance varies a lot.

[Apersoma]

I didn't realize until now that iN::MIN % -1 is an overflow and will panic and returns none for checked rem.

[tgross35]

Unless I'm missing something, I don't see div_rem, divrem, div_mod, divmod, rem_quo or remquo at https://llvm.org/docs/LangRef.html. So is there even any available optimization at this time, or does LLVM expect to be able to fold them itself? Regardless, it would be good to open LLVM issues about the cases where it could do better.

There is an equivalent similar operation for floats with remquo , but the remainder portion matches libm remainder rather than fmod (which is what our % is). We don't expose remainder.

[Apersoma]

Unless I'm missing something, I don't see div_rem, divrem, div_mod, divmod, rem_quo or remquo at https://llvm.org/docs/LangRef.html. So is there even any available optimization at this time, or does LLVM expect to be able to fold them itself? Regardless, it would be good to open LLVM issues about the cases where it could do better.

There is an equivalent similar operation for floats with remquo , but the remainder portion matches libm remainder rather than fmod (which is what our % is). We don't expose remainder.

pub const unsafe fn unchecked_div_rem(x: i32, y: i32) -> (i32, i32) {
    unsafe {
        let trunc = x.checked_div(y).unwrap_unchecked();
        let rem = x.unchecked_sub(trunc.wrapping_mul(y));
        (trunc, rem)
    }
}

compiles to

unchecked_div_rem:
        movl    %edi, %eax
        cltd
        idivl   %esi
        retq

and idivl is a combined instruction so it definitely can do it.

[programmerjake]

Unless I'm missing something, I don't see div_rem, divrem, div_mod, divmod, rem_quo or remquo at https://llvm.org/docs/LangRef.html. So is there even any available optimization at this time

yes, it happens when LLVM IR is going through the instruction selection stage when translating to MIR (machine IR, not to be confused with rustc's MIR), here's the function called by GlobalISel: https://github.com/llvm/llvm-project/blob/3b3ac5a1169722bff1ae0f5f8f27a48cc08c3d02/llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp#L1568

[kennytm]

For the u128 issue see rust-lang/rust#44545

div_rem was previously suggested in rust-lang/rfcs#914