search

rust-lang / rust

Empowering everyone to build reliable and efficient software.
https://www.rust-lang.org
Other
97.66k stars 12.63k forks source link

Tracking Issue for `int_roundings` #88581

Open jhpratt opened 3 years ago

jhpratt commented 3 years ago

Feature gate: #![feature(int_roundings)]

This is a tracking issue for the div_floor, div_ceil, next_multiple_of, and checked_multiple_of methods on all integer types.

Public API

impl {integer} {
    #[unstable]
    pub const fn div_floor(self, rhs: Self) -> Self;
}

impl {signed integer} {
    #[unstable]
    pub const fn div_ceil(self, rhs: Self) -> Self;

    #[unstable]
    pub const fn next_multiple_of(self, rhs: Self) -> Self;

    #[unstable]
    pub const fn checked_next_multiple_of(self, rhs: Self) -> Option<Self>;
}

impl {unsigned integer} {
    #[stable(since = "1.73.0")]
    pub const fn div_ceil(self, rhs: Self) -> Self;

    #[stable(since = "1.73.0")]
    pub const fn next_multiple_of(self, rhs: Self) -> Self;

    #[stable(since = "1.73.0")]
    pub const fn checked_next_multiple_of(self, rhs: Self) -> Option<Self>;
}

Steps / History

Unresolved Questions

fourbytes commented 3 years ago

Just updated to the latest nightly, looks like this feature breaks the num-bigint crate.

error[E0658]: use of unstable library feature 'int_roundings' ``` error[E0658]: use of unstable library feature 'int_roundings' --> /home/fourbytes/.cargo/registry/src/github.com-1ecc6299db9ec823/num-bigint-0.4.1/src/biguint.rs:398:45 | 398 | let root_scale = extra_bits.div_ceil(&n64); | ^^^^^^^^ | = note: see issue #88581 for more information = help: add `#![feature(int_roundings)]` to the crate attributes to enable error[E0308]: mismatched types --> /home/fourbytes/.cargo/registry/src/github.com-1ecc6299db9ec823/num-bigint-0.4.1/src/biguint.rs:398:54 | 398 | let root_scale = extra_bits.div_ceil(&n64); | ^^^^ expected `u64`, found `&u64` | help: consider removing the borrow | 398 - let root_scale = extra_bits.div_ceil(&n64); 398 + let root_scale = extra_bits.div_ceil(n64); | error[E0658]: use of unstable library feature 'int_roundings' --> /home/fourbytes/.cargo/registry/src/github.com-1ecc6299db9ec823/num-bigint-0.4.1/src/biguint/convert.rs:70:10 | 70 | .div_ceil(&big_digit::BITS.into()) | ^^^^^^^^ | = note: see issue #88581 for more information = help: add `#![feature(int_roundings)]` to the crate attributes to enable error[E0308]: mismatched types --> /home/fourbytes/.cargo/registry/src/github.com-1ecc6299db9ec823/num-bigint-0.4.1/src/biguint/convert.rs:70:19 | 70 | .div_ceil(&big_digit::BITS.into()) | ^^^^^^^^^^^^^^^^^^^^^^^ expected `u64`, found reference | = note: expected type `u64` found reference `&_` help: consider removing the borrow | 70 - .div_ceil(&big_digit::BITS.into()) 70 + .div_ceil(big_digit::BITS.into()) | error[E0658]: use of unstable library feature 'int_roundings' --> /home/fourbytes/.cargo/registry/src/github.com-1ecc6299db9ec823/num-bigint-0.4.1/src/biguint/convert.rs:585:10 | 585 | .div_ceil(&u64::from(bits)) | ^^^^^^^^ | = note: see issue #88581 for more information = help: add `#![feature(int_roundings)]` to the crate attributes to enable error[E0308]: mismatched types --> /home/fourbytes/.cargo/registry/src/github.com-1ecc6299db9ec823/num-bigint-0.4.1/src/biguint/convert.rs:585:19 | 585 | .div_ceil(&u64::from(bits)) | ^^^^^^^^^^^^^^^^ expected `u64`, found `&u64` | help: consider removing the borrow | 585 - .div_ceil(&u64::from(bits)) 585 + .div_ceil(u64::from(bits)) | error[E0658]: use of unstable library feature 'int_roundings' --> /home/fourbytes/.cargo/registry/src/github.com-1ecc6299db9ec823/num-bigint-0.4.1/src/biguint/convert.rs:613:10 | 613 | .div_ceil(&u64::from(bits)) | ^^^^^^^^ | = note: see issue #88581 for more information = help: add `#![feature(int_roundings)]` to the crate attributes to enable error[E0308]: mismatched types --> /home/fourbytes/.cargo/registry/src/github.com-1ecc6299db9ec823/num-bigint-0.4.1/src/biguint/convert.rs:613:19 | 613 | .div_ceil(&u64::from(bits)) | ^^^^^^^^^^^^^^^^ expected `u64`, found `&u64` | help: consider removing the borrow | 613 - .div_ceil(&u64::from(bits)) 613 + .div_ceil(u64::from(bits)) | Some errors have detailed explanations: E0308, E0658. For more information about an error, try `rustc --explain E0308`. error: could not compile `num-bigint` due to 8 previous errors warning: build failed, waiting for other jobs to finish... error: build failed ```
jhpratt commented 3 years ago

That is considered acceptable breakage. Per RFC 1105, adding an inherent impl is a minor change.

aidanhs commented 3 years ago

Though technically not a breaking change, I wonder if it's worth delaying it landing in stable for a bit? "Everything that uses num-bigint" feels kinda large. I guess we'll see the scope of the breakage on a release-based crater run.

jhpratt commented 3 years ago

num-bigint has already cut a release to fix it on their end. I suggested reverting the initial implementation on Zulip when that was pointed out. Definitely worth waiting a bit for stabilization to let things settle.

leonardo-m commented 3 years ago

Before stabilizing these functions let's see if enough people use them often enough (otherwise it's wiser to remove them).

jhpratt commented 3 years ago

There's a well-established use for them via the num crate. A number of algorithms would use div_floor and div_ceil, and next_multiple_of is useful for things like block sizes. The use case absolutely exists.

photino commented 3 years ago

The doc for checked_next_multiple_of is incomplete:

image

jhpratt commented 3 years ago

Whoops, somehow missed that. I'll send a follow-up PR to fix the docs in a bit.

fstirlitz commented 3 years ago

Was there an RFC for this feature or is it considered a ‘small change’?

Having proposed ceiling division myself at one point, I am now of the opinion that perhaps round-away-from-zero division would be a better primitive to have. Consider: if I need to paint a rectangle from (0, 0) to (X, Y) pixels with tiles of size x × y pixels, what are the coordinates of the farthest tile I need to draw? RAZ division generalises well to negative X and Y, ceiling division gives off-by-one answers. (In practice, I’d expect coordinates would usually be normalised to be always positive, but you never know.) I am having a hard time coming up with an opposite example where ceiling division would be advantageous over RAZ division.

jhpratt commented 3 years ago

No, there was no RFC for this. I brought it up on Zulip where the API was discussed to an extent.

I personally do not have a use case for ceiling division, but I also don't for next_multiple_of. Josh mentioned that the latter could be useful for memory pages, blocks, etc., but I think we both just assumed that there's some algorithm out there that could use ceiling division. Having floor but not ceiling would be somewhat odd, which I think you would agree with. Surely we're not wrong in that there's some algorithm out there that uses ceiling division?

kevincox commented 3 years ago

See https://github.com/rust-lang/rfcs/issues/2844 for people asking for ceiling division and its use cases.

jhpratt commented 3 years ago

Unfortunately none of the comments there (at first glance) indicate whether rounding away from zero or ceiling division is preferable, as the behavior is identical for positive integers.

kevincox commented 3 years ago

Ah sorry, I missed the distinction that you were making there. I also have not seen a use case that mentions negatives so I would start with ceiling. Away from zero can probably be deferred although maybe it is simpler to just add it as well for completeness.

gilescope commented 3 years ago

Feeling the pain of much breakage in the ecosystem due to num-bigint. So many things need upgrading to the newer version. From an ecosystem point of view having this as a warning before breaking nightly would have been kinder to everyone building on nightly. https://crates.io/crates/num-bigint You can see how much of the ecosystem has switched over to the new version at the bottom there. Some but not all by a long way. I know we need to make progress but a lot of people use nightly because of one or another reasons they can't quite be on stable.

tspiteri commented 3 years ago

From an ecosystem point of view having this as a warning before breaking nightly would have been kinder to everyone building on nightly.

Unless I'm missing something, this should currently only cause a warning: warning: once this associated item is added to the standard library, the ambiguity may cause an error or change in behavior! So currently this only breaks builds for people who use deny(warning) as they actually want their tests to fail to fix warnings early.

gilescope commented 3 years ago

I can't see any deny(warning) in the codebase for lighthouse. I agree a warning would be perfect - it's purpose built for the job.

gilescope commented 3 years ago

For those needing to fix their projects this seems the easiest way:

cargo install cargo-edit
cargo upgrade --workspace num-bigint
tspiteri commented 3 years ago

I can't see any deny(warning) in the codebase for lighthouse. I agree a warning would be perfect - it's purpose built for the job.

Ah, I missed that sometimes method resolution of references/not-references can mix things up: https://github.com/rust-lang/rust/issues/88878#issuecomment-917685132.

lewis421 commented 3 years ago

This does not work for me:

cargo install cargo-edit cargo upgrade --workspace num-bigint

Any other suggestions? This is rookie-level mistake-making

lewis421 commented 3 years ago

Put differently, What is the last build of num-bigint that does not break the most recent nightly?

CryZe commented 3 years ago

0.3.3 and 0.4.2 are the ones that are fixed. You likely just need to run cargo update.

lewis421 commented 3 years ago

Works!! You are the greatest, thanks CryZe

jhpratt commented 3 years ago

I've said this before, but I'm happy to send a PR temporarily reverting the int_roundings feature if necessary. May be useful to do for generating stable & beta releases, which would limit the regressions to nightly.

cuviper commented 3 years ago

On the possibility of renaming, did you consider floor_div and ceil_div? Or maybe floored_div and ceiling_div? Having the modifier as a prefix even fits better with checked_div and others, but on the other hand we did stabilize the suffixed div_euclid.

There's still going to be a clash with Integer::next_multiple_of, but I'm not sure if that one is hitting in practice.

jhpratt commented 3 years ago

checked_div and similar change the return type of the method, while div_euclid etc. change the manner in which it is calculated. In this sense, it would be preferable to keep the names as-is.

I don't think there's a nice way around Integer::next_multiple_of, but it would probably be worth a crater run prior to stabilization.

cuviper commented 3 years ago

That distinction is still blurry, since wrapping_div also only changes the manner (for the sole case of signed MIN/-1).

jhpratt commented 3 years ago

Granted. I didn't check the full API before commenting; just off the top of my head. Looking at the docs now, there's checked, overflowing, saturating, and wrapping, all of which are prefix. euclid is the sole method using a suffix.

To be honest I really don't care whether it's called div_floor or floor_div. Either is clear and unambiguous. I likely went for div_floor because that's what's used in the num crate and is what I've used as the name for an internal macro in my code.

joshtriplett commented 3 years ago

I don't have any strong preference on next_multiple_of, and if there's an equally obvious name that's fine. next_multiple_of seems like the right name, though. If we can continue using that name without too much disruption, that seems preferable.

osa1 commented 2 years ago

If you are confused about why div_floor and div_ceil methods are prefixed with unstable_ in the current nightly, see #88971.

jhpratt commented 2 years ago

Few questions:

  1. When was that changed and why? It's been on nightly for two months now and the issue has largely settled.
  2. Why is there no reference to this issue in the PR?
  3. What is the criteria for removing the prefix? The necessary change already exists in third party crates.
Andy-Python-Programmer commented 2 years ago

The current div_ceil implementation uses the modulo operator which is expensive. It can be replaced with (self + d - 1) / d which is a much faster version of ceiling an unsigned integer.

joshtriplett commented 2 years ago

@Andy-Python-Programmer That would require some care to avoid overflow, though.

fstirlitz commented 2 years ago

In practice, targets often provide either a combined integer-division-and-remainder instruction (like x86), a combined division-and-remainder support library function (32-bit ARM EABI) or, if division and remainder are separate instructions, the CPU can perform macro-instruction fusion (like RISC-V and AArch64). Optimisers are generally capable of reusing both results of this combined operation when both division and modulo are present in user code. So with a half-decent optimiser, performing both division and modulo should not be any more expensive than division alone.

(Although another alternative would be if self { (self - 1) / d + 1 } else { 0 }, much less likely to overflow.)

kornelski commented 2 years ago

Can .div_ceil() panic only if debug_assertions is enabled, so that it's analogous to regular .div()?

Otherwise it's not a zero-cost abstraction compared to (x + d - 1) / d, and I wouldn't use it where code size or autovectorization is important.

joshtriplett commented 2 years ago

@kornelski As far as I can tell, div_ceil should panic in exactly the cases div does. Is there a panicking case I'm missing?

cuviper commented 2 years ago

Otherwise it's not a zero-cost abstraction compared to (x + d - 1) / d, and I wouldn't use it where code size or autovectorization is important.

That has more chance of failure (panic or overflow) when computing the numerator, whereas div_ceil tries to be correct in all cases. If that cost is not acceptable to you, then you really should use your expression instead.

jhpratt commented 2 years ago

Stabilization PR up: #94455.

joshtriplett commented 2 years ago

Stabilization Report

Implementation History

API Summary

A summary of the API is included at the top of this tracking issue.

Experience Report

Example Usages

Many people have used these functions as part of num-integer; we're expecting that (subject to MSRV requirements) users can use the same functions as part of the standard library. A few folks reported converting their code over, while the functions were on nightly, and observed no issues doing so.

I think, at this point, we can reasonably stabilize these functions. We have evidence that people want these functions, and we have the infrastructure in place to avoid breakage. This also seems like a good time, since we just shipped 1.59 and 1.60 beta just branched, so we can put these into 1.61 and give the stabilization plenty of time to bake there.

Shall we stabilize these four functions on integers?

@rfcbot merge

rfcbot commented 2 years ago

Team member @joshtriplett has proposed to merge this. The next step is review by the rest of the tagged team members:

Concerns:

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

yaahc commented 2 years ago

Thank you for the fantastic summary of the history @joshtriplett!!

m-ou-se commented 2 years ago

@rfcbot concern Should these panic or wrap around on overflow in release mode?

The docs of these say This function will panic if [..] the operation results in overflow., but the implementation seems to use #[rustc_inherit_overflow_checks] and will only panic in debug mode, and silently overflow/wrap in release mode.

tspiteri commented 2 years ago

Division overflow panics in release mode too.

joshtriplett commented 2 years ago

I would expect these to panic iff overflow checks are enabled (except in the case of divide-by-zero, for which I'd expect unconditional panic).

tspiteri commented 2 years ago

@joshtriplett Do you mean that you expect i32::MIN.div_floor(-1) and i32::MIN.div_ceil(-1) to return a wrapped value in release mode?

With the code merged in #88581, these are the panics I think are possible:

My analysis of next_multiple_of with my notes marked Note: follows:

// This would otherwise fail when calculating `r` when self == T::MIN.
if rhs == -1 {
    return self;
}

let r = self % rhs;

// Note: If rhs = 0, a panic has already happened.
// Note: At this point, abs(r) < abs(rhs).

let m = if (r > 0 && rhs < 0) || (r < 0 && rhs > 0) {
    // Note: signum(r) != signum(rhs), and abs(r) < abs(rhs), so this branch
    //       will leave abs(m) < abs(rhs) and signum(m) = signum(rhs).
    // Note: can never overflow since r and rhs have opposite signs.
    r + rhs
} else {
    // Note: in this branch, abs(m) < abs(rhs). Also, either m is 0, or
    //       signum(m) = signum(rhs)
    r
};

if m == 0 {
    // Note: no overflow here.
    self
} else {
    // Note: (rhs - m) can never overflow since rhs and m have similar signs.
    // Note: overflow possible in the final addition.
    self + (rhs - m)
}

By the way, in checked_next_multiple_of there are two unnecessary try_opt! calls.

  1. try_opt!(r.checked_add(rhs)) should never fail since r and rhs have opposite signs.
  2. try_opt!(rhs.checked_sub(m)) should never fail since rhs and m have the same sign.
joshtriplett commented 2 years ago

@tspiteri I don't have any expectations regarding the signed versions; I have no plans to use them. I think next_multiple_of(-n) seems excessively confusing and I have no idea what semantics I'd expect there.

jhpratt commented 2 years ago

next_multiple_of(-n) has the following description. It's basically prev_multiple_of.

If rhs is negative, calculates the largest value less than or equal to self that is a multiple of rhs.

This matches my intuition (which should be obvious given that I'm the one that implemented it).

joshtriplett commented 2 years ago

next_multiple_of(-n) has the following description. It's basically prev_multiple_of.

If rhs is negative, calculates the largest value less than or equal to self that is a multiple of rhs.

This matches my intuition (which should be obvious given that I'm the one that implemented it).

Shouldn't that be "the largest value less than or equal to self that is a multiple of rhs.abs()"?

In any case, that still seems like confusing behavior, to the point that any code using it would necessitate a trip to the documentation to understand.

jhpratt commented 2 years ago

Well, it's still a multiple, just a negative multiple.

jhpratt commented 2 years ago

I presume everyone agrees that division by zero should panic. Simple division panics in release mode as well (i32::MIN / -1 is a test case). I think it makes sense to maintain this behavior for div_floor and div_ceil.

checked_next_multiple_of should never panic, given that its purpose is to do checked arithmetic. As such, the only question is whether next_multiple_of should panic in release mode.

Initially, I'd have said that wrapping was reasonable. This is because it would be most performant; code that can panic is not inlined often. While wrapping is sometimes the desired behavior in integer arithmetic, I don't see a similar use case here. Unless someone is able to articulate one, I think the best way forward is to change the current behavior and bring it in line with documentation: panic on overflow in release mode. If the user has desired behavior that is different, they would be free to use .checked_next_multiple_of(x).unwrap_or(y).

How do others feel about this?

fstirlitz commented 2 years ago

If next_multiple_of is defined as a + (b - a % b), and a % 0 is defined to equal a (as surprisingly makes sense mathematically), it follows that a.next_multiple_of(0) should be zero. But I don't think much code using the method will expect that. On the contrary, I think more users will expect the definition of a.next_multiple_of(b) = inf { x ∈ ℤ : b ∣ x ∧ x sgn(b) > a sgn(b) } (or just x > a, which is easily implementable in terms of that), in which case, there is no possible value to assign. It better panic for zero after all.

But the same definition can straightforwardly justify a.next_multiple_of(-1) == a - 1, and I see no reason not to extend that to all values other than short-term concessions to performance. And I would guess much of the time, b is going to be a compile-time constant anyway, in which case any extra branch to handle −1 can be eliminated.