[PATCH] mm/mmap.c: refine data locality of find_vma_prev

[PATCH] mm/mmap.c: refine data locality of find_vma_prev

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

Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
---
 mm/mmap.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/mm/mmap.c b/mm/mmap.c
index 7e8c3e8ae75f..284bc7e51f9c 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -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;
 }
-- 
2.17.1

Re: [PATCH] mm/mmap.c: refine data locality of find_vma_prev

[Vlastimil Babka]

On 8/6/19 10:11 AM, Wei Yang wrote:
> 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?

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

> Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
> ---
>  mm/mmap.c | 7 +++----
>  1 file changed, 3 insertions(+), 4 deletions(-)
> 
> diff --git a/mm/mmap.c b/mm/mmap.c
> index 7e8c3e8ae75f..284bc7e51f9c 100644
> --- a/mm/mmap.c
> +++ b/mm/mmap.c
> @@ -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;
>  }
> 

Re: [PATCH] mm/mmap.c: refine data locality of find_vma_prev

[Balbir Singh]

On Tue, Aug 06, 2019 at 04:11:23PM +0800, Wei Yang wrote:
> 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.
> 
> Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
> ---
>  mm/mmap.c | 7 +++----
>  1 file changed, 3 insertions(+), 4 deletions(-)
> 
> diff --git a/mm/mmap.c b/mm/mmap.c
> index 7e8c3e8ae75f..284bc7e51f9c 100644
> --- a/mm/mmap.c
> +++ b/mm/mmap.c
> @@ -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);

Can rb_node ever be NULL? assuming mm->mm_rb.rb_node is not NULL when we
enter here

Balbir Singh

Re: [PATCH] mm/mmap.c: refine data locality of find_vma_prev

[Wei Yang]

On Tue, Aug 06, 2019 at 11:29:52AM +0200, Vlastimil Babka wrote:
>On 8/6/19 10:11 AM, Wei Yang wrote:
>> 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?
>
>> 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?

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?

>
>The previous code is somewhat more obvious to me, so unless I'm missing
>something, readability and less churn suggests to not change.
>
>> Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
>> ---
>>  mm/mmap.c | 7 +++----
>>  1 file changed, 3 insertions(+), 4 deletions(-)
>> 
>> diff --git a/mm/mmap.c b/mm/mmap.c
>> index 7e8c3e8ae75f..284bc7e51f9c 100644
>> --- a/mm/mmap.c
>> +++ b/mm/mmap.c
>> @@ -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;
>>  }
>> 

-- 
Wei Yang
Help you, Help me

Re: [PATCH] mm/mmap.c: refine data locality of find_vma_prev

[Wei Yang]

On Tue, Aug 06, 2019 at 10:58:22AM +0000, Balbir Singh wrote:
>On Tue, Aug 06, 2019 at 04:11:23PM +0800, Wei Yang wrote:
>> 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.
>> 
>> Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
>> ---
>>  mm/mmap.c | 7 +++----
>>  1 file changed, 3 insertions(+), 4 deletions(-)
>> 
>> diff --git a/mm/mmap.c b/mm/mmap.c
>> index 7e8c3e8ae75f..284bc7e51f9c 100644
>> --- a/mm/mmap.c
>> +++ b/mm/mmap.c
>> @@ -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);
>
>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

>Balbir Singh

-- 
Wei Yang
Help you, Help me

Re: [PATCH] mm/mmap.c: refine data locality of find_vma_prev

[Michal Hocko]

On Wed 07-08-19 08:31:09, Wei Yang wrote:
> On Tue, Aug 06, 2019 at 11:29:52AM +0200, Vlastimil Babka wrote:
> >On 8/6/19 10:11 AM, Wei Yang wrote:
> >> 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?
> >
> >> 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?
> 
> 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.

Is there any measurable difference (on micro benchmarks or regular
workloads)?
-- 
Michal Hocko
SUSE Labs

Re: [PATCH] mm/mmap.c: refine data locality of find_vma_prev

[Wei Yang]

On Wed, Aug 07, 2019 at 09:51:01AM +0200, Michal Hocko wrote:
>On Wed 07-08-19 08:31:09, Wei Yang wrote:
>> On Tue, Aug 06, 2019 at 11:29:52AM +0200, Vlastimil Babka wrote:
>> >On 8/6/19 10:11 AM, Wei Yang wrote:
>> >> 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?
>> >
>> >> 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?
>> 
>> 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.
>
>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?

>-- 
>Michal Hocko
>SUSE Labs

-- 
Wei Yang
Help you, Help me

Re: [PATCH] mm/mmap.c: refine data locality of find_vma_prev

[Michal Hocko]

On Thu 08-08-19 11:26:38, Wei Yang wrote:
> On Wed, Aug 07, 2019 at 09:51:01AM +0200, Michal Hocko wrote:
> >On Wed 07-08-19 08:31:09, Wei Yang wrote:
> >> On Tue, Aug 06, 2019 at 11:29:52AM +0200, Vlastimil Babka wrote:
> >> >On 8/6/19 10:11 AM, Wei Yang wrote:
> >> >> 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?
> >> >
> >> >> 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?
> >> 
> >> 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.
> >
> >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?
-- 
Michal Hocko
SUSE Labs

Re: [PATCH] mm/mmap.c: refine data locality of find_vma_prev

[Wei Yang]

On Thu, Aug 08, 2019 at 08:02:10AM +0200, Michal Hocko wrote:
>On Thu 08-08-19 11:26:38, Wei Yang wrote:
>> On Wed, Aug 07, 2019 at 09:51:01AM +0200, Michal Hocko wrote:
>> >On Wed 07-08-19 08:31:09, Wei Yang wrote:
>> >> On Tue, Aug 06, 2019 at 11:29:52AM +0200, Vlastimil Babka wrote:
>> >> >On 8/6/19 10:11 AM, Wei Yang wrote:
>> >> >> 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?
>> >> >
>> >> >> 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?
>> >> 
>> >> 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.
>> >
>> >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.

>-- 
>Michal Hocko
>SUSE Labs

-- 
Wei Yang
Help you, Help me

Re: [PATCH] mm/mmap.c: refine data locality of find_vma_prev

[Vlastimil Babka]

On 8/8/19 5:26 AM, Wei Yang wrote:
> 
> @@ -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?

Yeah using rb_last() would be nicer than basically repeating its
implementation, so it's fine as a cleanup without performance implications.

>> -- 
>> Michal Hocko
>> SUSE Labs
> 

Re: [PATCH] mm/mmap.c: refine data locality of find_vma_prev

[Wei Yang]

On Thu, Aug 08, 2019 at 10:49:29AM +0200, Vlastimil Babka wrote:
>On 8/8/19 5:26 AM, Wei Yang wrote:
>> 
>> @@ -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?
>
>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.

>>> -- 
>>> Michal Hocko
>>> SUSE Labs
>> 

-- 
Wei Yang
Help you, Help me