Why can `ArrayList.toOwnedSlice()` fail?

Help
,
1

part1: ArrayList.toOwnedSlice():

        /// The caller owns the returned memory. Empties this ArrayList.
        /// Its capacity is cleared, making deinit() safe but unnecessary to call.
        pub fn toOwnedSlice(self: *Self, gpa: Allocator) Allocator.Error!Slice {
            const old_memory = self.allocatedSlice();
            if (gpa.remap(old_memory, self.items.len)) |new_items| {
                self.* = .empty;
                return new_items;
            }

            const new_memory = try gpa.alignedAlloc(T, alignment, self.items.len);
            @memcpy(new_memory, self.items);
            self.clearAndFree(gpa);
            return new_memory;
        }

How would this code ever get past the if statement, to the new_memory = try ... part? The .remap docs say

A null return value indicates that the resize would be equivalent to allocating new memory, copying the bytes from the old memory, and then freeing the old memory. In such case, it is more efficient for the caller to perform those operations.

In this case, the remap always shrinks the allocation (or leaves it the same size). So why would an allocator not be able to shrink memory?

I assume the answer is that different allocators store their metadata in different ways, and for some it just isn’t convenient to split up one allocation into a “shrunk” allocation and a “leftovers” allocation, so they just return null from .remap instead. Am I on the right track? Do you have specific examples of situations or allocators that can’t (ever?) shrink?

I mostly use ArenaAllocator, and it seems to always allow shrinking (but of course that’s one of the simplest allocators)

part2:

It feels wasteful for alist.toOwnedSlice() to sometimes allocate+copy, when it really doesn’t need to – all the data is already there! It could instead return a tuple: return .{ alist.items, alist.allocatedSlice() } – one slice of data the user wants, and one slice of data that needs to be deallocated later. (I assume calling myAllocator.free(alist.items) doesn’t work, because the length is wrong?)

Now, I think my suggestion here is clearly bad – needing to juggle both the-slice-I-care-about and the-slice-to-free-later sounds like a huge pain, and there might be a lot of unused/wasted memory sitting around in the allocated slice. But the status quo feels wasteful in a different way. I’m not sure what I’m asking here. Maybe it just boils down to my earlier question – why might a shrinking .remap() fail?

DoubleArrayList.toOwnedSlices()
2

part1: An example is SmpAllocator.remap.

part2: You mostly answered the question yourself. An ArrayList has a pointer, a length and a capacity. A slice has only a pointer and a length. For a ArrayList to become a slice, the length and the capacity have to have the same value. Note that sometimes (e.g. you build an ArrayList and use it’s values as a slice and then free it), using toOwnedSlice is not the best option. You can just use list.items instead and then deinit the list.

4 Likes
3

As for part2, it’s also a good idea to ask yourself what the intended usage of your API is.

If you ultimately don’t know the lifetime of the data you’re returning and how it’s going to be used by the caller, perhaps it’s a better idea for your function to take a pointer to a caller-supplied ArrayList, into which you then add your data.

pub fn populate(output_list: *std.ArrayList(Data), gpa: std.mem.Allocator) !void { ... }

Or perhaps the validity of the returned data is short, e.g. until the next call to your function. I have that in my turn-based game – there, in a play() function that performs a turn, I build a list of items, cache the list.allocatedSlice() in an internal state struct, then return the list.items, which is considered invalid the moment play() is called again and the previously allocated slice is reused.