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 r...@sgi.com -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/