mm/mmap.c: refine data locality of find_vma_prev
Subsystems (2)
PATCH 1/1 mm/mmap.c: refine data locality of find_vma_prev
When addr is out of the range of the whole rb_tree, pprev will points to the biggest node. find_vma_prev gets is by going through the right most node of the tree.
Since only the last node is the one it is looking for, it is not necessary to assign pprev to those middle stage nodes. By assigning pprev to the last node directly, it tries to improve the function locality a little.
--- mm/mmap.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-)
mm/mmap.c +3 -4
@@ -2271,11 +2271,10 @@ find_vma_prev(struct mm_struct *mm, unsigned long addr, *pprev = vma->vm_prev; }else {struct rb_node *rb_node = mm->mm_rb.rb_node; - *pprev =NULL ; -while (rb_node) { - *pprev = rb_entry(rb_node, struct vm_area_struct, vm_rb); +while (rb_node && rb_node->rb_right) rb_node = rb_node->rb_right; - } + *pprev = rb_node ?NULL + : rb_entry(rb_node, struct vm_area_struct, vm_rb); }return vma; }
Signature · 1 line
2.17.1
Quoted 2 lines · Wei Yang
When addr is out of the range of the whole
rb_tree, pprev will points to the biggest node.find_vma_prevgets is by going through the right most
s/biggest/last/ ? or right-most?
Quoted 6 lines
node of the tree.
Since only the last node is the one it is looking for, it is not necessary to assign pprev to those middle stage nodes. By assigning pprev to the last node directly, it tries to improve the function locality a little.
In the end, it will always write to the cacheline of pprev. The caller has most likely have it on stack, so it's already hot, and there's no other CPU stealing it. So I don't understand where the improved locality comes from. The compiler can also optimize the patched code so the assembly is identical to the previous code, or vice versa. Did you check for differences?
The previous code is somewhat more obvious to me, so unless I'm missing something, readability and less churn suggests to not change.
Quoted 25 lines
Signed-off-by Wei Yang <[email protected]>--- mm/mmap.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-)mm/mmap.c +3
-4@@ -2271,11 +2271,10 @@ find_vma_prev(struct mm_struct *mm, unsigned long addr, *pprev = vma->vm_prev; }else {struct rb_node *rb_node = mm->mm_rb.rb_node; - *pprev =NULL ; -while (rb_node) { - *pprev = rb_entry(rb_node, struct vm_area_struct, vm_rb); +while (rb_node && rb_node->rb_right) rb_node = rb_node->rb_right; - } + *pprev = rb_node ?NULL + : rb_entry(rb_node, struct vm_area_struct, vm_rb); }return vma; }
Quoted 13 lines · Vlastimil Babka
Quoted 2 lines · Wei Yang
When addr is out of the range of the whole
rb_tree, pprev will points to the biggest node.find_vma_prevgets is by going through the right mosts/biggest/last/ ? or right-most?
Quoted 6 lines
node of the tree.
Since only the last node is the one it is looking for, it is not necessary to assign pprev to those middle stage nodes. By assigning pprev to the last node directly, it tries to improve the function locality a little.
Quoted 5 lines
In the end, it will always write to the cacheline of pprev. The caller has most likely have it on stack, so it's already hot, and there's no other CPU stealing it. So I don't understand where the improved locality comes from. The compiler can also optimize the patched code so the assembly is identical to the previous code, or vice versa. Did you check for differences?
Vlastimil
Thanks for your comment.
I believe you get a point. I may not use the word locality. This patch tries to reduce some unnecessary assignment of pprev.
Original code would assign the value on each node during iteration, this is what I want to reduce.
The generated code looks different from my side. Would you mind sharing me how you compare the generated code?
Quoted 29 lines
The previous code is somewhat more obvious to me, so unless I'm missing something, readability and less churn suggests to not change.
Quoted 25 lines
Signed-off-by Wei Yang <[email protected]>--- mm/mmap.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-)mm/mmap.c +3
-4@@ -2271,11 +2271,10 @@ find_vma_prev(struct mm_struct *mm, unsigned long addr, *pprev = vma->vm_prev; }else {struct rb_node *rb_node = mm->mm_rb.rb_node; - *pprev =NULL ; -while (rb_node) { - *pprev = rb_entry(rb_node, struct vm_area_struct, vm_rb); +while (rb_node && rb_node->rb_right) rb_node = rb_node->rb_right; - } + *pprev = rb_node ?NULL + : rb_entry(rb_node, struct vm_area_struct, vm_rb); }return vma; }
Signature · 2 lines
Wei Yang Help you, Help me
Quoted 22 lines · Wei Yang
Quoted 13 lines · Vlastimil Babka
Quoted 2 lines · Wei Yang
When addr is out of the range of the whole
rb_tree, pprev will points to the biggest node.find_vma_prevgets is by going through the right mosts/biggest/last/ ? or right-most?
Quoted 6 lines
node of the tree.
Since only the last node is the one it is looking for, it is not necessary to assign pprev to those middle stage nodes. By assigning pprev to the last node directly, it tries to improve the function locality a little.
Quoted 5 lines
In the end, it will always write to the cacheline of pprev. The caller has most likely have it on stack, so it's already hot, and there's no other CPU stealing it. So I don't understand where the improved locality comes from. The compiler can also optimize the patched code so the assembly is identical to the previous code, or vice versa. Did you check for differences?
Vlastimil
Quoted 7 lines
Thanks for your comment.
I believe you get a point. I may not use the word locality. This patch tries to reduce some unnecessary assignment of pprev.
Original code would assign the value on each node during iteration, this is what I want to reduce.
Is there any measurable difference (on micro benchmarks or regular workloads)?
Signature · 2 lines
Michal Hocko SUSE Labs
Quoted 25 lines · Michal Hocko
Quoted 24 lines · Wei Yang
Quoted 13 lines · Vlastimil Babka
Quoted 2 lines · Wei Yang
When addr is out of the range of the whole
rb_tree, pprev will points to the biggest node.find_vma_prevgets is by going through the right mosts/biggest/last/ ? or right-most?
Quoted 6 lines
node of the tree.
Since only the last node is the one it is looking for, it is not necessary to assign pprev to those middle stage nodes. By assigning pprev to the last node directly, it tries to improve the function locality a little.
Quoted 5 lines
In the end, it will always write to the cacheline of pprev. The caller has most likely have it on stack, so it's already hot, and there's no other CPU stealing it. So I don't understand where the improved locality comes from. The compiler can also optimize the patched code so the assembly is identical to the previous code, or vice versa. Did you check for differences?
Vlastimil
Thanks for your comment.
Quoted 8 lines
Quoted 5 lines
I believe you get a point. I may not use the word locality. This patch tries to reduce some unnecessary assignment of pprev.
Original code would assign the value on each node during iteration, this is what I want to reduce.
Is there any measurable difference (on micro benchmarks or regular workloads)?
I wrote a test case to compare these two methods, but not find visible difference in run time.
While I found we may leverage rb_last to refine the code a little.
@@ -2270,12 +2270,9 @@ find_vma_prev(struct mm_struct *mm, unsigned long addr,
if (vma) {
*pprev = vma->vm_prev;
} else {
- struct rb_node *rb_node = mm->mm_rb.rb_node;
- *pprev = NULL;
- while (rb_node) {
- *pprev = rb_entry(rb_node, struct vm_area_struct, vm_rb);
- rb_node = rb_node->rb_right;
- }
+ struct rb_node *rb_node = rb_last(&mm->mm_rb);
+ *pprev = !rb_node ? NULL :
+ rb_entry(rb_node, struct vm_area_struct, vm_rb);
}
return vma;Not sure this style would help a little in understanding the code?
Quoted 3 lines
Signature · 2 lines
Michal Hocko SUSE Labs
Signature · 2 lines
Wei Yang Help you, Help me
Quoted 29 lines · Wei Yang
Quoted 28 lines · Michal Hocko
Quoted 27 lines · Wei Yang
Quoted 13 lines · Vlastimil Babka
Quoted 2 lines · Wei Yang
When addr is out of the range of the whole
rb_tree, pprev will points to the biggest node.find_vma_prevgets is by going through the right mosts/biggest/last/ ? or right-most?
Quoted 6 lines
node of the tree.
Since only the last node is the one it is looking for, it is not necessary to assign pprev to those middle stage nodes. By assigning pprev to the last node directly, it tries to improve the function locality a little.
Quoted 5 lines
In the end, it will always write to the cacheline of pprev. The caller has most likely have it on stack, so it's already hot, and there's no other CPU stealing it. So I don't understand where the improved locality comes from. The compiler can also optimize the patched code so the assembly is identical to the previous code, or vice versa. Did you check for differences?
Vlastimil
Thanks for your comment.
I believe you get a point. I may not use the word locality. This patch tries to reduce some unnecessary assignment of pprev.
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
Original code would assign the value on each node during iteration, this is what I want to reduce.
Is there any measurable difference (on micro benchmarks or regular workloads)?
I wrote a test case to compare these two methods, but not find visible difference in run time.
What is the point in changing this code if it doesn't lead to any measurable improvement?
Signature · 2 lines
Michal Hocko SUSE Labs
Quoted 33 lines · Michal Hocko
Quoted 32 lines · Wei Yang
Quoted 31 lines · Michal Hocko
Quoted 29 lines · Wei Yang
Quoted 13 lines · Vlastimil Babka
Quoted 2 lines · Wei Yang
When addr is out of the range of the whole
rb_tree, pprev will points to the biggest node.find_vma_prevgets is by going through the right mosts/biggest/last/ ? or right-most?
Quoted 6 lines
node of the tree.
Since only the last node is the one it is looking for, it is not necessary to assign pprev to those middle stage nodes. By assigning pprev to the last node directly, it tries to improve the function locality a little.
Quoted 5 lines
In the end, it will always write to the cacheline of pprev. The caller has most likely have it on stack, so it's already hot, and there's no other CPU stealing it. So I don't understand where the improved locality comes from. The compiler can also optimize the patched code so the assembly is identical to the previous code, or vice versa. Did you check for differences?
Vlastimil
Thanks for your comment.
I believe you get a point. I may not use the word locality. This patch tries to reduce some unnecessary assignment of pprev.
Original code would assign the value on each node during iteration, this is what I want to reduce.
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
Is there any measurable difference (on micro benchmarks or regular workloads)?
I wrote a test case to compare these two methods, but not find visible difference in run time.
What is the point in changing this code if it doesn't lead to any measurable improvement?
You are right.
Quoted 3 lines
Signature · 2 lines
Michal Hocko SUSE Labs
Signature · 2 lines
Wei Yang Help you, Help me
Quoted 17 lines · Wei Yang
mm/mmap.c +3
-6@@ -2270,12 +2270,9 @@ find_vma_prev(struct mm_struct *mm, unsigned long addr,if (vma) { *pprev = vma->vm_prev; }else { -struct rb_node *rb_node = mm->mm_rb.rb_node; - *pprev =NULL ; -while (rb_node) { - *pprev = rb_entry(rb_node, struct vm_area_struct, vm_rb); - rb_node = rb_node->rb_right; - } +struct rb_node *rb_node =rb_last (&mm->mm_rb); + *pprev = !rb_node ?NULL : + rb_entry(rb_node, struct vm_area_struct, vm_rb); }return vma;
Quoted 1 line
Not sure this style would help a little in understanding the code?
Yeah using rb_last() would be nicer than basically repeating its implementation, so it's fine as a cleanup without performance implications.
Quoted 4 lines
Quoted 3 lines
Signature · 2 lines
Michal Hocko SUSE Labs
Quoted 18 lines · Vlastimil Babka
Quoted 17 lines · Wei Yang
mm/mmap.c +3
-6@@ -2270,12 +2270,9 @@ find_vma_prev(struct mm_struct *mm, unsigned long addr,if (vma) { *pprev = vma->vm_prev; }else { -struct rb_node *rb_node = mm->mm_rb.rb_node; - *pprev =NULL ; -while (rb_node) { - *pprev = rb_entry(rb_node, struct vm_area_struct, vm_rb); - rb_node = rb_node->rb_right; - } +struct rb_node *rb_node =rb_last (&mm->mm_rb); + *pprev = !rb_node ?NULL : + rb_entry(rb_node, struct vm_area_struct, vm_rb); }return vma;
Quoted 5 lines
Quoted 1 line
Not sure this style would help a little in understanding the code?
Yeah using
rb_last()would be nicer than basically repeating its implementation, so it's fine as a cleanup without performance implications.
Thanks, I would send this version with proper change log.
Quoted 4 lines
Quoted 4 lines
Quoted 3 lines
Signature · 2 lines
Michal Hocko SUSE Labs
Signature · 2 lines
Wei Yang Help you, Help me
Quoted 20 lines · Wei Yang
When addr is out of the range of the whole
rb_tree, pprev will points to the biggest node.find_vma_prevgets is by going through the right most node of the tree.Since only the last node is the one it is looking for, it is not necessary to assign pprev to those middle stage nodes. By assigning pprev to the last node directly, it tries to improve the function locality a little.
Signed-off-by Wei Yang <[email protected]>--- mm/mmap.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-)mm/mmap.c +0
-0@@ -2271,11 +2271,10 @@ find_vma_prev(struct mm_struct *mm, unsigned long addr, *pprev = vma->vm_prev;
mm/mmap.c find_vma_prev(struct mm_struct *mm, unsigned long addr, · line 2277
Quoted 10 lines
mm/mmap.c +3
-4}else {struct rb_node *rb_node = mm->mm_rb.rb_node; - *pprev =NULL ; -while (rb_node) { - *pprev = rb_entry(rb_node, struct vm_area_struct, vm_rb); +while (rb_node && rb_node->rb_right) rb_node = rb_node->rb_right; - } + *pprev = rb_node ?NULL + : rb_entry(rb_node, struct vm_area_struct, vm_rb);
Can rb_node ever be NULL? assuming mm->mm_rb.rb_node is not NULL when we enter here
Balbir Singh
Quoted 26 lines · Balbir Singh
Quoted 25 lines · Wei Yang
When addr is out of the range of the whole
rb_tree, pprev will points to the biggest node.find_vma_prevgets is by going through the right most node of the tree.Since only the last node is the one it is looking for, it is not necessary to assign pprev to those middle stage nodes. By assigning pprev to the last node directly, it tries to improve the function locality a little.
Signed-off-by Wei Yang <[email protected]>--- mm/mmap.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-)mm/mmap.c +0
-3@@ -2271,11 +2271,10 @@ find_vma_prev(struct mm_struct *mm, unsigned long addr, *pprev = vma->vm_prev; }else {struct rb_node *rb_node = mm->mm_rb.rb_node; - *pprev =NULL ; -while (rb_node) { - *pprev = rb_entry(rb_node, struct vm_area_struct, vm_rb);
Quoted 9 lines
mm/mmap.c find_vma_prev(struct mm_struct *mm, unsigned long addr, · line 2277
Quoted 5 lines
mm/mmap.c +3
-1+while (rb_node && rb_node->rb_right) rb_node = rb_node->rb_right; - } + *pprev = rb_node ?NULL + : rb_entry(rb_node, struct vm_area_struct, vm_rb);Can
rb_nodeever be NULL? assumingmm->mm_rb.rb_nodeis not NULL when we enter here
My bad, it should be
*pprev = !rb_node ? NULL : rb_entry(rb_node, struct vm_area_struct, vm_rb);
Thanks
Quoted 1 line
Balbir Singh
Signature · 2 lines
Wei Yang Help you, Help me