Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tracking Issue for more const int functions #53718

Open
TimDiekmann opened this issue Aug 26, 2018 · 25 comments
Open

Tracking Issue for more const int functions #53718

TimDiekmann opened this issue Aug 26, 2018 · 25 comments

Comments

@TimDiekmann
Copy link
Contributor

@TimDiekmann TimDiekmann commented Aug 26, 2018

(none exhaustive) list of libcore::num, which should be a const fn:

  • feature = const_int_rotate
    • rotate_left #53697 -- stabilized
    • rotate_right #53697 -- stabilized
  • feature = const_int_checked
    • checked_add [1]
    • checked_sub [1]
    • checked_mul [1]
    • checked_div [1]
    • checked_rem [1]
    • checked_neg [1]
    • checked_shl [1]
    • checked_shr [1]
    • checked_abs [1]
  • feature = const_int_saturating
    • saturating_add #58246
    • saturating_sub #58246
    • saturating_mul [1]
  • feature = const_int_wrapping
    • wrapping_add #53697 -- stabilized
    • wrapping_sub #53697 -- stabilized
    • wrapping_mul #53697 -- stabilized
    • wrapping_div [1]
    • wrapping_rem [1]
    • wrapping_neg #58044 -- stabilized
    • wrapping_shl #53697 -- stabilized
    • wrapping_shr #53697 -- stabilized
    • wrapping_abs #63786 -- stabilized in 1.39
  • feature = const_int_overflowing
    • overflowing_add #53697
    • overflowing_sub #53697
    • overflowing_mul #53697
    • overflowing_div [1]
    • overflowing_rem [1]
    • overflowing_neg #58044 -- stabilized
    • overflowing_shl #53697
    • overflowing_shr #53697
    • overflowing_abs #63786 -- stabilized in 1.39
  • feature = const_int_euclidean
    • checked_div_euc [1]
    • checked_mod_euc [1]
    • wrapping_div_euc [1]
    • wrapping_mod_euc [1]
    • overflowing_div_euc [1]
    • overflowing_mod_euc [1]
  • feature = const_int_pow
    • pow[1, 2]
    • is_power_of_two #65092
    • next_power_of_two [1]
    • checked_pow [1]
    • checked_next_power_of_two [1]
    • saturating_pow [1, 2]
    • wrapping_pow [1, 2]
    • wrapping_next_power_of_two [1]
    • overflowing_pow [1, 2]
  • feature = const_int_sign
  • feature = const_int_conversion
  • feature = const_int_nonzero
    • NonZero*::new [1]
  1. Requires conditionals. Tracking Issue: #49146 (implemented on nightly)
  2. Requires loops. Tracking Issue: #52000

This issue has been assigned to @9999years via this comment.

@TheDarkula

This comment has been minimized.

Copy link
Contributor

@TheDarkula TheDarkula commented Aug 30, 2018

transmute() just got merged. You can start on your last block now :)

@TimDiekmann

This comment has been minimized.

Copy link
Contributor Author

@TimDiekmann TimDiekmann commented Aug 31, 2018

@TheDarkula Thank you, I'll start implementing them as soon as #53699 is merged.

@TimDiekmann

This comment has been minimized.

Copy link
Contributor Author

@TimDiekmann TimDiekmann commented Aug 31, 2018

Added rest of const_int_conversion to #53697

@TimDiekmann

This comment has been minimized.

Copy link
Contributor Author

@TimDiekmann TimDiekmann commented Sep 1, 2018

I'm currently rebasing #53697 and testing. Then the first bunch should be ready to merge.

bors added a commit that referenced this issue Sep 3, 2018
Add more const int ops

r? @oli-obk

Tracking Issue: #53718

list of `const fn`s in this PR:

- `feature = const_int_rotate`
  - `rotate_left`
  - `rotate_right`
- `feature = const_int_wrapping`
  - `wrapping_add`
  - `wrapping_sub`
  - `wrapping_mul`
  - `wrapping_shl`
  - `wrapping_shr`
- `feature = const_int_overflowing`
  - `overflowing_add`
  - `overflowing_sub`
  - `overflowing_mul`
  - `overflowing_shl`
  - `overflowing_shr`
- `feature = const_int_sign`
  - `is_positive`
  - `is_negative`
- `feature = const_int_conversion`
  - `reverse_bits`
  - `to_le_bytes`
  - `to_ne_bytes`
  - `from_be_bytes`
  - `from_le_bytes`
  - `from_ne_bytes`
  - `reverse_bits`
@mjbshaw

This comment has been minimized.

Copy link
Contributor

@mjbshaw mjbshaw commented Dec 31, 2018

Adding a comment here so I don't have to hunt for the following related issue: #51267 is the tracking issue for feature = const_int_ops, which tracks:

  • count_zeros -- stabilized
  • count_ones -- stabilized
  • leading_zeros -- stabilized
  • trailing_zeros -- stabilized
@Centril Centril closed this Jan 13, 2019
@Centril Centril reopened this Jan 13, 2019
@Lokathor Lokathor mentioned this issue Jan 13, 2019
0 of 21 tasks complete
@Lokathor

This comment has been minimized.

Copy link
Contributor

@Lokathor Lokathor commented Jan 13, 2019

wrapping_neg isn't on the list here it seems (though overflowing_neg is)

@ecstatic-morse

This comment has been minimized.

Copy link
Contributor

@ecstatic-morse ecstatic-morse commented Jun 8, 2019

It's possible to make a great number of these const without conditional statements being legal in const fn by using indexing (e.g. [x, -x][(x < 0) as usize]). However, it's a bad idea because the technique results in much less efficient generated code. You can check this by viewing ASM in the previous link. I'm posting this to avoid duplication of effort in case someone else has the same idea.

@mark-i-m

This comment has been minimized.

Copy link
Member

@mark-i-m mark-i-m commented Jun 8, 2019

In fact, we are already doing that to make Vec::new() a const fn 😛

pub const fn new_in(a: A) -> Self {
// !0 is usize::MAX. This branch should be stripped at compile time.
// FIXME(mark-i-m): use this line when `if`s are allowed in `const`
//let cap = if mem::size_of::<T>() == 0 { !0 } else { 0 };
// Unique::empty() doubles as "unallocated" and "zero-sized allocation"
RawVec {
ptr: Unique::empty(),
// FIXME(mark-i-m): use `cap` when ifs are allowed in const
cap: [0, !0][(mem::size_of::<T>() == 0) as usize],
a,
}
}

@ecstatic-morse

This comment has been minimized.

Copy link
Contributor

@ecstatic-morse ecstatic-morse commented Jun 8, 2019

@mark-i-m That's probably where I first saw this technique!

My point was that making a similar modification would likely slow down these arithmetic operations considerably. The use in Vec::new can be eliminated via const-propagation post-monomorphization, but that optimization doesn't apply here.

bors added a commit that referenced this issue Jun 8, 2019
Make `i*::signum` a `const fn`.

Ticks a box in #53718.

This uses a well-known branchless implementation of `signum`: `(n > 0) as i32 - (n < 0) as i32`.

Here's a [playground](https://play.rust-lang.org/?version=nightly&mode=release&edition=2018&gist=747cf191c4974bf66c9d75e509ae6e6e) comparing the two techniques. On x86 in release mode, the branchless implementation is able to replace a `mov` and `cmov` with a `sar` and `add`, so this should be a bit faster as well.

~~This is marked as a draft since I think I'll need to add `#[rustc_const_unstable]` somewhere. Perhaps the reviewer can point me in the right direction.~~
@ecstatic-morse

This comment has been minimized.

Copy link
Contributor

@ecstatic-morse ecstatic-morse commented Jun 8, 2019

@TimDiekmann. Now that #61635 has been merged, signum is an unstable const fn. Could you edit the initial post to reflect this?

@mjbshaw

This comment has been minimized.

Copy link
Contributor

@mjbshaw mjbshaw commented Jul 6, 2019

Some of these could be made const today without conditionals. For unsigned:

  • overflowing_div
  • wrapping_div
  • wrapping_div_euclid
  • wrapping_rem
  • wrapping_rem_euclid
  • overflowing_div
  • overflowing_div_euclid
  • overflowing_rem
  • overflowing_rem_euclid
  • div_euclid
  • rem_euclid
  • is_power_of_two

For u8:

  • is_ascii
@mjbshaw

This comment has been minimized.

Copy link
Contributor

@mjbshaw mjbshaw commented Jul 6, 2019

Also, wrapping_neg and overflowing_neg should be updated in the OP. Both were made const in #58044

@jonas-schievink

This comment has been minimized.

Copy link
Member

@jonas-schievink jonas-schievink commented Nov 4, 2019

is_power_of_two and next_power_of_two shouldn't require conditionals. See https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 (replacing && with &) and https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2, respectively.

@ecstatic-morse

This comment has been minimized.

Copy link
Contributor

@ecstatic-morse ecstatic-morse commented Nov 4, 2019

@jonas-schievink is_power_of_two was recently constified. I've updated the original post.

Currently, next_power_of_two uses a non-zero count trailing zeros intrinsic, so it might be hard to constify without regressing performance. It would be a good first issue for someone to try this out and see though.

@ecstatic-morse

This comment has been minimized.

Copy link
Contributor

@ecstatic-morse ecstatic-morse commented Nov 4, 2019

Actually, quite a few of these are now implemented. I've edited the post to reflect this. If anyone sees something out-of-date, let me know.

@mjbshaw

This comment has been minimized.

Copy link
Contributor

@mjbshaw mjbshaw commented Nov 5, 2019

@ecstatic-morse The intrinsic can be const and implemented in miri. That's what's done for trailing_zeros, for example.

@ecstatic-morse

This comment has been minimized.

Copy link
Contributor

@ecstatic-morse ecstatic-morse commented Nov 5, 2019

You need to handle zero somehow without branching, and you need to do so without regressing performance for non-const code.

(Also, I meant leading zeros above, my bad).

@SimonSapin

This comment has been minimized.

Copy link
Contributor

@SimonSapin SimonSapin commented Nov 25, 2019

Should NonZero*::new fall in this category?

@Lokathor

This comment has been minimized.

Copy link
Contributor

@Lokathor Lokathor commented Nov 25, 2019

not until const if

@ecstatic-morse

This comment has been minimized.

Copy link
Contributor

@ecstatic-morse ecstatic-morse commented Nov 25, 2019

@SimonSapin Yes. I've added it to the OP.

@Lucretiel

This comment has been minimized.

Copy link
Contributor

@Lucretiel Lucretiel commented Nov 27, 2019

Out of curiosity, what's the bar for the const if / const match functions to get merged? By which I mean– the standard library makes use of a lot of unstable features, even in stable code (iterator specializations being the most obvious example); at what point can the same thing happen with const conditionals?

@ecstatic-morse

This comment has been minimized.

Copy link
Contributor

@ecstatic-morse ecstatic-morse commented Nov 27, 2019

@Lucretiel I can't speak for the libs team, but I think anything in the standard library that could be constified with this feature gate should be. However, any PRs that do this need to also add #![rustc_const_unstable] to the newly const function, since without the attribute we would basically be back-door stabilizing #![feature(const_if_match)]. There's at least one lang team member who feels this way as well.

There's one additional complication: The current stage0 compiler, which is used to bootstrap rustc does not have #66507. That means any use of #![feature(const_if_match)] in the standard library must be behind #[cfg(not(bootstrap))]. Unless there is an urgent need, I think we should wait until this is no longer necessary to constify standard library functions. I believe this will happen in mid-December when the beta branch occurs.

@9999years

This comment has been minimized.

Copy link

@9999years 9999years commented Nov 30, 2019

@rustbot claim

Working on the ones blocked by const_if_match in #66884 (thanks for #66507, @ecstatic-morse!)

@rustbot rustbot self-assigned this Nov 30, 2019
@SimonSapin

This comment has been minimized.

Copy link
Contributor

@SimonSapin SimonSapin commented Nov 30, 2019

@Lokathor

This comment has been minimized.

Copy link
Contributor

@Lokathor Lokathor commented Nov 30, 2019

It's my understanding that things needing const if will stay nightly gated while const if itself is nightly gated. But you can probably submit it to be available as const on Nightly with just a PR.

9999years added a commit to 9999years/rust that referenced this issue Dec 3, 2019
With rust-lang#49146 merged, NonZero*::new can be const; see rust-lang#53718.
9999years added a commit to 9999years/rust that referenced this issue Dec 3, 2019
With rust-lang#49146 merged, {u8,i8,u16,...}::overflowing_div and
::overflowing_rem can be const; see rust-lang#53718.
9999years added a commit to 9999years/rust that referenced this issue Dec 3, 2019
With rust-lang#49146 merged, these can be const; see rust-lang#53718.
9999years added a commit to 9999years/rust that referenced this issue Dec 3, 2019
With rust-lang#49146 merged, these can be const; see rust-lang#53718.
9999years added a commit to 9999years/rust that referenced this issue Dec 3, 2019
With rust-lang#49146 merged, these can be const; see rust-lang#53718.
9999years added a commit to 9999years/rust that referenced this issue Dec 3, 2019
With rust-lang#49146 merged, NonZero*::new can be const; see rust-lang#53718.
9999years added a commit to 9999years/rust that referenced this issue Dec 3, 2019
With rust-lang#49146 merged, {u8,i8,u16,...}::overflowing_div and
::overflowing_rem can be const; see rust-lang#53718.
9999years added a commit to 9999years/rust that referenced this issue Dec 3, 2019
With rust-lang#49146 merged, these can be const; see rust-lang#53718.
9999years added a commit to 9999years/rust that referenced this issue Dec 3, 2019
With rust-lang#49146 merged, these can be const; see rust-lang#53718.
9999years added a commit to 9999years/rust that referenced this issue Dec 3, 2019
With rust-lang#49146 merged, these can be const; see rust-lang#53718.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
You can’t perform that action at this time.