Is there any overhead for using MultiArrayList to keep my pointers to pointers to data over using [][]u8 for that?
How does that scale with increasing number of pointers, let’s say up to 65K (u16) comparing with [][]u8?
I think there is probably minimal, constant time and space overhead, but this is an easily testable assertion that you could write a fun little shootout for and report back to us about!
1 Like
I don’t think they are the same thing.
Two-dimensional arrays, or array of string pointers, are probably exactly what you want.
MultiArrayList highlights a trick that transposes the storage layout. It splits each field of a struct into a separate array.
In your case, it’s perfectly fine to store points to strings of different lengths:
.{
"short-string",
"longer-strong-here",
"",
}
But AFAIK it’s not the use case for a multi-array-list.
2 Likes
If you are trying to store a list of strings, maybe look into StringTable and Programming without pointers. StringTable is a nice way to store a list of small strings. @andrewrk goes over the data structure (and other useful things) in the Programming without pointers talk.
2 Likes
MultiArrayList is backed by a single [*]u8. This means that, when you need to resize it, you’re resizing one allocation instead of many.
Most of the work done resizing is copying the old arrays into the new backing allocation - just resizing the allocation in-place is never practical since the memory layout is Struct-of-Arrays instead of Array-of-Structs.
By comparison, if you were using a [][]u8 and needed to add just one element, you would need to loop over the slice of pointers and resize every single allocation. While you conceivably could resize in-place without having to copy the memory over this way, resizing all of the allocations would still be a huge overhead, especially if you get unlucky and the host system says you have to allocate new memory and copy it over anyway.
1 Like
btw, the first time I read that string table solution I was thinking: it seems to make more sense to use an arena allocator rather than array list – no copies so the strings are stable, one fewer middle layer so the performance is arguably better.
You have to use array list. Otherwise you would not have handles(indices) to hand out. The handles are the whole point of string interning because you can trivially compare handles and easily check if a string is interned or not and remove duplicates. The array list could hold slices to strings backed by arena, instead of the strings themselves. Which would have advantages and disadvantages.
Indeed. Handles can save space too.
Maybe I’m misunderstanding OP’s usecase, but this doesn’t seem true to me? If we wanted to keep all the inner slices the same size then yes, we would have to resize them all, but seeing a [][]u8 makes me assume this is an array of strings, where we can add a string by resizing the outer slice, and extend any given string in the array by resizing that one slice.
A [][]T should actually be beneficial in that case over a one-deep slice if we often need to resize the inner slices as we can then do so by only resizing and copying that one smaller slice, as opposed to having to resize and copy the whole unislice.
If the inner slices are generally gonna remain unmodified though then I imagine a flat slice could be better in some cases though.
I allocate upfront, no allocation after init.
I also over allocate columns and rows.
I was wondering what performance implications can be using MultiArrayList instead of handling those manually. There is no appendSlice method for MultiArrayList.
I now see that MultiArrayList is being talked about with no knowledge of what it is. For a growable list of strings of differing lengths, let me just state clearly that it is the wrong tool for the job.
3 Likes
Well, as others have stated, that’s not what a MultiArrayList does, its purpose is efficiently storing structs and unions by converting them into a struct of arrays representation. See the std docs.
I don’t believe the Zig standard library provides any structure for representing a 2d array so you’d have to make one yourself there if you want something better than a [][]T.
For storing many strings efficiently I think one big []u8 for the contents of all the strings + a []u32 for the starting indexes of the strings could be better than a [][]u8. Depends on the exact usecase of course.
2 Likes