Re: [patch] mm: speedup in __early_pfn_to_nid

[Yinghai Lu]

On Mon, Mar 25, 2013 at 2:56 PM, Russ Anderson <rja@xxxxxxx> wrote:
> 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.

Please check attached patch that could be applied on top of your patch
in -mm.

Thanks

Yinghai

Attachment: memblock_search_pfn_nid.patch
Description: Binary data