It would be nice to have a type NonMaxUsize that is a usize without the value 0b11...1. For this type, it would also be useful to have niche value optimisation in enums, such that if size_of::<usize>() is 8 bytes, then an Option<NonMaxUsize> can be stored in 8 bytes as well.
Background
In Rust, I often find myself designing datastructures with indices into Vec. For example, in a graph datastructure in Rust, I would use an usize to index e.g. nodes in a Vec<NodeType>. Further, in graph algorithms, I often end up needing optional node ids. Their natural representation in Rust would be Option<usize>.
The Problem
The type Option<usize> in Rust takes 16 bytes, while usize only takes 8 bytes (64 bit arch, playground). However Option<usize> stores only one more value than usize, and hence wastes most of the extra space. When working with large graphs as they appear for example in route planning in road networks or various applications in bioinformatics, wasting memory like this is not desirable.
The Proposal
I would assume that the value usize::MAX will never be a valid index. In turn, by introducing a type NonMaxUsize and enabling niche value optimisation for it, we could get the size of our optional node id down to 8 bytes by using Option<NonMaxUsize>.
Alternatives
Use pointers: by convention, address zero is always unused, hence we could use nullptr to represent the absence of a value. However, Rust has been explicitly designed around this (and around using pointers in general) for good reasons.
Use Option<NonZeroUsize> for indices instead: possible, but we would either need to leave the element at position 0 unused by convention, or subtract one every time we use the index. Subtracting appears clearly inferior, because it means more instructions and hence less performance. Leaving the element at position zero unused would work, but feels hacky.
Create a custom OptionalNonMaxUsize that stores usize internally and can be converted from and into Option<usize>, using usize::MAX to represent None: has some implementation overhead, but probably (hopefully) compiles down to be as fast as using Option<NonMaxUsize> with niche value optimisation would be.
As of now, I am using the last alternative, and it works. But it feels like a shortcoming of Rust that a "null index" does not get niche value optimised, while e.g. Option<Box> or Option<NonZeroUsize> enjoy this feat. Hence it would be nice to have "null indices" as part of the language as well.
I would love to have a more general feature that let me declare range limited integer types, leaving the rest for automatic niche optimisation. E.g. If I have a number that only be in the range 0..32, why can't the optimiser use the rest of the range of an u8 for other uses?
I suspect that adding something like this is in and of itself unobjectionable, but the specific proposal here is probably not the right path. I suspect we'll want something that generalizes a little better (perhaps being able to define your own niches) instead of trying to add specific cases one-by-one.
So the main problem here is figuring out how to drive custom niches to stabilization. That's probably a lang-team thing? I'm not sure where they're at in terms of whether it's a desirable path (in general) or not.
I had the same issue where I was storing decimal digits 0..=9 in struct Digit(u8), and went with OptionalDigit that can be converted to and from Option<Digit> but is stored in a single u8 by manually using a niche value.
struct Number<const R: RangeInclusive<i128>>
where
Cond<{ R.start < R.end }>: True,
{
inner: /* magic type which has the size of
`((R.start - R.end).abs() as u128).next_power_of_two().ilog2() / 8` */
}
Which would have the correct niche value optimization so to emulate NonZero and NonMax you'd do:
struct NonZeroUsize(Numer<{ 1..=usize::MAX as i128 }>); // same size as usize
struct NonMaxUsize(Numer<{ 0..=(usize::MAX as i128) + 1}>); // same size as usize
struct Digit(Number<{ 0..=9 }>); // same size as u8
There's some experimental movement on "pattern restricted types" where you can write something like usize is 0..usize::MAX or u8 is 0..=9 for any type and pattern of that type to restrict what values are permitted, to replace the current ad-hoc #[rustc_valid_scalar_range_{start|end}] attributes. This is generally seen as the most promising way forward, since the compiler is already knowledge about patterns.
But there's still a number of thorny questions around subtyping, coercions, trait impl applicable, etc. last I saw.
For transient stack temporaries, just use Option<usize>; optimizations will reduce stack usage reasonably well. For values that get referenced and stick around for longer, though, your best bet currently remains the sentinel value (or reserving index zero for some special semantic[1]).
I've seen at least one data structure store its pointer as &data[-1] such that real data starts at data[1] just so that zero is an invalid index while keeping indexing as just a direct indexed pointer access. Perhaps overly clever, but localized to that component. (And exposed to C where memset(0) being the default/null/placeholder value is quite a desirable property.) âŠī¸
Just to expand on that based on my understanding of current ideas: For subtyping to work nicely, Option<u8 is 0..=9> would still need a separate discriminant byte, so that for instance &Option<u8 is 0..=9> could be used as an &Option<u8>.
On the other hand, a new-type like struct Digit(u8 is 0..=9) would have niches because it is not a subtype of anything with a larger set of values. That should also be the case for a type with const generic bounds.
This is correct: no Rust allocation (e.g. the heap slice managed by the Vec) can span more than isize::MAX bytes. So the maximum length of a [T] is isize::MAX / size_of::<T>() (with a special case for slice of ZST being allowed to have usize::MAX length to avoid the divide by zero).
To that end, Rust kind of wants for not just NonMaxU32, but also NonMinI32 and NonNegativeI32. (u31?)
But I don't expect we'll actually add any new restricted integer types into std until there's a more principled way to define them (i.e. pattern restricted types) than the ad-hoc rustc internal attribute hacks of questionable soundness.
Well, anything over isize::MAX can only ever be a valid index for a slice of ZST.
So I think more often useful would be the intersection of isize and usize, since that's all you need for any actually useful case, as far as I can tell. (I've never seen anyone explain a need to use arrays or Vecs of ZSTs with a length more than isize::MAX .) That would leave way more niches available, and also allow things like usize: From<ThisNewThing> & isize: From<ThisNewThing>.
(But, as others have said, I'd rather get a general system that add more one-off types, since there's so many reasonable one-off types.)
I think it makes sense to add a NonMax in std that is initially backed by NonZero, and then when (and if) Rust gets full support for arbitrary niche values, switch to that (this means that the bit pattern of NonMax would be #[repr(Rust)] and generally unavailable for inspection by FFI code). My rationale is that while NonMax is a special case that doesn't generalize, it's a very useful special case.
Maybe a plan would be, stabilize some common and useful Non* types now on stdlib, and maybe expose the full generality of consecutive niches if and when pattern types become available.
if coercion is used instead of subtyping, Option<u8 is 0..=9> can be a single byte since (according to what I'd expect the semantics to be) the is is not at the top level so &Option<u8 is 0..=9> can't be coerced to &Option<u8>, however, for Option<u8> is None | Some(0..=9) the isis at the top-level so would need to be 2 bytes.
I have a case for NonEmptyString. I'm writing an iterator over file/dir entries on a remote FTP server using LIST command. The first step in this algorithm should return the name of an entry if present or nothing otherwise. Right now I have a choice to either use Option<String> and pay negligible but annoying performance penalty OR pass around String and make the callee of this internal function. It is a pretty bad case but I bet that there could be problems where NonEmptyString could actually be beneficial.
P.S.
I could benefit even more from better support for self-referential structs but that's another topic.
Hmm, String (Vec) could use a dangling NonNull for the pointer when the string has no allocation, freeing the null pointer for discriminant use. In fact, I thought it does so already?
We can already add usize::MAX/2 + 1 niches to Vec, because the capacity can only be over isize::MAX when T is a ZST, and thus it's not actually allocated at all and the capacity is a lie: https://github.com/rust-lang/rust/pull/106790
Adding two more for zero is probably not that useful in comparison.
You made me realise that the solution to the problem I mention in the first post is not a NonMaxUsize type, but rather something like a VecIndex type. This type would represent exactly all the values that can be valid indices of a Vec. Plus possibly one more to represent the first invalid index for the purpose of ranges or so, if that is required (I don't know, just speculating).
I understand that language-wise, having the most generic option of a custom-ranged integer type akin to u8 is 0..=9 would be very useful in various cases, and could also cover the VecIndex case by doing usize is 0..=isize::MAX. Let me nevertheless explore the implications of adding a VecIndex type to the standard library. This is likely impossible, but would also come with some advantages:
Readability: for someone who does not know about the implementation details of Vec, it is not clear that usize is 0..=isize::MAX refers to the possible indices of a Vec. Further, if one asks the question what this type is, there is not documentation available, only the documentation of usize and isize. On the other hand, a type VecIndex is easier to understand already by name, and the corresponding documentation could explain what it is and what it is meant for.
Writability: I am sure noone will write usize is 0..=isize::MAX everywhere in their Rust program. Likely everyone who does not just want to use usize for indexing would make their own type alias. If every crate that uses a feature uses the same boiler plate around that feature, the boilerplate should likely be part of the standard library.
Semantics: A usize allows to store values that can never be valid indices into a Vec. So in a sense, it is not the correct type to index into Vec, since it can assume values that will always crash a Rust program.
To add some more details about how I imagine a VecIndex would be:
It probably lives under std::vec::VecIndex.
It implements at least TryFrom<usize>, TryFrom<isize>, Into<usize> and Into<isize>.
Arithmetics are not necessary. These can still be added later if needed.
To make it work well with Vec, we should also add impl<T> Index<VecIndex> for Vec<T>, and the corresponding IndexMut implementation.
Now for the issues:
Allowing to index into Vec with more than one type would break type inference when writing e.g. v[4] and all other cases where the type of the index is restricted only by the index operation. So to not break everyone's code, one would need to also change type inference in this case to favour usize. Which would probably create a mess.
Further, we get even more issues if we want the type to play nice with the functions of Vec, and all other functions in the standard library that currently use usize to index a Vec. They would need to be changed to use the new more accurate VecIndex type. This is a breaking change that would affect most parts of the standard library, and hence also most crates. Well...
Conclusion
It is sad, but it seems like the Rust standard libary is locked into the usage of usize for indexing vectors. And changing that seems impossible. So it seems like the problem of having optional Vec-indices needs to be solved by a crate, when at some point custom-range integers are stable. If I recall the orphan rule correctly, all the details I mentioned above could actually be implemented in a crate.