apple / apple/foundationdb

PTree nodes could possibly be allocated in per-version Arenas and avoid reference counting

Open
#1,360 5 comments 3 reactions 0 assignees View on GitHub
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.