Ranged integers for performance

language design
3

AFAIK this has already been discussed a couple of times, but no definite design has been produced yet. See for example:

The problems start to appear when you want to do operations on that type. If you add 1 to a usize[.. N] should you get a usize[1 .. N+1]? Or an Option<usize[.. N]>? Maybe just an usize? Keeping track of these invariants also quickly becomes quite a lot of work for the compiler and for who needs to implement the feature.

ps: Regarding your specific piece of code, it can be optimized with this weird trick:

fn permutations_array<T, const N: usize>
                     (data: &[T; N]) -> impl Iterator<Item=[&T; N]> {
    from_generator(move || {
        if N == 0 { return; }
-       let mut perm = from_fn(|i| i);
-       yield perm.map(|i| &data[i]); //1
+       let mut perm = from_fn(|i| &data[i]);
+       yield perm; //1

        loop {
            let mut i = N - 1;
-           while perm[i - 1] >= perm[i] {
+           while perm[i - 1] as *const _ >= perm[i] as *const _ {
                i -= 1;
                if i < 1 { return; }
            }
            let mut j = N;
-           while perm[j - 1] <= perm[i - 1] { j -= 1; }
+           while perm[j - 1] as *const _ <= perm[i - 1] as *const _ { j -= 1; }
            perm.swap(i - 1, j - 1);
            i += 1;
            j = N;
            perm[i - 1 .. j].reverse();
-           yield perm.map(|i| &data[i]); //2
+           yield perm; //2
        }
    })
}

Or, alternatively, you could define something like this, limiting the unsafe to a very small interface (which is the very point of unsafe!):

mod bounded {
    #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    pub struct Bounded<const N: usize>(usize);
    
    impl<const N: usize> Bounded<N> {
        pub fn new(n: usize) -> Self {
            assert!(n < N);
            Self(n)
        }
        pub fn into_usize(&self) -> usize {
            let n = self.0;
            if !(n < N) {
                unsafe { std::hint::unreachable_unchecked() };
            }
            n
        }
    }
}
3 Likes