From 989324e610d5b3c21f88387d14c7f0d16534eb0c Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 1 Dec 2020 11:04:49 -0500 Subject: [PATCH] maple_tree: Optimize mas_leaf_max_gap() by skipping slots after a gap. Two gaps cannot happen in a row, so don't bother checking the next slot if there exists a gap. Also, remove slot[0], slot[1], and slot[max] by checking them first. This allows for a more optimal loop Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 46 ++++++++++++++++++++++++++++++---------------- 1 file changed, 30 insertions(+), 16 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 3dc2ccc5dcf5..57a16eb464e9 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1078,14 +1078,16 @@ decrement: static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) { enum maple_type mt = mte_node_type(mas->node); - unsigned long pstart, pend, gap = 0, max_gap = 0; + unsigned long pstart, gap, max_gap; struct maple_node *mn = mas_mn(mas); unsigned long *pivots = ma_pivots(mn, mt); void **slots = ma_slots(mn, mt); unsigned char i; unsigned char max_piv; + max_gap = 0; if (unlikely(ma_is_dense(mt))) { + gap = 0; for (i = 0; i < mt_slots[mt]; i++) { if (slots[i]) { if (gap > max_gap) @@ -1101,28 +1103,40 @@ static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) } // Removing the pivot overflow optimizes the loop below. + // Check the first implied pivot. + i = 2; + if (!slots[0]) { + max_gap = pivots[0] - mas->min + 1; + } else if (!slots[1]) { + // Checking the first slot remove the !pstart && mas->min check + // below. + i = 3; + max_gap = pivots[1] - pivots[0]; + } + + // Check end implied pivot which can only be a gap on the right most + // node. max_piv = mt_pivots[mt] - 1; - if (pivots[max_piv] && pivots[max_piv] != mas->max && - !slots[max_piv + 1]) - max_gap = mas->max - pivots[max_piv]; + if (unlikely(mas->max == ULONG_MAX) && !slots[max_piv + 1] && + pivots[max_piv] && pivots[max_piv] != mas->max) { + gap = mas->max - pivots[max_piv]; + if (gap > max_gap) + max_gap = gap; + } - pstart = mas->min; - for (i = 0; i < mt_pivots[mt]; i++) { - pend = pivots[i]; - if (!pend && i) - pend = mas->max; + for (; i <= max_piv; i++) { + if (slots[i]) // data == no gap. + continue; - if (slots[i]) - goto next; + pstart = pivots[i - 1]; + if (!pstart || pstart == mas->max) // end cannot be a gap, so beyond data. + break; - gap = pend - pstart + 1; + gap = pivots[i] - pstart; if (gap > max_gap) max_gap = gap; -next: - if (pend >= mas->max) - break; - pstart = pend + 1; + i++; // There cannot be two gaps in a row. } return max_gap; } -- 2.50.1