Immovable hell

Help
1

I have found myself feeling not great about my codebase because so many things can not be moved/copied due to internal dependencies. The worst thing about this is that it spreads like disease. If a low level structure can not be moved, any structure that uses it also can not be moved, and that bubbles up. What makes matters worse is that spotting what can or can not be moved/copied is not trivial. I’ve found ways to mitigate the issues with this.

One problem I found was that the initialization of structs that hold these immovable structs was fragmented. So initially I was doing something like

self.* = .{
    .pin = .init(),
    .movable = .init(),
    .immovable = undefined,
};
self.pin.lock();
self.immovable.init();

But this was error prone, so I found I could initialize these structs at once which improved things.

self.* = .{
    .pin = .initAddrLocked(&self.pin),
    .movable = .init(),
    .immovable = immovable: {
        self.immovable.init();
        break :immovable self.immovable;
    },

The other big problem is actually knowing what may be copied. Initially initialization pattern was the only clue I could find. The “pin” helps with that since I can clearly see on inspection of the structure, but it required jumping through hoops - it is not something I can see just from seeing the variable. Also it doesn’t help with code that I do not own.

Everything works. Perfectly. But it just doesn’t feel good. It would be much better if immovable structures were rarity instead of majority.

Stdlib has this mostly solved by not having internal dependencies and letting user provide the buffers and other things. In user code these buffers have to live somewhere obviously, so that approach does not work as well.

I have a hunch that I am just too reluctant to using allocators to actually put internal dependencies on heap, but doing an allocation for small size that is comptime known feels wrong to me. Also it then requires passing allocator where it feels like one shouldn’t be needed.

How can I escape this “immovable hell” and make my codebase feel good again?

3 Likes
2

TL;DR: don’t think in objects (which is hard because most high level languages all the way back to C++, C#, Java and Javascript want you to think in objects).

My (somewhat simplified) philosophy is basically to never pass things across module/library boundaries that require thinking about “ownership”. There should never be an “ownership transfer” (maybe with the rare exception for ‘large bulk data blobs’). A module should never return pointers, and if a module function takes a pointer argument, it should always be a ‘borrowed’ reference: e.g. if the function needs to hold on to the pointed-to-data, it needs to copy the data instead of just storing the pointer it got from the outside world (or alternatively, provide a location to the caller where the data needs to be written to, e.g. some sort of ‘map/unmap’ function like in 3D APIs.

Define separate data types for the internal implementation of a module and its public interface. Internal data types can have complex relationships with other internal data types of the same module (because those data types are only used/managed by the module-internal implementation code), but the public datatypes should always be self-contained and trivially copyable via a simple assignment, without having to think about ‘external things’ dangling off the struct that might need to be copied separately. E.g. don’t require helper functions to copy or destroy such ‘pure-value-structs’.. A copy is always a = assignemnt, and a destruction is always a ‘no-op’.

Inside the module you can go wild of course (move things around, create complex ‘object spiderwebs’), but never let those implementation details escape outside the module (e.g. never return a direct pointer to the outside world, if you need to return ‘references’ to internal data items use some sort of opaque handles instead which can be runtime-checked to protect from dangling accesses (like generation-counted index handles => Handles are the better pointers).

Etc… etc… basically return your brain to a state where OOP wasn’t invented yet :wink:

21 Likes
3

I wouldn’t say I am thinking in OOP, but I may be wrong. I have recently seen the “Programming without pointers” video from Andrew and was thinking that maybe it could solve my problem. I assume it is same or similar approach to the blog post you linked? But the approach is very unfamiliar to me and I don’t feel like it is a good fit for my program. Am I thinking that just because of the unfamiliarity?

4

IIRC there is some overlap, yeah… basically “prefer value types over reference types”.

IMHO a good starting point is the idea of module boundaries to “contain” memory management complexity. E.g. isolate any complex “object interelationships” in the private module implementations, and try to define a public module interface which doesn’t leak those complex internals to the outside world (e.g. don’t return direct pointers to the ‘guts’ of the module). That way at least the internal complexity of each module doesn’t creep into the rest of the codebase so that you can’t become overwhelmed by the combined complexity of the entire contraption :wink:

PS: IME building a program from such self-contained modules also makes the entire codebase more malleable.

1 Like
5

It is not like I am drowning in complexity, I am managing it just fine. It works perfectly because most of the times lifetimes of the structures match their scope, so having the structures immovable and stack allocated is fine. It is just that having most of the structure not being able to move is annoying, more than anything. It’s just that

  • I don’t like that the initialization is annoying
  • I don’t like not having clear indicator of what should not be copied, which is also problem with stuff from stdlib (common newbie question about broken program after reader.interface copy).
  • I don’t like that I have to pass pointers around instead of copies. I am not exactly sure why I dislike it. I think that when copies are passed around, compiler can optimize better. Also I don’t really like having the mutable-by-default which comes with passing pointers around.

Maybe the codebase is actually perfectly fine and I just need to adjust myself? I am really not sure. There isn’t anything I can point to and claim that it is wrong/bad (except that it is not obvious what can or can not be copied, which is a maintenance burden), but it just does not feel right to me.

6

I can’t give something super concrete, a thing that really helped me writing code I would say is write the majority of functions ignoring globals, and take them as parameters.
The more I write code this way, the more I like it.

The result Is often functions that take in a lot of parameters, but they are very easy to reason about because they are entirely self contained. Or, you can pass like a giga-struct.

If you are concerned about perf you can make it take a comptime pointer and pass the global that way. (for example, the code below would work fine if it was comptime self: *@This() , with the thinking process that the “final” global will have it’s adress be comptime known.

Another thing that you can do in zig pretty well, is you can have a large struct and many functions inside it, I am going to copy paste a random example from a project.

pub const State = struct {
    ghostText: []const u8 = &[0]u8{},
    list: struct { 
        names: ?[]const []const u8 = null,
        active: ?usize = null,
    } = .{},
    activeDescription: []const u8 = &[0]u8{},
    descriptionBufferUse: usize = 0,
    handleKeyPressFunk: *const HandleKeyPressFunc = ignoreKeyPress,
    activeDescriptionBuffer: [DESCRIPTION_BUFFER_SIZE]u8 = undefined,
    ignoreList: bool = false,
 
    pub fn flushDescription(self: *@This()) void {
        self.descriptionBufferUse = 0;
        self.activeDescription = &[0]u8{};
    }
    pub fn descriptionPrintfmt(self: *@This(), comptime fmt: []const u8, args: anytype) void {
        const remnants = self.activeDescriptionBuffer[self.descriptionBufferUse..];
        const printed = std.fmt.bufPrint(remnants, fmt, args) catch remnants;
        self.descriptionBufferUse += printed.len;
        self.activeDescription = self.activeDescriptionBuffer[0..self.descriptionBufferUse];
    }
    
    pub fn descriptionPrint(self: *@This(), s: []const u8) void {
        const remnants = self.activeDescriptionBuffer[self.descriptionBufferUse..];
        const len = @min(s.len, remnants.len);
        @memcpy(remnants[0..len], s[0..len]);
        self.descriptionBufferUse += len;
        self.activeDescription = self.activeDescriptionBuffer[0..self.descriptionBufferUse];
    }

    pub fn reset(self: *@This()) void {
        self.* = .{};
    }
};

Now what ends up happening, is that file doesn’t have any variables, it’s basically just data and functions from it.

Then You can have an instance of this inside a different state struct inside let’s say whatever the module’s “main” file is. You do that a couple of times and you end up having just a single instance of a struct per “module” in your codebase (or you could even compose further, and put them just inside main).

So you might end up with a struct like this that contains instances of other “state” structs:

const State = struct {
    output: UndoBuffer(256) = .{},
    // outputBuffer: OutputBuffer(1024 * 128) = .{},
    tempBuffer: OutputBuffer(8096) = .{},
    inputBuffer: InputBuffer = .{},
    errorBuffer: ErrorBuffer = .{},
    descriptionBuffer: DescriptionBuffer = .{},

    fzfState: root.fzf.State = .{},
    paintFunction: *const Paintfunction = painter.emptyPaintFunction,
    backupExtraDescriptionFunction: *const fn() void = doNothing,
    helpProtocol: HelpProtocol.State = .{},
};
1 Like
7

Definitely solid advice. In my earlier program I had an “App” structure containing all dependencies, meaning Io, logging, C libraries integrations. Each thing hidden behind a vtable so that it could be trivially replaced in tests. That makes the testing so nice.

This sounds like a pro tip for performance, especially for my use case where the “App” is only one in non-test. Does that also work if @This() is on stack? But I suppose even in tests I could do global localized to the test with something like

test {
const LocallyGlobal = struct {
   var state: State = undefined;
}
}

I think that would also work with the comptime (if stack address wouldn’t)

8

I don’t think it saves that much performance to be honest, the math that’s required to do it at runtime is generally cheap, since it’s just a pointer, and most of the time is spent waiting for RAM, and the same RAM is asked for in both cases (comptime *@This() vs runtime).

This is pure speculation though, we would need benchmarks and check the generated ASM to know for sure how true any of this is.

9

Also to clarify, Globals have comptime known pointers, so it does work to pass it as comptime, I have been doing that in my project for a while.

10

I got a little confused there. I realized even functions will have different addresses on each run and they are still “baked in” and it still works, right? I guess that has something to do with address relocation.

Also I think the performance gain may be significant when using vtables extensively. If the pointer was comptime and the vtable stored directly on it, compiler should be able to devirtualize just fine. That is just a speculation ofc. I’ll have to experiment with that later.

1 Like
11

In my personal programming, I pay a lot of attention to the movability of structs. So for an object, I usually split it into different parts based on which parts are mutable and which are immutable, and then use a ‘Handle’ to assemble them into an easy-to-use version.

Mutable part: State. Generally, all members in this struct are mutable, so there are no stack pointers (because pointers themselves are immutable). The only exception is heap pointers, which are allowed inside State. State allows ownership to be transferred across threads by copying, which is what we mean by movable.

Immutable part: Deps. The immutable part usually refers to handles to other external objects (like pointers) or other configuration values that are never going to be modified. These config values are likely to be shared with other objects, so I think there’s a good reason to isolate them from State. Deps doesn’t guarantee movability, because you don’t know if the other external objects might move together—if the external objects never move, Deps can move; if they do move together, you need to separately move the entities behind the external object handles and then regenerate Deps.

Operational part: Handle. A typical Handle is either a State pointer assembled with Deps, or a State pointer assembled with an immutable pointer to Deps. It’s most user-friendly to put the object’s method operations in the Handle. The movability of Handle is the same as that of Deps.

An example of this idea in std is ArenaAllocator. ArenaAllocator itself doesn’t guarantee movability, representing Handle in this model. It’s an assembly of child_allocator and state, where child_allocator represents the Deps part of this model. It’s instance is external and assembled with the mutable part of this model (including heap pointers). If you want to construct a composite type based on arena, using only its State part ensures the best movability. After moving, you can get back its Handle for use via promote.

The unmanaged data structures in std also have this kind of conceptual feature, but they express Deps, that is, the allocator, as parameters for each method, so there’s no need to introduce a Handle for operations anymore. Unmanaged data structures are all movable, so they beat managed data structures.

1 Like
12

ArenaAllocator is kinda weird example for this because it is movable and comments specifically say it is a memory optimization, but I think I can see how this separation helps with my problem.

I am still having a hard time understanding it because ArenaAllocator can not really be used as 1-1 example due to it being fully movable. So if I understand it correctly, I allocate (on stack) state and deps separately, and then when I pass things around, I pass around the state that depends on deps that are left behind where they were created? I suppose that if I want to access the deps too sometimes, I could just hold pointer in state to the deps object?

The State and Deps in ArenaAllocator seem kinda mixed up for my use case. This is what I came up with. Does it look about right?

const QueueWithBuf = struct {
    const Deps = struct {
        buf: [32]u8,
        const init = .{ .buf = undefined };

        fn promote(self: *Deps) QueueWithBuf {
            return .{ .state = .init(self), .deps = self };
        }
    };

    deps: *Deps,
    queue: Io.Queue(u8),
    fn init(deps: *Deps) QueueWithBuf {
        return .{ .queue = .init(&deps.buf) };
    }
};

fn usage() void {
    var dep: QueueWithBuf.Deps = .init;
    const queue = dep.promote();
    otherUsage(queue);
}

fn otherUsage(queue: QueueWithBuf) void {
    _ = queue;
}
13

It might be a bit unfortunate, but only if the underlying structure is designed to be movable can we design movable extensions based on it. Since Io.Queue isn’t a movable structure (its design already assumes that its underlying buffer can’t be moved), it’s hard to design movable extensions based on it. We have to assume that structures designed on top of it are immovable. From a practical perspective, assuming that Io.Queue is immovable is perfectly fine.

14

Queue is movable in the sense that there are no internal references that would break. But of course, it is a copy, so it just creates another queue. Which is very likely to cause bugs too. So yes, this was not the best thing to choose for demonstration.