[PATCH v2 00/10] Enhance min heap API with non-inline functions and optimizations

From: Kuan-Wei Chiu
Date: Sun Oct 20 2024 - 00:02:35 EST


Add non-inline versions of the min heap API functions in lib/min_heap.c
and updates all users outside of kernel/events/core.c to use these
non-inline versions. To mitigate the performance impact of indirect
function calls caused by the non-inline versions of the swap and
compare functions, a builtin swap has been introduced that swaps
elements based on their size. Additionally, it micro-optimizes the
efficiency of the min heap by pre-scaling the counter, following the
same approach as in lib/sort.c. Documentation for the min heap API has
also been added to the core-api section.

Regards,
Kuan-Wei

---

Changes in v2:
- Added a builtin swap to reduce the performance impact of indirect
function calls.
- Cleaned up duplicate min_heap_callbacks in bcachefs.
- Wrapped documentation at 80 columns.
- Updated Example Usage.
- Included documentation explaining that NULL can be passed to the
swp in min_heap_callbacks to use the builtin swap.

v1: https://lore.kernel.org/lkml/20241013184703.659652-1-visitorckw@xxxxxxxxx

Kuan-Wei Chiu (10):
lib/min_heap: Introduce non-inline versions of min heap API functions
lib min_heap: Optimize min heap by prescaling counters for better
performance
lib min_heap: Avoid indirect function call by providing default swap
lib/test_min_heap: Update min_heap_callbacks to use default builtin
swap
perf/core: Update min_heap_callbacks to use default builtin swap
dm vdo: Update min_heap_callbacks to use default builtin swap
bcache: Update min_heap_callbacks to use default builtin swap
bcachefs: Clean up duplicate min_heap_callbacks declarations
bcachefs: Update min_heap_callbacks to use default builtin swap
Documentation/core-api: Add min heap API introduction

Documentation/core-api/index.rst | 1 +
Documentation/core-api/min_heap.rst | 300 +++++++++++++++++++++++
drivers/md/bcache/Kconfig | 1 +
drivers/md/bcache/alloc.c | 11 +-
drivers/md/bcache/bset.c | 14 +-
drivers/md/bcache/extents.c | 10 +-
drivers/md/bcache/movinggc.c | 10 +-
drivers/md/dm-vdo/Kconfig | 1 +
drivers/md/dm-vdo/repair.c | 2 +-
drivers/md/dm-vdo/slab-depot.c | 10 +-
fs/bcachefs/Kconfig | 1 +
fs/bcachefs/clock.c | 25 +-
fs/bcachefs/ec.c | 19 +-
include/linux/min_heap.h | 357 ++++++++++++++++++++++------
kernel/events/core.c | 15 +-
lib/Kconfig | 3 +
lib/Kconfig.debug | 1 +
lib/Makefile | 1 +
lib/min_heap.c | 70 ++++++
lib/test_min_heap.c | 16 +-
20 files changed, 694 insertions(+), 174 deletions(-)
create mode 100644 Documentation/core-api/min_heap.rst
create mode 100644 lib/min_heap.c

--
2.34.1