| Message ID | 20241114170524.64391-1-sidhartha.kumar@oracle.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | Track node vacancy to reduce worst case allocation counts | expand |
On 11/14/24 12:05 PM, Sidhartha Kumar wrote: > ================ overview ======================== > Currently, the maple tree preallocates the worst case number of nodes for > given store type by taking into account the whole height of the tree. This > comes from a worst case scenario of every node in the tree being full and > having to propagate node allocation upwards until we reach the root of the > tree. This can be optimized if there are vacancies in nodes that are at a > lower depth than the root node. This series implements tracking the level > at which there is a vacant node so we only need to allocate until this > level is reached, rather than always using the full height of the tree. > The ma_wr_state struct is modified to add a field which keeps track of the > vacant height and is updated during walks of the tree. This value is then > read in mas_prealloc_calc() when we decide how many nodes to allocate. > > For rebalancing stores, we also need to track the lowest height at which > a node has 1 more entry than the minimum sufficient number of entries. > This is because rebalancing can cause a parent node to become insufficient > which results in further node allocations. In this case, we need to use > the sufficient height as the worst case rather than the vacant height. > > patch 1-2: preparatory patches > patch 3: implement vacant height tracking + update the tests > patch 4: support vacant height tracking for rebalacning writes > patch 5: implement sufficient height tracking > > ================ results ========================= > Bpftrace was used to profile the allocation path for requesting new maple > nodes while running the ./mmap1_processes test from mmtests. The two paths > for allocation are requests for a single node and the bulk allocation path. > The histogram represents the number of calls to these paths and a shows the > distribution of the number of nodes requested for the bulk allocation path. > > > mm-unstable 11/13/24 > @bulk_alloc_req: > [2, 4) 10 |@@@@@@@@@@@@@ | > [4, 8) 38 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| > [8, 16) 19 |@@@@@@@@@@@@@@@@@@@@@@@@@@ | > > > mm-unstable 11/13/24 + this series > @bulk_alloc_req: > [2, 4) 9 |@@@@@@@@@@ | > [4, 8) 43 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| > [8, 16) 15 |@@@@@@@@@@@@@@@@@@ | > > We can see the worst case bulk allocations of [8,16) nodes are reduced after > this series. From running the ./malloc1_threads test case we eliminate almost all bulk allocation requests that fall between 8 and 16 nodes ./malloc1_threads -t 8 -s 100 mm-unstable + this series @bulk_alloc_req: [2, 4) 2 | | [4, 8) 3381 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [8, 16) 2 | | mm-unstable @bulk_alloc_req: [2, 4) 1 | | [4, 8) 1427 |@@@@@@@@@@@@@@@@@@@@@@@@@@ | [8, 16) 2790 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| > > Sidhartha Kumar (5): > maple_tree: convert mas_prealloc_calc() to take in a maple write state > maple_tree: use height and depth consistently > maple_tree: use vacant nodes to reduce worst case allocations > maple_tree: break on convergence in mas_spanning_rebalance() > maple_tree: add sufficient height > > include/linux/maple_tree.h | 4 + > lib/maple_tree.c | 89 +++++++++++++--------- > tools/testing/radix-tree/maple.c | 125 +++++++++++++++++++++++++++++-- > 3 files changed, 176 insertions(+), 42 deletions(-) >