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 6D57AC433F5 for ; Thu, 2 Dec 2021 00:32:05 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8FD356B0072; Wed, 1 Dec 2021 19:31:54 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 886B36B0073; Wed, 1 Dec 2021 19:31:54 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6B1476B0074; Wed, 1 Dec 2021 19:31:54 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0156.hostedemail.com [216.40.44.156]) by kanga.kvack.org (Postfix) with ESMTP id 597956B0072 for ; Wed, 1 Dec 2021 19:31:54 -0500 (EST) Received: from smtpin30.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay01.hostedemail.com (Postfix) with ESMTP id 1AE49181CC1AA for ; Thu, 2 Dec 2021 00:31:44 +0000 (UTC) X-FDA: 78870976128.30.ACE4ED3 Received: from mail-qv1-f54.google.com (mail-qv1-f54.google.com [209.85.219.54]) by imf07.hostedemail.com (Postfix) with ESMTP id 8A0D9100009E for ; Thu, 2 Dec 2021 00:31:43 +0000 (UTC) Received: by mail-qv1-f54.google.com with SMTP id a24so23413890qvb.5 for ; Wed, 01 Dec 2021 16:31:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:content-transfer-encoding:in-reply-to; bh=UYmHlVbMSQbQAn62a50WlYWlw5WYikEw/HKO8MU8o20=; b=d9ufFBZIjBeCnfJhxkhOJHR4U6gA3sYY5/+OartHrmtyqhNuwpEH+tfc93YA7tEDao yOKDodcNFRle3eMMLCg2FH/Tcgr7cW593yntXLl1utZLUJtVShRNQEOc9NvEo4hEL1rm L2l6bxTExKPSRmbnMRKqIcZhoOpd63W1ZKagDrFCRbYIcYvSgN+CxBxrwTxGRSsHeVKf UXZK5TS9EbCKBOwmJzZ51FgzKmkah4fU/bnP1hNtNTskTK6qjluwzPEk7uWUTAkKCdZ1 XxzA5TtEBQPg9PU9R4bStLW9Ne4zdJoIM+RpRwYI7AmQcqEYlTEIoOnEsCuvtTzXmNFj 00eA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:content-transfer-encoding :in-reply-to; bh=UYmHlVbMSQbQAn62a50WlYWlw5WYikEw/HKO8MU8o20=; b=HtkWBKyHE2nXYVsHFCb5VkbUX/wzzNAyybq72hfrRpSGVqTFZV59qX+UUjWEEMX/CG lK3HPVANEakxblQCdNCHNc/rIjG5XWth46wHDNN0lgElaFdPogQfZ6/f1bo7HsOwaal3 ODUWcvypgNDMG1jBtmgeQ975NASNkNl7crihXzvBV0Dlkc71xCYpmjrikRS7o4Vxkohv 0gwrhS12BRDB28GzQ+AKnqkG7ZxkG8G9zlXJhl5nZDsKBH27Kt6dT2YADJ+i88G8lySK lwGDfLuQ3hmnv/WYw6Sxtw09Jlt9to1cYP0jLNajIuS4ncw6rKI8TPoxxssERqUxatnQ Ks3Q== X-Gm-Message-State: AOAM532Qi4cVMFJjObemAr0I6U1Xk5VzNPBd+/yX/9OKMVqyBXTHGV6T OYoqgP20U2GUkrBhTmf86eU= X-Google-Smtp-Source: ABdhPJwpuPpSi7n83vlL+jLX5fyPRTIJyAHbiKfUe+xvjm76YV/xzPPNg/iMW1GhI6PSi3iKc0YBEA== X-Received: by 2002:a05:6214:ccc:: with SMTP id 12mr9930154qvx.8.1638405102640; Wed, 01 Dec 2021 16:31:42 -0800 (PST) Received: from localhost ([66.216.211.25]) by smtp.gmail.com with ESMTPSA id l1sm690890qkp.125.2021.12.01.16.31.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 01 Dec 2021 16:31:42 -0800 (PST) Date: Wed, 1 Dec 2021 16:31:40 -0800 From: Yury Norov To: =?utf-8?B?TWljaGHFgiBNaXJvc8WCYXc=?= 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 Message-ID: <20211202003140.GA430494@lapt> References: <20211128035704.270739-1-yury.norov@gmail.com> <20211129063839.GA338729@lapt> <3CD9ECD8-901E-497B-9AE1-0DDB02346892@rere.qmqm.pl> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <3CD9ECD8-901E-497B-9AE1-0DDB02346892@rere.qmqm.pl> X-Rspamd-Server: rspam01 X-Rspamd-Queue-Id: 8A0D9100009E X-Stat-Signature: usq8mggqzif46sadc6fj6id34ppmpptc Authentication-Results: imf07.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=d9ufFBZI; spf=pass (imf07.hostedemail.com: domain of yury.norov@gmail.com designates 209.85.219.54 as permitted sender) smtp.mailfrom=yury.norov@gmail.com; dmarc=pass (policy=none) header.from=gmail.com X-HE-Tag: 1638405103-609018 Content-Transfer-Encoding: quoted-printable 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: On Mon, Nov 29, 2021 at 04:34:07PM +0000, Micha=C5=82 Miros=C5=82aw wrote= : > 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.qmqm.pl wrote= : > >> 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 be= cause > >> > num_present_cpus() will traverse every word of underlying cpumask > >> > unconditionally. > >> >=20 > >> > We can significantly improve on it for many real cases if stop tra= versing > >> > the mask as soon as we count present cpus to any number greater th= an 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 node= mask. > >>=20 > >> Having slept on it I have more structured thoughts: > >>=20 > >> First, I like substituting bitmap_empty/full where possible - I thin= k > >> the change stands on its own, so could be split and sent as is. > > > >Ok, I can do it. > > > >> I don't like the proposed API very much. One problem is that it hide= s > >> the comparison operator and makes call sites less readable: > >>=20 > >> bitmap_weight(...) > N > >>=20 > >> becomes: > >>=20 > >> bitmap_weight_gt(..., N) > >>=20 > >> and: > >> bitmap_weight(...) <=3D N > >>=20 > >> becomes: > >>=20 > >> bitmap_weight_lt(..., N+1) > >> or: > >> !bitmap_weight_gt(..., N) > >>=20 > >> I'd rather see something resembling memcmp() API that's known enough > >> to be easier to grasp. For above examples: > >>=20 > >> bitmap_weight_cmp(..., N) > 0 > >> bitmap_weight_cmp(..., N) <=3D 0 > >> ... > > > >bitmap_weight_cmp() cannot be efficient. 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. >=20 > Thank you for the example. Indeed, for less-than to be efficient here y= ou would need to replace > bitmap_weight_cmp(..., N) < 0 > with > bitmap_weight_cmp(..., N-1) <=3D 0 Indeed, thanks for pointing to it. =20 > It would still be more readable, I think. To be honest, I'm not sure that bitmap_weight_cmp(..., N-1) <=3D 0 would be an obvious replacement for the original bitmap_weight(...) < N comparing to=20 bitmap_weight_lt(..., N) I think the best thing I can do is to add bitmap_weight_cmp() as you suggested, and turn lt and others to be wrappers on it. This will let people choose a better function in each case. I also think that for v2 it would be better to drop the conversion for short bitmaps, except for switching to bitmap_empty(), because in that case readability wins over performance; if no objections.=20 Thanks, Yury