Skip to contentSkip to conversation

mm/mmap.c: refine data locality of find_vma_prev

PATCH In review Wei Yang 5 participants 11 messages Aug 6, 2019 – Aug 8, 2019

Subsystems (2)
lore
Share & tools
lore

Wei Yang

author
#0 lore raw

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
index 7e8c3e8ae75f..284bc7e51f9c 100644
@@ -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
#1 lore raw
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_prev gets 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
---
 mm/mmap.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
mm/mmap.c +3 -4
index 7e8c3e8ae75f..284bc7e51f9c 100644
@@ -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;
 }
author
#2 lore raw
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_prev gets 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.

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
---
 mm/mmap.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
mm/mmap.c +3 -4
index 7e8c3e8ae75f..284bc7e51f9c 100644
@@ -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
#3 lore raw
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_prev gets 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.

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
author
#4 lore raw
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_prev gets 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.

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
#5 lore raw
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_prev gets 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.

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
author
#6 lore raw
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_prev gets 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.

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
#7 lore raw
In reply to Wei Yang
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
#8 lore raw
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
#9 lore raw
In reply to Wei Yang
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_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 +0 -0
index 7e8c3e8ae75f..284bc7e51f9c 100644
@@ -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

author
#10 lore raw
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_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 +0 -3
index 7e8c3e8ae75f..284bc7e51f9c 100644
@@ -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_node ever be NULL? assuming mm->mm_rb.rb_node is 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