5 ms·

If you created a custom NonZero type, how would the Rust compiler figure out how to optimize that? How would one communicate properties/traits of a custom type

If you created a custom NonZero type, how would the Rust compiler figure out how to optimize that? How would one communicate properties/traits of a custom type (like a non-zero unit) that a compiler can leverage to optimize (in general, for any programming language)?

dwattttt 2y ago
I don't think the mechanics of being able to convey a niche are stable/developer-accessible, but NonZero is a type provided by the standard library: https://doc.rust-lang.org/std/num/struct.NonZero.html https://doc.rust-lang.org/std/num/struct.NonZero.html An example of the niche optimisations is in that link; if a 32bit number is NonZero, you can put that in an Option, and your Option<NonZero<u32>> will be the same size as a normal u32.
- phamilton 2y ago
  An interesting project for niche types: https://github.com/rick-de-water/nonany https://github.com/rick-de-water/nonany It's not perfect but does allow some flexibility.
IshKebab 2y ago
In general, you need a type system that supports sets of integer values, e.g. range(2, 7) or set(3, 5, 7). Rust doesn't support that unfortunately so it has a special annotation instead to make NonZero work.
- jiggawatts 2y ago
  In terms of category theory, what we would need is subtraction and division types on top of product and sum types. So a 32-bit integer is the product of 32 two-state bit types. Something akin to NonZero could be defined as that type minus one state, such that there are now 4294967296 - 1 representable values. Similarly, pointer types on some machines always have some bits set to 0 due to hardware constraints. These can be represented in the type system as 2^64 / 2^n where 'n' is the number of bits that are not usable, resulting in something like 2^46 for typical CPUs. This would allow extra bits of state to be "packed in there". This concept is more generally useful, not just for bit-packing. For example, a database table row might be represented by a struct that contains a field for every column. But then, how to represent the result of a SELECT query!? Either you code-gen this into a new type, create that type manually, or use compiler-generated "unspeakable" type names. (Linq in C# does this.) Or... the language could natively support type division, so you could use one struct type for "all columns" and then use division on the type to delete columns you don't need for a particular query or REST response. There's a whole ecosystem of tools that work around the problem of not having this as a built-in feature in typical languages: AutoMapper, automap, Mapster, etc...
  - justincormack 2y ago
    Ada has constrained range types. Idris has lots more fun stuff with types. But not very mainstream yet.
  - IshKebab 2y ago
    As far as I understand it there's no need for that. You don't need to say [0, 256) except 0; you can just say [1, 256).
    - Lvl999Noob 2y ago
      With subtraction, you can say [0, 256) except [4, 9, 15, 26]. You can do that just by narrowing a single range. But then, its kinda hard to optimise such a split range in the general case. The narrowing option gives you 80% (maybe more) of the performance at 20% (probably even less) of the cost.
  - SkiFire13 2y ago
    > So a 32-bit integer is the product of 32 two-state bit types. Something akin to NonZero could be defined as that type minus one state, such that there are now 4294967296 - 1 representable values. I can see a couple of problem with this approach: - you need to be able to talk about bit-level types, which contradicts the common assumption that all types are addressable, i.e. whose size and alignment is some positive integer (or zero) number of bytes; - what if you want to substract more complex set of values? For example describing a 32 bit number without all multiples of 7? And how do you encode this in the compiler in such a way that type checking remains decidable? - how do you safely and concisely express conversions and operations on these kind of types? > Similarly, pointer types on some machines always have some bits set to 0 due to hardware constraints. These can be represented in the type system as 2^64 / 2^n where 'n' is the number of bits that are not usable, resulting in something like 2^46 for typical CPUs. This would allow extra bits of state to be "packed in there". Note that this is not forward compatible, since newer CPUs can start using more bits. In fact recent CPUs started using 57 bits instead of 48 bits, so a program that packed more state in those top bits would now be broken. You should generally instead try to pack data in the least significant bits that will always be 0 due to alignment constraints. Moreover the top bits are not always 0, they are equal to the most relevant bit of the used part of the address. On Linux this just happens to always be 0 for userspace addresses (and 1 for kernel addresses) but this won't be the case on all architectures and OSes. I also wonder how you would define these types using subtraction/division types such that they are different? - the address type being 64 bits but using only the least significant 48 bits and having the top 16 bits always 0 - the address type being 64 bits but using only the least significant 48 bits and having the top 16 bits always equal to the 48th bit - the address type being 48 bits Clearly these types are all isomorphic, but they are definitionally different and in a way that really matters to the hardware.
Timshel 2y ago
In general such a thing is written with a wrapper type which disappear at compilation (a kind of stricter type alias). In rust might be a NewType: https://www.howtocodeit.com/articles/ultimate-guide-rust-newtypes https://www.howtocodeit.com/articles/ultimate-guide-rust-new...

dwattttt 2y ago

I don't think the mechanics of being able to convey a niche are stable/developer-accessible, but NonZero is a type provided by the standard library: https://doc.rust-lang.org/std/num/struct.NonZero.html https://doc.rust-lang.org/std/num/struct.NonZero.html An example of the niche optimisations is in that link; if a 32bit number is NonZero, you can put that in an Option, and your Option<NonZero<u32>> will be the same size as a normal u32.

phamilton 2y ago
An interesting project for niche types: https://github.com/rick-de-water/nonany https://github.com/rick-de-water/nonany It's not perfect but does allow some flexibility.

IshKebab 2y ago

In general, you need a type system that supports sets of integer values, e.g. range(2, 7) or set(3, 5, 7). Rust doesn't support that unfortunately so it has a special annotation instead to make NonZero work.

jiggawatts 2y ago
In terms of category theory, what we would need is subtraction and division types on top of product and sum types. So a 32-bit integer is the product of 32 two-state bit types. Something akin to NonZero could be defined as that type minus one state, such that there are now 4294967296 - 1 representable values. Similarly, pointer types on some machines always have some bits set to 0 due to hardware constraints. These can be represented in the type system as 2^64 / 2^n where 'n' is the number of bits that are not usable, resulting in something like 2^46 for typical CPUs. This would allow extra bits of state to be "packed in there". This concept is more generally useful, not just for bit-packing. For example, a database table row might be represented by a struct that contains a field for every column. But then, how to represent the result of a SELECT query!? Either you code-gen this into a new type, create that type manually, or use compiler-generated "unspeakable" type names. (Linq in C# does this.) Or... the language could natively support type division, so you could use one struct type for "all columns" and then use division on the type to delete columns you don't need for a particular query or REST response. There's a whole ecosystem of tools that work around the problem of not having this as a built-in feature in typical languages: AutoMapper, automap, Mapster, etc...
- justincormack 2y ago
  Ada has constrained range types. Idris has lots more fun stuff with types. But not very mainstream yet.
- IshKebab 2y ago
  As far as I understand it there's no need for that. You don't need to say [0, 256) except 0; you can just say [1, 256).
  - Lvl999Noob 2y ago
    With subtraction, you can say [0, 256) except [4, 9, 15, 26]. You can do that just by narrowing a single range. But then, its kinda hard to optimise such a split range in the general case. The narrowing option gives you 80% (maybe more) of the performance at 20% (probably even less) of the cost.
- SkiFire13 2y ago
  > So a 32-bit integer is the product of 32 two-state bit types. Something akin to NonZero could be defined as that type minus one state, such that there are now 4294967296 - 1 representable values. I can see a couple of problem with this approach: - you need to be able to talk about bit-level types, which contradicts the common assumption that all types are addressable, i.e. whose size and alignment is some positive integer (or zero) number of bytes; - what if you want to substract more complex set of values? For example describing a 32 bit number without all multiples of 7? And how do you encode this in the compiler in such a way that type checking remains decidable? - how do you safely and concisely express conversions and operations on these kind of types? > Similarly, pointer types on some machines always have some bits set to 0 due to hardware constraints. These can be represented in the type system as 2^64 / 2^n where 'n' is the number of bits that are not usable, resulting in something like 2^46 for typical CPUs. This would allow extra bits of state to be "packed in there". Note that this is not forward compatible, since newer CPUs can start using more bits. In fact recent CPUs started using 57 bits instead of 48 bits, so a program that packed more state in those top bits would now be broken. You should generally instead try to pack data in the least significant bits that will always be 0 due to alignment constraints. Moreover the top bits are not always 0, they are equal to the most relevant bit of the used part of the address. On Linux this just happens to always be 0 for userspace addresses (and 1 for kernel addresses) but this won't be the case on all architectures and OSes. I also wonder how you would define these types using subtraction/division types such that they are different? - the address type being 64 bits but using only the least significant 48 bits and having the top 16 bits always 0 - the address type being 64 bits but using only the least significant 48 bits and having the top 16 bits always equal to the 48th bit - the address type being 48 bits Clearly these types are all isomorphic, but they are definitionally different and in a way that really matters to the hardware.

Timshel 2y ago

In general such a thing is written with a wrapper type which disappear at compilation (a kind of stricter type alias). In rust might be a NewType: https://www.howtocodeit.com/articles/ultimate-guide-rust-newtypes https://www.howtocodeit.com/articles/ultimate-guide-rust-new...