4 ms·
Here's an example. Imagine you're writing a parser that creates AST tree in C++. What 99% of people do is the "individual" style where every node is allocate w
by kjksf 10mo ago
Here's an example. Imagine you're writing a parser that creates AST tree in C++.
What 99% of people do is the "individual" style where every node is allocate with new and the memory comes from generic OS allocator.
Then when you free the AST tree, you have traverse the tree and call delete on every node.
There can be thousands of nodes.
The crucial observation is: the lifetime of all nodes is the same. It's the lifetime of AST tree.
The "grouped" thing is: you have an allocator dedicated to nodes of the AST tree. All nodes are allocated from this allocator.
This has numerous speed and simplicity benefits.
You need one free() call to free allocator vs. thousands of free() for each node.
You can optimize your allocator for that use case compared to general OS allocator. By definition it's a bump pointer allocator (i.e. allocation is mostly addr += sizeof(obj)) which is much faster than what even fastest general allocators can do.
You don't need to track per-allocation metadata that general allocator needs to be able to individually free each allocation. So you use less memory.
There's no fragmentation because your allocator is contiguous space.
The use of cache lines is most likely better because memory is not spread around. The nodes are used together so it's better if they are close in memory.
Those are very significant benefits and yet, as the article notices, very few people are aware of this.
Plus until very recently (before Rust became popular) the only serious low-level language was C/C++ and they don't help you programming in this style.
Odin, zig, jai do. They make an allocator an exposed thing and provide language and standard library support for using different allocators.
- ufmace 10mo agoOkay, it makes sense that that's what it is. Still, it seems to me like that's more of an optimization technique that's applicable to certain specific scenarios rather than a mindset to view all software development as. I have actually heard of something like that, as arena allocation, though mostly as something to use in a GCed language to either avoid or reduce the impact of GC cycles, also for certain specific scenarios.
- CyMonk 10mo agoIn this case the "grouped element mindset" means not only just using allocators but also avoiding RAII by flattening the traditional pointer- based OOP AST into arrays accessed by handles.