From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id C86EBC433FE for ; Mon, 29 Nov 2021 16:34:59 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2F5566B006C; Mon, 29 Nov 2021 11:34:49 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 27CA26B0071; Mon, 29 Nov 2021 11:34:49 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 0CF966B0075; Mon, 29 Nov 2021 11:34:49 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (relay025.a.hostedemail.com [64.99.140.25]) by kanga.kvack.org (Postfix) with ESMTP id EBEBD6B006C for ; Mon, 29 Nov 2021 11:34:48 -0500 (EST) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 9E57F207D8 for ; Mon, 29 Nov 2021 16:34:38 +0000 (UTC) X-FDA: 78862516236.01.3608A97 Received: from rere.qmqm.pl (rere.qmqm.pl [91.227.64.183]) by imf01.hostedemail.com (Postfix) with ESMTP id C5E6C508E0AB for ; Mon, 29 Nov 2021 16:34:22 +0000 (UTC) Received: from remote.user (localhost [127.0.0.1]) by rere.qmqm.pl (Postfix) with ESMTPSA id 4J2rXL58g0z9h; Mon, 29 Nov 2021 17:34:10 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=rere.qmqm.pl; s=1; t=1638203665; bh=qlu3mL+FOvVS9aPE/gZoS7KdAdQ/avBctxZ8QxqT38I=; h=Date:From:To:CC:Subject:In-Reply-To:References:From; b=GV8Md+4wLJhNSJZqrJvdjyVU0DlzlhbpPkGnTNqVApkG+uUQ6A+MoaqEQT9dgrjXq q+escBY9SwJTtDVYNHqesyY22ZcfBKeLVi2I4yINeaBpICc3EsCTOMz8/JkEhkxKwH 5jlUqEb0yuAf8eVUX8cWy9bi6RovdDbzWpM+g8ZdNeFAwiFdkLHHM+FUiQ+x0Dv37t bEpCos1VGSJffWt42H8cWp9GNUDKdAgiFLCcBLScmau30GyMgUFylkw6qvpMGUFype xiTzGA2klsrhcAXTQoeGJ7H6y00R/3ukWQ3tN7aMIYo31vE1Ni41oAjMZVdXQclWDE FhYcDpXStxEZw== X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.3 at mail Date: Mon, 29 Nov 2021 16:34:07 +0000 From: =?UTF-8?Q?Micha=C5=82_Miros=C5=82aw?= To: Yury Norov CC: linux-kernel@vger.kernel.org, "James E.J. Bottomley" , "Paul E. McKenney" , "Martin K. Petersen" , "Rafael J. Wysocki" , Russell King , Amitkumar Karwar , Alexey Klimov , linux-alpha@vger.kernel.org, Alexander Shishkin , Andy Gross , Mike Marciniszyn , Petr Mladek , Andrew Morton , Andrew Lunn , Andi Kleen , Tejun Heo , Ard Biesheuvel , Vlastimil Babka , Anup Patel , linux-ia64@vger.kernel.org, Andy Shevchenko , Andy Lutomirski , Matti Vaittinen , Mel Gorman , Christoph Hellwig , Palmer Dabbelt , Catalin Marinas , Rasmus Villemoes , Borislav Petkov , Arnd Bergmann , Arnaldo Carvalho de Melo , Stephen Rothwell , David Laight , Sunil Goutham , David Airlie , Thomas Gleixner , Dave Hansen , Viresh Kumar , Daniel Vetter , bcm-kernel-feedback-list@broadcom.com, Christoph Lameter , linux-crypto@vger.kernel.org, Hans de Goede , linux-mm@kvack.org, Guo Ren , linux-snps-arc@lists.infradead.org, Geetha sowjanya , Mark Rutland , Dinh Nguyen , Mauro Carvalho Chehab , Dennis Zhou , Michael Ellerman , Heiko Carstens , Nicholas Piggin , Greg Kroah-Hartman , Peter Zijlstra , Geert Uytterhoeven , Randy Dunlap , Roy Pledge , Saeed Mahameed , Jens Axboe , Jason Wessel , Jakub Kicinski , Sergey Senozhatsky , Ingo Molnar , Stephen Boyd , Ian Rogers , Steven Rostedt , Sagi Grimberg , Sudeep Holla , Kalle Valo , Tariq Toukan , Juri Lelli , Thomas Bogendoerfer , Jonathan Cameron , Ulf Hansson , Jiri Olsa , Vineet Gupta , Solomon Peachy , Vivien Didelot , Lee Jones , Will Deacon , Krzysztof Kozlowski , kvm@vger.kernel.org, Kees Cook , linux-arm-kernel@lists.infradead.org, Subbaraya Sundeep , linux-csky@vger.kernel.org, Marcin Wojtas , linux-mips@vger.kernel.org, Marc Zyngier , linux-perf-users@vger.kernel.org, Vincent Guittot , linux-s390@vger.kernel.org, Mark Gross , linux-riscv@lists.infradead.org, linuxppc-dev@lists.ozlabs.org Subject: Re: [PATCH 0/9] lib/bitmap: optimize bitmap_weight() usage User-Agent: K-9 Mail for Android In-Reply-To: <20211129063839.GA338729@lapt> References: <20211128035704.270739-1-yury.norov@gmail.com> <20211129063839.GA338729@lapt> Message-ID: <3CD9ECD8-901E-497B-9AE1-0DDB02346892@rere.qmqm.pl> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: C5E6C508E0AB X-Stat-Signature: ciixprft6azsaqcytqk5e8e8ys35yttf Authentication-Results: imf01.hostedemail.com; dkim=pass header.d=rere.qmqm.pl header.s=1 header.b=GV8Md+4w; spf=pass (imf01.hostedemail.com: domain of mirq-linux@rere.qmqm.pl designates 91.227.64.183 as permitted sender) smtp.mailfrom=mirq-linux@rere.qmqm.pl; dmarc=pass (policy=reject) header.from=rere.qmqm.pl X-HE-Tag: 1638203662-584914 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Dnia 29 listopada 2021 06:38:39 UTC, Yury Norov = napisa=C5=82/a: >On Sun, Nov 28, 2021 at 07:03:41PM +0100, mirq-test@rere=2Eqmqm=2Epl wrot= e: >> On Sat, Nov 27, 2021 at 07:56:55PM -0800, Yury Norov wrote: >> > In many cases people use bitmap_weight()-based functions like this: >> >=20 >> > if (num_present_cpus() > 1) >> > do_something(); >> >=20 >> > This may take considerable amount of time on many-cpus machines becau= se >> > num_present_cpus() will traverse every word of underlying cpumask >> > unconditionally=2E >> >=20 >> > We can significantly improve on it for many real cases if stop traver= sing >> > the mask as soon as we count present cpus to any number greater than = 1: >> >=20 >> > if (num_present_cpus_gt(1)) >> > do_something(); >> >=20 >> > To implement this idea, the series adds bitmap_weight_{eq,gt,le} >> > functions together with corresponding wrappers in cpumask and nodemas= k=2E >>=20 >> Having slept on it I have more structured thoughts: >>=20 >> First, I like substituting bitmap_empty/full where possible - I think >> the change stands on its own, so could be split and sent as is=2E > >Ok, I can do it=2E > >> I don't like the proposed API very much=2E One problem is that it hides >> the comparison operator and makes call sites less readable: >>=20 >> bitmap_weight(=2E=2E=2E) > N >>=20 >> becomes: >>=20 >> bitmap_weight_gt(=2E=2E=2E, N) >>=20 >> and: >> bitmap_weight(=2E=2E=2E) <=3D N >>=20 >> becomes: >>=20 >> bitmap_weight_lt(=2E=2E=2E, N+1) >> or: >> !bitmap_weight_gt(=2E=2E=2E, N) >>=20 >> I'd rather see something resembling memcmp() API that's known enough >> to be easier to grasp=2E For above examples: >>=20 >> bitmap_weight_cmp(=2E=2E=2E, N) > 0 >> bitmap_weight_cmp(=2E=2E=2E, N) <=3D 0 >> =2E=2E=2E > >bitmap_weight_cmp() cannot be efficient=2E Consider this example: > >bitmap_weight_lt(1000 0000 0000 0000, 1) =3D=3D false > ^ > stop here > >bitmap_weight_cmp(1000 0000 0000 0000, 1) =3D=3D 0 > ^ > stop here > >I agree that '_gt' is less verbose than '>', but the advantage of=20 >'_gt' over '>' is proportional to length of bitmap, and it means >that this API should exist=2E Thank you for the example=2E Indeed, for less-than to be efficient here yo= u would need to replace bitmap_weight_cmp(=2E=2E=2E, N) < 0 with bitmap_weight_cmp(=2E=2E=2E, N-1) <=3D 0 It would still be more readable, I think=2E Best Regards Micha=C5=82 Miros=C5=82aw