Generic Integers V2: It's Time

clarfonthey commented 2 months ago

Summary

Adds the builtin types u<N> and i<N>, allowing integers with an arbitrary size in bits.

Details

This is a follow-up to #2581, which was previously postponed. A lot has happened since then, and there has been general support for this change from a lot of different people. It's time.

There are a few key differences from the previous RFC, but I trust that you can read.

Thanks

Thank you to everyone who responded to the pre-RFC on Internals with feedback.

jhpratt commented 2 months ago

As much as I dislike as casts and would prefer a better solution, until that solution exists (in the standard library), this is probably the best way to go.

:+1: from me

Alonely0 commented 2 months ago

Even if we should probably leave them out of the initial RFC for complexity reasons, I would just cheat with floats, as they rely on system libraries and hardware instructions way more than regular integers. By that, I mean that I'd allow f<32> for consistency reasons, but only those that are actually supported would compile; i.e., f<3> would throw a compile-time error (it could either be done at monomorphisation time, or disallowing const generics on that one). Overall, I think this RFC is in the right track, but I'd postpone it until we're past Rust 2024.

matthieu-m commented 2 months ago

Overall, I think this RFC is in the right track, but I'd postpone it until we're past Rust 2024.

Are you proposing delaying the discussion or the implementation?

My understanding is that with a release early 2025, Rust 2024 will be done by mid November, which is only 2 months away, and it seems quite unlikely this RFC would be accepted and implementation ready to start by then, so I see no conflict with regard to starting on the implementation...

... but I could understand a focus on the edition for the next 2 months, and thus less bandwidth available for discussing RFCs.

clarfonthey commented 2 months ago

Even if we should probably leave them out of the initial RFC for complexity reasons, I would just cheat with floats, as they rely on system libraries and hardware instructions way more than regular integers. By that, I mean that I'd allow f<32> for consistency reasons, but only those that are actually supported would compile; i.e., f<3> would throw a compile-time error (it could either be done at monomorphisation time, or disallowing const generics on that one).

The problem with this approach is that any "cheating" becomes permanently stabilised, and thus, it's worth putting in some thought for the design. This isn't to say that f<N> is a bad design (I personally don't like it, but I won't fault people for wanting to use it), but rather that u<N> and i<N> are good designs in several ways that f<N> is not.

Plus, monomorphisation-time errors were actually one of the big downsides to the original RFC, and I suspect that people haven't really changed their thoughts since then. Effectively, while it's okay to allow some of edge-case monomorphisation-time errors like this RFC includes (for example, asking for u<0xFFFF_FFFF_FFFF> is a hard error, since it's larger than u32::MAX), but not extremely-common errors like just asking for f<N> where N is anything that isn't 16, 32, 64, or 128.

One potential solution that was proposed for unifying u<N>, i<N>, usize, and isize was to have some separate ADT that encapsulates signedness and has different options for "size" and N. This kind of solution feels promising for generic floats since it means that you could have an impl like:

impl<const F: FloatKind> MyTrait for f<F> {
    // ...
}

And it would support all float types, forever, and there would be no invalid values for F since we've explicitly defined it. However, this requires const_adt_params which is currently unstable.

Overall, I think this RFC is in the right track, but I'd postpone it until we're past Rust 2024.

As stated: yes, RFCs take time to discuss and implement and it's very reasonable to expect people to focus on the 2024 edition for now. However, that doesn't mean that we can't discuss this now, especially since there are bound to be things that were missed that would be good to point out.

diondokter commented 2 months ago

I love this!

One point that is touched upon here is aliases for uN <=> u<N>.

I think that'd be super valuable to have. Rust already has a lot of symbols and being able to not use the angle brackets makes sure that the code is much calmer to look upon. It's also not the first explicit syntax sugar since an async fn is treated the same as fn -> impl Future in a lot of places.

Having the aliases also allows for this while keeping everything consistent:

fn foo<const N: usize>(my_num: u<N>) { ... }

foo(123); // What is the bit width? u32 by default?
foo(123u7); // Fixed it

clarfonthey commented 2 months ago

I love this!

One point that is touched upon here is aliases for uN <=> u<N>.

I think that'd be super valuable to have. Rust already has a lot of symbols and being able to not use the angle brackets makes sure that the code is much calmer to look upon. It's also not the first explicit syntax sugar since an async fn is treated the same as fn -> impl Future in a lot of places.

I agree with you, just didn't want to require them for the initial RFC, since I wanted to keef it simple. Ideally, the language will support uN aliases as well as uN suffixes.

Diggsey commented 2 months ago

Two things that came to mind:

Are there any issues with the self-referentiality of these types? Although usize is a distinct type, one could easily imagine wanting to make it a "new-type wrapper" around the appropriate integer type, which would make a circular dependency between the two implementations. We could say that usize is not implemented that way, but then it's surprising to me that usize would be the "foundation" rather than the other way around.
Even though LLVM can express integers of arbitrary size, it seems unlikely that these types have seen extensive use with unusual sizes. Maybe these integer types should be lowered to common integer types within rustc, so that backends can be simplified.

clarfonthey commented 2 months ago

When the last RFC was postponed, the stated reason was waiting for pure library solutions to emerge and letting the experience with those inform the design. I don't really see much of this in the current RFC, so here's a bunch of questions about it. It would also be great if some non-obvious design aspects of the RFC (such as limits on N, whether and how post-monomorphization errors work, padding, alignment, etc.) could be justified with experience from such libraries.

So, I agree that this was one of the reasons, but it's worth reiterating that also, at that time, const generics weren't even stable. We had no idea what the larger ecosystem would choose to do with them, considering how many people were waiting for stabilisation to really start using them. (We had an idea of what was possible, but not what would feel most ergonomic for APIs, etc.)

So, I personally felt that the library solution idea was mostly due to that fact that we didn't really know what libraries would do with const generics. And, overwhelmingly, there hasn't been much interest in it for what I believe to be the most compelling use case: generalising APIs without using macros, which right now cannot really be done without language support.

hanna-kruppe commented 2 months ago

By itself, the observation that the ecosystem isn't rushing to write and use such libraries doesn't tell us much. What if there just isn't much demand for generalizing code like that? On the other hand, if people have tried to write this code, and have run into concrete problems that they can't solve with more library code, then that is useful information for extending the language. Our discussion above has already focused on this. In addition, if there's any practical experience with API design, regardless of QoI problems like runtime performance / compile time / compiler diagnostics, then it would be useful to incorporate that into the RFC.

clarfonthey commented 2 months ago

Are there any issues with the self-referentiality of these types? Although usize is a distinct type, one could easily imagine wanting to make it a "new-type wrapper" around the appropriate integer type, which would make a circular dependency between the two implementations. We could say that usize is not implemented that way, but then it's surprising to me that usize would be the "foundation" rather than the other way around.

I mean, ultimately, the compiler can pretty easily deal with this kind of self-referencing by nature of what it is. Whenever the compiler even sees u<N> or usize, it's immediately going to replace them internally with some native backend integer type, and be able to triage integer intrinsics just fine. In fact, it already does this for usize: the difference between usize and uN, where N is the target pointer width, is effectively zero outside of library methods, where they're explicitly different types due to API concerns.

It would be an issue to have, for example, Struct<S> where S: Struct<S>, since it's unclear how the compiler can figure what S is without first figuring out what S is. But the compiler already knows what usize is, so, it doesn't need to try to figure it out before continuing.

Even though LLVM can express integers of arbitrary size, it seems unlikely that these types have seen extensive use with unusual sizes. Maybe these integer types should be lowered to common integer types within rustc, so that backends can be simplified.

I mean, even C is adding these now as features, so, I think that regardless of whether the compilers are robust enough, they will be robust enough by the time an implementation in Rust comes to fruition.

RalfJung commented 2 months ago

I mean, ultimately, the compiler can pretty easily deal with this kind of self-referencing by nature of what it is. Whenever the compiler even sees u or usize, it's immediately going to replace them internally with some native backend integer type, and be able to triage integer intrinsics just fine. In fact, it already does this for usize: the difference between usize and uN, where N is the target pointer width, is effectively zero outside of library methods, where they're explicitly different types due to API concerns.

That's not true. usize and u64 remain distinct types throughout the compiler, and they become the same only during LLVM IR generation. See e.g. UintTy, which indicates "which kind of unsigned integer" a TyKind::Uint is.

lolbinarycat commented 2 months ago

When stored, u<N> should always zero-extend to the size of the type and i<N> should always sign-extend. This means that any padding bits for u<N> can be expected to be zero, but padding bits for i<N> may be either all-zero or all-one depending on the sign.

how does this interact with enum layout optimizations? can Option<i<7>> be represented in a single byte?

programmerjake commented 2 months ago

how does this interact with enum layout optimizations? can Option<i<7>> be represented in a single byte?

that i<7> is stored sign-extended to i8 implies that, yes, Option<i<7>> can (but is not required to) be stored in a single byte since the compiler can pick any of -128..-64 or 64..128 to represent None since those are all out of range of i<7>

clarfonthey commented 2 months ago

wrong but left for posterity

> > how does this interact with enum layout optimizations? can `Option>` be represented in a single byte? > > that `i<7>` is stored sign-extended to `i8` implies that, yes, `Option>` can (but is not required to) be stored in a single byte since the compiler can pick any of `-128..-64` or `64..128` to represent `None` since those are all out of range of `i<7>` So, it's slightly more complicated than that; -128i8 and -64i7 have the same bit pattern in memory: all ones. However, you're right that there are values in there that don't, like positive 64 (which is `0b1_0000000`, and thus invalid since the 0 in the 7th bit doesn't match the 1 in the 8th bit. So, really, the valid ranges ranges are, assuming we're treating the number as an `i8`, `-64..0` and `64..128`.

That's not true. usize and u64 remain distinct types throughout the compiler, and they become the same only during LLVM IR generation. See e.g. UintTy, which indicates "which kind of unsigned integer" a TyKind::Uint is.

This is where I definitely should have been more careful in my wording: I meant that the backend doesn't distinguish them, but you're right that the type system needs to distinguish them all the way until the code has all been generated. My statement was basically wrong as-is.

clarfonthey commented 2 months ago

Why do they even have that lever?

programmerjake commented 2 months ago

So, it's slightly more complicated than that; -128i8 and -64i7 have the same bit pattern in memory: all ones.

you need to check your math, -1 has all ones, but -64i7 as u8 is 0xC0 and -128i8 as u8 is 0x80 -- neither of them are remotely all ones nor the same bit pattern.

clarfonthey commented 2 months ago

So, it's slightly more complicated than that; -128i8 and -64i7 have the same bit pattern in memory: all ones.

you need to check your math, -1 has all ones, but -64i7 as u8 is 0xC0 and -128i8 as u8 is 0x80 -- neither of them are remotely all ones nor the same bit pattern.

You're right 🤦🏻

hecatia-elegua commented 2 months ago

I want to chime in here and link to another library: https://github.com/danlehmann/arbitrary-int That lib is used in both @danlehmann's and my own bitfield libs.

I would say the main painpoints of using a library here are all the conversions between different number sizes (and in the case of bitfields, structs) and the ergonomics (e.g. https://github.com/hecatia-elegua/bilge/issues/75).

Another nice byproduct of this RFC would be the constification of conversions between arbitrary ints by design. For some time I used the unstable const-trait-impl with const-from for converting between things, but that's being reworked now and not currently available.

danlehmann commented 2 months ago

Hey, I'm the author of https://crates.io/crates/arbitrary-int . It seems like this proposal has some overlap with what I've built as a crate, so I can talk a bit about the hurdles I've run into.

Arbitrary-int has a generic type UInt<T, const BITS: usize>. T refers to the underlying type, which is usually the next larger native integer.

It also provides types to shorten the name. For example u3 becomes a shortcut for UInt<u8, 3>, u126 is a shortcut for UInt<u128, 126>. The types all pick the next largest built-in type, though it's also possible to specify this directly through e.g. UInt<u32, 6>.

It also provides a Number trait which unifies arbitrary-ints with regular ints, allowing completely generic programming over all of those types.

In general, implementing this as a crate worked pretty well, but there are some downsides:

Implementing From and TryFrom: This can't be done with the current type system. Once you implement From, the standard lib automatically adds TryFrom; I tried many ways of limiting this based on the size of the BITS involved but the type system always complains about multiple implementation. I think the specialization feature would allow me to address that, but it's unstable.
Lack of const generics: The other issue with From is that it's a trait which can't be used in const contexts; to work around that, arbitrary-int provides another function new which IS const and which allows creating a type directly.
No special syntax: As it's not a built-in feature, I can't provide custom suffixes like 1u4. So the shortest ways to create a number is generally u4::new(1). Not horrible, but not quite native.

danlehmann commented 2 months ago

Hey, I'm the author of https://crates.io/crates/arbitrary-int . It seems like this proposal is very close to what I've built as a crate (I think arbitrary-int is also the closest to this rfc), so I can talk a bit about the hurdles I've run into.

Arbitrary-int has a generic type UInt<T, const BITS: usize>. T refers to the underlying type, which is usually the next larger native integer.

It also provides types to shorten the name. For example u3 becomes a shortcut for UInt<u8, 3>, u126 is a shortcut for UInt<u128, 126>. The types all pick the next largest built-in type, though it's also possible to specify this directly through e.g. UInt<u32, 6>.

It also provides a Number trait which unifies arbitrary-ints with regular ints, allowing completely generic programming over all of those types.

In general, implementing this as a crate worked pretty well, but there are some downsides:
* Implementing `From` and `TryFrom`: This can't be done with the current type system. Once you implement `From`, the standard lib automatically adds `TryFrom`; I tried many ways of limiting this based on the size of the BITS involved but the type system always complains about multiple implementation. I think the `specialization` feature would allow me to address that, but it's unstable.

* Lack of const generics: The other issue with `From` is that it's a trait which can't be used in const contexts; to work around that, arbitrary-int provides another function `new` which IS const and which allows creating a type directly.

* No special syntax: As it's not a built-in feature, I can't provide custom suffixes like `1u4`. So the shortest ways to create a number is generally `u4::new(1)`. Not horrible, but not quite native.

Also due to my design decision to base everything on a simple types (no arrays), the maximum number of bits supported is u127.

clarfonthey commented 2 months ago

Also due to my design decision to base everything on a simple types (no arrays), the maximum number of bits supported is u127.

I hadn't actually read the code yet, but I'm actually a bit curious why the max number of bits is 127 instead of 128. This feels like a weird restriction.

danlehmann commented 2 months ago

Also due to my design decision to base everything on a simple types (no arrays), the maximum number of bits supported is u127.

I hadn't actually read the code yet, but I'm actually a bit curious why the max number of bits is 127 instead of 128. This feels like a weird restriction.

It is 128 bits actually. UInt<u128, 128> works just fine (though it is just somewhat useless as you might as well use the actual u128). My main point was that larger numbers aren't possible, unlike it e.g. ruint, which operates on arrays.

danlehmann commented 2 months ago

By the way, I love this RFC! While arbitrary-int (as well as ux) provide the unusually-sized ints like u48 etc, having a built-in solution will feel more natural and allows to treat numbers in a much more unified fashion, which I'm looking forward to.

programmerjake commented 1 month ago

(replying to https://github.com/rust-lang/rfcs/pull/3686#discussion_r1787372929 here so it's less likely to get lost when that thread gets resolved)

How often do you need an array with one element per bit?

when doing SIMD with bitmasks -- all the time. using Mask<T, N> and Simd<T, N> will be more common, but using [T; N] and u<N> will still be decently common. Mask<T, N> on many architectures is just a wrapper over u<N> (currently done with macros for a limited set of N), and Simd<T, N> is basically the same as [T; N] except with perhaps more alignment and better codegen.

In particular this is a big motivation for using usize for N in u<N>, since that's what all of Simd<T, N>, Mask<T, N>, and [T; N] need.

hanna-kruppe commented 1 month ago

I am not super familiar with core::simd, so please correct me if I misunderstood something. I understand that the N in Simd<T, N> and Mask<T, N> needs to be usize because both often occur in type signatures together and Simd<T, N> is closely tied to [T; N] in various ways. But mixing those types with u<N> seems much more niche, for reasons that I think are pretty fundamental.

From looking at the current implementation it seems that Mask<T, N> is a wrapper for Simd<T, N> on every target except x86 with AVX-512. That's what I would expect, since SIMD masks on most architectures really want to stay in SIMD registers or in dedicated mask registers when they exist -- and the latter are more like <i1 x N> than uN. Even AVX-512 has the k-regs, but for various reasons it's common to pass masks around as integers. Punning between masks and integers is sometimes useful, but it's not free (even on x86, even more so in the rest of the computing world) and should only be done very deliberately. That's one reason why Mask<T, N> and its equivalents in libraries like memchr and hashbrown have a lot of helper methods instead of just conversions to/from integers.

As long as masks are a separate type with platform-dependent representation, it seems to me that the interaction with u<N> is only skin-deep. It could simplify a few functions in the public API, but otherwise masks will still revolve around a cfg'd newtype or associated type. Users who want abstract over lane count will also be limited in how much they can equivocate between masks and integers: they may want a method like fn to_bits(self) -> u<N> on Mask<T, N> but it's not clear to me whether a return type like u<{N as u32}> would be much worse for them. Ideally there would be no casts anywhere, but as @scottmcm points out, choosing usize also requires casts for some reasonable use cases.

clarfonthey commented 1 month ago

Honestly, if the arguments for usize and u32 are equally compelling, I personally think the tie should be broken toward usize, for the simple reason that it is effectively the default type for generic constants. The number of bits makes sense as an unsigned size, and that's the full reasoning.

I do think that it would be worthwhile to choose one over the other if there actually were a lot of cases where it were valuable, and SIMD does feel compelling enough to be valuable, but honestly, it's kind of tied at this point.

I personally think that choosing u32 for a lot of the integer methods that involve bits was a mistake, but we're stuck with it for better or worse, and it feels like no matter what we do, there is going to be some inconsistency somewhere. So, might as well conceptually treat it as an "array of bits" IMHO.

Like realistically, if we were choosing an appropriate size for the count of bits, we should have chosen u16 instead of u32, since more than 8KiB in a single integer that isn't a big-integer feels kind of absurd. But again, hindsight doesn't really matter when deciding this; we just have to figure out a compromise.

hanna-kruppe commented 1 month ago

Using u16 would have the advantage that conversion to u32 and to usize is always lossless while the opposite direction isn’t. usize::from(x) isn’t a const expression today but the monomorphic case could be allowed without touching the whole “maybe-const trait bounds” subject. It’s still too wordy to seriously propose (without adding implicit widening, which is a whole other can of worms). But if we ever get usize: From<u32> then that would be a point in favor of u32 in my opinion.

Wild idea: is there anything forcing the u<N> and i<N> constructors to pick a single type for N? If they’re mostly compiler magic anyway, couldn’t they accept any unsigned integer? For example, can u<7u32> and u<7usize> be the same type? That might resolve most (not all) clashes of u32 vs usize in const generic APIs.

hanna-kruppe commented 1 month ago

Nevermind that last bit, the lang item might not have to pick a type for N, but all the impl blocks involving those types have to pick a type for their const generic parameter, so fn foo<const N: u8>(x: u<N>) couldn’t do anything with it’s argument.

clarfonthey commented 1 month ago

I mean, it would be nice if you could allow {N as T} expressions in const generics as a special case when there's no truncation, under the assumption that it's always unambiguous, but again, this runs into all the other problems with const generics and unification.

I don't think it'd be a good idea to delay deciding what the type of the parameter should be in this case, although we might end up getting the above anyway before this feature is actually implemented, since it's currently one of the project goals; see https://github.com/rust-lang/rust-project-goals/issues/100

hanna-kruppe commented 1 month ago

You mean carve it out as something that doesn't even need any of the implementation challenges to be solved because you could mostly ignore the cast completely? Might work, might cause horrible problems down the line, I don't know. But I'm already working under the assumption that "MVP generic const expressions" is a prerequisite for generic integers to be stabilized and widely used. Starting from a smaller type doesn't buy you anything in terms of language design or type system interactions,, but it's a nicer model for users (well, for me at least) because it means far fewer places where my "could this truncate?" spidey sense tingles.

programmerjake commented 1 month ago

I am not super familiar with core::simd, so please correct me if I misunderstood something. I understand that the N in Simd<T, N> and Mask<T, N> needs to be usize because both often occur in type signatures together and Simd<T, N> is closely tied to [T; N] in various ways. But mixing those types with u<N> seems much more niche, for reasons that I think are pretty fundamental.

From looking at the current implementation it seems that Mask<T, N> is a wrapper for Simd<T, N> on every target except x86 with AVX-512.

That's mostly because we only got around to setting it to bitmasks on AVX512, other targets that have bitmasks are at least RISC-V V and ARM SVE.

I fully expect Mask<T, N> to just be a wrapper over u<N> for any architecture that has bitmasks mostly because that gives the correct in-memory size, mask operations would either be direct integer operations on the mask integer and/or intrinsics that bitcast to llvm ir <N x i1> bitvectors. note that none of those intrinsics are architecture-specific, we let llvm translate from architecture independent operations to whatever the architecture uses -- except for dynamic swizzle since llvm doesn't yet have llvm ir instructions/intrinsics for architecture-independent dynamic swizzle.

clarfonthey commented 1 month ago

But I'm already working under the assumption that "MVP generic const expressions" is a prerequisite for generic integers to be stabilized and widely used.

I'm not, actually, which is why I felt comfortable restarting this RFC at this point in time.

Back at the original RFC's time, we were in a similar situation with regard to const generics in general that we are right now with regard to these other const generic features: they were definitely coming, we had plans for them, and we abstractly knew what they would look like, but they weren't complete yet. The difference is that we genuinely cannot implement generic integers without const generics, whereas we totally can have generic integers without generic const expressions.

Yes, it's likely that a lot of these things will be mostly resolved by the time an implementation exists, but even if they were delayed for a year, they didn't live up to what we hoped they'd be, or they take a very long time to become stable, I think that generic integers could still exist and be useful. For example, if we allowed most integer methods and operations via the generic type but still made from_ne_bytes exclusive to the current integer types, I would say that's still very valuable, and we can always improve it later.

So, I think that it's better to consider the feature from the perspective that these features don't exist, so we don't hype up potentially unrealistic fantasies of what we'll be able to do with them. And I think that even without them, this is still incredibly useful of a proposal, and it's not incompatible with the improvements we can make later with these features.

hanna-kruppe commented 1 month ago

That's mostly because we only got around to setting it to bitmasks on AVX512, other targets that have bitmasks are at least RISC-V V and ARM SVE.

Adding additional platforms that use an integer representation for masks internally doesn't remove the (common and important!) ones that prefer the vector representation. It also doesn't make mask<->integer punning in user code any better for performance portability -- even on SVE and RVV, you want the generated code to stay in predicate/mask land as much as possible.

I also have some doubts about whether integers are really the best representation of masks in RVV and predicates in SVE, considering ISA design, calling conventions, the vendor-defined C intrinsics, and what little I know about existing uarchs. But I don't want to come off as telling you and the others working on portable SIMD how to do your job and this isn't the right venue for a deeper discussion in any case.

programmerjake commented 1 month ago

Adding additional platforms that use an integer representation for masks internally doesn't remove the (common and important!) ones that prefer the vector representation. It also doesn't make mask<->integer punning in user code any better for performance portability -- even on SVE and RVV, you want the generated code to stay in predicate/mask land as much as possible.

portable-simd's only vector representation for masks is not bitmasks, but instead full integer elements that are 0 or !0 (we call them full masks). e.g. on avx2 Mask<i16, 16> is basically Simd<i16, 16> but with each element known to be either 0 or !0.

bitmasks currently are just struct wrappers around an integer (and that seems unlikely to change, though operations may change to use more intrinsics). we rely on llvm optimizations to translate that to operations on mask/predicate registers.

hanna-kruppe commented 1 month ago

I don't get why you're explaining that in response to what I've written. Let's try a different angle. Can you point at some concrete code snippets where u<N> would occur together with Simd<T, N> or Mask<T, N>?

I've tried to guess at where exactly you're trying to go with that connection but it feels a bit like we've been talking past each other. Put differently, I would distinguish between two aspects:

u<N> would be used internally inside Mask<T, N> on some platforms, in place of what's currently [u8; (N+7)/8] behind some macros and traits. I think I understand the benefits of this, but their scope is very bounded.
Code using the portable SIMD APIs would juggle u<N> along other type constructors also involving N (and wanting it to be usize. This aspect I don't really understand yet.

I'm aware of the existence Mask::{to,from}_bitmask (currently dealing in u64 but u<N> would be more natural). I'm specifically wondering about how commonplace and useful those two methods are, as opposed to all the other ways of working with masks. As I said, I don't have much experience with portable SIMD APIs, so I really don't know the answer. From all I know about the codegen that I'd want on various architecture, it seems like a performance footgun for portable code. So if you ask me, I'd only use in target- and lane-count-specific code that happens to be more convenient to write with core::simd than with core::arch (where the extra generality of u<N> as opposed to u64 is not very useful). If I'm wrong about that, please show me a counter-example.

clarfonthey commented 1 month ago

Unrelated to the above, but another thing that occurred to me as a benefit of this system is exhaustive matching.

In a recent project I have quite a few places where I'm doing bitmasking, then matching on the result, where there always has to be a wildcard unreachable!() branch. This could help reduce the number of cases of that by replacing them with exhaustive matches over smaller integer types.

juntyr commented 1 month ago

Unrelated to the above, but another thing that occurred to me as a benefit of this system is exhaustive matching.

In a recent project I have quite a few places where I'm doing bitmasking, then matching on the result, where there always has to be a wildcard unreachable!() branch. This could help reduce the number of cases of that by replacing them with exhaustive matches over smaller integer types.

That’s a really good point, that I think even applies to current types.

Let’s say I have a random number generator that gives me a u64, and I want to split that into two u32s. For explicitness sake, I will usually bitmask both the original number and the down-shifted one with u32::MAX before as-casting to u32. Clippy of course still complains and so I need to allow some truncation lint.

What would be great, especially for generic ints, would be to have a method truncate_into<const N: usize>(self) -> u<N> that would do both the masking and type conversion and be as explicit as doing the bit masking myself.

clarfonthey commented 1 month ago

What would be great, especially for generic ints, would be to have a method truncate_into<const N: usize>(self) -> u<N> that would do both the masking and type conversion and be as explicit as doing the bit masking myself.

So, at least that part will hopefully be covered by the WrappingFrom RFC, but I was thinking of going further than this and maybe offering a bitfield<const N: usize, const M: usize>(self) -> u<{M-N}> function, maybe returning u<M> depending on how long generic const exprs take.

Sure, this doesn't cover cases where the bit fields are discontinuous, but it covers most of them.

programmerjake commented 1 month ago

I don't get why you're explaining that in response to what I've written. Let's try a different angle. Can you point at some concrete code snippets where u<N> would occur together with Simd<T, N> or Mask<T, N>?

I've tried to guess at where exactly you're trying to go with that connection but it feels a bit like we've been talking past each other. Put differently, I would distinguish between two aspects:

u<N> would be used internally inside Mask<T, N> on some platforms, in place of what's currently [u8; (N+7)/8] behind some macros and traits. I think I understand the benefits of this, but their scope is very bounded.

yes they are bounded, but also critical for getting arbitrary length Simd types so we can remove the trait bounds on the length, which makes portable-simd much more ergonomic when dealing with generic lengths.

Code using the portable SIMD APIs would juggle u<N> along other type constructors also involving N (and wanting it to be usize. This aspect I don't really understand yet.

I'm aware of the existence Mask::{to,from}_bitmask (currently dealing in u64 but u<N> would be more natural). I'm specifically wondering about how commonplace and useful those two methods are, as opposed to all the other ways of working with masks.

One example is when counting the number of Mask elements that are set, there you'd use my_mask.to_bitmask().count_ones(). Also for figuring out the first/last index that is set/clear (e.g. searching for stuff), where you'd use my_mask.to_bitmask().trailing_zeros() to return the index of the first set element, and similarly for the other combinations.

tmccombs commented 1 month ago

One example is when counting the number of Mask elements that are set, there you'd use my_mask.to_bitmask().count_ones(). Also for figuring out the first/last index that is set/clear (e.g. searching for stuff), where you'd use my_mask.to_bitmask().trailing_zeros() to return the index of the first set element, and similarly for the other combinations.

Those both seem like things that it would make sense to have methods for directly on Mask.

programmerjake commented 1 month ago

One example is when counting the number of Mask elements that are set, there you'd use my_mask.to_bitmask().count_ones(). Also for figuring out the first/last index that is set/clear (e.g. searching for stuff), where you'd use my_mask.to_bitmask().trailing_zeros() to return the index of the first set element, and similarly for the other combinations.

Those both seem like things that it would make sense to have methods for directly on Mask.

Yeah, that's part of the problem: either things are popular enough to warrant a method on Mask or are not quite popular enough so they need to depend on to_bitmask()...

This issue on adding something like to_bitmask() to WASM also has some other uses: https://github.com/WebAssembly/simd/issues/131 e.g. one commenter wanted to use to_bitmask() for indexing for a decision tree for JPEG stuff: https://github.com/WebAssembly/simd/issues/131#issuecomment-573839183

also, AVX512 has kadd* for adding two masks to each other, so they presumably thought adding two bitmasks was useful enough to add to AVX512, idk what it's used for though... This seems like something that won't be added to Mask though.

hanna-kruppe commented 1 month ago

yes they are bounded, but also critical for getting arbitrary length Simd types so we can remove the trait bounds on the length, which makes portable-simd much more ergonomic when dealing with generic lengths.

If the end goal is to not have any bounds, then that's a fair point. There are other possible solutions (e.g., enough "generic const expressions" to make struct Mask<N: usize>([u8; (N + 7) / 8]) feasible) but they're not better either and who knows which will get implemented first.

One example is when counting the number of Mask elements that are set, there you'd use my_mask.to_bitmask().count_ones(). Also for figuring out the first/last index that is set/clear (e.g. searching for stuff), where you'd use my_mask.to_bitmask().trailing_zeros() to return the index of the first set element, and similarly for the other combinations.

I know these use cases well, but as mentioned I would prefer not to write them that way in portable SIMD because there are much more efficient ways to implement them on most non-x86 targets. Sometimes even the most efficient spelling is not worth it (e.g., SwissTable/Hashbrown switches between 128-bit SSE2, 64-bit NEON, and integer-based SWAR depending on the target mostly because of the wildly varying cost of the necessary mask operations). As far as possible, a portable API should avoid guiding people into performance portability cliffs, and provide more abstract operations whenever feasible. This was also a theme in the Webassembly discussion you linked. As you say, there's always a long tail of creative uses that the mask abstraction can't cover completely, so I would never argue for not having conversions between masks and integers at all. But I think in the context of "using core::simd instead of core::arch, and abstracting over lane count" they're so niche that nicer APIs for that specific combination comes very low on the list of priorities. Removing SupportedLaneCount<N>-style bounds from portable SIMD code that only ever mentions Mask<T, N> and Simd<T, N> seems much more significant to me.

Aside about AVX-512 `kadd*`

> also, AVX512 has [`kadd*`](https://www.felixcloutier.com/x86/kaddw:kaddb:kaddq:kaddd) for adding two masks to each other, so they presumably thought adding two bitmasks was useful enough to add to AVX512, idk what it's used for though... This seems like something that won't be added to `Mask` though. I would love to hear why the architects added this one. I googled a bit and found virtually no mention of it and [only one potential use](http://numberworld.org/y-cruncher/internals/addition.html). But that article also says that the instruction is too slow to be worthwhile on the CPUs considered and simply doing the mask->GPR->mask round-trip that `kadd*` is supposed to avoid turns out faster. Indeed Agner Fog lists it as latency 4 throughput 1 on *all* existing Intel chips that implement it. Zen 4 has put more effort into it, which could either be because they care about some code that uses or could use the instruction, or because it just happened to be easier for them because of other design decisions. In any case, this instruction just replaces three cheap uops (move mask register into GPR, do add in GPR, move result from GPR to mask register) with one -- whether that's a win depends on their relative cost and on which uarch resources are the bottleneck for whatever you're doing. It's potentially very useful if and only if you're already counting uops and critical path length on a particular targets and spend hours thinking about how you can reduce those figures by warping how you do a computation around the idiosyncrasies of your target hardware. That sort of work can be interesting and useful, but in my experience it's rarely if ever done from behind the veil of portable SIMD abstractions. Yeah, I wouldn't add this operation to `Mask`. But also, if that was the only operation that required mask<->uN conversions (it's not), I don't know if that would be sufficient motivation for adding it.

programmerjake commented 1 month ago

As far as possible, a portable API should avoid guiding people into performance portability cliffs, and provide more abstract operations whenever feasible.

yes, but I also think that translating from a reasonable portable implementation to whatever weirdness your particular cpu architecture requires should be mostly llvm's problem to handle -- since that's how almost all of portable-simd currently operates and that allows portable-simd's users to easily write actually portable simd and still get good performance without having to spend weeks researching how every different target does stuff its own special way.

iirc so far the only exceptions to portable-simd's leaving it up to llvm are switching between bitmasks/fullmasks, implementing dynamic swizzle (since llvm just plain doesn't have a non-arch-specific operation for that), and working around aarch64 backend bugs for integer division.

so, in summary, I think a programmer writing my_mask.to_bitmask().count_leading_zeros() or any other common bitmask op should compile to the optimal arch-specific weirdness for that, even if we wrap that to_bitmask call sequence into a Mask helper method.

hanna-kruppe commented 1 month ago

I don't disagree but I also don't think it conflicts with what I said, considering that LLVM does not (and might never) 100% live up to that goal. Providing higher-level operations on Mask and guiding people towards those doesn't require users to know about different targets and implementation strategies, they just need the methods to exist and documentation to encourage their use. The higher level operations are strictly better whenever they're applicable: easier to use than manually translating to integer bit twiddling, more self-documenting, gives at least equally good codegen, and makes it easier for Rust to work around missing optimizations in LLVM or other changes in backends.

As I said before, getting rid of the bounds on N in the Simd<T, N> and Mask<T, N> is a good argument independently of the above. Everything beyond that has only a very loose relation to u<N>, so I would suggest we either stop here or take it elsewhere (you can open an issue anywhere and ping me, if you want).

rust-lang / rfcs