Data structures with or without allocation?

Explain
,
1

Hi everyone,

Having worked with Rust, I’m used to decide whether I make fields of a struct owning the data or referring to it.

How does this usually work in Zig? When I create a data structure, let’s say a TriangularMatrix, do I usually decide whether

  • TriangularMatrix has an init function to allocate the required memory,
  • TriangluarMatrix has an init function that expects a backing buffer that could, for example, be in a local variable on the stack?

Why not have both?

I tried to figure out, what’s idiomatic, and had a look at std.RingBuffer, which seems to require that an allocator is used.

But why isn’t there a function like initNoAlloc, which does something like:

pub fn ringBufferNoAlloc(backing_array: []u8) std.RingBuffer {
    return std.RingBuffer{
        .data = backing_array,
        .read_index = 0,
        .write_index = 0,
    };
}

Then you could do:

pub fn main() !void {
    var backing_array: [16]u8 = undefined;
    // var ring_buffer = std.RingBuffer.initNoAlloc(&backing_array);
    var ring_buffer = ringBufferNoAlloc(&backing_array);
    try ring_buffer.write(1);
    try ring_buffer.write(7);
    std.debug.assert(ring_buffer.read() == 1);
    std.debug.assert(ring_buffer.read() == 7);
    std.debug.assert(ring_buffer.read() == null);
}

I guess I could still use a FixedBufferAllocator in those cases. Is that the way to go? Why not have a much more simple initNoAlloc function? Because it’s boilerplate to always provide both?

And what should I usually do with my own data structures, in particular if I want to model certain mathematical (numerical) objects?

Your help and comments are appreciated. :folded_hands:

1 Like
2

Looking at ring buffers in Zig to find idiomatic use is interesting, since there are so many: https://github.com/ziglang/zig/issues/19231 :slight_smile:

That said, LinearFifo (a kind of ring buffer, as mentioned in that issue) sort of have the flexibility you ask for. Not sure if LinearFifo will survive in std, but your design consideration is certainly valid.

1 Like
3

Accepting an allocator allows for both, e.g. you can pass in a FixedBufferAllocator backed by a stack buffer. Sure there will be some overhead, but it’s usually negligible and in my opinion it’s more important to have a simpler API.

1 Like
4

You don’t necessarily have to choose between the two; you can also design your data structure in such a way that it supports both usages. Look to std.ArrayListUnmanaged for inspiration:

// allocator-backed
{
    const allocator = std.heap.page_allocator;

    var items: std.ArrayListUnmanaged(i32) = try .initCapacity(allocator, 256);
    defer items.deinit(allocator);

    items.appendAssumeCapacity(1);
    items.appendAssumeCapacity(2);
    items.appendAssumeCapacity(3);
}

// buffer-backed (calling any method that takes an allocator argument becomes UB)
{
    var buf: [256]i32 = undefined;

    var items: std.ArrayListUnmanaged(i32) = .initBuffer(&buf);

    items.appendAssumeCapacity(1);
    items.appendAssumeCapacity(2);
    items.appendAssumeCapacity(3);
}
1 Like
5

Yeah, I feel like it’s a weighing of pros and cons, and I wonder if maybe there was some “usual” way of how this is handled.

So it looks like std goes both ways and isn’t always consistent: std.RingBuffer always demands allocation (disregarding whether it will disappear one day), but std.ArrayListUnmanaged provides two init functions (initBuffer and initCapacity).

(I do understand that making std consistent isn’t a top priority as of yet, but to be done some time in future.)