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 BBD8DC433FE for ; Tue, 14 Dec 2021 19:43:43 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D6BE06B0073; Tue, 14 Dec 2021 14:43:32 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id CF5176B0074; Tue, 14 Dec 2021 14:43:32 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B6E416B0075; Tue, 14 Dec 2021 14:43:32 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0150.hostedemail.com [216.40.44.150]) by kanga.kvack.org (Postfix) with ESMTP id A96596B0073 for ; Tue, 14 Dec 2021 14:43:32 -0500 (EST) Received: from smtpin06.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with ESMTP id 71972884AD for ; Tue, 14 Dec 2021 19:43:22 +0000 (UTC) X-FDA: 78917423844.06.963118E Received: from mail-pf1-f171.google.com (mail-pf1-f171.google.com [209.85.210.171]) by imf11.hostedemail.com (Postfix) with ESMTP id 53FC74000A for ; Tue, 14 Dec 2021 19:43:20 +0000 (UTC) Received: by mail-pf1-f171.google.com with SMTP id r130so18755795pfc.1 for ; Tue, 14 Dec 2021 11:43:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=LCilH12wWw0seUa3hiJyDy0VxFX2Q3bA7Y0HXIYHhF8=; b=mgUrMQhC4/CUdwucboxOLaDGWbb/3r/d8db3O9NgfZYUYEd6Zjz2nbba51SL7zLe8Y HoPx+IQ/X0fM2kJmgKk06iLEcvvTYlX2h8Als5lC5pEfulogO+sUqemRF4n6m2Eekf4w CtPoyJGaZ6slsRjff5y3xVucnMlyQBZjuB7TsLW/QfR5HbmU2eCSX+iDyn3uJA04puJa dF//PJEuj31ulpS82MggltzR4G2RUQnzjtNrp/7HOGpfHVW7cNQpoT3ypqVvpPJEUhsf QvGgSrM2kq5yWe5ythTOhC41utztrjpAcYlGjjw1vz9wzYdQhMtOLwSCYyXNwoJoZq7H sX/w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=LCilH12wWw0seUa3hiJyDy0VxFX2Q3bA7Y0HXIYHhF8=; b=THDHhwlrTHhPy11LYwbMl+ydhCDswD9gFTGJssN5A4T6td/Mcvq4Hmp28zINk/WRxk VCiD8Wrv5lyfFLBaV+Bw/vecTZFifUom5/UMsWOdRZveJxJe/ZawH7oJIiv4lAwGM7lM +dpAP4a4quAu6NqaQwc2KYrI75nSWXDbPdUHI+NzSPXpv4UE04F3xZwdMS27eEBcN4/j Ctb36CS2zgehBRTflyPW5RtxS6uivBVpYLXy84h0FiwNPp4J6qf3BZi5pkfW5+nc4Sm/ 1DiyDzW3yihhSIfBMv/M9ViD8wiy5Mp8ZHfO/nUZDybPW6IPAwtT/Ky5iSfUF3JYPTpE vIrQ== X-Gm-Message-State: AOAM530ru4o94SBdrkDScKgdYba5FCCi4hPHeOK3wPu2LdvmvQ2LjRlh 21Kb82QZpbtKPbMpSSBGB4XFw4tkGqngraEfcOw= X-Google-Smtp-Source: ABdhPJx1omsyXEH84uuE4kzYpPBu5v24anF9kQ0616INOFdPlqou2FDes2afxUGAuG2JNukP2+Sny94qEgWXdVVJ7J8= X-Received: by 2002:a63:3f4e:: with SMTP id m75mr4955451pga.587.1639511000707; Tue, 14 Dec 2021 11:43:20 -0800 (PST) MIME-Version: 1.0 References: <20211128035704.270739-1-yury.norov@gmail.com> <20211128035704.270739-3-yury.norov@gmail.com> In-Reply-To: From: Yury Norov Date: Tue, 14 Dec 2021 11:43:09 -0800 Message-ID: Subject: Re: [PATCH 2/9] lib/bitmap: implement bitmap_{empty,full} with bitmap_weight_eq() To: =?UTF-8?B?TWljaGHFgiBNaXJvc8WCYXc=?= Cc: linux-kernel@vger.kernel.org, "James E.J. Bottomley" , "Martin K. Petersen" , "Paul E. McKenney" , "Rafael J. Wysocki" , Alexander Shishkin , Alexey Klimov , Amitkumar Karwar , Andi Kleen , Andrew Lunn , Andrew Morton , Andy Gross , Andy Lutomirski , Andy Shevchenko , Anup Patel , Ard Biesheuvel , Arnaldo Carvalho de Melo , Arnd Bergmann , Borislav Petkov , Catalin Marinas , Christoph Hellwig , Christoph Lameter , Daniel Vetter , Dave Hansen , David Airlie , David Laight , Dennis Zhou , Dinh Nguyen , Geetha sowjanya , Geert Uytterhoeven , Greg Kroah-Hartman , Guo Ren , Hans de Goede , Heiko Carstens , Ian Rogers , Ingo Molnar , Jakub Kicinski , Jason Wessel , Jens Axboe , Jiri Olsa , Jonathan Cameron , Juri Lelli , Kalle Valo , Kees Cook , Krzysztof Kozlowski , Lee Jones , Marc Zyngier , Marcin Wojtas , Mark Gross , Mark Rutland , Matti Vaittinen , Mauro Carvalho Chehab , Mel Gorman , Michael Ellerman , Mike Marciniszyn , Nicholas Piggin , Palmer Dabbelt , Peter Zijlstra , Petr Mladek , Randy Dunlap , Rasmus Villemoes , Roy Pledge , Russell King , Saeed Mahameed , Sagi Grimberg , Sergey Senozhatsky , Solomon Peachy , Stephen Boyd , Stephen Rothwell , Steven Rostedt , Subbaraya Sundeep , Sudeep Holla , Sunil Goutham , Tariq Toukan , Tejun Heo , Thomas Bogendoerfer , Thomas Gleixner , Ulf Hansson , Vincent Guittot , Vineet Gupta , Viresh Kumar , Vivien Didelot , Vlastimil Babka , Will Deacon , bcm-kernel-feedback-list@broadcom.com, kvm@vger.kernel.org, linux-alpha@vger.kernel.org, linux-arm-kernel@lists.infradead.org, linux-crypto@vger.kernel.org, linux-csky@vger.kernel.org, linux-ia64@vger.kernel.org, linux-mips@vger.kernel.org, linux-mm@kvack.org, linux-perf-users@vger.kernel.org, linux-riscv@lists.infradead.org, linux-s390@vger.kernel.org, linux-snps-arc@lists.infradead.org, linuxppc-dev@lists.ozlabs.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=mgUrMQhC; spf=pass (imf11.hostedemail.com: domain of yury.norov@gmail.com designates 209.85.210.171 as permitted sender) smtp.mailfrom=yury.norov@gmail.com; dmarc=pass (policy=none) header.from=gmail.com X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: 53FC74000A X-Stat-Signature: r9b9myi61ccz1j66sxnxo1y3kxwpapfn X-HE-Tag: 1639511000-510160 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 Sun, Nov 28, 2021 at 10:10 AM Micha=C5=82 Miros=C5=82aw wrote: > > On Sat, Nov 27, 2021 at 07:56:57PM -0800, Yury Norov wrote: > > Now as we have bitmap_weight_eq(), switch bitmap_full() and > > bitmap_empty() to using it. > > > > Signed-off-by: Yury Norov > > --- > > include/linux/bitmap.h | 26 ++++++++++---------------- > > 1 file changed, 10 insertions(+), 16 deletions(-) > > > > diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h > > index 996041f771c8..2d951e4dc814 100644 > > --- a/include/linux/bitmap.h > > +++ b/include/linux/bitmap.h > > @@ -386,22 +386,6 @@ static inline int bitmap_subset(const unsigned lon= g *src1, > > return __bitmap_subset(src1, src2, nbits); > > } > > > > -static inline bool bitmap_empty(const unsigned long *src, unsigned nbi= ts) > > -{ > > - if (small_const_nbits(nbits)) > > - return ! (*src & BITMAP_LAST_WORD_MASK(nbits)); > > - > > - return find_first_bit(src, nbits) =3D=3D nbits; > > -} > > Since this is supposed to be an optimization, I would go all the way and > replace this with the trivial implementation instead: > > bool bitmap_empty(long *bits, size_t nbits) > { > for (; nbits >=3D BITS_PER_LONG; ++bits, nbits -=3D BITS_PER_LONG= ) > if (*bits) > return false; > > if (nbits && *bits & BITMAP_LAST_WORD_MASK(nbits)) > return false; > > return true; > } This is what current implementations basically do, based on find_first_bit(= ). I think that for long bitmaps the most time consuming operation is moving data to L1, and for short bitmaps the difference between approaches is barely measurable. But hweght_long on each iteration can't be more effective than the current version. So, I'll drop this patch for v2 and keep things unchanged.