PTree nodes could possibly be allocated in per-version Arenas and avoid reference counting
- Dominant language
- C++
- Stars
- 16.7k
- Forks
- 1.6k
- Avg merge
- 1d 20h
- Merged PRs (30d)
- 126
Description
I'll start by saying I'm not intimately familiar with the PTree code, but I think it's true that all PTree nodes created as part of applying mutations at version V will all be removed at the same time (logically, though actual removal is lazy) later when version V rolls out of the version window the PTree is holding.
Currently, each PTree node is fast-allocated and reference-counted independently. However, I think if the first paragraph is true then it is possible to avoid both of these things on a per-node basis. New PTree nodes could be allocated in per-version Arenas, one for each mutation version applied to the tree. A queue of (Version, Arena) pairs can be maintained and popped as versions roll out of the version window the PTree is covering. So that would take care of per-node fast alloc/free, and then I think there are two ways to avoid reference counting.
1. Track a list of PTree nodes by version so destructors can be called after the version has been excised from the tree
2. Ensure that PTree::data's dynamic memory is entirely located in the same Arena that the PTree instance is in so that PTree does not require a destructor call. This of course places restrictions on the template type that PTree can be used with. If the T being inserted is a Standalone<> type its Arena can be linked into the per-version PTree arena with Arena::dependsOn().
This certainly isn't a trivial task, so we should attempt to determine if the performance gain would be significant.
Contributor guide
Research direction
Read the PTree implementation and its existing node allocation and reference-counting paths first, then inspect Arena, PTree::data, and Arena::dependsOn as named in the proposal. Done means measuring whether per-version arenas and either cleanup strategy provide a significant performance gain while accounting for the stated template and destructor constraints.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- databases, performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100