refine mas_mab_cp()
Subsystems (3)
cover refine mas_mab_cp()
By analysis the code, one condition check could be removed and one case would hit a redundant assignment.
Just remove it.
Wei Yang (2):
maple_tree: i is always less than or equal to mas_end
maple_tree: goto complete directly on a pivot of 0
lib/maple_tree.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-)
Signature · 1 line
2.34.1
PATCH 1/2 maple_tree: i is always less than or equal to mas_end
mas_mab_cp() copy range [mas_start, mas_end] inclusively from a maple_node to maple_big_node. This implies mas_start <= mas_end.
Based on the relationship of mas_start and mas_end, we can have the following four cases:
| mas_start == mas_end | mas_start < mas_end ---------------+----------------------+---------------------- mas_start == 0 | 1 | 2 ---------------+----------------------+---------------------- mas_start != 0 | 3 | 4
We can see in all these four cases, i is always less than or equal to mas_end after finish the loop:
Case 1: After assign pivot 0, i is set to 1, which is bigger than
mas_end 0. So it jumps to complete and skip the check.
Case 2: After assign pivot 0, i is set to 1.
∵ (mas_start < mas_end) && (mas_start == 0)
==> (1 <= mas_end)
∵ (i == 1) && (1 <= mas_end)
==> (i <= mas_end)
∴ Before loop, we have (i <= mas_end). And we still hold this
if it skips the loop. For example, (i == mas_end).
Now let's see what happens in the loop:
∵ piv_end = min(mas_end, mt_pivots[mt])
==> (piv_end <= mas_end)
∵ loop condition is (i < piv_end)
==> (i <= piv_end) on finish the loop both normally or break
∵ (i <= piv_end) && (piv_end <= mas_end)
==> (i <= mas_end)
∴ After loop, we still get (i <= mas_end) in this case Case 3: This case would skip both if clause and loop. So when it comes
to the check, i is still mas_start which equals to mas_end.
Case 4: This case would skip the if clause.
∵ (mas_start < mas_end) && (i == mas_start)
==> (i < mas_end)
∴ Before loop, we have (i < mas_end).
The loop process is similar with Case 2, so we get the same result.
Now we can conclude in all cases, we get (i <= mas_end) when doing check. Then it is not necessary to do the check.
--- lib/maple_tree.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)
lib/maple_tree.c +1 -2
@@ -1948,8 +1948,7 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, goto complete; } -if (likely (i <= mas_end)) - b_node->pivot[j] =mas_safe_pivot (mas, pivots, i, mt); + b_node->pivot[j] =mas_safe_pivot (mas, pivots, i, mt); complete: b_node->b_end = ++j;
Signature · 1 line
2.34.1
Re: [PATCH 1/2] maple_tree: i is always less than or equal to mas_end
Quoted 42 lines · Wei Yang
mas_mab_cp()copy range [mas_start,mas_end] inclusively from amaple_nodetomaple_big_node. This impliesmas_start<=mas_end.Based on the relationship of
mas_startandmas_end, we can have the following four cases:| mas_start == mas_end | mas_start < mas_end ---------------+----------------------+---------------------- mas_start == 0 | 1 | 2 ---------------+----------------------+---------------------- mas_start != 0 | 3 | 4We can see in all these four cases, i is always less than or equal to
mas_endafter finish the loop:Case 1: After assign pivot 0, i is set to 1, which is bigger than
mas_end0. So it jumps to complete and skip the check.
Case 2: After assign pivot 0, i is set to 1.∵ (mas_start < mas_end) && (mas_start == 0) ==> (1 <= mas_end) ∵ (i == 1) && (1 <= mas_end) ==> (i <= mas_end) ∴ Before loop, we have (i <= mas_end). And we still hold this if it skips the loop. For example, (i == mas_end). Now let's see what happens in the loop: ∵ piv_end = min(mas_end, mt_pivots[mt]) ==> (piv_end <= mas_end) ∵ loop condition is (i < piv_end) ==> (i <= piv_end) on finish the loop both normally or break ∵ (i <= piv_end) && (piv_end <= mas_end) ==> (i <= mas_end) ∴ After loop, we still get (i <= mas_end) in this caseCase 3: This case would skip both if clause and loop. So when it comes
to the check, i is stillmas_startwhich equals tomas_end.
Case 4: This case would skip the if clause.
∵ (mas_start<mas_end) && (i ==mas_start)
==> (i <mas_end)
∴ Before loop, we have (i <mas_end).
The loop process is similar with Case 2, so we get the same result.
Quoted 4 lines
Now we can conclude in all cases, we get (i <=
mas_end) when doing check. Then it is not necessary to do the check.Signed-off-by Wei Yang <[email protected]>
Quoted 22 lines
--- lib/maple_tree.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)lib/maple_tree.c +1
-2@@ -1948,8 +1948,7 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, goto complete; } -if (likely (i <= mas_end)) - b_node->pivot[j] =mas_safe_pivot (mas, pivots, i, mt); + b_node->pivot[j] =mas_safe_pivot (mas, pivots, i, mt); complete: b_node->b_end = ++j;Signature · 1 line
2.34.1
PATCH 2/2 maple_tree: goto complete directly on a pivot of 0
In reply to Wei YangWhen we break the loop after assigning a pivot, the index i/j is not changed. Then the following code assign pivot, which means we do the assignment with same i/j by mas_safe_pivot.
Since the loop condition is (i < piv_end), from which we can get i is less than mt_pivots[mt]. It implies mas_safe_pivot() return pivot[i] which is the same value we get in loop.
Now we can conclude it does a redundant assignment on a pivot of 0. Let's just go to complete to avoid it.
--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/maple_tree.c +1 -1
@@ -1942,7 +1942,7 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start,for (; i < piv_end; i++, j++) { b_node->pivot[j] = pivots[i];if (unlikely (!b_node->pivot[j])) -break ; + goto complete;if (unlikely (mas->max == b_node->pivot[j])) goto complete;
Signature · 1 line
2.34.1
Re: [PATCH 2/2] maple_tree: goto complete directly on a pivot of 0
Quoted 4 lines · Wei Yang
When we break the loop after assigning a pivot, the index i/j is not changed. Then the following code assign pivot, which means we do the assignment with same i/j by
mas_safe_pivot.
Quoted 8 lines
Since the loop condition is (i <
piv_end), from which we can get i is less than mt_pivots[mt]. It impliesmas_safe_pivot()return pivot[i] which is the same value we get in loop.Now we can conclude it does a redundant assignment on a pivot of 0. Let's just go to complete to avoid it.
Signed-off-by Wei Yang <[email protected]>
Quoted 20 lines
--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/maple_tree.c +1
-1@@ -1942,7 +1942,7 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start,for (; i < piv_end; i++, j++) { b_node->pivot[j] = pivots[i];if (unlikely (!b_node->pivot[j])) -break ; + goto complete;if (unlikely (mas->max == b_node->pivot[j])) goto complete;Signature · 1 line
2.34.1