Re: + mm-memblock-reduce-overhead-in-binary-search.patch added to -mm tree

Re: + mm-memblock-reduce-overhead-in-binary-search.patch added to -mm tree

[Michal Hocko]

[Sorry for the late reply]

On Fri 07-09-12 16:50:57, Andrew Morton wrote:
> 
> The patch titled
>      Subject: mm/memblock: reduce overhead in binary search
> has been added to the -mm tree.  Its filename is
>      mm-memblock-reduce-overhead-in-binary-search.patch
> 
> Before you just go and hit "reply", please:
>    a) Consider who else should be cc'ed
>    b) Prefer to cc a suitable mailing list as well
>    c) Ideally: find the original patch on the mailing list and do a
>       reply-to-all to that, adding suitable additional cc's
> 
> *** Remember to use Documentation/SubmitChecklist when testing your code ***
> 
> The -mm tree is included into linux-next and is updated
> there every 3-4 working days
> 
> ------------------------------------------------------
> From: Wanpeng Li <liwanp@linux.vnet.ibm.com>
> Subject: mm/memblock: reduce overhead in binary search
> 
> When checking that the indicated address belongs to the memory region, the
> memory regions are checked one by one through a binary search, which will
> be time consuming.

How many blocks do you have that O(long) is that time consuming?

> If the indicated address isn't in the memory region, then we needn't do
> the time-consuming search.  

How often does this happen?

> Add a check on the indicated address for that purpose.

We have 2 users of this function. One is exynos_sysmmu_enable and the
other pfn_valid for unicore32. The first one doesn't seem to be used
anywhere (as per git grep). The other one could benefit from it but it
would be nice to hear about how much it really helps becuase if the
address is (almost) never outside of start,end DRAM bounds then you just
add a pointless check.
Besides that, if this kind of optimization is really worth, why don't we
do the same thing for memblock_is_reserved and memblock_is_region_memory
as well?

So, while the patch seems correct, I do not see how much it helps while
it definitely adds a code to maintain.

> Signed-off-by: Wanpeng Li <liwanp@linux.vnet.ibm.com>
> Cc: Michal Hocko <mhocko@suse.cz>
> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
> Cc: Minchan Kim <minchan@kernel.org>
> Cc: Gavin Shan <shangw@linux.vnet.ibm.com>
> Cc: Yinghai Lu <yinghai@kernel.org>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> ---
> 
>  mm/memblock.c |    5 +++++
>  1 file changed, 5 insertions(+)
> 
> diff -puN mm/memblock.c~mm-memblock-reduce-overhead-in-binary-search mm/memblock.c
> --- a/mm/memblock.c~mm-memblock-reduce-overhead-in-binary-search
> +++ a/mm/memblock.c
> @@ -888,6 +888,11 @@ int __init memblock_is_reserved(phys_add
>  
>  int __init_memblock memblock_is_memory(phys_addr_t addr)
>  {
> +
> +	if (unlikely(addr < memblock_start_of_DRAM() ||
> +		addr >= memblock_end_of_DRAM()))
> +		return 0;
> +
>  	return memblock_search(&memblock.memory, addr) != -1;
>  }
>  
> _
> 
> Patches currently in -mm which might be from liwanp@linux.vnet.ibm.com are
> 
> mm-mmu_notifier-init-notifier-if-necessary.patch
> mm-vmscan-fix-error-number-for-failed-kthread.patch
> mm-memblock-reduce-overhead-in-binary-search.patch
> mm-memblock-rename-get_allocated_memblock_reserved_regions_info.patch
> mm-memblock-use-existing-interface-to-set-nid.patch
> mm-memblock-cleanup-early_node_map-related-comments.patch
> 

-- 
Michal Hocko
SUSE Labs

Re: + mm-memblock-reduce-overhead-in-binary-search.patch added to -mm tree

[Michal Hocko]

On Mon 10-09-12 17:46:04, Wanpeng Li wrote:
> On Mon, Sep 10, 2012 at 10:22:39AM +0200, Michal Hocko wrote:
> >[Sorry for the late reply]
> >
> >On Fri 07-09-12 16:50:57, Andrew Morton wrote:
> >> 
> >> The patch titled
> >>      Subject: mm/memblock: reduce overhead in binary search
> >> has been added to the -mm tree.  Its filename is
> >>      mm-memblock-reduce-overhead-in-binary-search.patch
> >> 
> >> Before you just go and hit "reply", please:
> >>    a) Consider who else should be cc'ed
> >>    b) Prefer to cc a suitable mailing list as well
> >>    c) Ideally: find the original patch on the mailing list and do a
> >>       reply-to-all to that, adding suitable additional cc's
> >> 
> >> *** Remember to use Documentation/SubmitChecklist when testing your code ***
> >> 
> >> The -mm tree is included into linux-next and is updated
> >> there every 3-4 working days
> >> 
> >> ------------------------------------------------------
> >> From: Wanpeng Li <liwanp@linux.vnet.ibm.com>
> >> Subject: mm/memblock: reduce overhead in binary search
> >> 
> >> When checking that the indicated address belongs to the memory region, the
> >> memory regions are checked one by one through a binary search, which will
> >> be time consuming.
> >
> >How many blocks do you have that O(long) is that time consuming?
> >
> >> If the indicated address isn't in the memory region, then we needn't do
> >> the time-consuming search.  
> >
> >How often does this happen?
> >
> >> Add a check on the indicated address for that purpose.
> >
> >We have 2 users of this function. One is exynos_sysmmu_enable and the
> >other pfn_valid for unicore32. The first one doesn't seem to be used
> >anywhere (as per git grep). The other one could benefit from it but it
> >would be nice to hear about how much it really helps becuase if the
> >address is (almost) never outside of start,end DRAM bounds then you just
> >add a pointless check.
> >Besides that, if this kind of optimization is really worth, why don't we
> >do the same thing for memblock_is_reserved and memblock_is_region_memory
> >as well?
> 
> As Yinghai said,
> 
> BIOS could have reserved some ranges, and those ranges are not overlapped by 
> RAM. and so those range will not be in memory and reserved array.
> 
> later kernel will probe some range, and reserved those range, so those
> range get inserted into reserved array. reserved and memory array is
> different.

OK. Thanks for the clarification. The main question remains, though. Is
this worth for memblock_is_memory?

> >So, while the patch seems correct, I do not see how much it helps while
> >it definitely adds a code to maintain.
> >
> >> Signed-off-by: Wanpeng Li <liwanp@linux.vnet.ibm.com>
> >> Cc: Michal Hocko <mhocko@suse.cz>
> >> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
> >> Cc: Minchan Kim <minchan@kernel.org>
> >> Cc: Gavin Shan <shangw@linux.vnet.ibm.com>
> >> Cc: Yinghai Lu <yinghai@kernel.org>
> >> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> >> ---
> >> 
> >>  mm/memblock.c |    5 +++++
> >>  1 file changed, 5 insertions(+)
> >> 
> >> diff -puN mm/memblock.c~mm-memblock-reduce-overhead-in-binary-search mm/memblock.c
> >> --- a/mm/memblock.c~mm-memblock-reduce-overhead-in-binary-search
> >> +++ a/mm/memblock.c
> >> @@ -888,6 +888,11 @@ int __init memblock_is_reserved(phys_add
> >>  
> >>  int __init_memblock memblock_is_memory(phys_addr_t addr)
> >>  {
> >> +
> >> +	if (unlikely(addr < memblock_start_of_DRAM() ||
> >> +		addr >= memblock_end_of_DRAM()))
> >> +		return 0;
> >> +
> >>  	return memblock_search(&memblock.memory, addr) != -1;
> >>  }
> >>  
> >> _
> >> 
> >> Patches currently in -mm which might be from liwanp@linux.vnet.ibm.com are
> >> 
> >> mm-mmu_notifier-init-notifier-if-necessary.patch
> >> mm-vmscan-fix-error-number-for-failed-kthread.patch
> >> mm-memblock-reduce-overhead-in-binary-search.patch
> >> mm-memblock-rename-get_allocated_memblock_reserved_regions_info.patch
> >> mm-memblock-use-existing-interface-to-set-nid.patch
> >> mm-memblock-cleanup-early_node_map-related-comments.patch
> >> 
> >
> >-- 
> >Michal Hocko
> >SUSE Labs
> >
> >--
> >To unsubscribe, send a message with 'unsubscribe linux-mm' in
> >the body to majordomo@kvack.org.  For more info on Linux MM,
> >see: http://www.linux-mm.org/ .
> >Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
> 

-- 
Michal Hocko
SUSE Labs

Re: + mm-memblock-reduce-overhead-in-binary-search.patch added to -mm tree

[Michal Hocko]

On Mon 10-09-12 19:30:51, Wanpeng Li wrote:
> On Mon, Sep 10, 2012 at 01:05:50PM +0200, Michal Hocko wrote:
> >On Mon 10-09-12 17:46:04, Wanpeng Li wrote:
> >> On Mon, Sep 10, 2012 at 10:22:39AM +0200, Michal Hocko wrote:
> >> >[Sorry for the late reply]
> >> >
> >> >On Fri 07-09-12 16:50:57, Andrew Morton wrote:
> >> >> 
> >> >> The patch titled
> >> >>      Subject: mm/memblock: reduce overhead in binary search
> >> >> has been added to the -mm tree.  Its filename is
> >> >>      mm-memblock-reduce-overhead-in-binary-search.patch
> >> >> 
> >> >> Before you just go and hit "reply", please:
> >> >>    a) Consider who else should be cc'ed
> >> >>    b) Prefer to cc a suitable mailing list as well
> >> >>    c) Ideally: find the original patch on the mailing list and do a
> >> >>       reply-to-all to that, adding suitable additional cc's
> >> >> 
> >> >> *** Remember to use Documentation/SubmitChecklist when testing your code ***
> >> >> 
> >> >> The -mm tree is included into linux-next and is updated
> >> >> there every 3-4 working days
> >> >> 
> >> >> ------------------------------------------------------
> >> >> From: Wanpeng Li <liwanp@linux.vnet.ibm.com>
> >> >> Subject: mm/memblock: reduce overhead in binary search
> >> >> 
> >> >> When checking that the indicated address belongs to the memory region, the
> >> >> memory regions are checked one by one through a binary search, which will
> >> >> be time consuming.
> >> >
> >> >How many blocks do you have that O(long) is that time consuming?
> >> >
> >> >> If the indicated address isn't in the memory region, then we needn't do
> >> >> the time-consuming search.  
> >> >
> >> >How often does this happen?
> >> >
> >> >> Add a check on the indicated address for that purpose.
> >> >
> >> >We have 2 users of this function. One is exynos_sysmmu_enable and the
> >> >other pfn_valid for unicore32. The first one doesn't seem to be used
> >> >anywhere (as per git grep). The other one could benefit from it but it
> >> >would be nice to hear about how much it really helps becuase if the
> >> >address is (almost) never outside of start,end DRAM bounds then you just
> >> >add a pointless check.
> >> >Besides that, if this kind of optimization is really worth, why don't we
> >> >do the same thing for memblock_is_reserved and memblock_is_region_memory
> >> >as well?
> >> 
> >> As Yinghai said,
> >> 
> >> BIOS could have reserved some ranges, and those ranges are not overlapped by 
> >> RAM. and so those range will not be in memory and reserved array.
> >> 
> >> later kernel will probe some range, and reserved those range, so those
> >> range get inserted into reserved array. reserved and memory array is
> >> different.
> >
> >OK. Thanks for the clarification. The main question remains, though. Is
> >this worth for memblock_is_memory?
> 
> There are many call sites need to call pfn_valid, how can you guarantee all
> the addrs are between memblock_start_of_DRAM() and memblock_end_of_DRAM(), 
> if not can this reduce possible overhead ? 

That was my question. I hoped for an answer in the patch description. I
am really not familiar with unicore32 which is the only user now.

> I add unlikely which means that this will not happen frequently. :-)

unlikely doesn't help much in this case. You would be doing the test for
every pfn_valid invocation anyway. So the main question is. Do you want
to optimize for something that doesn't happen often when it adds a cost
(not a big one but still) for the more probable cases?
I would say yes if we clearly see that the exceptional case really pays
off. Nothing in the changelog convinces me about that.
-- 
Michal Hocko
SUSE Labs

Re: + mm-memblock-reduce-overhead-in-binary-search.patch added to -mm tree

[Andrew Morton]

On Mon, 10 Sep 2012 13:55:15 +0200
Michal Hocko <mhocko@suse.cz> wrote:

> > >OK. Thanks for the clarification. The main question remains, though. Is
> > >this worth for memblock_is_memory?
> > 
> > There are many call sites need to call pfn_valid, how can you guarantee all
> > the addrs are between memblock_start_of_DRAM() and memblock_end_of_DRAM(), 
> > if not can this reduce possible overhead ? 
> 
> That was my question. I hoped for an answer in the patch description. I
> am really not familiar with unicore32 which is the only user now.
> 
> > I add unlikely which means that this will not happen frequently. :-)
> 
> unlikely doesn't help much in this case. You would be doing the test for
> every pfn_valid invocation anyway. So the main question is. Do you want
> to optimize for something that doesn't happen often when it adds a cost
> (not a big one but still) for the more probable cases?
> I would say yes if we clearly see that the exceptional case really pays
> off. Nothing in the changelog convinces me about that.

I don't believe Michal's questions have been resolved yet, so I'll keep
this patch on hold for now.

Re: + mm-memblock-reduce-overhead-in-binary-search.patch added to -mm tree

[Andrew Morton]

On Mon, 8 Oct 2012 12:42:34 -0700
Andrew Morton <akpm@linux-foundation.org> wrote:

> On Mon, 10 Sep 2012 13:55:15 +0200
> Michal Hocko <mhocko@suse.cz> wrote:
> 
> > > >OK. Thanks for the clarification. The main question remains, though. Is
> > > >this worth for memblock_is_memory?
> > > 
> > > There are many call sites need to call pfn_valid, how can you guarantee all
> > > the addrs are between memblock_start_of_DRAM() and memblock_end_of_DRAM(), 
> > > if not can this reduce possible overhead ? 
> > 
> > That was my question. I hoped for an answer in the patch description. I
> > am really not familiar with unicore32 which is the only user now.
> > 
> > > I add unlikely which means that this will not happen frequently. :-)
> > 
> > unlikely doesn't help much in this case. You would be doing the test for
> > every pfn_valid invocation anyway. So the main question is. Do you want
> > to optimize for something that doesn't happen often when it adds a cost
> > (not a big one but still) for the more probable cases?
> > I would say yes if we clearly see that the exceptional case really pays
> > off. Nothing in the changelog convinces me about that.
> 
> I don't believe Michal's questions have been resolved yet, so I'll keep
> this patch on hold for now.

ETIMEDOUT.  I'll drop the patch.  Please resend if you think it's still
needed and if these questions can be addressed.