bcache: Fix the tail IO latency regression due to the use of lib min_heap
Subsystems (3)
cover bcache: Fix the tail IO latency regression due to the use of lib min_heap
This patch series reverts bcache to its original top-down heap sifting strategy for LRG cache replacement, which fixes a tail I/O latency regression.
Robert Pang (3):
lib min_heap: refactor min_heap to allow the alternative sift-down
function to be used
lib min_heap: add alternative APIs that use the conventional top-down
strategy to sift down elements
bcache: Fix the tail IO latency regression due to the use of lib
min_heap
drivers/md/bcache/alloc.c | 14 ++-- include/linux/min_heap.h | 135 ++++++++++++++++++++++++++++++++------ lib/min_heap.c | 31 ++++++--- 3 files changed, 145 insertions(+), 35 deletions(-)
Signature · 1 line
2.50.0.rc1.591.g9c95f17f64-goog
PATCH 1/3 lib min_heap: refactor min_heap to allow the alternative sift-down function to be used
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
--- include/linux/min_heap.h | 60 ++++++++++++++++++++++++++-------------- lib/min_heap.c | 24 ++++++++++------ 2 files changed, 56 insertions(+), 28 deletions(-)
include/linux/min_heap.h +40 -20
@@ -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 */
lib/min_heap.c +16 -8
@@ -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);
Signature · 1 line
2.50.0.rc1.591.g9c95f17f64-goog
PATCH 2/3 lib min_heap: add alternative APIs that use the conventional top-down strategy to sift down elements
In reply to Robert PangAdd these min_heap functions that re-introduce the conventional top-down strategy to sift down elements. This strategy offers significant performance improvements for data that are mostly identical. [1]
- heapify_all_top_down
- heap_pop_top_down
- heap_pop_push_top_down
- heap_del_top_down
--- include/linux/min_heap.h | 75 ++++++++++++++++++++++++++++++++++++++++ lib/min_heap.c | 7 ++++ 2 files changed, 82 insertions(+)
include/linux/min_heap.h +75 -0
@@ -494,4 +494,79 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx,__min_heap_del (container_of (&(_heap)->nr, min_heap_char, nr), \ __minheap_obj_size(_heap), _idx, _func, _args, __min_heap_sift_down) +static __always_inline +void __min_heap_sift_down_top_down_inline(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; +/* pre-scale counters for performance */ +size_t a = pos * elem_size; +size_t b, c, d, smallest; +size_t n = heap->nr * elem_size; + +if (!swp) + swp =select_swap_func (data, elem_size); + +for (;;) { +if (2 * a + elem_size >= n) +break ; + + c =2 * a + elem_size; + b = a; + smallest = b; +if (func->less (data + c, data + smallest, args)) + smallest = c; + +if (c + elem_size < n) { + d = c + elem_size; +if (func->less (data + d, data + smallest, args)) + smallest = d; + } +if (smallest == b) +break ; +do_swap (data + smallest, data + b, elem_size, swp, args); + a = (smallest == c) ? c : d; + } +} + +#define min_heap_sift_down_top_down_inline (_heap, _pos, _func, _args) \ + __min_heap_sift_down_top_down_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ + _pos, __minheap_obj_size(_heap), _func, _args) +#define min_heapify_all_top_down_inline (_heap, _func, _args) \ + __min_heapify_all_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _func, _args, \ + __min_heap_sift_down_top_down_inline) +#define min_heap_pop_top_down_inline (_heap, _func, _args) \ + __min_heap_pop_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _func, _args, \ + __min_heap_sift_down_top_down_inline) +#define min_heap_pop_push_top_down_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, \ + __min_heap_sift_down_top_down_inline) +#define min_heap_del_top_down_inline (_heap, _idx, _func, _args) \ + __min_heap_del_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _idx, _func, _args, \ + __min_heap_sift_down_top_down_inline)) + +void __min_heap_sift_down_top_down (min_heap_char *heap,int pos,size_t elem_size, +const struct min_heap_callbacks *func,void *args); + +#define min_heap_sift_down_top_down (_heap, _pos, _func, _args) \ + __min_heap_sift_down(container_of(&(_heap)->nr, min_heap_char, nr), _pos, \ + __minheap_obj_size(_heap), _func, _args) +#define min_heapify_all_top_down (_heap, _func, _args) \ + __min_heapify_all(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _func, _args, __min_heap_sift_down_top_down) +#define min_heap_pop_top_down (_heap, _func, _args) \ + __min_heap_pop(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _func, _args, __min_heap_sift_down_top_down) +#define min_heap_pop_push_top_down (_heap, _element, _func, _args) \ + __min_heap_pop_push(container_of(&(_heap)->nr, min_heap_char, nr), _element, \ + __minheap_obj_size(_heap), _func, _args, __min_heap_sift_down_top_down) +#define min_heap_del_top_down (_heap, _idx, _func, _args) \ + __min_heap_del(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _idx, _func, _args, __min_heap_sift_down_top_down) +#endif /* _LINUX_MIN_HEAP_H */
lib/min_heap.c +7 -0
@@ -27,6 +27,13 @@ void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size, }EXPORT_SYMBOL (__min_heap_sift_down); +void __min_heap_sift_down_top_down (min_heap_char *heap,int pos,size_t elem_size, +const struct min_heap_callbacks *func,void *args) +{ +__min_heap_sift_down_top_down_inline (heap, pos, elem_size, func, args); +} +EXPORT_SYMBOL (__min_heap_sift_down_top_down); +void __min_heap_sift_up (min_heap_char *heap,size_t elem_size,size_t idx,const struct min_heap_callbacks *func,void *args) {
Signature · 1 line
2.50.0.rc1.591.g9c95f17f64-goog
Kuan-Wei Chiu
maintainerRe: [PATCH 2/3] lib min_heap: add alternative APIs that use the conventional top-down strategy to sift down elements
Quoted 10 lines · Robert Pang
Add these
min_heapfunctions that re-introduce the conventional top-down strategy to sift down elements. This strategy offers significant performance improvements for data that are mostly identical. [1]-
heapify_all_top_down
-heap_pop_top_down
-heap_pop_push_top_down
-heap_del_top_down
Nit: I'd prefer using a Link: tag here.
Quoted 40 lines
Signed-off-by Robert Pang <[email protected]>--- include/linux/min_heap.h | 75 ++++++++++++++++++++++++++++++++++++++++ lib/min_heap.c | 7 ++++ 2 files changed, 82 insertions(+)include/linux/min_heap.h +25
-0@@ -494,4 +494,79 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx,__min_heap_del (container_of (&(_heap)->nr, min_heap_char, nr), \ __minheap_obj_size(_heap), _idx, _func, _args, __min_heap_sift_down) +static __always_inline +void __min_heap_sift_down_top_down_inline(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; +/* pre-scale counters for performance */ +size_t a = pos * elem_size; +size_t b, c, d, smallest; +size_t n = heap->nr * elem_size; + +if (!swp) + swp =select_swap_func (data, elem_size); + +for (;;) { +if (2 * a + elem_size >= n) +break ; + + c =2 * a + elem_size; + b = a; + smallest = b; +if (func->less (data + c, data + smallest, args)) + smallest = c; + +if (c + elem_size < n) {
include/linux/min_heap.h bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, · line 531
Quoted 10 lines
include/linux/min_heap.h +10
-0+ d = c + elem_size; +if (func->less (data + d, data + smallest, args)) + smallest = d; + } +if (smallest == b) +break ; +do_swap (data + smallest, data + b, elem_size, swp, args); + a = (smallest == c) ? c : d; + } +}
The logic looks correct, but we actually only need variables a, b, and c. The use of d and the extra nested if seem unnecessary. I think the following version is shorter and easier to understand:
for (;;) {
b = 2 * a + elem_size;
c = b + elem_size;
smallest = a;
if (b >= n)
break;
if (func->less(data + b, data + smallest, args))
smallest = b;
if (c < n && func->less(data + c, data + smallest, args))
smallest = c;
if (smallest == a)
break;
do_swap(data + a, data + smallest, elem_size, swp, args);
a = smallest;
}Quoted 30 lines
include/linux/min_heap.h +30
-0+ +#define min_heap_sift_down_top_down_inline (_heap, _pos, _func, _args) \ + __min_heap_sift_down_top_down_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ + _pos, __minheap_obj_size(_heap), _func, _args) +#define min_heapify_all_top_down_inline (_heap, _func, _args) \ + __min_heapify_all_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _func, _args, \ + __min_heap_sift_down_top_down_inline) +#define min_heap_pop_top_down_inline (_heap, _func, _args) \ + __min_heap_pop_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _func, _args, \ + __min_heap_sift_down_top_down_inline) +#define min_heap_pop_push_top_down_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, \ + __min_heap_sift_down_top_down_inline) +#define min_heap_del_top_down_inline (_heap, _idx, _func, _args) \ + __min_heap_del_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _idx, _func, _args, \ + __min_heap_sift_down_top_down_inline)) + +void __min_heap_sift_down_top_down (min_heap_char *heap,int pos,size_t elem_size, +const struct min_heap_callbacks *func,void *args); + +#define min_heap_sift_down_top_down (_heap, _pos, _func, _args) \ + __min_heap_sift_down(container_of(&(_heap)->nr, min_heap_char, nr), _pos, \ + __minheap_obj_size(_heap), _func, _args) +#define min_heapify_all_top_down (_heap, _func, _args) \ + __min_heapify_all(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _func, _args, __min_heap_sift_down_top_down)
include/linux/min_heap.h bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, · line 571
Quoted 10 lines
include/linux/min_heap.h +10
-0+#define min_heap_pop_top_down (_heap, _func, _args) \ + __min_heap_pop(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _func, _args, __min_heap_sift_down_top_down) +#define min_heap_pop_push_top_down (_heap, _element, _func, _args) \ + __min_heap_pop_push(container_of(&(_heap)->nr, min_heap_char, nr), _element, \ + __minheap_obj_size(_heap), _func, _args, __min_heap_sift_down_top_down) +#define min_heap_del_top_down (_heap, _idx, _func, _args) \ + __min_heap_del(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _idx, _func, _args, __min_heap_sift_down_top_down) +
I think we should document in Documentation/core-api/min_heap.rst why the *_top_down variants exist and how to choose between them. Otherwise, it could be confusing for future users.
Regards,
Kuan-Wei
Quoted 22 lines
include/linux/min_heap.h +0
-0#endif /* _LINUX_MIN_HEAP_H */ lib/min_heap.c +7
-0@@ -27,6 +27,13 @@ void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size, }EXPORT_SYMBOL (__min_heap_sift_down); +void __min_heap_sift_down_top_down (min_heap_char *heap,int pos,size_t elem_size, +const struct min_heap_callbacks *func,void *args) +{ +__min_heap_sift_down_top_down_inline (heap, pos, elem_size, func, args); +} +EXPORT_SYMBOL (__min_heap_sift_down_top_down); +void __min_heap_sift_up (min_heap_char *heap,size_t elem_size,size_t idx,const struct min_heap_callbacks *func,void *args) {Signature · 1 line
2.50.0.rc1.591.g9c95f17f64-goog
PATCH 3/3 bcache: Fix the tail IO latency regression due to the use of lib min_heap
In reply to Robert PangIn commit "lib/min_heap: introduce non-inline versions of min heap API functions" (92a8b22), bcache migrates to the generic lib min_heap for all heap operations. This causes sizeable the tail IO latency regression during the cache replacement.
This commit updates invalidate_buckets_lru() to use the alternative APIs that sift down elements using the top-down approach like bcache's own original heap implementation.
--- drivers/md/bcache/alloc.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-)
drivers/md/bcache/alloc.c +7 -7
@@ -207,15 +207,15 @@ static void invalidate_buckets_lru(struct cache *ca)if (!bch_can_invalidate_bucket (ca, b))continue ; -if (!min_heap_full (&ca->heap)) -min_heap_push (&ca->heap, &b, &bucket_max_cmp_callback, ca); -else if (!new_bucket_max_cmp (&b,min_heap_peek (&ca->heap), ca)) { +if (!min_heap_full_inline (&ca->heap)) +min_heap_push_inline (&ca->heap, &b, &bucket_max_cmp_callback, ca); +else if (!new_bucket_max_cmp (&b,min_heap_peek_inline (&ca->heap), ca)) { ca->heap.data[0 ] = b; -min_heap_sift_down (&ca->heap,0 , &bucket_max_cmp_callback, ca); +min_heap_sift_down_top_down_inline (&ca->heap,0 , &bucket_max_cmp_callback, ca); } } -min_heapify_all (&ca->heap, &bucket_min_cmp_callback, ca); +min_heapify_all_top_down_inline (&ca->heap, &bucket_min_cmp_callback, ca);while (!fifo_full (&ca->free_inc)) {if (!ca->heap.nr) {
@@ -227,8 +227,8 @@ static void invalidate_buckets_lru(struct cache *ca)wake_up_gc (ca->set);return ; } - b =min_heap_peek (&ca->heap)[0 ]; -min_heap_pop (&ca->heap, &bucket_min_cmp_callback, ca); + b =min_heap_peek_inline (&ca->heap)[0 ]; +min_heap_pop_top_down_inline (&ca->heap, &bucket_min_cmp_callback, ca);bch_invalidate_one_bucket (ca, b); }
Signature · 1 line
2.50.0.rc1.591.g9c95f17f64-goog
Kuan-Wei Chiu
maintainerQuoted 3 lines · Robert Pang
In commit "
lib/min_heap: introduce non-inline versions of min heap API functions" (92a8b22), bcache migrates to the generic libmin_heapfor all heap operations. This causes sizeable the tail IO latency regression during the cache replacement.
Nit: According to the documentation, I'd prefer referencing the commit like this:
92a8b224b833 ("lib/min_heap: introduce non-inline versions of min heap API functions")
https://docs.kernel.org/process/submitting-patches.html#describe-your-changes
Also, if the regression is caused by the heapify method, shouldn't the commit that introduced it be 866898efbb25 ("bcache: remove heap-related macros and switch to generic min_heap") ?
Quoted 17 lines
This commit updates
invalidate_buckets_lru()to use the alternative APIs that sift down elements using the top-down approach like bcache's own original heap implementation.Signed-off-by Robert Pang <[email protected]>--- drivers/md/bcache/alloc.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-)drivers/md/bcache/alloc.c +0
-0
drivers/md/bcache/alloc.c static void invalidate_buckets_lru(struct cache *ca) · line 211
Quoted 8 lines
drivers/md/bcache/alloc.c +2
-3@@ -207,15 +207,15 @@ static void invalidate_buckets_lru(struct cache *ca)if (!bch_can_invalidate_bucket (ca, b))continue ; -if (!min_heap_full (&ca->heap)) -min_heap_push (&ca->heap, &b, &bucket_max_cmp_callback, ca); -else if (!new_bucket_max_cmp (&b,min_heap_peek (&ca->heap), ca)) { +if (!min_heap_full_inline (&ca->heap)) +min_heap_push_inline (&ca->heap, &b, &bucket_max_cmp_callback, ca);
If the regression is caused by the heapify method rather than the inline vs non-inline change, is it necessary to switch to the non-inline version here?
Regards,
Kuan-Wei
Quoted 26 lines
drivers/md/bcache/alloc.c +5
-4+else if (!new_bucket_max_cmp (&b,min_heap_peek_inline (&ca->heap), ca)) { ca->heap.data[0 ] = b; -min_heap_sift_down (&ca->heap,0 , &bucket_max_cmp_callback, ca); +min_heap_sift_down_top_down_inline (&ca->heap,0 , &bucket_max_cmp_callback, ca); } } -min_heapify_all (&ca->heap, &bucket_min_cmp_callback, ca); +min_heapify_all_top_down_inline (&ca->heap, &bucket_min_cmp_callback, ca);while (!fifo_full (&ca->free_inc)) {if (!ca->heap.nr) {@@ -227,8 +227,8 @@ static void invalidate_buckets_lru(struct cache *ca)wake_up_gc (ca->set);return ; } - b =min_heap_peek (&ca->heap)[0 ]; -min_heap_pop (&ca->heap, &bucket_min_cmp_callback, ca); + b =min_heap_peek_inline (&ca->heap)[0 ]; +min_heap_pop_top_down_inline (&ca->heap, &bucket_min_cmp_callback, ca);bch_invalidate_one_bucket (ca, b); }Signature · 1 line
2.50.0.rc1.591.g9c95f17f64-goog
When I tested this patch series initially, merely switching to the traditional top-down sift-down alone did not resolve the latency regression fully. It requires both the top-down sift-down plus inlining together to match the original latency numbers before the migration to lib/min_heap API. As I understand, the invalidate_buckets_lru() is performance-critical and requires both optimizations.
Best regards
Robert
Quoted 76 lines · Kuan-Wei Chiu
Quoted 3 lines · Robert Pang
In commit "
lib/min_heap: introduce non-inline versions of min heap API functions" (92a8b22), bcache migrates to the generic libmin_heapfor all heap operations. This causes sizeable the tail IO latency regression during the cache replacement.Nit: According to the documentation, I'd prefer referencing the commit like this:
92a8b224b833("lib/min_heap: introduce non-inline versions of min heap API functions")
https://docs.kernel.org/process/submitting-patches.html#describe-your-changesAlso, if the regression is caused by the heapify method, shouldn't the commit that introduced it be
866898efbb25("bcache: remove heap-related macros and switch to genericmin_heap") ?Quoted 17 lines
This commit updates
invalidate_buckets_lru()to use the alternative APIs that sift down elements using the top-down approach like bcache's own original heap implementation.Signed-off-by Robert Pang <[email protected]>--- drivers/md/bcache/alloc.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-)drivers/md/bcache/alloc.c +0
-0drivers/md/bcache/alloc.c static void invalidate_buckets_lru(struct cache *ca) · line 211
Quoted 8 lines
drivers/md/bcache/alloc.c +2
-3@@ -207,15 +207,15 @@ static void invalidate_buckets_lru(struct cache *ca)if (!bch_can_invalidate_bucket (ca, b))continue ; -if (!min_heap_full (&ca->heap)) -min_heap_push (&ca->heap, &b, &bucket_max_cmp_callback, ca); -else if (!new_bucket_max_cmp (&b,min_heap_peek (&ca->heap), ca)) { +if (!min_heap_full_inline (&ca->heap)) +min_heap_push_inline (&ca->heap, &b, &bucket_max_cmp_callback, ca);If the regression is caused by the heapify method rather than the inline vs non-inline change, is it necessary to switch to the non-inline version here?
Regards,
Kuan-WeiQuoted 26 lines
drivers/md/bcache/alloc.c +5
-5+else if (!new_bucket_max_cmp (&b,min_heap_peek_inline (&ca->heap), ca)) { ca->heap.data[0 ] = b; -min_heap_sift_down (&ca->heap,0 , &bucket_max_cmp_callback, ca); +min_heap_sift_down_top_down_inline (&ca->heap,0 , &bucket_max_cmp_callback, ca); } } -min_heapify_all (&ca->heap, &bucket_min_cmp_callback, ca); +min_heapify_all_top_down_inline (&ca->heap, &bucket_min_cmp_callback, ca);while (!fifo_full (&ca->free_inc)) {if (!ca->heap.nr) {@@ -227,8 +227,8 @@ static void invalidate_buckets_lru(struct cache *ca)wake_up_gc (ca->set);return ; } - b =min_heap_peek (&ca->heap)[0 ]; -min_heap_pop (&ca->heap, &bucket_min_cmp_callback, ca); + b =min_heap_peek_inline (&ca->heap)[0 ]; +min_heap_pop_top_down_inline (&ca->heap, &bucket_min_cmp_callback, ca);bch_invalidate_one_bucket (ca, b); } --2.50.0.rc1.591.g9c95f17f64-goog