Runtime Array creation

Explain
, ,
1

Hi, recently ive been having to create runtime arrays where i have some data to iterate over and append it to an array, and although i have a way that works (and even think is the proper/accepted way)

One of my usecases: create an array of the cli arguments. Solution:

pub fn argsToArray(gpa: std.mem.Allocator, args: std.process.Args) []const []const u8 {
    var result: std.ArrayList([]const u8) = .empty;
    defer result.deinit(gpa);

    var iter = args.iterate();
    _ = iter.skip(); // skip program name
    while (iter.next()) |arg| result.append(gpa, arg) catch @panic("insufficient memory");
    return result.toOwnedSlice(gpa) catch @panic("insufficient memory");
}

I dont like having to use ArrayList. i dont quite like it. I think i find it “ugly”. And i feel it has unnecessary allocations. And i feel im having to create a lot of ArrayList in so many different places (even more so when there are ArrayList inside something that im also grouping in ArrayList).

TL;DR

This pattern appears again and again and again. And i dont quite actually like it and am wondering if theres another simpler way im missing, or even if not simpler, prettier.

Extra question:

  • why does args.Iterator not have a peek()?
  • whats more recommended: returning toOwnedSlice() or keeping the ArrayList around?

The extra info:

(All of this is not really relevant to the question)

The reason i had to do that instead of using args.Iterator I needed to parse the cli where some option would take a list of arguments --foo a b c --bar.

while (iter.next()) |opt| {
  if (eql(u8, opt, "--foo")) {
    while (iter.next()) |arg| {
      if (startswith(arg, '-') break;
      ...
    }
  } else if (eql(u8, opt, "--bar") {...}
}

This is simple, and clean, and gets the values fine, but then --bar gets skipped because we already looked at it with next(). (and im realising i could have the else if be an if and it would get executed next, but that gets messy with more options and other complex parsings)

So we would need the args.Iterator to either be able to set the index back, which not possible because the iterator is consuming the arguments and only keeps remaining, or for the iterator to have a peek which it doesnt have (and i cant understand why it wouldnt, so thats another question if anyone can answer). So instead i had to do what i pasted up there: go throug it all and create my own array with all the elements. And then have my own iterator that has an index so each next increments the index and then i can if (startswith(arg, '-') {iter.index -=1; break;}.

More cases where i had to do this:

Right here, getting the list of options passed to --foo.
When i was using the args.Iterator i would need to do it with an ArrayList again.
Not anymore though. Now using my iterator that keeps the og array i can get the iter index when we enter the --foo and get the index when we get the next option that starts with - and return a slice/copy of the slice (copy of slice if i deallocate the args list after parsing, slice otherwise; havent decided yet what to do, for now i copy).
Im quite happy with this :smiley:


(Actually --foo takes multiple lists so --foo a b --bar --foo c would set foo=[[a,b],[c]]), so thats another ArrayList)


Im working with sqlite data. The sqlite statement gives me an iterator. So i want to iter through the rows to get an array and then i will further work with that.
Same process.


And lastly (so far) those rows have some data in strings that i want to split into an array of strings.
mem.split... returns an iterator. Again the same.
Although im thinking that for this particular case i could do a mem.count of the splitting character and then use an `ArrayList with a fixedbuffer of that lenght. And that should remove some allocations.

2

I’m sorry, I didn’t understand at all what this post is looking for.

For the case of args specifically, if you want a more flexible form of iteration, you might want to do args.toSlice(gpa) and then work with the resulting []const [:0]const u8.

If you want to avoid ArrayList because of too many allocations you could try the Reserve First strategy? or rethink your memory layout to be flatter? (struct-of-arrays style thinking)

2 Likes
4

its true, this post is very messy. tried to gather the important thoughts/questions in the tldr, which is “what are some other options for this pattern that yield the same result, an array at runtime”.

but i gotta say that even for not understanding your answer was quite helpful :smiley:

how even did i miss this when looking at std lol

could you expand on this? maybe some example?

5

Sure! the “struct-of-arrays” thinking is inspired by things like std.MultiArrayList, “data-oriented design” etc. in case keywords are useful.

Here’s how I’ve used it in a project that implements the VDB data structure. For a quick and shallow introduction, you could skim through the “deep” dive here: JangaFX - Insight: VDB, a deep dive

The main thing to take away is that a VDB is a bit like a B-tree or an octree; nodes are nested inside nodes and they have physical coordinates. The Zig project I’m about to link to below used to, like the (very naïve) Odin code in the link above, also model the tree as a tree in memory, so that each Node object would maintain its own std.AutoHashMap of children.

The problem with this is of course that it is extremely wasteful in terms of memory and cache locality, since each node has a separate allocation for its children.

Here is how the Zig project currently structures the VDB type in memory:

This is a classic “struct of arrays”: all of the nodes at the possible heights “A”, “B” and “C” are stored contiguously in memory by type reducing the number of individual allocations a VDB manages from O(n^3) to O(1).

This of course makes traversing the tree in memory slightly more complicated; I use a technique detailed in the original white paper.

In testing my reorganization, my results saw a ~25% speedup and reduced peak rss by a factor of 3, so there are real gains to be made :slight_smile:

4 Likes
6

toSlice expects an arena as it leaks memory.

1 Like