Skip to contentSkip to conversation

maple_tree: simplify mas_wr_node_walk for improved readability

PATCH NAK Hao Li 3 participants 5 messages Aug 23, 2024 – Aug 26, 2024

Subsystems (2)
lore
Share & tools
lore

Hao Li

author
#0 lore raw

PATCH v2 1/1 maple_tree: simplify mas_wr_node_walk for improved readability

Refactor mas_wr_node_walk to make the code more clear and easier to understand. The main changes are:

1. Replace the forward-iterating loop with a backward-iterating loop. This simplifies the logic for determining the correct range containing mas->index.

2. Eliminate the ternary operator.

The new implementation maintains the same functionality as before, but with improved readability. The performance characteristics remain essentially the same, as we cannot predict which interval mas->index will fall into.

---
 lib/maple_tree.c | 18 ++++++++----------
 1 file changed, 8 insertions(+), 10 deletions(-)
lib/maple_tree.c +8 -10
index fe1b01b29..0b3eb55d8 100644
@@ -2203,7 +2203,7 @@ static inline void mas_node_or_none(struct ma_state *mas,
 static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
 {
 	struct ma_state *mas = wr_mas->mas;
-	unsigned char count, offset;
+	int idx;
 
 	if (unlikely(ma_is_dense(wr_mas->type))) {
 		wr_mas->r_max = wr_mas->r_min = mas->index;
@@ -2213,16 +2213,14 @@ static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
 
 	wr_mas->node = mas_mn(wr_mas->mas);
 	wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type);
-	count = mas->end = ma_data_end(wr_mas->node, wr_mas->type,
+	mas->end = ma_data_end(wr_mas->node, wr_mas->type,
 				       wr_mas->pivots, mas->max);
-	offset = mas->offset;
-
-	while (offset < count && mas->index > wr_mas->pivots[offset])
-		offset++;
-
-	wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max;
-	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset);
-	wr_mas->offset_end = mas->offset = offset;
+	wr_mas->r_max = mas->max;
+	idx = mas->end - 1;
+	while (idx >= mas->offset && wr_mas->pivots[idx] >= mas->index)
+		wr_mas->r_max = wr_mas->pivots[idx--];
+	wr_mas->offset_end = mas->offset = idx + 1;
+	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, mas->offset);
 }
 
 /*
Signature · 1 line
2.21.0
#1 lore raw
Quoted 6 lines · Hao Li

Refactor mas_wr_node_walk to make the code more clear and easier to understand. The main changes are:

1. Replace the forward-iterating loop with a backward-iterating loop. This simplifies the logic for determining the correct range containing mas->index.

I don't think iterating in reverse is a good idea, it makes the code different from everywhere else.

Quoted 50 lines

2. Eliminate the ternary operator.

The new implementation maintains the same functionality as before, but with improved readability. The performance characteristics remain essentially the same, as we cannot predict which interval mas->index will fall into.

---
  lib/maple_tree.c | 18 ++++++++----------
  1 file changed, 8 insertions(+), 10 deletions(-)
lib/maple_tree.c +8 -10
index fe1b01b29..0b3eb55d8 100644
@@ -2203,7 +2203,7 @@ static inline void mas_node_or_none(struct ma_state *mas,
  static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
  {
  	struct ma_state *mas = wr_mas->mas;
-	unsigned char count, offset;
+	int idx;
 
  	if (unlikely(ma_is_dense(wr_mas->type))) {
  		wr_mas->r_max = wr_mas->r_min = mas->index;
@@ -2213,16 +2213,14 @@ static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
 
  	wr_mas->node = mas_mn(wr_mas->mas);
  	wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type);
-	count = mas->end = ma_data_end(wr_mas->node, wr_mas->type,
+	mas->end = ma_data_end(wr_mas->node, wr_mas->type,
  				       wr_mas->pivots, mas->max);
-	offset = mas->offset;
-
-	while (offset < count && mas->index > wr_mas->pivots[offset])
-		offset++;
-
-	wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max;
-	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset);
-	wr_mas->offset_end = mas->offset = offset;
+	wr_mas->r_max = mas->max;
+	idx = mas->end - 1;
+	while (idx >= mas->offset && wr_mas->pivots[idx] >= mas->index)
+		wr_mas->r_max = wr_mas->pivots[idx--];
+	wr_mas->offset_end = mas->offset = idx + 1;
+	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, mas->offset);
  }
 
  /*
author
#2 lore raw
Quoted 11 lines · Peng Zhang
Quoted 6 lines · Hao Li

Refactor mas_wr_node_walk to make the code more clear and easier to understand. The main changes are:

1. Replace the forward-iterating loop with a backward-iterating loop. This simplifies the logic for determining the correct range containing mas->index.

I don't think iterating in reverse is a good idea, it makes the code different from everywhere else.

I understand your concern about consistency in iteration direction.

While the original code correctly handled all cases, the process wasn't as definitive or clear.

The new approach unifies the logic by eliminating the need to treat offset >= count as a special case. This results in a more straightforward and consistent flow throughout the function, which provides a more deterministic and easy-to-follow path through the logic. We can more clearly see and understand how we're determining the correct range for mas->index without having to mentally parse complex conditional logic.

Quoted 47 lines
Quoted 47 lines

2. Eliminate the ternary operator.

The new implementation maintains the same functionality as before, but with improved readability. The performance characteristics remain essentially the same, as we cannot predict which interval mas->index will fall into.

---
  lib/maple_tree.c | 18 ++++++++----------
  1 file changed, 8 insertions(+), 10 deletions(-)
lib/maple_tree.c +8 -10
index fe1b01b29..0b3eb55d8 100644
@@ -2203,7 +2203,7 @@ static inline void mas_node_or_none(struct ma_state *mas,
  static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
  {
  	struct ma_state *mas = wr_mas->mas;
-	unsigned char count, offset;
+	int idx;
  	if (unlikely(ma_is_dense(wr_mas->type))) {
  		wr_mas->r_max = wr_mas->r_min = mas->index;
@@ -2213,16 +2213,14 @@ static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
  	wr_mas->node = mas_mn(wr_mas->mas);
  	wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type);
-	count = mas->end = ma_data_end(wr_mas->node, wr_mas->type,
+	mas->end = ma_data_end(wr_mas->node, wr_mas->type,
  				       wr_mas->pivots, mas->max);
-	offset = mas->offset;
-
-	while (offset < count && mas->index > wr_mas->pivots[offset])
-		offset++;
-
-	wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max;
-	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset);
-	wr_mas->offset_end = mas->offset = offset;
+	wr_mas->r_max = mas->max;
+	idx = mas->end - 1;
+	while (idx >= mas->offset && wr_mas->pivots[idx] >= mas->index)
+		wr_mas->r_max = wr_mas->pivots[idx--];
+	wr_mas->offset_end = mas->offset = idx + 1;
+	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, mas->offset);
  }
  /*
#3 lore raw
Quoted 6 lines · Hao Li
Quoted 5 lines · Peng Zhang
Quoted 2 lines · Hao Li

Refactor mas_wr_node_walk to make the code more clear and easier to understand. The main changes are:

Thank you for your patch, but I don't think this is a good change.

NACK

Quoted 7 lines
Quoted 6 lines
Quoted 4 lines

1. Replace the forward-iterating loop with a backward-iterating loop. This simplifies the logic for determining the correct range containing mas->index.

I don't think iterating in reverse is a good idea, it makes the code different from everywhere else.

I also agree with Peng that having one loop go a different way seems like it's asking for trouble.

Quoted 5 lines

I understand your concern about consistency in iteration direction.

While the original code correctly handled all cases, the process wasn't as definitive or clear.

Quoted 10 lines

The new approach unifies the logic by eliminating the need to treat offset >= count as a special case. This results in a more straightforward and consistent flow throughout the function, which provides a more deterministic and easy-to-follow path through the logic. We can more clearly see and understand how we're determining the correct range for mas->index without having to mentally parse complex conditional logic.

Quoted 2 lines
Quoted 2 lines

2. Eliminate the ternary operator.

This is not more clear as one may miss that the loop may not execute at all. So you eliminated the ternary operator, but have all but hidden the assignment. I would rather an if/else for verbosity, but not enough to reject the patch that added it in the first place.

You also replaced the "unsigned char count" with an "int idx", for some reason. It seems like you've rewritten it so it's more clear for you.

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

The new implementation maintains the same functionality as before, but with improved readability. The performance characteristics remain essentially the same, as we cannot predict which interval mas->index will fall into.

We do favour the left side of the tree to increase data density, so it is more likely to find what we are looking for in the lower slots (but not by a whole lot right now). There will probably be more of this favouring in the future - minimum span for internal nodes.

BENCH_NODE_STORE went from 8.79, 8.85, 8.79 seconds to 9.68, 9.74, 9.72. This change is slower. It may be because you removed all the temporary variables that avoided dereferencing, so the compiler can't be as smart about optimisation. I'm not really interested in finding out why it's slower as I don't think this is a good change on the grounds of other reasons stated as well.

Thanks,
Liam

Quoted 40 lines
Quoted 40 lines
Quoted 40 lines
---
  lib/maple_tree.c | 18 ++++++++----------
  1 file changed, 8 insertions(+), 10 deletions(-)
lib/maple_tree.c +8 -10
index fe1b01b29..0b3eb55d8 100644
@@ -2203,7 +2203,7 @@ static inline void mas_node_or_none(struct ma_state *mas,
  static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
  {
  	struct ma_state *mas = wr_mas->mas;
-	unsigned char count, offset;
+	int idx;
  	if (unlikely(ma_is_dense(wr_mas->type))) {
  		wr_mas->r_max = wr_mas->r_min = mas->index;
@@ -2213,16 +2213,14 @@ static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
  	wr_mas->node = mas_mn(wr_mas->mas);
  	wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type);
-	count = mas->end = ma_data_end(wr_mas->node, wr_mas->type,
+	mas->end = ma_data_end(wr_mas->node, wr_mas->type,
  				       wr_mas->pivots, mas->max);
-	offset = mas->offset;
-
-	while (offset < count && mas->index > wr_mas->pivots[offset])
-		offset++;
-
-	wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max;
-	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset);
-	wr_mas->offset_end = mas->offset = offset;
+	wr_mas->r_max = mas->max;
+	idx = mas->end - 1;
+	while (idx >= mas->offset && wr_mas->pivots[idx] >= mas->index)
+		wr_mas->r_max = wr_mas->pivots[idx--];
+	wr_mas->offset_end = mas->offset = idx + 1;
+	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, mas->offset);
  }
  /*
author
#4 lore raw
Quoted 9 lines · Liam R. Howlett
Quoted 6 lines · Hao Li
Quoted 5 lines · Peng Zhang
Quoted 2 lines · Hao Li

Refactor mas_wr_node_walk to make the code more clear and easier to understand. The main changes are:

Thank you for your patch, but I don't think this is a good change.

Thank you for taking the time to review my patch and provide detailed feedback.

Quoted 28 lines

NACK

Quoted 7 lines
Quoted 6 lines
Quoted 4 lines

1. Replace the forward-iterating loop with a backward-iterating loop. This simplifies the logic for determining the correct range containing mas->index.

I don't think iterating in reverse is a good idea, it makes the code different from everywhere else.

I also agree with Peng that having one loop go a different way seems like it's asking for trouble.

Quoted 14 lines

I understand your concern about consistency in iteration direction.

While the original code correctly handled all cases, the process wasn't as definitive or clear.

The new approach unifies the logic by eliminating the need to treat offset >= count as a special case. This results in a more straightforward and consistent flow throughout the function, which provides a more deterministic and easy-to-follow path through the logic. We can more clearly see and understand how we're determining the correct range for mas->index without having to mentally parse complex conditional logic.

Quoted 1 line
Quoted 1 line
Quoted 6 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line

2. Eliminate the ternary operator.

This is not more clear as one may miss that the loop may not execute at all. So you eliminated the ternary operator, but have all but hidden the assignment. I would rather an if/else for verbosity, but not enough to reject the patch that added it in the first place.

Got it!

Quoted 10 lines

You also replaced the "unsigned char count" with an "int idx", for some reason. It seems like you've rewritten it so it's more clear for you.

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

The new implementation maintains the same functionality as before, but with improved readability. The performance characteristics remain essentially the same, as we cannot predict which interval mas->index will fall into.

Quoted 4 lines

We do favour the left side of the tree to increase data density, so it is more likely to find what we are looking for in the lower slots (but not by a whole lot right now). There will probably be more of this favouring in the future - minimum span for internal nodes.

Got it.

Quoted 7 lines

BENCH_NODE_STORE went from 8.79, 8.85, 8.79 seconds to 9.68, 9.74, 9.72. This change is slower. It may be because you removed all the temporary variables that avoided dereferencing, so the compiler can't be as smart about optimisation. I'm not really interested in finding out why it's slower as I don't think this is a good change on the grounds of other reasons stated as well.

Thanks for this benchmarking, I didn't even realize this performance regression.

Regards,
Hao Li

Quoted 44 lines

Thanks,
Liam

Quoted 40 lines
Quoted 40 lines
Quoted 40 lines
---
  lib/maple_tree.c | 18 ++++++++----------
  1 file changed, 8 insertions(+), 10 deletions(-)
lib/maple_tree.c +8 -10
index fe1b01b29..0b3eb55d8 100644
@@ -2203,7 +2203,7 @@ static inline void mas_node_or_none(struct ma_state *mas,
  static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
  {
  	struct ma_state *mas = wr_mas->mas;
-	unsigned char count, offset;
+	int idx;
  	if (unlikely(ma_is_dense(wr_mas->type))) {
  		wr_mas->r_max = wr_mas->r_min = mas->index;
@@ -2213,16 +2213,14 @@ static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
  	wr_mas->node = mas_mn(wr_mas->mas);
  	wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type);
-	count = mas->end = ma_data_end(wr_mas->node, wr_mas->type,
+	mas->end = ma_data_end(wr_mas->node, wr_mas->type,
  				       wr_mas->pivots, mas->max);
-	offset = mas->offset;
-
-	while (offset < count && mas->index > wr_mas->pivots[offset])
-		offset++;
-
-	wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max;
-	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset);
-	wr_mas->offset_end = mas->offset = offset;
+	wr_mas->r_max = mas->max;
+	idx = mas->end - 1;
+	while (idx >= mas->offset && wr_mas->pivots[idx] >= mas->index)
+		wr_mas->r_max = wr_mas->pivots[idx--];
+	wr_mas->offset_end = mas->offset = idx + 1;
+	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, mas->offset);
  }
  /*