Allocations & Data Structures

[smoky aspen]

I am building a toy HTML parser to learn Zig. It has no long running, calls main and exits. But I still want to make sure I am correctly allocating and handling memory for future projects, meaning I don't want to just use a page_allocator and deinit it once.

Below is a contrived example, but is not too far off what I am actually doing in my application, which is hundreds of more lines long and has nested ArrayListUnmanaged allocators to mimic a HTML DOM structure.

https://pastebin.com/V4PiP2ua

defer gpa.free(post.html);

As someone new to memory management, this feels like an anti-pattern having to know this stack backed struct has one heap backed field, I only realised this because of the leak detector.

1. Is there a better approach to laying out and allocating this data structure?
2. Do you have any general advice on how to think about this? I have read the below articles which has helped me understand how to literally use allocators, but I've not yet grokked how to deploy them properly.

https://pedropark99.github.io/zig-book/Chapters/01-memory.html
https://gencmurat.com/en/posts/using-allocators-in-zig/
https://ziglang.org/documentation/master/#Memory

[granite gull]

You probably want to have a deinit function within Post where you would do the free and call defer post.deinit(gpa); in main.

Whenever possible, I allocate and free memory symmetrically; when the memory is allocated in init of a struct, I deallocate it in a deinit. When I allocate it in main and pass it to a structure for usage, I free it in main after it ends using it, never in the structure.

As someone new to memory management, this feels like an anti-pattern having to know this stack backed struct has one heap backed field, I only realised this because of the leak detector.
Exactly, that's why the struct should take care of deinitialization within it's own code. You're feeling it right I think.

[smoky aspen]

when the memory is allocated in init of a struct, I deallocate it in a deinit. When I allocate it in main and pass it to a structure for usage, I free it in main
I like this a lot.

So you're saying because I have a init function I should follow the same pattern of std.ArrayListUnmanaged — I feel like that makes sense because deinit is useful as I don't really know what ArrayListUnmanaged did with the memory, or what needs freeing, in the same way I don't (as a consumer) need to know what Post.init() did with the allocator either.

[fresh bane]

to automate this, convert your main() into a test but use std.testing.allocator which is just a gpa. this will call .deinit() and check for leaks/double frees.

then you might check out this blog which shows how you can test for missing errdefer free()s and similar https://www.ryanliptak.com/blog/zig-intro-to-check-all-allocation-failures/

[granite gull]

Yeah, exactly.

[smoky aspen]

I've made a memory mess again — I worked through all the detected leaks but I feel like I am having to free so much memory manually that I think I'm doing an anti-pattern, implemented something wrong or I just have serious garbage-collected-language brain

main: https://pastebin.com/iH0P9YkD
post: https://pastebin.com/fwiC6J42

there are so many defer blocks and for loops to deinit for something so simple that I am praying I am doing something wrong here.

The goal of this code is to take a dir_path, open that dir, load all markdown files, process them and return them as []Post.

1. am I fundamentally doing something wrong?
2. if not, is there a better approach to memory that would reduce the mental overheard of so much free'ing?

[fresh bane]

one idea is to make an arena in main and pass it to Posts.init() instead of the gpa. however that has the downside of not being able to free any memory except for the most recent allocation. so perhaps pass in both gpa and arena and use the gpa for short lived stuff and the arena for long lived stuff you want to be able to deinit all at once.

i mean that if you only pass a single arena, you will end up with higher memory usage (because it can't free except for its most recent allocation). that might be a good tradoff for simpler deinit.

[smoky aspen]

thats helpful thanks, i went a slightly weird approach where inside of init() i now create an arena allocator, and use the AA for the temp init only stuff, but put the Post stuff I want returned into the gpa.

helped clean up a lot of the defer blocks in init

[fresh bane]

ah that makes sense. seems simpler than my suggestions.

[earnest verge]

Interesting discussion. I am also learning about memory management and how to return values from function which have dynamic content: a struct with a dynamically sized array (result of processing a text file). I ended up using an ArrayList in the struct type, pseudocode:

const MyStruct = struct {
   processedData: ArrayList(SubStruct);

   fn init(ally: Allocator, path: [] const u8): !MyStruct {
      var data: ArrayList(SubStruct).init(ally);
      // do stuff, appending to data
      return MyStruct{
           .processesData: data
      };
   }
   fn deinit(self: *MyStruct) {
       self.data.deinit();
   }
}

I was really trying to use a slice or array in the struct first, it felt more "right", however in the end I changed my mind. Since the return from init (which perhaps could be called "process" instead?) is dynamic, why not be explicit about it?

[granite gull]

Yes you've made a bit of a mess. You broke my symmetry advice and now your init allocates multiple posts, but deinit deallocates just one. I think this is not very good. I can see why the init must return multiple post, but I would make an important change: rename the file from post.zig to posts.zig and make it store the array list; then, make the deinit destroy all of the posts. Within posts.zig, you can add the final Post structure as part of the file.
Another thing is that you are needlessly saving the paths into another array. Just don't save them – use them on the run with just one while loop. Even if you needed the paths later, for another iteration, it would probably be batter to store each path in the related Post and deinit it within Post.deinit(), but as far as I can see, you are only using the path during initialization so the copy is not needed at all.
Also, in main you are doing a catch; I think this is redundant since you can just try in main and Zig will tell you what the error was. If you didn't want to exit after an error, catch is the way, but you are exiting anyway so it would be simpler with try. You can see that I've made your main() really tiny. (tho I skipped the gpa choice in my snipped).
I think something like this would be good: https://pastebin.com/t0XGPdr0

[granite gull]

For me, personally, init is a better name as it pairs well with deinit. Zig STD however does not enforce this rule as stron as me so I will not recommend it as a standard, but within my projects I always pair inits and deinits. If I need different ways of initialization, or want to specify the "way" of initialization, I usually call it initX: initEmpty, initCopy, or in your example initProcess. But for most people, process would also be fine, I think.
If you predict that the processedData may be expanded or shrinked, you could also just make process work on an existing instance and have three functions: init, process, and deinit, used like this:

var x: MyStruct = .init(allocator);
defer x.deinit();
x.process("some/path.bin");

[earnest verge]

Thank you that's good advice. I like the initEmpty, initProcess idea - clear and intentional.

What do you think of having ArrayList inside a struct that is used as a function return type? It feels a bit 'off' for me still, especially since after the processing is done, that data is 'readonly/const'. No need for the dynamicness of ArrayList.

[granite gull]

It's ok. The data allocated by the array stays in the same place in memory. By returning the struct by value, you are only copying (moving) the pointer that the ArrayList holds. The overhead of having a list instead of simply a slice is small, but if it bothers you this much you could use toOwnedSlice at the end of init just like OP did in their second snippet. This will though need more complex errdefer blocks though.

[earnest verge]

Thank you very much @granite gull for all advice.

[smoky aspen]

@granite gull , just finished up my refactor from your guidance, it's so so much cleaner now, thanks a lot for your explanations and code 👌