Skip to contentSkip to conversation

refine mas_mab_cp()

PATCH Applied Wei Yang 2 participants 5 messages Sep 11, 2024

Subsystems (3)
lore
Share & tools
lore

Wei Yang

author
#0 lore raw

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
author
#1 lore raw

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
index 76b68568f77b..6fd62b7ef240 100644
@@ -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
Reviewed-by on v1 1/2
#2 lore raw

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 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.

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.

Quoted 22 lines
---
 lib/maple_tree.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
lib/maple_tree.c +1 -2
index 76b68568f77b..6fd62b7ef240 100644
@@ -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
author
#3 lore raw

PATCH 2/2 maple_tree: goto complete directly on a pivot of 0

In reply to 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.

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
index 6fd62b7ef240..f7bb3f686548 100644
@@ -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
Reviewed-by on v1 2/2
#4 lore raw

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 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.

Quoted 20 lines
---
 lib/maple_tree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/maple_tree.c +1 -1
index 6fd62b7ef240..f7bb3f686548 100644
@@ -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