handmade.network » Forums » Ideas on tree memory allocation
JayMech
Jayme
2 posts
#13269 Ideas on tree memory allocation
1 month ago

Hello, I'm new to this forum, so let me know if there's a better place for this post.

I'm working on writing a compiler from scratch, following (to some extent) the course at https://lagunita.stanford.edu/cou...gineering/Compilers/Fall2014/info.
I've gotten to the part where I'm constructing an abstract syntax tree and I'm having dificulty figuring out how to construct the data structure in a HMH way. Each node of the tree is a Token that can have any number of Children nodes.

I've decided on one of 2 options for the child pointer:
1. A pointer to an array of Token pointers
2. A pointer to a linked list of Tokens

My question is how to allocate memory for these scenarios:
1. In this case the only solution I can think of is to call realloc() every time a node gets added (or to do it less fequently by mainting a capacity and doubling when needed.) The problem is most nodes will only have 1 or 2 children, but some can have 100s or more. Perhaps the most HMH way to do this would be to write my own version of realloc?

2. This way seems pretty straight forward to allocate memory for: An array of Tokens and pointers address the children and siblings. I didn't particularly like this option because seeking through the linked list might not be ideal performance-wise.

What are the benefits or drawbacks of these ideas? Is there other ways that I haven't thought of?

And if there's a HMH episode where he does something similar, or any other resources, post a link (I'm still not very far in the series).
ratchetfreak
315 posts
#13270 Ideas on tree memory allocation
1 month ago

Profile and see what the common use cases are. Then you can target the allocation sizes accordingly.

Starting with 16 and doubling every time you exceed the capacity is a common general strategy.

Of course if your most common case is 1 or 2 and then it jumps to large arrays immediately after then start with 2 and go straight to 16 once a third gets added.

Also consider some kind of short buffer optimization. Where you have a `Node* shortBuffer[2];` inside Node to store just the first 2 children and then a Node** array to store the array of pointers for the rest once you need it.
dfrunza
Dumitru Frunza
21 posts

Apprentice
github.com/dfrunza/hoc

#13278 Ideas on tree memory allocation
1 month ago

I prefer the second option - a linked list of Tokens:
1) It's the simpler solution.
2) Easy to implement, which frees up more time to think about the main problem, i.e. the building of the AST.
3) If the performance turns out to be a problem, then the "pre-allocated children per Token" solution could be tried. Or another solution alltogether. At this point, the AST should be figured out, so the usage code has been written, and that can be used as a guide to the optimal solution.

I'm also writing a compiler and was faced with the same dilemma. I've opted for the linked-list solution, for the reasons above.


Programming is hard, let's go shopping!
JayMech
Jayme
2 posts
#13292 Ideas on tree memory allocation
1 month ago

Thanks for your replies!
I've decided to implement the Array/pointer method and use realloc() for now. I may go back and try to implement my own allocator later.
I found this article while looking for ideas: http://g.oswego.edu/dl/html/malloc.html.
It's an interesting read so far.