From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752191AbeDFKXU (ORCPT ); Fri, 6 Apr 2018 06:23:20 -0400 Received: from mail-ot0-f196.google.com ([74.125.82.196]:46626 "EHLO mail-ot0-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751672AbeDFKXT (ORCPT ); Fri, 6 Apr 2018 06:23:19 -0400 X-Google-Smtp-Source: AIpwx4+5qetVFI++1nj4Vx3o8BmcxdYrYeJ/6RUEbXN1h8RT8uRxv3fwt8PSGHTt4QyYHhypf0PgKCW+O0AyN6purew= MIME-Version: 1.0 In-Reply-To: <20180406090920.GM16141@n2100.armlinux.org.uk> References: <1522915478-5044-1-git-send-email-hejianet@gmail.com> <1522915478-5044-3-git-send-email-hejianet@gmail.com> <20180405113444.GB2647@bombadil.infradead.org> <1f809296-e88d-1090-0027-890782b91d6e@gmail.com> <20180405125054.GC2647@bombadil.infradead.org> <20180406090920.GM16141@n2100.armlinux.org.uk> From: Daniel Vacek Date: Fri, 6 Apr 2018 12:23:17 +0200 Message-ID: Subject: Re: [PATCH v7 2/5] arm: arm64: page_alloc: reduce unnecessary binary search in memblock_next_valid_pfn() To: Russell King - ARM Linux Cc: Matthew Wilcox , Jia He , Catalin Marinas , Will Deacon , Mark Rutland , Ard Biesheuvel , Andrew Morton , Michal Hocko , Wei Yang , Kees Cook , Laura Abbott , Vladimir Murzin , Philip Derrin , AKASHI Takahiro , James Morse , Steve Capper , Pavel Tatashin , Gioh Kim , Vlastimil Babka , Mel Gorman , Johannes Weiner , Kemi Wang , Petr Tesarik , YASUAKI ISHIMATSU , Andrey Ryabinin , Nikolay Borisov , Daniel Jordan , Eugeniu Rosca , linux-arm-kernel , open list , Linux-MM , Jia He Content-Type: text/plain; charset="UTF-8" Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Fri, Apr 6, 2018 at 11:09 AM, Russell King - ARM Linux wrote: > On Thu, Apr 05, 2018 at 05:50:54AM -0700, Matthew Wilcox wrote: >> On Thu, Apr 05, 2018 at 08:44:12PM +0800, Jia He wrote: >> > >> > >> > On 4/5/2018 7:34 PM, Matthew Wilcox Wrote: >> > > On Thu, Apr 05, 2018 at 01:04:35AM -0700, Jia He wrote: >> > > > Commit b92df1de5d28 ("mm: page_alloc: skip over regions of invalid pfns >> > > > where possible") optimized the loop in memmap_init_zone(). But there is >> > > > still some room for improvement. E.g. if pfn and pfn+1 are in the same >> > > > memblock region, we can simply pfn++ instead of doing the binary search >> > > > in memblock_next_valid_pfn. >> > > Sure, but I bet if we are >end_pfn, we're almost certainly going to the >> > > start_pfn of the next block, so why not test that as well? >> > > >> > > > + /* fast path, return pfn+1 if next pfn is in the same region */ >> > > > + if (early_region_idx != -1) { >> > > > + start_pfn = PFN_DOWN(regions[early_region_idx].base); >> > > > + end_pfn = PFN_DOWN(regions[early_region_idx].base + >> > > > + regions[early_region_idx].size); >> > > > + >> > > > + if (pfn >= start_pfn && pfn < end_pfn) >> > > > + return pfn; >> > > early_region_idx++; >> > > start_pfn = PFN_DOWN(regions[early_region_idx].base); >> > > if (pfn >= end_pfn && pfn <= start_pfn) >> > > return start_pfn; >> > Thanks, thus the binary search in next step can be discarded? >> >> I don't know all the circumstances in which this is called. Maybe a linear >> search with memo is more appropriate than a binary search. This is actually a good point. > That's been brought up before, and the reasoning appears to be > something along the lines of... > > Academics and published wisdom is that on cached architectures, binary > searches are bad because it doesn't operate efficiently due to the > overhead from having to load cache lines. Consequently, there seems > to be a knee-jerk reaction that "all binary searches are bad, we must > eliminate them." a) This does not make sense. At least in general case. b) It is not the case here. Here it's really mostly called with sequentially incremented pfns, AFAICT. > What is failed to be grasped here, though, is that it is typical that > the number of entries in this array tend to be small, so the entire > array takes up one or two cache lines, maybe a maximum of four lines > depending on your cache line length and number of entries. > > This means that the binary search expense is reduced, and is lower > than a linear search for the majority of cases. In this case it hits mostly the last result or eventually the sequentially next one. > What is key here as far as performance is concerned is whether the > general usage of pfn_valid() by the kernel is optimal. We should > not optimise only for the boot case, which means evaluating the > effect of these changes with _real_ workloads, not just "does my > machine boot a milliseconds faster". IIUC, this is only used during early boot (and memory hotplug) and it does not influence regular runtime. Whether the general usage of pfn_valid() by the kernel is optimal is another good question, but that's totally unrelated to this series, IMHO. On the other hand I also wonder if this all really is worth the negligible boot time speedup. --nX > -- > RMK's Patch system: http://www.armlinux.org.uk/developer/patches/ > FTTC broadband for 0.8mile line in suburbia: sync at 8.8Mbps down 630kbps up > According to speedtest.net: 8.21Mbps down 510kbps up