Can we get rid of usize?

kj4tmp · December 29, 2024, 4:31am

So I’ve got a generics based serializer for MessagePack. With tons of abuses of generics all over the place :).

One of them is this:

pub fn EncodeError(comptime T: type) type {
    if (@sizeOf(usize) > 4 and containsSlice(T)) {
        return error{
            NoSpaceLeft,
            // MessagePack only supports up to 32 bit lengths of arrays.
            SliceLenTooLarge,
        };
    } else {
        return error{NoSpaceLeft};
    }
}

/// Encode the value to MessagePack bytes.
pub fn encode(value: anytype, out: []u8) EncodeError(@TypeOf(value))![]u8 {
    return try encodeCustom(value, out, .{});
}

The reason for this code is that MessagePack does not support arrays with lengths longer than max unsigned 32 bit integer.

So the length type of a slice matters to me, and its usize. I’m a little miffed about this, because every time I use a slice I need to think “what architecture am I on”. This kind of goes against the zen:

Edge cases matter. (there is some friction here in handling usize edge cases).

but usize also supports the the vague unwritten zen I have in my head:

Zig is not a language that attempts to abstract away the properties of the hardware. (The hardware has a pointer size).

kj4tmp · December 29, 2024, 4:46am

Array/Slice custom index type

opened 01:07PM - 14 Dec 18 UTC

Hejsil

proposal

One thing I end of doing sometimes is constructing a table that maps all `u4` va…lues to something else. I tend to do this with arrays: ```rust const channel_message_table = blk: { var res = []?midi.ChannelMessage.Kind{null} ** (math.maxInt(u4) + 1); res[0x8] = midi.ChannelMessage.Kind.NoteOff; res[0x9] = midi.ChannelMessage.Kind.NoteOn; res[0xA] = midi.ChannelMessage.Kind.PolyphonicKeyPressure; res[0xB] = midi.ChannelMessage.Kind.ControlChange; res[0xC] = midi.ChannelMessage.Kind.ProgramChange; res[0xD] = midi.ChannelMessage.Kind.ChannelPressure; res[0xE] = midi.ChannelMessage.Kind.PitchBendChange; break :blk res; }; ``` And then, when I wanna access items in my array, I ensure that I have a `u4` type before I index: ```rust const upper = @truncate(u4, b >> 4); const lower = @truncate(u4, b); if (channel_message_table[upper]) |kind| { ``` As long as I ensure that I index with a `u4` this is 100% safe. Sadly the compiler doesn't enforce this. Here are a few benitfits that this kind of feature could provide: * Smaller slices. A slice of type `[u4]u8` (this is made up syntax) would be the same as this struct: `struct { ptr: [*]u8, len: u4 }`. This should also work for [enum arrays](https://github.com/ziglang/zig/issues/793): `[SomeEnum]u8 == struct { ptr: [*]u8, len: @TagType(SomeEnum) }`. This would work well with the #978, as a struct marked `@optimizeFor(.Small)` would allow data to be packed with the length of the slice: ```rust struct(@optimizeFor(.Small)) { slice: [u4]u8, meta: u4, } // data layout: // len // | ptr | | // pp pp pp pp lm // | // meta ``` * Static garenties about the access into these arrays/slices. Ofc, this might not require a feature. I can imagine a userland implementation that could give me all these benifits (except for the fact that I'd have to call `.at(index)` instead of `[index]`)

github.com/ziglang/zig

allow integer types to be any range

opened 10:31PM - 29 Nov 19 UTC

andrewrk

breaking proposal

Zig already has ranged integer types, however the range is required to be a sign…ed or unsigned power of 2. This proposal is for generalizing them further, to allow any arbitrary range. ```zig comptime { assert(i32 == @Int(-1 << 31, 1 << 31)); assert(u32 == @Int(0, 1 << 32)); assert(u0 == @Int(0, 1); assert(noreturn == @int(0, 0)); } ``` ---- Let's consider some reasons to do this: One common practice for C developers is to use `-1` or `MAX_UINT32` (and related) constants as an *in-bound* indicator of metadata. For example, the stage1 compiler uses a `size_t` field to indicate the ABI size of a type, but the value `SIZE_MAX` is used to indicate that the size is not yet computed. In Zig we want people to use [Optionals](https://ziglang.org/documentation/master/#Optionals) for this, but there's a catch: the in-bound special value uses less memory for the type. In Zig on 64-bit targets, `@sizeOf(usize) == 8` and `@sizeOf(?usize) == 16`. That's a huge cost to pay, for something that could take up 0 bits of information if you are willing to give up a single value inside the range of a `usize`. With ranged integers, this could be made type-safe: ```zig const AbiSize = @Int(0, (1 << usize.bit_count) - 1); const MyType = struct { abi_size: ?AbiSize, }; var my_type: MyType = undefined; test "catching a bug" { var other_thing: usize = 1234; my_type.abi_size = other_thing; // error: expected @Int(0, 18446744073709551615), found usize } ``` Now, not only do we have the Optionals feature of zig protecting against accidentally using a very large integer when it is supposed to indicate `null`, but we also have the compile error helping out with range checks. One can choose to deal with the larger ranged value by handling the possibility, and returning an error, or with `@intCast`, which inserts a handy safety check. How about if there are 2 special values rather than 1? ```zig const N = union(enum) { special1, special2, normal: @Int(0, (1 << u32) - 2), }; ``` Here, size of N would be 4 bytes. ---- Let's consider another example, with enums. Enums allow defining a set of possible values for a type: ```zig const E = enum { one, two, three, }; ``` There are 3 possible values of this type, so Zig chooses to use `u2` for the tag type. It will require 1 byte to represent it, wasting 6 bits. If you wrap it in an optional, that will be 16 bits to represent something that, according to information theory, requires only 2 bits. And Zig's hands are tied; because currently each field requires ABI alignment, each byte is necessary. If #3802 is accepted and implemented, and the `is_null` bit of optionals becomes `align(0)`, then `?E` can remain 1 byte, and `?E` in a struct with `align(0)` will take up 3 bits. However, consider if the enum was allowed to choose a ranged integer type. It would choose `@Int(0, 3)`. Wrapped in an optional, it actually could choose to use the integer value 3 as the `is_null` bit. Then `?E` in a struct will take up 2 bits. Again, assuming #3802 is implemented, Zig would even be able to "flatten" several enums into the same integer: ```zig const Mode = enum { // 2-bit tag type Debug, ReleaseSafe, ReleaseFast, ReleaseSmall }; const Endian = enum { // 1-bit tag type big, little, }; pub const AtomicOrder = enum { // 3-bit tag type Unordered, Monotonic, Acquire, Release, AcqRel, SeqCst, }; pub const AtomicRmwOp = enum { // 4-bit tag type Xchg, Add, Sub, And, Nand, Or, Xor, Max, Min, }; const MyFancyType = struct { mode: Mode align(0), endian: Endian align(0), atomic_order: AtomicOrder align(0), op: AtomicRmwOp align(0), }; ``` If you add up all the bits of the tag type, it comes out to 10, meaning that the size of MyFancyType would have to be 2 bytes. However, with ranged integers as tag types, zig would be able to flatten out all the enum tag values into one byte. In fact there are only 21 total tag types here, leaving room for 235 more total tags before MyFancyType would have to gain another byte of size. ---- This proposal would solve #747. Peer type resolution of comptime ints would produce a ranged integer: ```zig export fn foo(b: bool) void { // master branch: error: cannot store runtime value in type 'comptime_int' const x = if (b) -10 else 100; // proposal: @typeOf(x) == @Int(-10, 101) } ``` ---- With optional pointers, Zig has an optimization to use the zero address as the null value. The `allowzero` property can be used to indicate that the address 0 is valid. This is effectively treating the address as a ranged integer type! This optimization for optional pointers could now be described in userland types: ```zig const PointerAddress = @Int(1, 1 << usize.bit_count); const Pointer = ?PointerAddress; comptime { assert(@sizeOf(PointerAddress) == @sizeOf(usize)); assert(@sizeOf(Pointer) == @sizeOf(usize)); } ``` One possible extension to this proposal would be to allow pointer types to override the address integer type. Rather than `allowzero` which is single purpose, they could do something like this: ```zig comptime { assert(*addrtype(usize) i32 == *allowzero i32); assert(*addrtype(@Int(1, 1 << usize.bit_count)) == *i32); } ``` This would also introduce type-safety to using more than just 0x0 as a special pointer address, which is perfectly acceptable on most hosted operating systems, and also typically set up in freestanding environments as well. Typically, the entire first page of memory is unmapped, and often the virtual address space is limited to 48 bits making `@Int(os.page_size, 1 << 48)` a good default address type for pointers on many targets! Combining this with the fact that pointers also have alignment bits to play with, this would give Zig's type system the ability to pack a lot of data into pointers which are annotated with `align(0)`. ---- What about two's complement wrapping math operations? Two's complement only works on powers-of-two integer types. Wrapping math operations would not be allowed on non-power-of-two integer types. Compile error.

andrewrk · December 29, 2024, 5:00am

Also related:

github.com/ziglang/zig

enum-backed address spaces

opened 07:52PM - 31 Oct 24 UTC

andrewrk

proposal

## Problem Statement The address zero (`0`) is sometimes mapped. This is why …`allowzero` exists. However it is also the case that other parts of the address range in any given space are unmapped. In such case, those nonzero unmapped values should be candidates for being the null value, and they should be available for packing data into pointers in a type-safe manner. As an example, [on amdgcn](https://llvm.org/docs/AMDGPUUsage.html#address-spaces) it would be ideal for an optional pointer have the same size as a non-optional pointer while using the value `0xFFFFFFFF` for null. Furthermore, it would be ideal for pointers to take up only the correct number of bits in a packed struct and allow bit packing when used as peers of align(0) fields in auto-layout structs. ## Proposal This proposal depends on new enum syntax for marking ranges of integer values illegal. The x86_64-linux address space would be defined like this: ```zig pub const Generic = enum(u64) { unreachable = 0x0000000000000...0x00007fefffffffff, unreachable = 0x1000000000000...0xffffffffffffffff, _, }; ``` On x86_64-freestanding it might instead be defined like this, since the pages at the beginning are mapped, but the hardware is still limited to 48 bits: ```zig pub const Generic = enum(u64) { unreachable = 0x1000000000000...0xffffffffffffffff, _, }; ``` `allowzero` is no longer needed because it is communicated by the valid range of the enum. By making value ranges unreachable, it means the language is free to pack data into those unused integer values when constructing types such as optionals or error unions. It also means that `@ptrFromInt` gains an additional safety check, ensuring the value is in-range. Notice that `0xaaaaaaaaaaaaaaaa` is outside the valid pointer range on this very common triple. `usize` would be redefined as the tag type of the default address space. Pointers carry address space data, so by indexing into a slice in a given address space, the result location type of the element index (i.e. `ptr[i]`) would be the tag type of the respective address space. This is almost sufficient to address the problem statement, however, we need well-defined memory layout for pointers, including null pointers. So, an additional part of this proposal is recognizing the tag `null` in an address space enum: ```zig /// x86-64 example pub const Generic = enum(u64) { null = 0x0000000000000, unreachable = 0x0000000000001...0x00007fefffffffff, unreachable = 0x1000000000000...0xffffffffffffffff, _, }; /// amdgcn example pub const Local = enum(u32) { null = 0xffffffff, _, }; ``` This also opens the door to automated bit-packing for auto-layout structs when pointers along with sibling fields use align(0): ```zig struct { /// Note the alignment here is a property of the field, not the pointer ptr: *anyopaque align(0), flag_a: bool align(0), flag_b: bool align(0), } ``` In this case, using the above x86_64-linux address space definition, it would be legal, but not required, for a zig compiler to lower the struct with a memory layout that uses 8 bytes, packing the booleans into the unused integer value ranges. It also provides opportunity for the compiler to strategize around ensuring that the 0xAA bit pattern is unambiguously detectable as an invalid state by safety checks. Each target would have a default pointer address space. When used in pointer syntax, it would be equivalent to omitting it. i.e. for x86_64-linux, `*addrspace(Generic) T == *T`. ## Implementation Details `std.builtin.AddressSpace` would change from an enum to something like this: ```zig pub const AddressSpace = switch (target.cpu.arch) { .x86_64 => switch (target.os.tag) { .linux => struct { pub const Generic = enum(u64) { null = 0x0000000000000, unreachable = 0x0000000000001...0x00007fefffffffff, unreachable = 0x1000000000000...0xffffffffffffffff, _, }; }, // ... }, .amdgcn => struct { pub const Generic = enum(u64) { null = 0, _, }; pub const Local = enum(u32) { null = 0xffffffff, _, }; /// All address spaces mapped pub const Region = enum(u32) { _, }; // ... }, // ... }; ``` A Zig compiler would have hard-coded awareness of the address space names within this namespace and how to map them to e.g., an LLVM address space number. The address spaces would be user overridable in the root source file. This would be especially useful for a freestanding target.

Another primary need for usize is for de-bloating generics. Imagine if ArrayList and HashMap data structures were also generic across the index type (currently hard-coded to usize). That would be a lot of unnecessary bloat. usize helps the same machine code to be able to handle multiple different max capacities.

For instance, your arrays limit to u32 capacity, however, someone might use your package in an application that otherwise uses arrays with u64 capacity. In this case usize means the same machine code can serve both use cases, although it will require use of @intCast in some places. That’s the tradeoff.

Going back to that issue that I linked, I mentioned this:

The address spaces would be user overridable in the root source file. This would be especially useful for a freestanding target.

This would effectively be a way for an application to choose the size of usize, and consequently the max capacity of all data structures that map their storage to virtual memory addresses.

Cloudef · December 30, 2024, 8:12pm

I think the fact that the native pointer size is 64 bits and msgpack supports only 32 bits lengths should not be mixed together. What you should do is try to std.math.cast the usize to u32 and error if the cast is not possible.

Use the uNN types when you need exact sizes, use usize when you need the native pointer size.

How the application manages their lengths so that they won’t go over u32 limit for msgpack de/serialization will be the application level code problem.

I would not special case the error set here with generic function, as this would make a programmer on a 32bit platform ignore the 64bit platform error scenario. If they only target 32bit platform, they can explicitly point that error scenario to unreachable.

kj4tmp · December 31, 2024, 5:16am

I realized this a while later and removed the usize check. I think you are right that it would just make it more difficult to write code for multiple platforms.

pub fn EncodeError(comptime T: type) type {
    if (containsSlice(T)) {
        return error{
            NoSpaceLeft,
            /// MessagePack only supports up to 32 bit lengths of arrays.
            /// If usize is 32 bits or smaller, this is unreachable.
            SliceLenTooLarge,
        };
    } else {
        return error{NoSpaceLeft};
    }
}