From: Yury Norov <yury.norov@gmail.com>
To: linux-kernel@vger.kernel.org, linux-arch@vger.kernel.org,
Benjamin Herrenschmidt <benh@kernel.crashing.org>,
Catalin Marinas <catalin.marinas@arm.com>,
Will Deacon <will@kernel.org>,
Yoshinori Sato <ysato@users.sourceforge.jp>,
Brian Cain <bcain@codeaurora.org>,
Geert Uytterhoeven <geert@linux-m68k.org>,
Thomas Bogendoerfer <tsbogend@alpha.franken.de>,
Jonas Bonn <jonas@southpole.se>,
Stefan Kristiansson <stefan.kristiansson@saunalahti.fi>,
"James E.J. Bottomley" <James.Bottomley@HansenPartnership.com>,
Palmer Dabbelt <palmer@dabbelt.com>,
Heiko Carstens <hca@linux.ibm.com>, Rich Felker <dalias@libc.org>,
David Hildenbrand <david@redhat.com>,
Jaegeuk Kim <jaegeuk@kernel.org>, Arnd Bergmann <arnd@arndb.de>,
Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
Rasmus Villemoes <linux@rasmusvillemoes.dk>,
Andrew Morton <akpm@linux-foundation.org>,
Alexander Lobakin <alobakin@pm.me>,
Samuel Mendoza-Jonas <sam@mendozajonas.com>,
Jakub Kicinski <kuba@kernel.org>,
Daniel Bristot de Oliveira <bristot@redhat.com>,
Alexey Klimov <aklimov@redhat.com>,
Ingo Molnar <mingo@redhat.com>
Cc: Yury Norov <yury.norov@gmail.com>
Subject: [PATCH 5/8] lib: add find_first_and_bit()
Date: Sat, 12 Jun 2021 05:36:36 -0700 [thread overview]
Message-ID: <20210612123639.329047-6-yury.norov@gmail.com> (raw)
In-Reply-To: <20210612123639.329047-1-yury.norov@gmail.com>
Currently find_first_and_bit() is an alias to find_next_and_bit(). However,
it is widely used in cpumask, so it worth to optimize it. This patch adds
its own implementation for find_first_and_bit().
On x86_64 find_bit_benchmark says:
Before (#define find_first_and_bit(...) find_next_and_bit(..., 0):
Start testing find_bit() with random-filled bitmap
[ 140.291468] find_first_and_bit: 46890919 ns, 32671 iterations
Start testing find_bit() with sparse bitmap
[ 140.295028] find_first_and_bit: 7103 ns, 1 iterations
After:
Start testing find_bit() with random-filled bitmap
[ 162.574907] find_first_and_bit: 25045813 ns, 32846 iterations
Start testing find_bit() with sparse bitmap
[ 162.578458] find_first_and_bit: 4900 ns, 1 iterations
(Thanks to Alexey Klimov for thorough testing.)
Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
include/linux/find.h | 27 +++++++++++++++++++++++++++
lib/find_bit.c | 21 +++++++++++++++++++++
lib/find_bit_benchmark.c | 21 +++++++++++++++++++++
3 files changed, 69 insertions(+)
diff --git a/include/linux/find.h b/include/linux/find.h
index ea57f7f38c49..6048f8c97418 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -12,6 +12,8 @@ extern unsigned long _find_next_bit(const unsigned long *addr1,
const unsigned long *addr2, unsigned long nbits,
unsigned long start, unsigned long invert, unsigned long le);
extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size);
+extern unsigned long _find_first_and_bit(const unsigned long *addr1,
+ const unsigned long *addr2, unsigned long size);
extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size);
@@ -123,6 +125,31 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
}
#endif
+#ifndef find_first_and_bit
+/**
+ * find_first_and_bit - find the first set bit in both memory regions
+ * @addr1: The first address to base the search on
+ * @addr2: The second address to base the search on
+ * @size: The bitmap size in bits
+ *
+ * Returns the bit number for the next set bit
+ * If no bits are set, returns @size.
+ */
+static inline
+unsigned long find_first_and_bit(const unsigned long *addr1,
+ const unsigned long *addr2,
+ unsigned long size)
+{
+ if (small_const_nbits(size)) {
+ unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
+
+ return val ? __ffs(val) : size;
+ }
+
+ return _find_first_and_bit(addr1, addr2, size);
+}
+#endif
+
#ifndef find_first_zero_bit
/**
* find_first_zero_bit - find the first cleared bit in a memory region
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 0f8e2e369b1d..1b8e4b2a9cba 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -89,6 +89,27 @@ unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
EXPORT_SYMBOL(_find_first_bit);
#endif
+#ifndef find_first_and_bit
+/*
+ * Find the first set bit in two memory regions.
+ */
+unsigned long _find_first_and_bit(const unsigned long *addr1,
+ const unsigned long *addr2,
+ unsigned long size)
+{
+ unsigned long idx, val;
+
+ for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
+ val = addr1[idx] & addr2[idx];
+ if (val)
+ return min(idx * BITS_PER_LONG + __ffs(val), size);
+ }
+
+ return size;
+}
+EXPORT_SYMBOL(_find_first_and_bit);
+#endif
+
#ifndef find_first_zero_bit
/*
* Find the first cleared bit in a memory region.
diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index 5637c5711db9..db904b57d4b8 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -49,6 +49,25 @@ static int __init test_find_first_bit(void *bitmap, unsigned long len)
return 0;
}
+static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, unsigned long len)
+{
+ static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
+ unsigned long i, cnt;
+ ktime_t time;
+
+ bitmap_copy(cp, bitmap, BITMAP_LEN);
+
+ time = ktime_get();
+ for (cnt = i = 0; i < len; cnt++) {
+ i = find_first_and_bit(cp, bitmap2, len);
+ __clear_bit(i, cp);
+ }
+ time = ktime_get() - time;
+ pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
+
+ return 0;
+}
+
static int __init test_find_next_bit(const void *bitmap, unsigned long len)
{
unsigned long i, cnt;
@@ -129,6 +148,7 @@ static int __init find_bit_test(void)
* traverse only part of bitmap to avoid soft lockup.
*/
test_find_first_bit(bitmap, BITMAP_LEN / 10);
+ test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 2);
test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
pr_err("\nStart testing find_bit() with sparse bitmap\n");
@@ -145,6 +165,7 @@ static int __init find_bit_test(void)
test_find_next_zero_bit(bitmap, BITMAP_LEN);
test_find_last_bit(bitmap, BITMAP_LEN);
test_find_first_bit(bitmap, BITMAP_LEN);
+ test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN);
test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
/*
--
2.30.2
next prev parent reply other threads:[~2021-06-12 12:37 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-06-12 12:36 [PATCH 0/8] all: use find_next_*_bit() instead of find_first_*_bit() where possible Yury Norov
2021-06-12 12:36 ` [PATCH 1/8] bitops: protect find_first_{,zero}_bit properly Yury Norov
2021-06-12 21:38 ` Andy Shevchenko
2021-06-29 1:29 ` Yury Norov
2021-06-12 12:36 ` [PATCH 2/8] bitops: move find_bit_*_le functions from le.h to find.h Yury Norov
2021-06-12 12:36 ` [PATCH 3/8] include: move find.h from asm_generic to linux Yury Norov
2021-06-12 12:36 ` [PATCH RESEND 4/8] arch: remove GENERIC_FIND_FIRST_BIT entirely Yury Norov
2021-06-12 12:36 ` Yury Norov [this message]
2021-06-14 15:45 ` [PATCH 5/8] lib: add find_first_and_bit() Alexey Klimov
2021-06-12 12:36 ` [PATCH 6/8] cpumask: use find_first_and_bit() Yury Norov
2021-06-12 12:36 ` [PATCH 7/8] all: replace find_next{,_zero}_bit with find_first{,_zero}_bit where appropriate Yury Norov
2021-06-12 21:47 ` Andy Shevchenko
2021-06-13 0:32 ` Yury Norov
[not found] ` <CAHp75VeXJcPai=w3Fbx11TPf_CZTusD6U_E2R+XSaCcebV7uBw@mail.gmail.com>
2021-06-15 1:07 ` Andrew Morton
2021-06-12 12:36 ` [PATCH 8/8] tools: sync tools/bitmap with mother linux Yury Norov
2021-06-13 23:16 ` [PATCH] cpumask: replace cpumask_next_* with cpumask_first_* where appropriate Yury Norov
2021-06-29 1:48 ` [PATCH 0/8] all: use find_next_*_bit() instead of find_first_*_bit() where possible Yury Norov
2021-06-29 16:18 ` Andy Shevchenko
2021-07-28 15:00 ` Yury Norov
2021-07-28 15:13 ` Joe Perches
2021-07-28 15:55 ` Yury Norov
2021-07-28 16:06 ` Joe Perches
2021-07-28 16:28 ` Yury Norov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20210612123639.329047-6-yury.norov@gmail.com \
--to=yury.norov@gmail.com \
--cc=James.Bottomley@HansenPartnership.com \
--cc=aklimov@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=alobakin@pm.me \
--cc=andriy.shevchenko@linux.intel.com \
--cc=arnd@arndb.de \
--cc=bcain@codeaurora.org \
--cc=benh@kernel.crashing.org \
--cc=bristot@redhat.com \
--cc=catalin.marinas@arm.com \
--cc=dalias@libc.org \
--cc=david@redhat.com \
--cc=geert@linux-m68k.org \
--cc=hca@linux.ibm.com \
--cc=jaegeuk@kernel.org \
--cc=jonas@southpole.se \
--cc=kuba@kernel.org \
--cc=linux-arch@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux@rasmusvillemoes.dk \
--cc=mingo@redhat.com \
--cc=palmer@dabbelt.com \
--cc=sam@mendozajonas.com \
--cc=stefan.kristiansson@saunalahti.fi \
--cc=tsbogend@alpha.franken.de \
--cc=will@kernel.org \
--cc=ysato@users.sourceforge.jp \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.