DoubleArrayList.toOwnedSlices()

Brainstorming
, ,
1

I’m making a small library for analyzing graphs, and I ran into an issue with memory allocation / error handling. Basically it boils down to “how do I call .toOwnedSlice() on two separate ArrayLists?”, with @matklad’s great article as context for why this isn’t simple:

Here’s my main type (relevant parts only)

pub fn DirectedGraph(Node: type) type {
    return struct {
        const Link = struct { usize, usize };
        nodes: []Node, // contents should never change
        links: []Link, // contents should never change

        pub fn fromOwnedSlices(nodes: []Node, links: []Link) @This() {
            return .{
                .nodes = nodes,
                .links = links,
            };
        }

        pub fn deinit(self: *@This(), gpa: std.mem.Allocator) void {
            gpa.free(self.nodes);
            gpa.free(self.links);
            self.* = undefined;
        }

        // ...
    };
}

Now, I want to be able to build these graphs incrementally (e.g. by reading from stdin), so I made a helper type:

/// used to build a DirectedGraph of unknown size
pub fn DirectedGraphBuilder(Node: type) type {
    return struct {
        const Link = struct { usize, usize };

        nodes: std.ArrayList(Node),
        links: std.ArrayList(Link),

        const empty: @This() = .{
            .nodes = .empty,
            .links = .empty,
        };

        // BUGGY
        pub fn toFrozen_v10(self: *@This(), gpa: std.mem.Allocator) !DirectedGraph(Node) {
            const nodes = try self.nodes.toOwnedSlice(gpa);
            const links = try self.links.toOwnedSlice(gpa);

            return .fromOwnedSlices(nodes,links);
        }

        pub fn deinit(self: *@This(), gpa: std.mem.Allocator) void {
            self.nodes.deinit(gpa);
            self.links.deinit(gpa);
            self.* = undefined;
        }

        // pub fn addNode(...) !void { ... }
        // pub fn addLink(...) !void { ... }
    };
}

toFrozen_v10 is buggy: if the second try fails, the const nodes slice will leak, and calling deinit() later won’t help.

So… how about this?

// BUGGY
pub fn toFrozen_v20(self: *@This(), gpa: std.mem.Allocator) !DirectedGraph(Node) {
    const nodes = try self.nodes.toOwnedSlice(gpa);
    errdefer gpa.free(nodes);
    const links = try self.links.toOwnedSlice(gpa);
    errdefer gpa.free(links); // (this is a no-op, but the symmetry is nice)

    errdefer comptime unreachable;
    
    return .fromOwnedSlices(nodes,links);
}

Still no good: No leak this time, but if the second try fails, the builder will be left in an invalid state (empty self.nodes, non-empty self.links)

Okay, let’s do the “reserve first” strategy:

// works?
pub fn toFrozen_v30(self: *@This(), gpa: std.mem.Allocator) !DirectedGraph(Node) {
    const nodes_opt = gpa.remap(self.nodes.allocatedSlice(), self.nodes.items.len);
    const nodes = if (nodes_opt) |nodes|
        nodes
    else
        try gpa.alloc(Node, self.nodes.items.len);
    errdefer { if (nodes_opt==null) gpa.free(nodes); }

    const links_opt = gpa.remap(self.links.allocatedSlice(), self.links.items.len);
    const links = if (links_opt) |links|
        links
    else
        try gpa.alloc(Link, self.links.items.len);
    errdefer { if (links_opt==null) gpa.free(links); }
    
    errdefer comptime unreachable;

    if (nodes_opt) |_| {
        self.nodes = .empty;
    } else {
        @memcpy(nodes, self.nodes.items);
        self.nodes.clearAndFree(gpa);
    }
    if (links_opt) |_| {
        self.links = .empty;
    } else {
        @memcpy(links, self.links.items);
        self.links.clearAndFree(gpa);
    }
    
    return .fromOwnedSlices(nodes,links);
}

Well… I think it finally works (no error will leak memory or put this data structure into an invalid state, I think) but yikes, that did not go well. We wanted to just write v10, but ended up needing v30 instead to properly handle errors.

I basically had to inline each .toOwnedList() so that I could interleave them, to reserve all of the memory in advance. I wonder if the API of toOwnedList() should be reconsidered somehow: it’s a bit awkward that it can error, and that it does two separate things (remap, and reallocate if the remap fails).

This would be much nicer:

// BUGGY
pub fn toFrozen_v40(self: *@This(), gpa: std.mem.Allocator) DirectedGraph(Node) {
    self.nodes.shrinkAndFree(gpa, self.nodes.items.len);
    self.links.shrinkAndFree(gpa, self.links.items.len);
    
    const nodes = self.nodes.toOwnedSlice(gpa) catch unreachable;
    const links = self.links.toOwnedSlice(gpa) catch unreachable;
    
    return .fromOwnedSlices(nodes,links);
}

but this doesn’t work either: shrinkAndFree() claims to reduce the allocated capacity to the given length, but it gives up if the remap and reallocation both fail, so when toOwnedSlice() runs, it hits the same remap and allocation failures, triggering unreachable.

If we made a fn shrinkAndFreeForRealPlease(...) !void that errored if it wasn’t able to shrink to exactly the requested length, then this might be nice:

// IMAGINARY, AND BAD
pub fn toFrozen_v50(self: *@This(), gpa: std.mem.Allocator) !DirectedGraph(Node) {
    try self.nodes.shrinkAndFreeForRealPlease(gpa, self.nodes.items.len);
    try self.links.shrinkAndFreeForRealPlease(gpa, self.links.items.len);
    
    errdefer comptime unreachable;

    const nodes = self.nodes.allocatedSlice();
    const links = self.links.allocatedSlice();
    self.nodes = .empty;
    self.links = .empty;
    
    return .fromOwnedSlices(nodes,links);
}

but this doesn’t work either: there are good reasons why an allocator might not be able to shrink an allocation.

I may turn this into a blog post but I wanted to get some feedback first. Thoughts? Can you do better than my toFrozen_v30? Can you imagine a better version of the ArrayList.toOwnedSlice() API, or is it fine as-is? Should I change my graph API somehow? I might remove the split between DirectedGraph and DirectGraphBuilder, and instead add a pointer_stability lock, like HashMapUnmanaged. But that feels like giving up after just two try statements, surely it’s possible to deal with multiple erroring functions without running away screaming?

2

wait, toFrozen_v30 still isn’t right: if the first gpa.remap succeeds but the second gpa.alloc fails, self.nodes.deinit(gpa) will fail because we remapped the memory for self.nodes without updating it. But that should be fixable by reaching in and manually setting self.nodes.capacity, I think.

3

Most of the complexity here comes from trying to remap or alloc/shrink and free one list, then do the same for the other.

In other words, you’re overlapping your creation of the new resource with the cleaning up of the old. Now this is intrinsic to remapping, so if you want to remove this issue you have to remove your attempts to keep remap.

Something like:

pub fn toFrozen_vIDK(self: *@This(), gpa: std.mem.Allocator) !DirectedGraph(Node) {
    const nodes = try gpa.alloc(Node, self.nodes.items.len);
    errdefer gpa.free(nodes);
    const links = try gpa.alloc(Link, self.links.items.len);
    errdefer gpa.free(links);

    errdefer comptime unreachable;

    @memcpy(nodes, self.nodes.items);
    @memcpy(links, self.links.items);

    self.nodes.deinit(gpa);
    self.links.deinit(gpa);

    return .fromOwnedSlices(nodes,links);
}

Now there is nowhere to fail and invalidate the builder.

I imagine this operation happens after a hot section, so there is less concern on the performance/efficiency so you can forgo trying to remap.

1 Like
4

One meta Zig lesson I am still learning is that Zig seems to encourage building small, “domain specific” data structures, rather than re-using something general purpose. A bunch of beneficial refactors I did in the past were of the form of

const NodeList = ArrayList(Node);
    ->
const NodeList = struct { ... };

where you don’t necessary think in terms of concrete representation (an array list of nodes), but rather think at the higher level of abstraction (a set of nodes), and then implementation is whatever (it might be ultimately backed by an ArrayList, but could also be more custom).

Applying this here, I think it’s not necessarily given that Graph and GraphBuilder will use identical internal representation. The fact that you can convert array list to slice directly is incidental, and is not a fundamental shape of the problem (what if want to change Graph to use adjacency matrix?).

So, I’d go for the following API shape:

const GraphBuilder = struct {
    pub fn to_graph(builder: *const GraphBuilder, gpa: Allocator) !Graph {
        var graph = try Graph.initWithCapacity(gpa, .{ 
            .node_count = builder.nodes.count(), 
            .link_count = builder.link.count(), 
        });
        errdefer comptime unreachable; 
        // Code to copy from Builder into Graph, 
        // adjusting representation if necessary. 
        return graph;
    }
}

The purpose of the Builder is to compute node&link count (and maybe per-node in-out degrees), so that we can allocate Graph’s storage in one go.

5 Likes
5

Does MultiArrayList not solve this use case?

6

I would have done this:

pub fn toFrozen_vRevert(self: *@This(), gpa: std.mem.Allocator) !DirectedGraph(Node) {
    const nodes = try self.nodes.toOwnedSlice(gpa);
    errdefer self.nodes = .fromOwnedSlice(nodes);
    const links = try self.links.toOwnedSlice(gpa);
    errdefer comptime unreachable;
    
    return .fromOwnedSlices(nodes,links);
}
3 Likes
7

I don’t think it does.

The datastructure is a (directed) graph, and these normally have the characteristic that links.len > nodes.len.

std.MultiArrayList on the other hand is conceptually more of an optimisation over std.ArrayList(MyType) where the data is just laid out differently if I understand it correctly.

2 Likes
8

Now I understand, different lengths. Thanks!

9

Thanks! These replies have given me a lot to think about. You’ve solved my practical problems, but theoretically I still wonder about Allocator.remap. It might be nice if there was a non-mutating version, maybe Allocator.canRemap() bool. Then my v30 could make all its decisions before it started mutating the data. (assuming this split is even possible? I suppose the canRemap result can become outdated as other allocations happen, hm)

I’m not suggesting this seriously, it’s just an idle thought after getting through the problem. My v30 is a dead end anyway: Sze’s vRevert is tons better, and vulpesx/matklad’s suggestions seem like the best way forward: accept an “unnecessary” memcpy in exchange for simplicity and flexibility.

1 Like