The Limits of Devirtualization

Brainstorming
, ,
47

We definitely need some way of defining an abstract interface. I was thinking about how we could make Allocator a generic interface, which would provides a vtable-based implementation on-demand for situations needing one. I hit a brick wall basically because there’s no good way to specify a function placeholder. Something like this is too ugly to work:

pub fn rawAlloc(self: anytype, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {
    _ = self;
    _ = len;
    _ = alignment;
    _ = ret_addr;
    @compileError("Interface function");
}

pub fn rawFree(self: anytype, memory: []u8, alignment: Alignment, ret_addr: usize) void {
    _ = self;
    _ = memory;
    _ = alignment;
    _ = ret_addr;
    @compileError("Interface function");
}

// ...
1 Like
48

Why do you need a placeholder?

For any generic type that lets you provide state and implementation (which is common), you can just create an implementation+state that is a runtime interface.

49

I was also thinking about this. My thought is that if the core team wants to go runtime, perhaps I could push stuff into comptime on my end. I thought about something like this:

fn foo(allocator: anytype) !void{}

fn AllocatorAdapter(comptime Ctx: type, comptime vtable_: type) type{
  return struct{
    pub const vtable = vtable_;
    ctx: Ctx,

    pub fn alloc(self: @This(), comptime T: type, n: usize) Allocator.Error!void{
      const allocator: std.mem.Allocator = .{
        .ptr = self.ctx,
        .vtable = vtable,
      }
      return allocator.alloc(T, n);
    }
  };
}

pub fn main()!void{
  const A = std.heap.DebugAllocator(.{});
  var gpa: A = .{};
  const Adapter = AllocatorAdapter(*A, A.vtable);
  var adapter: Adapter = .{ .ctx = &gpa };
  try foo(adapter);
}

I haven’t tested this yet, but the idea is that I made the vtable comptime-known. The std.mem.Allocator is created immediately before the call, giving the compiler everything it needs to devirtualize. If that fails, we could go one level lower and call the functions inside the vtable directly, bypassing the entire type erasure.

3 Likes
58

These things are not my specialty, so I might be horribly wrong, but is there a reason the language can’t demand us to pass this information as comptime known?

similar to this idiom the language has:
struct myStruct {
fn foo(self: *@This()) void {…}
}
Then when we have to do comptime asserts and things like that to check that the thing we pass actually has the correct functions to adhere to the interface, but it gives the compiler room to optimize all of these problems away. Obviously this is harder to work with than a struct where you fill function pointers and zls can immediately tell you when you do something wrong, but I think that’s something the language can fix.

Then demanding we pass these things at compile time known. Because as I get it right now we end up passing objects that have runtime known function pointers.
Have people frequently encountered situations where they pass an Io or an allocator that are not compile time known? Because it has never happened to me, but I feel like I must be missing something.

2 Likes
60

Imagine you are writing a networking library, e.g. Redis client. You shouldn’t need to know how is Io implemented. It might do simple blocking system calls, it might be done in a non-blocking coroutine-based runtime, it doesn’t matter. That’s the main promise of the Io interface, it allows you to build reusable code, that can be used in very different execution models.

5 Likes
62

How does requiring that a parameter be compile time known prevent the code from being reusable? When we pass a compile time known function pointer to a data structure that needs it, the data structure doesn’t know anything about how that function is implemented.
Thanks for the reply regardless.

1 Like
63

Yes, that’s correct, but then you need to use anytype and that makes using the parameter kind of hard, it’s hard to read, you will get no support from any tool. If Zig had at least comptime interfaces, I’d fully agree that making the Io comptime-known would be a better option.

2 Likes
64

That’s what I am saying, why don’t we introduce a more “nice” way to express compile time interfaces and use that? I think it would solve the problem discussed in this thread and result in better generated code overall.
Better codegen feels very in line with the language’s philosophy, has something like that not come up before

3 Likes
66

Decoupling the function pointers from the buffer seems like it could be enough. However I think, unless you type “comptime” before io in the function signatures there’s no guarantee by the compiler that the struct containing the function pointers will be compile time known.

So maybe something like that could work? Passing a compile time known struct of function pointers, and then a run-time known state. At least until we figure something else out.

68

That would be equivalent to taking an anytype, and calling the methods directly.

70

Yeah, just a different way to express it with that would get more help from zls

1 Like
71

It seems to be that Io has so much function pointers in it’s vtable it would be very hard to go and implement all of them in embeded, where all of these functions don’t really make sense. Some of them don’t have a file system, some of them have no cryptographically secure RNG, or networking, or even threads/cores, the list goes on. Having this many function pointers empty (or set to panic()) is worrying to me because then we won’t have a great compatibility between platforms (especially between 2 embeded platforms, or between OSes). It also makes them more painfull to wrap to add custom behaviour, wrapping std.mem.Allocator is quicker and easier to do.

5 Likes
72

Well, presumably, if a library uses these things, it would have used them even if they were not in the vtable.
In fact, by having the abstraction layer, you can emulate whatever behavior is necessary. If a particular library insists on using files, but you just want it to output raw bytes and no file, you can create an Io that redirects anything file related to memory.

1 Like
73

That only alleviate the impact on performance and code size. We’re still stuck with the constraints that vtable interfaces impose on program design.

What we need to recognize is that the standard library is very much a special case. It’s by no mean representative of general programming. Few of us write stuff that interacts with the code of the entire community. We usually write stuff that interacts with our own stuff. Employing type erasure don’t make sense in such scenarios. We’d just be hiding details from ourselves.

3 Likes
74

The standard library really isn’t a special case. All libraries meant for general consumption have the same requirements, and the language needs to have the facilities needed to meet those requirements. There will never be an std that can do everything.

2 Likes
75

Right, though restricted function types should help in this case, yeah?

As I understand it, yes, this should help devirtualize function calls. However, there is currently no work in this direction (the proposal has been accepted).

It is worth noting that std.Io is designed around the principle of “one std.Io per whole program”, so restricted function pointers would help in this case. Following this principle also allows overriding std.Io types using std.Options, as is currently done for std.Io.File.Permissions.

UPD: Couldn’t find any proof for “one std.Io per whole program”. Sorry for (possible) misleading.

76

Won’t there frequently be two, given that juicy main offers a default io ? Not sure what happens if that default isn’t used by the program itself.

edit: ah, there’s std.process.Init.Minimal which doesn’t have an io field.

77

Was this documented somewhere? In my use cases, writing database-like servers with network frontends, I have need for two implementations inside one program.

2 Likes
78

Would it be possible/helpful to break out the vtable into more granular, optional feature groups?

where ex: std.Io.VTable would have:

fs: ?std.Io.VTable.Filesystem;
async: ?std.Io.VTable.Async;
network: ?std.Io.VTable.Networking;
cryptography: ?std.Io.VTable.Cryptography;

etc.

If something requires ex: filesystem IO, but the VTable’s fs is null, then it would fall under a similar category of error to trying to pass a blocking IO implementation to something that explicitly requires concurrency.

This would make it easier to write custom IO implementations with incomplete feature sets. I don’t know if simply making feature groups optional would allow for better dropping of functions if they’re never used (I don’t think it does…), but I think it potentially could make it easier to think about optimizing stuff away if we explicitly allow it to be null.

9 Likes
Discussion about Io and Zig
79

To take this idea a bit further, instead of having 107 function pointers that are always in a struct, what if Io was parameratized in a way that let you “opt in” to certain Io groups.

so (pseudo code):


pub fn Io(comptime config: struct{ async: bool, networking: bool, crypto: bool, filesystem: bool }) type {
    return struct {
        userdata: *anyopaque,
        vtable: *const VTable(config),
    };

    pub fn VTable(config: ...) type {
        return struct {
            if (config.networking) {
                // Networking "mixins" go here
            }
            if (config.crypto) {
                 // crypto "mixins"
            }
            // etc.
        };
    }
}

This isn’t unfamilair with the std library. DebugAllocator takes a config which alters the behavior (but not necessarily struct size).
This could solve the size issue here. The VTable only includes the groups of functions we actually care about. However, I’m not sure how that works with the actual std library code. We want a concrete type so that we don’t have to put anytype everywhere, which was part of the catalyst for the change in the first place.

Instead of a config that is passed into the type, it could be part of the std_options defined in the module root which would still allow for customization without having a generic Io function for specialization. Just like we can customize the log function, or page size min/max.

To some degree, we will have to wait to see what type of optimizations/changes happen after the Io stuff lands. I think part of the reason we have 107 function pointers is to list out all that is needed and they can tweak it after it lands.

8 Likes