From fecef1f5716f1f239dae3a1cc50298fce0559525 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 3 Dec 2020 12:04:18 -0500 Subject: [PATCH] maple_tree: Speed up reverse allocation walks. Rewrite loops to be quicker by removing special cases. Also skip the next slot if a leaf has a gap that is not large enough. Benchmarks of BENCK_AWALK below: Old: ./maple 13.57s user 0.00s system 99% cpu 13.596 total New: ./maple 11.87s user 0.01s system 99% cpu 11.936 total Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 77 +++++++++++++++++++++++++++--------------------- 1 file changed, 44 insertions(+), 33 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 781432f3b291..2206cd14e1f5 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3891,7 +3891,8 @@ static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) struct maple_node *node = mas_mn(mas); unsigned long *pivots, *gaps = NULL; void **slots; - unsigned long gap, max, min, index; + unsigned long gap = 0; + unsigned long max, min, index; unsigned char offset; if (unlikely(mas_is_err(mas))) @@ -3904,50 +3905,60 @@ static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) pivots = ma_pivots(node, type); slots = ma_slots(node, type); + offset = mas->offset; if (!ma_is_leaf(type)) gaps = ma_gaps(node, type); - min = _mas_safe_pivot(mas, pivots, mas->offset, type) + 1; - do { - max = min - 1; - min = mas_safe_min(mas, pivots, mas->offset); - if (mas->last < min) - continue; - - - if (mas->index > max) { - mas_set_err(mas, -EBUSY); - return false; - } + min = mas_safe_min(mas, pivots, offset); + while (mas->last < min) // Skip out of bounds. + min = mas_safe_min(mas, pivots, --offset); + max = _mas_safe_pivot(mas, pivots, offset, type); + index = mas->index; + while (index <= max) { + gap = 0; if (!ma_is_leaf(type)) - gap = gaps[mas->offset]; - else if (mas_slot(mas, slots, mas->offset)) - continue; // no gap in leaf. - else + gap = gaps[offset]; + else if (!mas_slot(mas, slots, offset)) gap = max - min + 1; - if (size > gap) // gap too small - continue; + if (gap) { + if ((size <= gap) && (size <= mas->last - min + 1)) + break; - if (size > mas->last - min + 1) - continue; + if (ma_is_leaf(type)) { + // Skip the next slot, it cannot be a gap. + if (offset < 2) + goto ascend; - if (ma_is_leaf(type)) { - mas->min = min; - mas->max = min + gap - 1; - return true; + offset -= 2; + max = pivots[offset]; + goto next; + } } - break; - } while (mas->offset--); - if (mas->offset >= mt_slots[type]) { // Overflow, node exhausted. - mas->offset = 0; - goto ascend; + if (!offset) + goto ascend; + + offset--; + max = min - 1; +next: + min = mas_safe_min(mas, pivots, offset); + } + + if (unlikely(index > max)) { + mas_set_err(mas, -EBUSY); + return false; + } + + if (unlikely(ma_is_leaf(type))) { + mas->min = min; + mas->max = min + gap - 1; + return true; } //descend - mas->node = mas_slot(mas, slots, mas->offset); + mas->node = mas_slot(mas, slots, offset); mas->min = min; mas->max = max; mas->offset = mas_data_end(mas); @@ -4165,7 +4176,7 @@ static inline bool mas_rewind_node(struct ma_state *mas) return true; } -void mas_rev_awalk(struct ma_state *mas, unsigned long size) +static void mas_rev_awalk(struct ma_state *mas, unsigned long size) { struct maple_enode *last = NULL; @@ -4177,7 +4188,7 @@ void mas_rev_awalk(struct ma_state *mas, unsigned long size) * no gap found. (return, slot == MAPLE_NODE_SLOTS) * found the gap. (return, slot != MAPLE_NODE_SLOTS) */ - while (!mas_is_err(mas) && !_mas_rev_awalk(mas, size)) { + while (!_mas_rev_awalk(mas, size)) { if (last == mas->node) mas_rewind_node(mas); else -- 2.50.1