maple_tree: simplify mas_wr_node_walk for improved readability
Subsystems (2)
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
@@ -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
Quoted 6 lines · Hao Li
Refactor
mas_wr_node_walkto 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->indexwill fall into.Signed-off-by Hao Li <[email protected]>--- lib/maple_tree.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-)lib/maple_tree.c +8
-10@@ -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); }/*
Quoted 11 lines · Peng Zhang
Quoted 6 lines · Hao Li
Refactor
mas_wr_node_walkto 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->indexwill fall into.Signed-off-by Hao Li <[email protected]>--- lib/maple_tree.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-)lib/maple_tree.c +8
-10@@ -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); }/*
Liam R. Howlett
NAKQuoted 6 lines · Hao Li
Quoted 5 lines · Peng Zhang
Quoted 2 lines · Hao Li
Refactor
mas_wr_node_walkto 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 >= countas 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 formas->indexwithout 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->indexwill 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
Signed-off-by Hao Li <[email protected]>--- lib/maple_tree.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-)lib/maple_tree.c +8
-10@@ -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); }/*
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_walkto 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 >= countas 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 formas->indexwithout 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->indexwill 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_STOREwent 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,
LiamQuoted 40 lines
Quoted 40 lines
Quoted 40 lines
Signed-off-by Hao Li <[email protected]>--- lib/maple_tree.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-)lib/maple_tree.c +8
-10@@ -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); }/*