AcademySoftwareFoundation / AcademySoftwareFoundation/openvdb
Make Tree an AllocatorAwareContainer [REQUEST]
- Dominant language
- C++
- Stars
- 3.4k
- Forks
- 774
- Avg merge
- 3d 9h
- Merged PRs (30d)
- 34
Description
### Is your feature request related to a problem? Please describe.
https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer
As far as I can tell, OpenVDB does all of its memory management with `new` and `delete` as in `child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));` and `delete mNodes[n].getChild();`. C++17 in particular provided stateful allocators designed for use with pmr allocators. Things like memory pools and `monotonic_buffer_resource` seem ideal for some usage patterns of OpenVDB.
### Describe the solution you'd like
I think this would involve adding a template parameter to `InternalNode`:
```
template>
class InternalNode
{
public:
using allocator_type = Allocator;
```
where `AllocatorForChildNodeT` would be a metafunction so that if `_ChildNodeType` is an `InternalNode` it rebinds that allocator and if it's `LeafNode<...>` it is `std::allocator>` and adding `const Allocator& alloc = Allocator()` arguments to `InternalNode`'s constructor.
I think that then gets propagated up the tree so `RootNode` would do the same thing and. Likewise `Tree` (which has its `RootNode` by value) would just have `using allocator_type = typename RootNodeType::allocator_type;` and would add `const allocator_type& alloc = allocator_type()` arguments to its c'tors.
We'd have to add the member allocators and change the child allocation to use the allocators and change things like
```
template>
struct Tree4 {
using Type = Tree, N2, std::allocator_traits::template rebind_alloc>, N1>>>;
};
```
### Describe alternatives you've considered
I haven't experimented with this, and so far for my purposes I haven't found need of this... yet. But everything I've read/watched about allocators makes me think it's relevant to OpenVDB: From custom allocators for fixed-sized blocks to freeing large trees all at once.
### Additional context
One particularly interesting trick with allocators is what John Lakos calls "winking out", where a large tree structure (sound familiar?) can be build with a memory resource and then when done, rather than freeing each node of the structure, the entire thing can be freed in one big `free`.
Contributor guide
Research direction
Start by tracing the InternalNode, RootNode, Tree, and Tree4 definitions and the shown child allocation and deletion sites. Compare their current constructors and ownership paths with the AllocatorAwareContainer requirements. Done means the tree hierarchy consistently accepts and propagates allocators and uses them for child allocation, with relevant tests added or updated where the existing tree tests cover these types.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- data
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100