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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id B6B4AC433EF for ; Mon, 29 Nov 2021 16:36:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1346820AbhK2Qju (ORCPT ); Mon, 29 Nov 2021 11:39:50 -0500 Received: from rere.qmqm.pl ([91.227.64.183]:50146 "EHLO rere.qmqm.pl" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1345506AbhK2Qhq (ORCPT ); Mon, 29 Nov 2021 11:37:46 -0500 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 Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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