From: Robert Pang <robertpang@google.com>
To: Coly Li <colyli@kernel.org>,
Kent Overstreet <kent.overstreet@linux.dev>,
linux-bcache@vger.kernel.org
Cc: Robert Pang <robertpang@google.com>,
Kuan-Wei Chiu <visitorckw@gmail.com>
Subject: [PATCH 1/3] lib min_heap: refactor min_heap to allow the alternative sift-down function to be used
Date: Fri, 6 Jun 2025 00:19:43 -0700 [thread overview]
Message-ID: <20250606071959.1685079-2-robertpang@google.com> (raw)
In-Reply-To: <20250606071959.1685079-1-robertpang@google.com>
Refactor these min_heap's internal functions that require sifting down elements
to take the sift-down function to use. This change will allow for the use of
alternative sift-down strategies, potentially offering significant performance
improvements for certain data distributions compared to the current bottom-up
approach.
- heapify_all
- heap_pop
- heap_pop_push
- heap_del
Signed-off-by: Robert Pang <robertpang@google.com>
---
include/linux/min_heap.h | 60 ++++++++++++++++++++++++++--------------
lib/min_heap.c | 24 ++++++++++------
2 files changed, 56 insertions(+), 28 deletions(-)
diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h
index 1160bed6579e..1fe6772170e7 100644
--- a/include/linux/min_heap.h
+++ b/include/linux/min_heap.h
@@ -322,22 +322,27 @@ void __min_heap_sift_up_inline(min_heap_char *heap, size_t elem_size, size_t idx
/* Floyd's approach to heapification that is O(nr). */
static __always_inline
void __min_heapify_all_inline(min_heap_char *heap, size_t elem_size,
- const struct min_heap_callbacks *func, void *args)
+ const struct min_heap_callbacks *func, void *args,
+ void (*sift_down)(min_heap_char *heap, int pos, size_t elem_size,
+ const struct min_heap_callbacks *func, void *args))
{
int i;
for (i = heap->nr / 2 - 1; i >= 0; i--)
- __min_heap_sift_down_inline(heap, i, elem_size, func, args);
+ sift_down(heap, i, elem_size, func, args);
}
#define min_heapify_all_inline(_heap, _func, _args) \
__min_heapify_all_inline(container_of(&(_heap)->nr, min_heap_char, nr), \
- __minheap_obj_size(_heap), _func, _args)
+ __minheap_obj_size(_heap), _func, _args, \
+ __min_heap_sift_down_inline)
/* Remove minimum element from the heap, O(log2(nr)). */
static __always_inline
bool __min_heap_pop_inline(min_heap_char *heap, size_t elem_size,
- const struct min_heap_callbacks *func, void *args)
+ const struct min_heap_callbacks *func, void *args,
+ void (*sift_down)(min_heap_char *heap, int pos, size_t elem_size,
+ const struct min_heap_callbacks *func, void *args))
{
void *data = heap->data;
@@ -347,14 +352,15 @@ bool __min_heap_pop_inline(min_heap_char *heap, size_t elem_size,
/* Place last element at the root (position 0) and then sift down. */
heap->nr--;
memcpy(data, data + (heap->nr * elem_size), elem_size);
- __min_heap_sift_down_inline(heap, 0, elem_size, func, args);
+ sift_down(heap, 0, elem_size, func, args);
return true;
}
#define min_heap_pop_inline(_heap, _func, _args) \
__min_heap_pop_inline(container_of(&(_heap)->nr, min_heap_char, nr), \
- __minheap_obj_size(_heap), _func, _args)
+ __minheap_obj_size(_heap), _func, _args, \
+ __min_heap_sift_down_inline)
/*
* Remove the minimum element and then push the given element. The
@@ -363,15 +369,18 @@ bool __min_heap_pop_inline(min_heap_char *heap, size_t elem_size,
*/
static __always_inline
void __min_heap_pop_push_inline(min_heap_char *heap, const void *element, size_t elem_size,
- const struct min_heap_callbacks *func, void *args)
+ const struct min_heap_callbacks *func, void *args,
+ void (*sift_down)(min_heap_char *heap, int pos, size_t elem_size,
+ const struct min_heap_callbacks *func, void *args))
{
memcpy(heap->data, element, elem_size);
- __min_heap_sift_down_inline(heap, 0, elem_size, func, args);
+ sift_down(heap, 0, elem_size, func, args);
}
#define min_heap_pop_push_inline(_heap, _element, _func, _args) \
__min_heap_pop_push_inline(container_of(&(_heap)->nr, min_heap_char, nr), _element, \
- __minheap_obj_size(_heap), _func, _args)
+ __minheap_obj_size(_heap), _func, _args, \
+ __min_heap_sift_down_inline)
/* Push an element on to the heap, O(log2(nr)). */
static __always_inline
@@ -402,7 +411,9 @@ bool __min_heap_push_inline(min_heap_char *heap, const void *element, size_t ele
/* Remove ith element from the heap, O(log2(nr)). */
static __always_inline
bool __min_heap_del_inline(min_heap_char *heap, size_t elem_size, size_t idx,
- const struct min_heap_callbacks *func, void *args)
+ const struct min_heap_callbacks *func, void *args,
+ void (*sift_down)(min_heap_char *heap, int pos, size_t elem_size,
+ const struct min_heap_callbacks *func, void *args))
{
void *data = heap->data;
void (*swp)(void *lhs, void *rhs, void *args) = func->swp;
@@ -419,14 +430,15 @@ bool __min_heap_del_inline(min_heap_char *heap, size_t elem_size, size_t idx,
return true;
do_swap(data + (idx * elem_size), data + (heap->nr * elem_size), elem_size, swp, args);
__min_heap_sift_up_inline(heap, elem_size, idx, func, args);
- __min_heap_sift_down_inline(heap, idx, elem_size, func, args);
+ sift_down(heap, idx, elem_size, func, args);
return true;
}
#define min_heap_del_inline(_heap, _idx, _func, _args) \
__min_heap_del_inline(container_of(&(_heap)->nr, min_heap_char, nr), \
- __minheap_obj_size(_heap), _idx, _func, _args)
+ __minheap_obj_size(_heap), _idx, _func, _args, \
+ __min_heap_sift_down_inline))
void __min_heap_init(min_heap_char *heap, void *data, int size);
void *__min_heap_peek(struct min_heap_char *heap);
@@ -436,15 +448,23 @@ void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size,
void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx,
const struct min_heap_callbacks *func, void *args);
void __min_heapify_all(min_heap_char *heap, size_t elem_size,
- const struct min_heap_callbacks *func, void *args);
+ const struct min_heap_callbacks *func, void *args,
+ void (*sift_down)(min_heap_char *heap, int pos, size_t elem_size,
+ const struct min_heap_callbacks *func, void *args));
bool __min_heap_pop(min_heap_char *heap, size_t elem_size,
- const struct min_heap_callbacks *func, void *args);
+ const struct min_heap_callbacks *func, void *args,
+ void (*sift_down)(min_heap_char *heap, int pos, size_t elem_size,
+ const struct min_heap_callbacks *func, void *args));
void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t elem_size,
- const struct min_heap_callbacks *func, void *args);
+ const struct min_heap_callbacks *func, void *args,
+ void (*sift_down)(min_heap_char *heap, int pos, size_t elem_size,
+ const struct min_heap_callbacks *func, void *args));
bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size,
const struct min_heap_callbacks *func, void *args);
bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx,
- const struct min_heap_callbacks *func, void *args);
+ const struct min_heap_callbacks *func, void *args,
+ void (*sift_down)(min_heap_char *heap, int pos, size_t elem_size,
+ const struct min_heap_callbacks *func, void *args));
#define min_heap_init(_heap, _data, _size) \
__min_heap_init(container_of(&(_heap)->nr, min_heap_char, nr), _data, _size)
@@ -460,18 +480,18 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx,
__minheap_obj_size(_heap), _idx, _func, _args)
#define min_heapify_all(_heap, _func, _args) \
__min_heapify_all(container_of(&(_heap)->nr, min_heap_char, nr), \
- __minheap_obj_size(_heap), _func, _args)
+ __minheap_obj_size(_heap), _func, _args, __min_heap_sift_down)
#define min_heap_pop(_heap, _func, _args) \
__min_heap_pop(container_of(&(_heap)->nr, min_heap_char, nr), \
- __minheap_obj_size(_heap), _func, _args)
+ __minheap_obj_size(_heap), _func, _args, __min_heap_sift_down)
#define min_heap_pop_push(_heap, _element, _func, _args) \
__min_heap_pop_push(container_of(&(_heap)->nr, min_heap_char, nr), _element, \
- __minheap_obj_size(_heap), _func, _args)
+ __minheap_obj_size(_heap), _func, _args, __min_heap_sift_down)
#define min_heap_push(_heap, _element, _func, _args) \
__min_heap_push(container_of(&(_heap)->nr, min_heap_char, nr), _element, \
__minheap_obj_size(_heap), _func, _args)
#define min_heap_del(_heap, _idx, _func, _args) \
__min_heap_del(container_of(&(_heap)->nr, min_heap_char, nr), \
- __minheap_obj_size(_heap), _idx, _func, _args)
+ __minheap_obj_size(_heap), _idx, _func, _args, __min_heap_sift_down)
#endif /* _LINUX_MIN_HEAP_H */
diff --git a/lib/min_heap.c b/lib/min_heap.c
index 4485372ff3b1..4ec425788783 100644
--- a/lib/min_heap.c
+++ b/lib/min_heap.c
@@ -35,23 +35,29 @@ void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx,
EXPORT_SYMBOL(__min_heap_sift_up);
void __min_heapify_all(min_heap_char *heap, size_t elem_size,
- const struct min_heap_callbacks *func, void *args)
+ const struct min_heap_callbacks *func, void *args,
+ void (*sift_down)(min_heap_char *heap, int pos, size_t elem_size,
+ const struct min_heap_callbacks *func, void *args))
{
- __min_heapify_all_inline(heap, elem_size, func, args);
+ __min_heapify_all_inline(heap, elem_size, func, args, sift_down);
}
EXPORT_SYMBOL(__min_heapify_all);
bool __min_heap_pop(min_heap_char *heap, size_t elem_size,
- const struct min_heap_callbacks *func, void *args)
+ const struct min_heap_callbacks *func, void *args,
+ void (*sift_down)(min_heap_char *heap, int pos, size_t elem_size,
+ const struct min_heap_callbacks *func, void *args))
{
- return __min_heap_pop_inline(heap, elem_size, func, args);
+ return __min_heap_pop_inline(heap, elem_size, func, args, sift_down);
}
EXPORT_SYMBOL(__min_heap_pop);
void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t elem_size,
- const struct min_heap_callbacks *func, void *args)
+ const struct min_heap_callbacks *func, void *args,
+ void (*sift_down)(min_heap_char *heap, int pos, size_t elem_size,
+ const struct min_heap_callbacks *func, void *args))
{
- __min_heap_pop_push_inline(heap, element, elem_size, func, args);
+ __min_heap_pop_push_inline(heap, element, elem_size, func, args, sift_down);
}
EXPORT_SYMBOL(__min_heap_pop_push);
@@ -63,8 +69,10 @@ bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size,
EXPORT_SYMBOL(__min_heap_push);
bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx,
- const struct min_heap_callbacks *func, void *args)
+ const struct min_heap_callbacks *func, void *args,
+ void (*sift_down)(min_heap_char *heap, int pos, size_t elem_size,
+ const struct min_heap_callbacks *func, void *args))
{
- return __min_heap_del_inline(heap, elem_size, idx, func, args);
+ return __min_heap_del_inline(heap, elem_size, idx, func, args, sift_down);
}
EXPORT_SYMBOL(__min_heap_del);
--
2.50.0.rc1.591.g9c95f17f64-goog
next prev parent reply other threads:[~2025-06-06 7:20 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-06-06 7:19 [PATCH 0/3] bcache: Fix the tail IO latency regression due to the use of lib min_heap Robert Pang
2025-06-06 7:19 ` Robert Pang [this message]
2025-06-06 7:19 ` [PATCH 2/3] lib min_heap: add alternative APIs that use the conventional top-down strategy to sift down elements Robert Pang
2025-06-06 12:52 ` Kuan-Wei Chiu
2025-06-06 7:19 ` [PATCH 3/3] bcache: Fix the tail IO latency regression due to the use of lib min_heap Robert Pang
2025-06-06 13:01 ` Kuan-Wei Chiu
2025-06-10 12:44 ` Robert Pang
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=20250606071959.1685079-2-robertpang@google.com \
--to=robertpang@google.com \
--cc=colyli@kernel.org \
--cc=kent.overstreet@linux.dev \
--cc=linux-bcache@vger.kernel.org \
--cc=visitorckw@gmail.com \
/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.