Help me choose between multiarraylist and arraylist for a recursive structure

Help
1

My struct is

const Trie = struct {
    char: u21,
    occurances: usize = 0,
    end: bool = false,
    children: std.ArrayListUnmanaged(Trie) = .{},
}

and it works fine. The trie does, however, get very big. This is why im wondering if I should switch to a multiarraylist instead. Because, however, the multiarraylist in itself is a field larger, I am wondering if I may have deminishing returns.

Tldr:

  • My goal: make the trie as small as possible
  • My question: is a multiarraylist truly more efficient than a regular arraylist here (or am i getting deminishing return because it has one more field)?

EDIT:
I just noticed, arraylist is made of a slice and a usize, so technically just three usizes, while a multiarraylist is one multiitempointer and two usizes, so technically also just three usizes as well. Am I wrong here or are there technically only upsides to the multiarraylist here?

1 Like
2

Yep, the code

test {
    @compileLog(@sizeOf(std.MultiArrayList(struct {})));
    @compileLog(@sizeOf(std.ArrayListUnmanaged(struct {})));
}

revealed that they are both the same size, meaning that using a multiarraylist is clearly superior here, and literally ever other case when it comes to size.

I dont know why I just tested this myself earlier, but if anyone ever wonders, maybe they find this thread.

1 Like
3

We need to analyze this a bit deeper because the test you provided hides some of the nuances of this data structure.

Let’s look at the implementation of MultiArrayList…

The outer portion of MultiArrayList is the same size - it has a pointer, a length and a capacity (not unlike a slice and a capacity as in ArrayListUnmanaged):

bytes: [*]align(@alignOf(T)) u8 = undefined,
len: usize = 0,
capacity: usize = 0,

Now, this seems well and good, but you’ll notice a bit further down that there is a helper type named Slice that has a different set of data members.

pub const Slice = struct {
    /// This array is indexed by the field index which can be obtained
    /// by using @intFromEnum() on the Field enum
    ptrs: [fields.len][*]u8,
    len: usize,
    capacity: usize,

Here, you can see that this has an array of pointers equal to the length of the number of fields. If you have a long list of fields, this is quite a bit larger.

The question is, how is this internal structure used? That could have consequences.

When you call items to get your items, it calls slice under-the-hood:

/// Get the slice of values for a specified field.
/// If you need multiple fields, consider calling slice()
/// instead.
pub fn items(self: Self, comptime field: Field) []FieldType(field) {
    return self.slice().items(field);
}

Here’s how slice is constructed:

/// Compute pointers to the start of each field of the array.
/// If you need to access multiple fields, calling this may
/// be more efficient than calling `items()` multiple times.
pub fn slice(self: Self) Slice {
    var result: Slice = .{
        .ptrs = undefined,
        .len = self.len,
        .capacity = self.capacity,
    };
    var ptr: [*]u8 = self.bytes;
    for (sizes.bytes, sizes.fields) |field_size, i| {
        result.ptrs[i] = ptr;
        ptr += field_size * self.capacity;
    }
    return result;
}

It’s important to check the assembly. While these Slice objects are probably transient in your case compared to the instance of the MultiArrayList, they aren’t without a cost and they may have a size on the stack in certain conditions. More importantly, you have to calculate pointer offsets when you create them.

Long story short, a series of ArrayListUnmanaged and this have different costs/benefits by design.

1 Like
4

I agree with you, but thats also why I clarified that im optimizing purely for size on the heap.

5

If you really want to save memory, then the best solution would be to make your own (multi-)arraylist where len and capacity are u32 instead of usize. And maybe you could also turn occurences into a u32 as well