Is it possible to avoid stack allocation when populating an ArrayList?

lhk · October 18, 2023, 7:33am

I was looking at a snippet of code that adds items to an ArrayList. The new item is first created on the stack and then passed over to the ArrayList.

Isn’t this inefficient? What if the item is very large? Maybe it’s not even possible to have a copy of the item on the stack, because it is too large.

I’ve created a small toy example. The first test “intoListFromStack” shows the code I’ve been using so far to populate an ArrayList. But the struct LargeStruct is not compatible with this code, it’s too large for the stack:


const SmallStruct = struct {
    data: usize,
};

const LargeStruct = struct {
    data: [1000000]i128,
};

test "intoListFromStack" {
    var list = std.ArrayList(SmallStruct).init(std.testing.allocator);
    defer list.deinit();
    const N = 3;
    for (0..N) |_| {
        var small = SmallStruct{ .data = 0 };
        try list.append(small);
    }
    // the following crashes, the struct is too large for the stack
    //var big = LargeStruct{ .data = undefined };
}

It is possible to allocate LargeStruct on the heap:

test "simpleAlloc" {
    // but it is possible to allocate on the heap
    var big = try std.testing.allocator.alloc(LargeStruct, 1);
    defer std.testing.allocator.free(big);
    std.debug.print("big: {d}\n", .{big[0].data[0]});
}

So now I’d like to create an ArrayList with pointers to LargeStruct. But looking at the ArrayList source code, I’m a bit confused how that would be possible.
I think the relevant line is this, a new item is added to the list:

github.com

ziglang/zig/blob/aeadcb3918f7e6bc7abb08e70ffe3b3c25fb9c22/lib/std/array_list.zig#L268


      
                  }
          
                  self.items.len -= len - new_items.len;
              }
          }
          
          /// Extend the list by 1 element. Allocates more memory as necessary.
          /// Invalidates pointers if additional memory is needed.
          pub fn append(self: *Self, item: T) Allocator.Error!void {
              const new_item_ptr = try self.addOne();
              new_item_ptr.* = item;
          }
          
          /// Extend the list by 1 element, but assert `self.capacity`
          /// is sufficient to hold an additional item. **Does not**
          /// invalidate pointers.
          pub fn appendAssumeCapacity(self: *Self, item: T) void {
              const new_item_ptr = self.addOneAssumeCapacity();
              new_item_ptr.* = item;
          }

I think new_item_ptr.* = item means that the value of item is copied to new_item_ptr.*.
So if item itself is a pointer, how can that work? Is there some automatic dereferentiation?

I’ve created another test which tries to populate an ArrayList with items created on the heap.
But this doesn’t work.
The ArrayList doesn’t take ownership of the pointer, so I still need to clean it up.
And when it runs out of scope (and its memory is freed) the ArrayList ends up pointing to freed memory, leading to a segfault:

test "intoListFromHeap" {
    // attempt 2 at creating an ArrayList of LargeStructs
    // this time I'm keeping pointers, to heap allocated memory
    var list = std.ArrayList(*LargeStruct).init(std.testing.allocator);
    defer list.deinit();

    const N = 3;
    for (0..N) |_| {
        // allocating a new entry on the heap
        var large = try std.testing.allocator.create(LargeStruct);

        // the following line confuses me
        // I would have expected, that the ArrayList takes ownership of the heap allocated memory
        // but if I remove the following line, the memory is leaked
        defer std.testing.allocator.destroy(large);
        try list.append(large);
    }
}

How does this work? Can I create an ArrayList of LargeStruct?

squeek502 · October 18, 2023, 8:02am

ArrayList(*LargeStruct) would be the way to go.

I believe you essentially have two options:

Create a new struct that has the ArrayList as a field, add a deinit function that destroys the *LargeStructs as well as deinits the ArrayList, and document that this is what it does. This is sort of the approach std.BufMap takes, in particular see the putMove function.
If it’s a temporary ArrayList with a known scope, then it might be easy enough to make sure the pointers outlive the ArrayList. Avoiding use-after-free would be on you, though; the compiler won’t assist you in this scenario.

IntegratedQuantum · October 18, 2023, 8:18am

There is a way to make this work with an ArrayList(LargeStruct).
The function ArrayList.addOne() adds an element and return a pointer to the newly inserted element.
You can then use the pointer to init the element:

const elem_ptr = list.addOne();
elem_ptr.* = big_ptr.*; // You can copy an existing big struct from the heap.
elem_ptr = .{.fieldA = someValue, .fieldB = otherValue}; // You can use regular struct initialization.
elem_ptr.fieldA = someValue; // You can initialize individual fields.
elem_ptr.fieldB = otherValue;

All of these should not cause stack overflows.

But keep in mind that the pointer from addOne is invalid as soon as you add more elements to the list.

matklad · October 18, 2023, 9:24am

Conversely, another gotcha is that you must write an element to avoid getting an inconsistent state. Code like this could end up creating a list with uninitialized elements

const elem_ptr = list.addOne();
elem_ptr.* = try compute_element();

lhk · October 18, 2023, 10:28am

@IntegratedQuantum thanks for the help again

but calling addOne causes out of memory errors.

At first I suspected that the list provisions space for more than one element and therefore runs out of memory.
But allocating an array of LargeStruct on the heap works fine:

var big = try std.testing.allocator.alloc(LargeStruct, 3);
defer std.testing.allocator.free(big);
std.debug.print("big: {d}\n", .{big[0].data[0]});

Whereas this returns an out of memory error:

var list = std.ArrayList(*LargeStruct).initCapacity(std.testing.allocator, 3);

Here’s the full code snippet again, with some more comments

const std = @import("std");

const SmallStruct = struct {
    data: usize,
};

const LargeStruct = struct {
    data: [1000000]i128,
};

test "intoListFromStack" {
    var list = std.ArrayList(SmallStruct).init(std.testing.allocator);
    defer list.deinit();
    const N = 3;
    for (0..N) |_| {
        var small = SmallStruct{ .data = 0 };
        try list.append(small);
    }
    // the following crashes, the struct is too large for the stack
    //var big = LargeStruct{ .data = undefined };
}

test "simpleAlloc" {
    // but it is possible to allocate on the heap
    var big = try std.testing.allocator.alloc(LargeStruct, 3);
    defer std.testing.allocator.free(big);
    std.debug.print("big: {d}\n", .{big[0].data[0]});
}

test "intoListFromHeap" {
    // when using initCapacity it fails
    var list = std.ArrayList(*LargeStruct).init(std.testing.allocator);
    defer list.deinit();

    const N = 3;
    for (0..N) |_| {
        // allocating a new entry on the heap
        var large = try std.testing.allocator.create(LargeStruct);

        large.data[0] = 42;
        std.debug.print("large: {d}\n", .{large.data[0]});

        // // if this line is not included, memory is leaked
        defer std.testing.allocator.destroy(large);

        // this fails
        //const elem_ptr = list.addOne();
        //elem_ptr.* = large.*;

        // end of the scope, the pointer is cleaned up
    }

    // segmentation fault
    //std.debug.print("list: {d}\n", .{list.items[0].data[0]});
}

lhk · October 18, 2023, 10:32am

Thanks for the feedback.
But it’s not clear to me how I would implement your suggestion. My gut feeling is that there’s still a problem around who owns the pointer to LargeStruct and I don’t see how a wrapper around ArrayList would solve that.

lhk · October 18, 2023, 11:02am

It’s a fun problem
I’ve tried to create my own ArrayList, probably horribly inefficient and buggy.

Here goes:


const MyOwnArrayList = struct {
    const Self = @This();

    allocator: std.mem.Allocator,
    items: []LargeStruct,
    len: usize,

    pub fn init(allocator: std.mem.Allocator, capacity: usize) !MyOwnArrayList {
        const memory = try allocator.alloc(LargeStruct, capacity);
        return Self{ .allocator = allocator, .items = memory, .len = capacity };
    }

    pub fn get(self: *Self, index: usize) !*LargeStruct {
        if (index >= self.len) {
            const new_capacity = self.len * 2;
            const new_items = try self.allocator.alloc(LargeStruct, new_capacity);
            @memcpy(new_items[0..self.len], self.items);
            self.allocator.free(self.items);
            self.items = new_items;
            self.len = new_capacity;
        }
        // could be uninitialized
        return &self.items[index];
    }

    pub fn deinit(self: *Self) void {
        self.allocator.free(self.items);
        self.len = 0;
    }
};

test "MyOwnArrayList" {
    var list = try MyOwnArrayList.init(std.testing.allocator, 3);
    defer list.deinit();

    for (1..10) |i| {
        const ptr = try list.get(i);
        ptr.data[0] = i;
    }
    for (1..10) |i| {
        const ptr = try list.get(i);
        try std.testing.expect(ptr.data[0] == i);
    }
}

permutationlock · October 18, 2023, 11:03am

You should have ArrayList(LargeStruct) and also need a try when calling addOne. This modified test works for me:

test "intoListFromHeap" {
    var list = std.ArrayList(LargeStruct).init(std.testing.allocator);
    defer list.deinit();

    const N = 3;
    for (0..N) |_| {
        var large = try std.testing.allocator.create(LargeStruct);
        defer std.testing.allocator.destroy(large);

        large.data[0] = 42;
        std.debug.print("large: {d}\n", .{large.data[0]});

        var elem_ptr = try list.addOne();
        elem_ptr.* = large.*;
    }

    std.debug.print("list: {d}\n", .{list.items[0].data[0]});
}

lhk · October 18, 2023, 11:04am

Maybe noteworthy:
This creates instances of LargeStruct on the heap.
It dynamically changes size (initialized with capacity 2, then 10 elements are used).
And it’s probably very inefficient, since every access checks bounds.
Plus, that’s the very first time I’m using something like memcpy so I’m not at all sure whether I’m doing the right thing.

lhk · October 18, 2023, 11:05am

Interesting, will try this later.
Thanks for your help

dee0xeed · October 18, 2023, 11:13am

If you have a list of pointers to structs, the items must be pointers.

I have some pool implemented as a stack on top of ArrayList, here is the code:

const std = @import("std");
const edsm = @import("engine/edsm.zig");
const StageMachine = edsm.StageMachine;
const Allocator = std.mem.Allocator;

pub const MachinePool = struct {

    const Self = @This();
    const MachinePtrList = std.ArrayList(*StageMachine);

    allocator: Allocator,
    list: MachinePtrList,

    pub fn init(a: Allocator, cap: usize) !Self {
        return Self {
            .allocator = a,
            .list = try MachinePtrList.initCapacity(a, cap),
        };
    }

    pub fn put(self: *Self, sm: *StageMachine) !void {
        var p = try self.list.addOne();
        p.* = sm;
    }

    pub fn get(self: *Self) ?*StageMachine {
        return self.list.popOrNull();
    }
};

StageMachines themselves are allocated on the heap outside and then pointers to them are added/removed to/from this simple stack.

Note const MachinePtrList = std.ArrayList(*StageMachine);

lhk · October 18, 2023, 12:57pm

@permutationlock thanks, your code seems to work and is quite intuitive

@dee0xeed thanks to you, too
But I’m confused about the memory management in your code snippet.
The StageMachine pointers which are passed to put are allocated on the heap outside of this code, right?
So, who is responsible for cleaning them up?
From the code I see, I would imagine a usage pattern like this:

var sm = try allocator.create(StageMachine);
// populate sm.* with initial values
defer allocator.destroy(sm);

machinePool.put(sm);

But then, as soon as the sm pointer goes out of scope, your MachinePool will have dangling pointers.

lhk · October 18, 2023, 1:06pm

Hm, not sure how to formulate this correctly.

Is it possible to hand responsibility for a pointer over to the ArrayList?
If I create an ArrayList(*LargeStruct), which stores pointers to heap allocated objects, can I let the deinit of the ArrayList handle the memory cleanup, and just not do defer cleanup for the heap allocated object?

I’ve tried to set this up in the very first code snippet, but couldn’t make it work.
Is this because the ArrayList API just isn’t made for this, or is there something more fundamental about the problem.

Rough outline:

var list = ArrayList(*LargeStruct).init(allocator);
defer list.deinit()
var s = try allocator.create(LargeStruct);
// no cleanup of s

// the pointer is handed to ArrayList, it's cleaned up by ArrayList
try list.append(s);

In Rust this would be a transfer of ownership.
I’d create a heap allocated object, and pass ownership of it to a container.

Also, something completely different: @dee0xeed where do you deinit the list inside of your MachinePool?

dee0xeed · October 18, 2023, 1:24pm

Yes, that’s right.

In that particular program where I took the snippet from,
StageMachines entities (pointers to which are kept in the pool) exist
‘forever’ (until the program termination), so I never destroy() them.

dee0xeed · October 18, 2023, 1:37pm

Of course, when initializing, a result from create() stored in local var is eventually goes out of scope, but we stored this pointer into our ArrayList. If I wanted to destroy all existing machines in the end I would exract them one by one from the pool and… destroy them.
This is the pool that keeps the pointers and they can not be dangling, they always points to the right places.

dude_the_builder · October 18, 2023, 1:41pm

Maybe I missed this somewhere already in this thread, but if you have an ArrayList of pointers, you clean it all up with:

defer {
   for (list.items) |ptr| allocator.destroy(ptr);
   list.deinit();
}

if the items themselves require a deinit:

defer {
   for (list.items) |ptr| {
        ptr.deinit();
        allocator.destroy(ptr);
    }
   list.deinit();
}

dee0xeed · October 18, 2023, 1:42pm

Nowhere, an instance of the pool is needed until program termination.
In my particular case of course.

Luke · October 18, 2023, 2:43pm

lhk:

var sm = try allocator.create(StageMachine);
// populate sm.* with initial values
defer allocator.destroy(sm);

machinePool.put(sm);
But then, as soon as the sm pointer goes out of scope, your MachinePool will have dangling pointers.

I think that contrary to Rust and like C, ownership is not a working concept in zig. It is implied from the code. And here, calling destroy on sm means that you are not transferring the ownership to the ArrayList must expect dangling pointers. If you want to transfer ownership, you should only destroy sm when you remove it from the machinePool later in your code or when you destroy the ArrayList.

ivanhernandez · October 18, 2023, 6:19pm

Would do that, wrapping it within your custom array type.

Anyway, Should not an arena allocator and an ArrayList of pointers solve this problem? Just deferring both ArrayList and allocator deinitializations should do the trick, if I’m not wrong. Taking your modified example (will mark modified lines with //**):

onst std = @import("std");

const SmallStruct = struct {
    data: usize,
};

const LargeStruct = struct {
    data: [1000000]i128,
};

test "intoListFromStack" {
    var list = std.ArrayList(SmallStruct).init(std.testing.allocator);
    defer list.deinit();
    const N = 3;
    for (0..N) |_| {
        var small = SmallStruct{ .data = 0 };
        try list.append(small);
    }
    // the following crashes, the struct is too large for the stack
    //var big = LargeStruct{ .data = undefined };
}

test "simpleAlloc" {
    // but it is possible to allocate on the heap
    var big = try std.testing.allocator.alloc(LargeStruct, 3);
    defer std.testing.allocator.free(big);
    std.debug.print("big: {d}\n", .{big[0].data[0]});
}

test "intoListFromHeap" {
    // Use arena allocator (is it valid to wrap testing allocator?)   //**
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);  //**
    const itemsAllocator = arena.allocator();  //**
    // when using initCapacity it fails
    var list = std.ArrayList(*LargeStruct).init(itemsAllocator);

    defer list.deinit();
    defer arena.deinit(); // Will not deal with elements deallocation... arena will be destroyed //**

    const N = 3;
    for (0..N) |_| {
        // allocating a new entry on the heap
        var allocated = try itemsAllocator.alloc(LargeStruct, 1);
        var large = allocated[0];

        large.data[0] = 42;
        std.debug.print("large: {d}\n", .{large.data[0]});

        // // if this line is not included, memory is leaked
        // DON'T defer std.testing.allocator.destroy(large); //**

        // this fails
        //const elem_ptr = list.addOne();
        //elem_ptr.* = large.*;

        // end of the scope, the pointer is cleaned up
    }

    // segmentation fault
    //std.debug.print("list: {d}\n", .{list.items[0].data[0]});
}

dude_the_builder · October 18, 2023, 6:41pm

Hey, using ArenaAllocator is cheating! lol Yes, an arena for this type of situation is a good fit, and I’ve also foond it to be indispensable if allocation is mixed with recursion. Also, in Zig, unlike C, if you’re allocating a single item you use allocator.create(Type) and free it with allocator.destroy(ptr). If it’s multiple items (a slice) you then use allocator.alloc(Type, N) and free it with allocator.free(slice).