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
