AcademySoftwareFoundation / AcademySoftwareFoundation/openvdb

Make Tree an AllocatorAwareContainer [REQUEST]

Open
#1,002 9 comments 0 reactions 0 assignees View on GitHub
enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.