refine mas_end of mas_mab_cp()
Subsystems (3)
cover refine mas_end of mas_mab_cp()
mas_mab_cp() copy range [mas_start, mas_end] inclusively. For some usage, the mas_end passed could be refined.
Patch 1: if we know the end of a maple_node, we don't need to copy end + 1. Patch 2: this one tries to leverage mt_pivot_count() for optimize the code. Patch 3: the maximum end of a maple_node is mt_pivot_count() instead of
mt_slot_count()
Patch 4: after above cleanup, we are sure mas_end won't exceed mt_pivots[], so
we can remove the check in mas_mab_cp()
Wei Yang (4):
maple_tree: not necessary to copy mas->end + 1
maple_tree: use mt_pivot_count() to replace mt_slot_count() - 1
maple_tree: copy to mt_pivot_count() instead of mt_slot_count()
maple_tree: now we are sure mas_end wouldn't exceed mt_pivots[mt]
lib/maple_tree.c | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-)
Signature · 1 line
2.34.1
PATCH 1/4 maple_tree: not necessary to copy mas->end + 1
mas_mab_cp() copy range [mas_start, mas_end] inclusively, so we just need to copy to mas->end which points to the last valid data in maple node.
--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/maple_tree.c +1 -1
@@ -2099,7 +2099,7 @@ static noinline_for_kasan void mas_store_b_node(struct ma_wr_state *wr_mas, goto b_end;/* Copy end data to the end of the node. */ -mas_mab_cp (mas, slot, mas->end +1 , b_node, ++b_end); +mas_mab_cp (mas, slot, mas->end, b_node, ++b_end); b_node->b_end--;return ;
Signature · 1 line
2.34.1
PATCH 2/4 maple_tree: use mt_pivot_count() to replace mt_slot_count() - 1
In reply to Wei YangWe have (mt_slot_count() - 1 == mt_pivot_count()), except for maple_dense node. Since mas_mab_cp() doesn't apply to maple_dense node, it is fine to use mt_pivot_count() here.
By doing so we can save instruction to decrease 1 from mt_slot_count(). Below is the comparison of generated code.
Current:
.L1595:
lib/maple_tree.c:3165: mas_mab_cp(mas, split + skip, mt_slot_count(mas->node) - 1,
movl %ebx, (%esp) # prephitmp_234, movzbl mt_slots(%edx), %ecx # mt_slots[_90], mt_slots[_90] movl %esi, 4(%esp) # _26, movzbl -23(%ebp), %eax # %sfp, movzbl -21(%ebp), %edx # %sfp, split decb %cl # tmp258 movzbl %cl, %ecx # tmp258, tmp260 addb %al, %dl #, split movl -16(%ebp), %eax # %sfp, movzbl %dl, %edx # tmp261, tmp262 call mas_mab_cp #
After applying this patch:
.L1595:
lib/maple_tree.c:3165: mas_mab_cp(mas, split + skip, mt_pivot_count(mas->node),
movl %ebx, (%esp) # prephitmp_231, movzbl mt_pivots(%edx), %ecx # mt_pivots[_87], mt_pivots[_87] movl %esi, 4(%esp) # _26, movzbl -23(%ebp), %eax # %sfp, movzbl -21(%ebp), %edx # %sfp, split addb %al, %dl #, split movl -16(%ebp), %eax # %sfp, movzbl %dl, %edx # tmp256, tmp257 call mas_mab_cp #
--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/maple_tree.c +1 -1
@@ -3167,7 +3167,7 @@ static inline void mast_fill_bnode(struct maple_subtree_state *mast, cp = false;if (cp) -mas_mab_cp (mas, split + skip,mt_slot_count (mas->node) -1 , +mas_mab_cp (mas, split + skip,mt_pivot_count (mas->node), mast->bn, mast->bn->b_end); mast->bn->b_end--;
Signature · 1 line
2.34.1
PATCH 3/4 maple_tree: copy to mt_pivot_count() instead of mt_slot_count()
In reply to Wei Yangmas_mab_cp() copy a maple_node's range inclusively, and the maximum valid data index is (mt_slot_count() - 1) instead of mt_slot_count().
But if using (mt_slot_count() - 1) directly, it would have more instructions. The good news is we have defined mt_pivot_count() == (mt_slot_count - 1), except for maple_dense node. And mas_mab_cp() doesn't handle maple_dense node. So it is safe to use it.
By doing so have almost identical generated code:
Current:
lib/maple_tree.c:2209: mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node),
movl %esi, (%esp) # _135, movl -88(%ebp), %eax # %sfp, _137 movzbl mt_slots(%edx), %ecx # mt_slots[_142], mt_slots[_142] xorl %edx, %edx # movl %eax, 4(%esp) # _137, movl %ebx, %eax # _138, call mas_mab_cp #
After applying this patch:
lib/maple_tree.c:2209: mas_mab_cp(mast->orig_r, 0, mt_pivot_count(mast->orig_r->node),
movl %esi, (%esp) # _135, movl -88(%ebp), %eax # %sfp, _137 movzbl mt_pivots(%edx), %ecx # mt_pivots[_142], mt_pivots[_142] xorl %edx, %edx # movl %eax, 4(%esp) # _137, movl %ebx, %eax # _138, call mas_mab_cp #
The difference is we access mt_pivots to get ecx instead of mt_slots, which doesn't expect performance difference.
--- lib/maple_tree.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)
lib/maple_tree.c +3 -3
@@ -2211,7 +2211,7 @@ static inline void mast_rebalance_next(struct maple_subtree_state *mast) {unsigned char b_end = mast->bn->b_end; -mas_mab_cp (mast->orig_r,0 ,mt_slot_count (mast->orig_r->node), +mas_mab_cp (mast->orig_r,0 ,mt_pivot_count (mast->orig_r->node), mast->bn, b_end); mast->orig_r->last = mast->orig_r->max; }
@@ -2692,7 +2692,7 @@ static inline void mast_combine_cp_right(struct maple_subtree_state *mast)return ;mas_mab_cp (mast->orig_r, mast->orig_r->offset +1 , -mt_slot_count (mast->orig_r->node), mast->bn, +mt_pivot_count (mast->orig_r->node), mast->bn, mast->bn->b_end); mast->orig_r->last = mast->orig_r->max; }
@@ -2963,7 +2963,7 @@ static inline int mas_rebalance(struct ma_state *mas, l_mas = r_mas = *mas;if (mas_next_sibling (&r_mas)) { -mas_mab_cp (&r_mas,0 ,mt_slot_count (r_mas.node), b_node, b_end); +mas_mab_cp (&r_mas,0 ,mt_pivot_count (r_mas.node), b_node, b_end); r_mas.last = r_mas.index = r_mas.max; }else {mas_prev_sibling (&l_mas);
Signature · 1 line
2.34.1
PATCH 4/4 maple_tree: now we are sure mas_end wouldn't exceed mt_pivots[mt]
In reply to Wei YangNow all the cases of mas_mab_cp() is called with mas_end at most equals mt_pivots[mt]. So we can get piv_end == mas_end.
--- lib/maple_tree.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-)
lib/maple_tree.c +2 -3
@@ -1907,11 +1907,11 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start,void __rcu **slots;unsigned long *pivots, *gaps;int i = mas_start, j = mab_start; -unsigned char piv_end; node =mas_mn (mas); mt =mte_node_type (mas->node); pivots =ma_pivots (node, mt); +if (!i) { b_node->pivot[j] = pivots[i++];if (unlikely (i > mas_end))
@@ -1919,8 +1919,7 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, j++; } - piv_end =min (mas_end, mt_pivots[mt]); -for (; i < piv_end; i++, j++) { +for (; i < mas_end; i++, j++) { b_node->pivot[j] = pivots[i];if (unlikely (!b_node->pivot[j])) goto complete;
Signature · 1 line
2.34.1
Quoted 4 lines · Wei Yang
mas_mab_cp()copy range [mas_start,mas_end] inclusively. For some usage, themas_endpassed could be refined.Patch 1: if we know the end of a
maple_node, we don't need to copy end + 1.
I haven't looked too hard at patch 1, I am currently away.
Quoted 5 lines
Patch 2: this one tries to leverage
mt_pivot_count()for optimize the code. Patch 3: the maximum end of amaple_nodeismt_pivot_count()instead ofmt_slot_count()Patch 4: after above cleanup, we are sure
mas_endwon't exceed mt_pivots[], so
we can remove the check inmas_mab_cp()
You are changing the generic code to only work for the current node types and I don't want to do that. I wrote it to be more generic, so now we are introducing the requirement that slots are one larger than pivots.
Again, I haven't looked too closely at this but it seems like you are making the code depend on the array differences staying constant.
Quoted 13 lines
Wei Yang (4):
maple_tree: not necessary to copymas->end+ 1
maple_tree: usemt_pivot_count()to replacemt_slot_count()- 1
maple_tree: copy tomt_pivot_count()instead ofmt_slot_count()
maple_tree: now we are suremas_endwouldn't exceed mt_pivots[mt]lib/maple_tree.c | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-)Signature · 1 line
2.34.1