Zig: circular slice type

[shawnl]

Much of std that takes slices could work with fully-aligned circular buffers. This is a proposal to extend the slice type.

    pub const Pointer = struct {
        size: Size,
        is_const: bool,
        is_volatile: bool,
        alignment: comptime_int,
        child: type,
        is_allowzero: bool,

        pub const Size = enum {
            One,
            Many,
            Slice,
            CircSlice,
            C,
        };
    };

Circular slices at runtime have three values

struct {
    ptr: [*]T,
    len: usize,
    circle: [*]T,
};

All functions that accept slices can accept circular slices, but the compiler has to generate a different version of the function for each.

Circular slices can be re-sliced.

All of the bounds checking of slice changes, but I think these details are self-evident.

????? When should circle be allowed to be changed? Every time it is changed, it requires (1 << (@ctz() + 1)) - 1), the mask, to be calculated. I think it should be allowed to change at any time, but only from the same thread, and then the compiler has to be smart of not calculating the mask excessively.

These could be declared with a builtin @sliceMakeCircular(comptime T: type, buffer: []T, read: usize, writen: usize); which will set circle to buffer, ptr to &buffer[read], and len to write - read. In release mode buffer.len is ignored. It is only used to validate the alignment of buffer.

[shawnl]

Yeah, this is needed by std.zig.render, which is used by zig fmt.

[andrewrk]

This proposal will need justification for why it should be a language primitive and not a userland struct.

[shawnl]

This proposal will need justification for why it should be a language primitive and not a userland struct.

Because as a language primitive it is compatible with all the existing code. 99.9% of code that uses slices would be compatible.

[hryx]

Because as a language primitive it is compatible with all the existing code.

I assume the kind of justification a language change proposal demands isn't whether it breaks existing code (although it may be a factor in the final decision). Lots of accepted proposals are breaking. Because of zig's goal to remain stringently as small as possible, these might help your case:

• a clear demonstration of why the status quo is undesirable
• why it would be insufficient, impossible, or overly difficult to implement in userland
• an overview of the impact (pros/cons) it will have on the language
• alternative solutions which you or others may have considered

[shawnl]

a clear demonstration of why the status quo is undesirable

I can't do mem.indexOfScalar, I can't do mem.eql(). I can't do similar things. If I copied these functions they would work, but it seems stupid to make copies of all these low level things. The copies also would not benefit from performance improvements. I think avoiding duplication when it does not negatively impact readability is a win.

why it would be insufficient, impossible, or overly difficult to implement in user-land

Because it would require new version of all the main routines, and anything that calls the main routines could not be used.

an overview of the impact (pros/cons) it will have on the language

We can make the parsing code faster, by streaming the file reader => versifiers => tokeniser/parser. I don't like that it makes the language bigger.

alternative solutions which you or others may have considered

It can be done in user-space, however nothing that uses slices can be used with circular buffers without this.

[hryx]

Because it would require new version of all the main routines

Forgive my slowness, but what are the "main routines" in this context? Also, to clarify, do you mean that anything _which wishes to take advantage of circular buffers_ would have to be rewritten? (Perhaps implying that such a rewrite could hypothetically be done incrementally?)

Do I understand correctly that you want existing slice syntax but with this new data structure underlying it? As a reminder, there are other specialized data structures implemented in stdlib rather than as a language feature. User code sacrifices some brevity when it needs to use a more specialized data structure — heck, zig doesn't even have a hash map in the language, that's in stdlib too.

[shawnl]

Also, to clarify, do you mean that anything which wishes to take advantage of circular buffers would have to be rewritten?

And all the support code, like what is in mem.zig. That is what I mean by main routines.

Do I understand correctly that you want existing slice syntax but with this new data structure underlying it?

Yes. I agree that anything that can reasonably be implemented in stdlib should be, but this cannot because then it cannot take advantage of a bunch of useful stdlib stuff.

Now that I am thinking about it, these slices wouldn't have a len usize, but rather a end offset. .len would still work by doing a modulo subtraction, however code that cares to learn about this type would be slightly better off with having this same information stored as an end offset.

[andrewrk]

I don't see this being added to the language. I think it should be a userland solution.