| Message ID | 20241020040200.939973-1-visitorckw@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | Enhance min heap API with non-inline functions and optimizations | expand |
On Sun, Oct 20, 2024 at 12:01:50PM +0800, Kuan-Wei Chiu wrote: > 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. What tree (and commit) this series is based on? Confused...
On Mon, Oct 21, 2024 at 04:33:37PM +0700, Bagas Sanjaya wrote: > On Sun, Oct 20, 2024 at 12:01:50PM +0800, Kuan-Wei Chiu wrote: > > 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. > > What tree (and commit) this series is based on? > > Confused... > This patchset is based on Linus' tree, commit 715ca9dd687f ("Merge tag 'io_uring-6.12-20241019' of git://git.kernel.dk/linux"). Since it touches multiple subsystems, I'm not entirely sure which tree I should base it on. Should it be linux-next, perhaps? Regards, Kuan-Wei
On Sun, Oct 20, 2024 at 12:01:50PM +0800, Kuan-Wei Chiu wrote: > 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. > Hi Kent, FWIW, here are the bcachefs CI test results for this patch series: https://evilpiepirate.org/~testdashboard/ci?user=visitorckw&branch=min-heap-update Regards, Kuan-Wei
On Mon, Oct 21, 2024 at 09:47:45PM +0800, Kuan-Wei Chiu wrote: > On Mon, Oct 21, 2024 at 04:33:37PM +0700, Bagas Sanjaya wrote: > > On Sun, Oct 20, 2024 at 12:01:50PM +0800, Kuan-Wei Chiu wrote: > > > 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. > > > > What tree (and commit) this series is based on? > > > > Confused... > > > This patchset is based on Linus' tree, commit 715ca9dd687f ("Merge tag > 'io_uring-6.12-20241019' of git://git.kernel.dk/linux"). Since it > touches multiple subsystems, I'm not entirely sure which tree I should > base it on. Should it be linux-next, perhaps? Nope. Anyway, series applied for docs review. Thanks!
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@gmail.com 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