Re: [patch] mm: speedup in __early_pfn_to_nid

[Russ Anderson]

On Mon, Mar 25, 2013 at 10:11:27AM +0800, Lin Feng wrote:
> On 03/24/2013 04:37 AM, Yinghai Lu wrote:
> > +#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
> > +int __init_memblock memblock_search_pfn_nid(unsigned long pfn,
> > +			 unsigned long *start_pfn, unsigned long *end_pfn)
> > +{
> > +	struct memblock_type *type = &memblock.memory;
> > +	int mid = memblock_search(type, (phys_addr_t)pfn << PAGE_SHIFT);
> 
> I'm really eager to see how much time can we save using binary search compared to
> linear search in this case :)

I have machine time tonight to measure the difference.

Based on earlier testing, a system with 9TB memory calls
__early_pfn_to_nid() 2,377,198,300 times while booting, but
only 6815 times does it not find that the memory range is
the same as previous and search the table.  Caching the
previous range avoids searching the table 2,377,191,485 times,
saving a significant amount of time.

Of the remaining 6815 times when it searches the table, a binary
search may help, but with relatively few calls it may not
make much of an overall difference.  Testing will show how much.

> (quote)
> > A 4 TB (single rack) UV1 system takes 512 seconds to get through
> > the zone code.  This performance optimization reduces the time
> > by 189 seconds, a 36% improvement.
> >
> > A 2 TB (single rack) UV2 system goes from 212.7 seconds to 99.8 seconds,
> > a 112.9 second (53%) reduction.
> (quote)
> 
> thanks,
> linfeng

-- 
Russ Anderson, OS RAS/Partitioning Project Lead  
SGI - Silicon Graphics Inc          rja@xxxxxxx
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/