`Step::forward/backward_overflowing`

[pitaj]

Proposal

Problem statement

The existing Step functions optimize poorly in certain cases which come up often in real-world usage.

Motivating examples or use cases

We all know the RangeInclusive optimization issue. Often, it results in a measurable decrease in performance when using s..=e instead of s..e+1. I've discovered that switching from Step::forward* to overflowing_add convinces LLVM that the bool field is actually just an extra bit. This allows many of the same optimizations that occur on the normal Range type.

godbolt

Solution sketch

trait Step: ... {
    // ... existing functions

    // New required functions
    fn forward_overflowing(start: Self, count: usize) -> (Self, bool);
    fn backward_overflowing(start: Self, count: usize) -> (Self, bool);
}

Adding these still allows Step to still be compatible with BigInt use-cases, in those cases they will just never overflow. For char, AsciiChar, Ipv4Addr, and Ipv6Addr overflow is still well-defined, even if it is less meaningful it still works for this usecase.

Alternatives

We could instead add the overflowing stuff to TrustedStep, but that would make eventual third-party implementors worse off.

Links and related work

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.

[nia-e]

This was discussed in today's @rust-lang/libs-api meeting and we decided to approve it. Thanks!

[pitaj]

Question that came up during implementation: What do we do for types like NonZero<uN> and char which may have unintuitive or ill-defined wrapping behavior? One option is to define these functions such that saturation is allowed in those cases.

Another option is to just wrap at the MIN and MAX boundaries. For NonZero<uN> this gets a little weird, but essentially ends up as arithmetic modulo 2^N - 1 offset +1:

// skip 0 by adding 1 after the underlying integer overflows
assert_eq!(Step::forward_overflowing(NonZero::new(255_u8).unwrap(), 1), 1);
// might expect this to be 254, but 255+1 overflows to 1, so 254 past that is 255
assert_eq!(Step::forward_overflowing(NonZero::new(255_u8).unwrap(), 255), 255);
// might expect this to be 255, but wraps twice to become 1
assert_eq!(Step::forward_overflowing(NonZero::new(255_u8).unwrap(), 256), 1);

I first thought char would be easier, it could just be arithmetic modulo 0x110000. But the middle gap makes it more complicated.

[kennytm]

Since self.overflow || self.start > self.last will always be true regardless of the value of self.start, I think allowing the result to take any valid but unspecified value is fine, e.g.

fn forward_overflowing(a: NonZero<u8>, b: usize) -> (NonZero<u8>, bool) {
    let (res, overflow) = usize::from(a.get()).overflowing_add(b);
    let overflow = overflow || res > usize::from(u8::MAX);
    // SAFETY: lowest 8 bit of `res` can be zero only on overflow, so the bitwise OR is always nonzero.
    (unsafe { NonZero::new_unchecked((res as u8) | (overflow as u8)) }, overflow)
}

[pitaj]

Yeah I'm leaning towards keeping things simple. Unfortunately, for NonZero, I haven't found any invocations that please the optimizer gods.

Everything optimizes equally poorly, including @kennytm's suggestion.

tried several variations for NonZero
and for char as well (though for char even the exclusive range doesn't optimize well)

[pitaj]

Presumably this can just be added to the existing step_trait tracking issue: rust-lang/rust#42168

impl PR: rust-lang/rust#155114