linux-sh.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH v5 00/12] lib/find_bit: fast path for small bitmaps
@ 2021-03-21 21:54 Yury Norov
  2021-03-21 21:54 ` [PATCH 01/12] tools: disable -Wno-type-limits Yury Norov
                   ` (11 more replies)
  0 siblings, 12 replies; 16+ messages in thread
From: Yury Norov @ 2021-03-21 21:54 UTC (permalink / raw)
  To: linux-kernel
  Cc: Yury Norov, linux-m68k, linux-arch, linux-sh, Alexey Klimov,
	Andrew Morton, Andy Shevchenko, Arnd Bergmann, David Sterba,
	Dennis Zhou, Geert Uytterhoeven, Jianpeng Ma, Joe Perches,
	John Paul Adrian Glaubitz, Josh Poimboeuf, Rasmus Villemoes,
	Rich Felker, Stefano Brivio, Wei Yang, Wolfram Sang,
	Yoshinori Sato

Bitmap operations are much simpler and faster in case of small bitmaps
which fit into a single word. In linux/bitmap.c we have a machinery that
allows compiler to replace actual function call with a few instructions
if bitmaps passed into the function are small and their size is known at
compile time.

find_*_bit() API lacks this functionality; but users will benefit from it
a lot. One important example is cpumask subsystem when
NR_CPUS <= BITS_PER_LONG.

v1: https://www.spinics.net/lists/kernel/msg3804727.html
v2: https://www.spinics.net/lists/linux-m68k/msg16945.html
v3: https://www.spinics.net/lists/kernel/msg3837020.html
v4: https://patchwork.kernel.org/project/linux-sh/cover/20210316015424.1999082-1-yury.norov@gmail.com/
v5: - drop BITS_{FIRST,LAST} patch;
    - minor changes.

Yury Norov (12):
  tools: disable -Wno-type-limits
  tools: bitmap: sync function declarations with the kernel
  tools: sync BITMAP_LAST_WORD_MASK() macro with the kernel
  arch: rearrange headers inclusion order in asm/bitops for m68k and sh
  lib: extend the scope of small_const_nbits() macro
  tools: sync small_const_nbits() macro with the kernel
  lib: inline _find_next_bit() wrappers
  tools: sync find_next_bit implementation
  lib: add fast path for find_next_*_bit()
  lib: add fast path for find_first_*_bit() and find_last_bit()
  tools: sync lib/find_bit implementation
  MAINTAINERS: Add entry for the bitmap API

 MAINTAINERS                             |  16 ++++
 arch/m68k/include/asm/bitops.h          |   6 +-
 arch/sh/include/asm/bitops.h            |   5 +-
 include/asm-generic/bitops/find.h       | 108 +++++++++++++++++++++---
 include/asm-generic/bitops/le.h         |  38 ++++++++-
 include/asm-generic/bitsperlong.h       |  12 +++
 include/linux/bitmap.h                  |   8 --
 include/linux/bitops.h                  |  12 ---
 lib/find_bit.c                          |  68 ++-------------
 tools/include/asm-generic/bitops/find.h |  85 +++++++++++++++++--
 tools/include/asm-generic/bitsperlong.h |   3 +
 tools/include/linux/bitmap.h            |  18 ++--
 tools/lib/bitmap.c                      |   4 +-
 tools/lib/find_bit.c                    |  56 +++++-------
 tools/scripts/Makefile.include          |   1 +
 15 files changed, 284 insertions(+), 156 deletions(-)

-- 
2.25.1


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [PATCH v6 00/12] lib/find_bit: fast path for small bitmaps
@ 2021-04-01  0:31 Yury Norov
  2021-04-01  0:31 ` [PATCH 03/12] tools: sync BITMAP_LAST_WORD_MASK() macro with the kernel Yury Norov
  0 siblings, 1 reply; 16+ messages in thread
From: Yury Norov @ 2021-04-01  0:31 UTC (permalink / raw)
  To: linux-kernel, Andrew Morton
  Cc: Yury Norov, linux-m68k, linux-arch, linux-sh, Alexey Klimov,
	Andy Shevchenko, Arnd Bergmann, David Sterba, Dennis Zhou,
	Geert Uytterhoeven, Jianpeng Ma, Joe Perches,
	John Paul Adrian Glaubitz, Josh Poimboeuf, Rasmus Villemoes,
	Rich Felker, Stefano Brivio, Wei Yang, Wolfram Sang,
	Yoshinori Sato

Bitmap operations are much simpler and faster in case of small bitmaps
which fit into a single word. In linux/bitmap.c we have a machinery that
allows compiler to replace actual function call with a few instructions
if bitmaps passed into the function are small and their size is known at
compile time.

find_*_bit() API lacks this functionality; but users will benefit from it
a lot. One important example is cpumask subsystem when
NR_CPUS <= BITS_PER_LONG.

v6 is mostly a resend. The only change comparing to v5 is a fix of
small_const_nbits() synchronization patch.

v1: https://www.spinics.net/lists/kernel/msg3804727.html
v2: https://www.spinics.net/lists/linux-m68k/msg16945.html
v3: https://www.spinics.net/lists/kernel/msg3837020.html
v4: https://patchwork.kernel.org/project/linux-sh/cover/20210316015424.1999082-1-yury.norov@gmail.com/
v5: https://lore.kernel.org/linux-arch/20210321215457.588554-1-yury.norov@gmail.com/T/
v6: - sync small_const_nbits() properly (patch 6).
    - Rasmus' ack added.

Yury Norov (12):
  tools: disable -Wno-type-limits
  tools: bitmap: sync function declarations with the kernel
  tools: sync BITMAP_LAST_WORD_MASK() macro with the kernel
  arch: rearrange headers inclusion order in asm/bitops for m68k and sh
  lib: extend the scope of small_const_nbits() macro
  tools: sync small_const_nbits() macro with the kernel
  lib: inline _find_next_bit() wrappers
  tools: sync find_next_bit implementation
  lib: add fast path for find_next_*_bit()
  lib: add fast path for find_first_*_bit() and find_last_bit()
  tools: sync lib/find_bit implementation
  MAINTAINERS: Add entry for the bitmap API

 MAINTAINERS                             |  16 ++++
 arch/m68k/include/asm/bitops.h          |   6 +-
 arch/sh/include/asm/bitops.h            |   5 +-
 include/asm-generic/bitops/find.h       | 108 +++++++++++++++++++++---
 include/asm-generic/bitops/le.h         |  38 ++++++++-
 include/asm-generic/bitsperlong.h       |  12 +++
 include/linux/bitmap.h                  |   8 --
 include/linux/bitops.h                  |  12 ---
 lib/find_bit.c                          |  68 ++-------------
 tools/include/asm-generic/bitops/find.h |  85 +++++++++++++++++--
 tools/include/asm-generic/bitsperlong.h |   3 +
 tools/include/linux/bitmap.h            |  18 ++--
 tools/lib/bitmap.c                      |   4 +-
 tools/lib/find_bit.c                    |  56 +++++-------
 tools/scripts/Makefile.include          |   1 +
 15 files changed, 284 insertions(+), 156 deletions(-)

-- 
2.25.1


^ permalink raw reply	[flat|nested] 16+ messages in thread

end of thread, other threads:[~2021-04-01  0:33 UTC | newest]

Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-03-21 21:54 [PATCH v5 00/12] lib/find_bit: fast path for small bitmaps Yury Norov
2021-03-21 21:54 ` [PATCH 01/12] tools: disable -Wno-type-limits Yury Norov
2021-03-21 21:54 ` [PATCH 02/12] tools: bitmap: sync function declarations with the kernel Yury Norov
2021-03-21 21:54 ` [PATCH 03/12] tools: sync BITMAP_LAST_WORD_MASK() macro " Yury Norov
2021-03-21 21:54 ` [PATCH 04/12] arch: rearrange headers inclusion order in asm/bitops for m68k and sh Yury Norov
2021-03-21 21:54 ` [PATCH 05/12] lib: extend the scope of small_const_nbits() macro Yury Norov
2021-03-21 21:54 ` [PATCH 06/12] tools: sync small_const_nbits() macro with the kernel Yury Norov
2021-03-22  8:34   ` Rasmus Villemoes
2021-03-24 19:49     ` Yury Norov
2021-03-21 21:54 ` [PATCH 07/12] lib: inline _find_next_bit() wrappers Yury Norov
2021-03-21 21:54 ` [PATCH 08/12] tools: sync find_next_bit implementation Yury Norov
2021-03-21 21:54 ` [PATCH 09/12] lib: add fast path for find_next_*_bit() Yury Norov
2021-03-21 21:54 ` [PATCH 10/12] lib: add fast path for find_first_*_bit() and find_last_bit() Yury Norov
2021-03-21 21:54 ` [PATCH 11/12] tools: sync lib/find_bit implementation Yury Norov
2021-03-21 21:54 ` [PATCH 12/12] MAINTAINERS: Add entry for the bitmap API Yury Norov
2021-04-01  0:31 [PATCH v6 00/12] lib/find_bit: fast path for small bitmaps Yury Norov
2021-04-01  0:31 ` [PATCH 03/12] tools: sync BITMAP_LAST_WORD_MASK() macro with the kernel Yury Norov

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).