Why are the Reader and Writer vtables intrusive as well?

Explain
1

I think I get why the buffer needs to be intrusive
but why does the vtable have to be as well?
Why isn’t it a copyable handle more similar to the Allocator interface?
something like this:

// std/Io/Writer.zig
const Writer = @This();

vtable: *const VTable,
state: *State,

pub const State = struct {
    buffer: []u8,
    end: usize = 0,
};
pub const VTable = struct {
    drain: *const fn (w: Writer, data: []const []const u8, splat: usize) Error!usize,
    // ...
};


pub fn write(w: Writer, bytes: []const u8) Error!usize {
    if (w.state.end + bytes.len <= w.state.buffer.len) {
        @branchHint(.likely);
        @memcpy(w.state.buffer[w.state.end..][0..bytes.len], bytes);
        w.state.end += bytes.len;
        return bytes.len;
    }
    return w.vtable.drain(w, &.{bytes}, 1);
}

// MyWriter.zig

const MyWriterImpl = @This();
interface_state: Io.Writer.State,

// and impl state...

pub fn drain(io_w: Io.Writer, data: []const []const u8, splat: usize) Io.Writer.Error!usize {
    const w: *MyWriterImpl = @alignCast(@fieldParentPtr("interface_state", io_w.state));
    // funky implementation details
}

Edit: could just pass in the state pointer to the vfunc but you get the point

I think this is the same amount if indirection
Is it so we can store it in half the size (without adding another indirection layer)? If so, why isn’t the Allocator vtable intrusive as well so we pass it by pointer?

Edit: Thanks all, think I get it now:

Summary

For completeness the best answer I can come up with to my original question is:
By putting the vtable pointer inside the “intrusive” interface, we only have to pass around a single pointer at the cost of one extra layer of indirection to the vtable, this does not matter for Reader/Writer as the vtable is the cold path which will involve a sys call. No indirection as Interface has already been loaded because of buffer access in vtable paths, see vulpesx 's reply
Conversely this for Allocator this is a price we do not want to pay, the vtable is always called, even for an implementation that might not do a sys call on that virtual call
/+ possible devirutalisation I haven’t looked into

2

I presume it comes down to performance and memory requirements?

Since allocator represents truly type-erased runtime-polymorphic state (e.g. polymorphic layout - pointer to arena vs pointer to gpa), it makes sense to keep the interface as a fat pointer (anyopaque + vtable). It describes your complete state with minimum amount of data (ptr to state + ptr to behavior).

A reader/writer itself has a lot more common state, it isn’t a truly type erased interface in purest sense. It just makes sense to put the vtable inside, e.g. coupling vtable with all the state inside makes sense both at a system level (you can describe the complete state via a single pointer), but also it’s because you have static memory requirements (a reader/writer always has a known layout and always has a vtable and always has a buffer).

It also aligns with utilizing @fieldParentPtr offers the same workflow as it does with SinglyLinkedList, and the reasoning is pretty clear: firstly as you posted, performance. Having the state north of the vtable allows most interaction with the interface occur without a dispatch. Second is composition over inheritance. In this sense I would argue that the VTable is not actually “intrusive”. It’s inside the Writer object, not inside the FileWriter or any other specialization of the interface. An Allocator interface models polymporphism, strictly something that in C++ would be modelled via a single-level inheritance hierarchy and virtual methods (even though that would yield a sub-optimal layout strictly closer to the Reader/Writer implementation. I recommend a really cool video on the topic here.). A Reader Writer implements polymorphism via DoD - separating common functionality into a static type and then offering the implementation site freedom to integrate it however it sees fit via composition).

3

Another important distinction is where this actually starts to matter - having the vtable as part of the handle (as Allocator does), affects memory fetching patterns if you have for example a 100k different allocators you call alloc on in a sequence, and they could have wildly unpredictable implementations.

Since neither Allocator nor Reader/Writer tend to operate in this mode (you are much more likely to either have up to 100 or 50 Writers of a similiar or different type, and you pretty much only ever use one or max like 5 allocators), you get into hardware prefetching, L1 D-cache and I-cache, and none of this makes any tangible difference. Because strictly speaking, the second indirection (Writer → VTable) does require the first indirection (ptr → Writer) to resolve before it can begin, Having it as you specify would be better for cases that these structures are unlikely to come across. This indirection is irrelevant because for the vtable to actually needed, you are already inside Writer methods, and those are already using end, buffer, etc, and the fetch has to be finished before their code that could dispatch to vtable can execute.

1 Like
4

I wonder if the difference between Allocator/Writer API is volontary or is just an artifact of the two being implemented years apart with Andrew having a better idea of what Zig is.

Like if I was doing Allocator API now I would be really tempted to follow the Writer pattern and return a pointer into the Arena instead of passing a pointer to the Arena plus the vtable. It doesn’t matter too much until you start storing a lot of allocators, which we are moving away with the removal of “managed” data structure.

5

Thanks for responding!

By this do you just mean that the interface holds no state? I’m not sure there is a meaningful difference here, the allocator handle could just as easily point to an embedded Allocator interface, which could either be an empty struct, or contain the vtable pointer instead of it being where the handle is. The difference is where the vtable pointer is kept.

I don’t follow.

I don’t understand what you mean by this, we always know the memory layout of the interface/handle and vtable, in both cases we do not know the layout statically of the implementation

Your second paragraph is about where the buffer is, I was only concerned about where the vtable pointer is, and whether the term intrusive accurate is besides the point

Thanks for the video recommendation, I will check it out when I get the chance

6

So you are saying it shouldn’t matter either way? :sweat_smile:

7

Yeah this is a good point, perhaps it’s more likely for a reader / writer to be stored in an object, whereas as you say for Allocators we are moving away from managed containers so the extra size doesn’t matter

edit: another thought is maybe there is an aversion to using @fieldparentptr when unnecessary due to the added complexity, but if we have to anyway since our interface is stateful, it is essentially “free” complexity wise to put the vtable pointer in the interface and keep usage only requiring a pointer sized type

8

The Allocator API used to use the fieldParentPtr approach until allocgate

2 Likes
9

Interesting, I wonder how the much the devirtualisation problem was to do with the design and how much it was to do with the vtable being scored fully in the implementation as mutable pointers zig/lib/std/mem/Allocator.zig at 0.8.x · ziglang/zig · GitHub
(at least that is what I think that is? the old syntax for function pointers is not intuitive I’m glad that was changed!)
The article mentions that you can store the vtable in static memory elsewhere but it adds a layer of indirection… that’s what we do now with Reader/Writer!

Just because I’m losing track myself with all these implementations here are the current amount of indirection for each

New Reader/Writer:
*Writer → follow pointer to get *vtable → follow pointer to get function pointer → call it
and for buffer:
*Writer → follow pointer to get buffer slice → follow slice pointer to get underlying memory

Allocator:
Allocator → follow vtable pointer member to get function pointer → call it

Old Allocator:
*Allocator → follow pointer to get function pointer (vtable functions stored inline - not as pointer) → call it

Alternate Writer:
Writer → follow vtable pointer to get function pointer → call it
and to access buffer
Writer → follow state pointer to get slice → follow slice pointer to get underlying memory

It seems the existing Reader/Writer have the extra layer of indirection that post is talking about

10

You’re ignoring that the vtable is always called after first accessing the state.
so it’s more like:

Follow pointer to get slice, if slice has capacity follow pointer to underlying memory, otherwise follow vtable pointer then function pointer.

The alternate writer just shuffles pointers around, but the amount of indirection stays the same.

11

Ah yes so for the cases where the vtable gets called
New writer:
*Writer → follow pointer to get buffer slice → follow slice pointer to get underlying memory, probably get a branch misprediction → back to *Writer follow pointer to get *vtable → follow pointer to get function pointer → call it

Alternate Writer:
Writer → follow state pointer to get slice → follow slice pointer to get underlying memory, branch misprediction, back to Writer → follow vtable pointer to get function pointer → call it
and to access buffer

so there is still one extra layer of indirection but I suppose the whole point with the new Reader/Writer is that this is the cold path which will include a sys call anyway
(I can’t think of a scenario where it wouldn’t be, I think the fixed readers and writers return an error on these paths anyway except the fixed reader flush which is a noop)

whereas for allocator the vtable is always taken, and indirection can matter as it will not always be a sys call (thinking arenas and fixedbufferallocators, this case should still be fast)

For completeness the best answer I can come up with to my original question is:
By putting the vtable pointer inside the “intrusive” interface, we only have to pass around a single pointer at the cost of one extra layer of indirection to the vtable, this does not matter for Reader/Writer as the vtable is the cold path which will involve a sys call.
Conversely this for Allocator this is a price we do not want to pay, the vtable is always called, even for an implementation that might not do a sys call on that virtual call
/+ possible devirutalisation I haven’t looked into

1 Like
12

this was already followed and should still be in cache, it is unlikely the cpu would need to follow it again.

So no, there is still not an extra layer of indirection.

Allocating is an example, and no, it does not always take the vtable; It takes advantage of the interfaces built in buffering logic to handle the simple case where there is already available capacity.

Other examples would include the TLS implementations, also the (de)compression implementations.

This is not to say there is no merit to your alternative design, it would help alleviate the common foot-gun of copying the interface (and using it after).

13

I missed this thank you

An example where the Writer vtable path isn’t a slow sys call?
Sorry I’m a bit confused because you say it uses the built in buffering logic which makes me think the Writer vtable path does allocate, since if there was room in the buffer wouldn’t get that far.
I’ll have a look at Writer.Allocating to see what you mean

14

Yes, but allocation does not always mean a syscall, that’s up to the allocator, as well as the amount you allocate; allocators typically try to reuse memory as much as possible to avoid syscalls, so unless your allocating memory pages worth each time you won’t be doing that many syscalls.

Though allocation does go through another vtable, and an algorithm, so it is not free by any means.

The other implementations I mentioned are better examples.

1 Like
15

It does matter, but in configutations which are uncommon for general zig code, e.g. if you exceed a certain amount of unpredictability or the cache gets evicted.

16

This (allocator being implemented like a writer) is highly unlikely in my opinion for these exact reasons (restating my previous post for better understanding:

The difference between an Allocator and a Writer:

  • Allocator state can be truly anything, to the degree where you can not create a common data structure shared between the interfaces (e.g. a GeneralPurposeAllocator, ArenaAllocator, or SMPAllocator have absolutely no state common to all of them. There is no buffer or end that would be like yes, each and every Allocator interface needs this and utilizes this in its non-virtual implementation). What IS shared between Allocators is the functionality - a bunch of methods which operate on unknown state via polymorphic baseline methods behind the VTable.
  • We need to separate Writer Interface and Writer Implementation. a Writer Implementation is like the Allocator state in the sense that it can contain anything, it can implement writing over different things (like File Writer or Buffer Writer or whatever). This is the special state that is only accessible from behind the VTable (via @fieldParentPtr). The Writer Interface on the other hand has state. It has the buffer, and the end. Every Writer Implementation needs to have a buffer and an end, because that’s state common to the Writer Interface methods that use it to buffer the calls and implement optimal code. There is non-virtual code in the Writer Interface that pulls stuff from the buffer, advances the end index, etc.

While there are two possible ways to organize the Writer interface as you suggested:

Fat Pointer:

[ptr][vtable]

behind ptr:
[internal_state][buffer][end]

Intrusive VTable inside common state:

[internal_state][vtable][buffer][end]

The second option is more optimal because in the end, you would have to use @fieldParentPtr for the implementation either way, and it allows you to pass around the whole Writer Interface via a single pointer. It allows for the whole state of the Writer Interface to be passed around as a pointer to a single block of data instead of decoupling it, which would then for example make it more cumbersome to store in an array list. Instead of a single pointer, you would have to store both the pointer and pointer to the VTable, but that’s redundant since the VTable is a property of the Writer Interface not the pointer to the Writer Interface. You could not do this for an Allocator (e.g. store the VTable pointer in the state), because you need it accessible via the pointer to the Allocator.

There are benefits to both Fat Pointer and Intrusive VTable approaches, it’s good when the language can comfortably implement both and the engineer decides which one is appropriate to each case.

Hope that makes it more clear.

Edit: You can’t pass around the single block of data (implies being passed by value).

17

This is not quite right: the “fat pointer” method of interfaces does not use @fieldParentPtr. what is true is that some pointer indirection (via the vtable) is happening either way. what happens within the vtable is either loading the implementation via @fieldParentPtr or by @ptrCast(ptr).

It’s also not true that the Writer interface may be passed by value: the writer implementation may be passed by value, as can a fat pointer interface. The invariant that must be preserved in the fat pointer case is that ptr continues to point to the implementation, while in the @fieldParentPtr case, it is that the interface pointer continues to point to a field of the implementation.

18

For a Writer implemention via a fat pointer, you would be required to use @fieldParentPtr, since otherwise the non-virtual methods of the interface would not have access to the fields of the base state (buffer and end). For a general case of a fat pointer, what you said holds true. That also kind of proves my point why with an Allocator a fat pointer makes sense, as you can use @ptrCast, and have no common state. For a Writer, it is a sub-optimal solution, as mentioned in the talk by Andrew himself.

On your second point, I misspoke. What I wanted to say is that you can describe the state by a single block of data passed around via a pointer, which is presumably more robust than having decoupled state to a fat pointer and a base state.

19

Ah, I misunderstood your proposed other structure. You meant

const Writer = struct {
    ptr: *AbstractImplementation
    vtable *const VTable
};

const ConcreteImplementation = struct {
    // state: T,
    base: AbstractImplementation,
};

const AbstractImplementation = struct {
    buffer: []u8,
    end: usize,
};

I agree, this would need fieldParentPtr to work. I was imagining ptr would instead point to the ConcreteImplementation directly, since we’re calling into a VTable already.

20

I mean with the standard Writer implementations:

// in File.zig
pub const Writer = struct {
    interface: std.Io.Writer, // without vtable
    // ... other fields

    pub fn writerSelf(self: *@This()) FatPointer {
        // This does not work, we can't access ptr.interface.buffer
        // because the layout is unknown on the consumer-side of the interface.
        // Here we can do
        // const self: *@This() = @ptrCast(@alignCast(ptr));
        // when inside the vtable implementation methods (drain, rebase, etc.).
        return .{ .ptr = @ptrCast(self), .vtable = &vtable };
    }

    pub fn writerInterface(self: *@This()) FatPointer {
        // This does work, we can access ptr.buffer, but requires
        // const self: *@This() = @fieldParentPtr("interface", ptr);
        // when inside the vtable implementation methods (drain, rebase, etc.).
        // At that point it is easier to just put the vtable inside std.Io.Writer.
        return .{ .ptr = &self.interface, .vtable = &vtable };
    }
};

When talking about accessing the buffer, I am talking specifically about methods on the std.Io.Writer interface, such as write(), writeAll(), etc.