Skip to content

Fix bcache regression with equality-aware heap APIs

Kuan-Wei Chiu linux-bcache linux-doc lkml stable 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest8 patches 9 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/8lib min_heap: Add equal-elements-aware sift_down variantinclude/linux/min_heap.h lib/min_heap.c+58 -02 replies
2/8lib min_heap: Add typedef for sift_down function pointerinclude/linux/min_heap.h+3 -00 replies
3/8lib min_heap: add eqaware variant of min_heapify_all()include/linux/min_heap.h lib/min_heap.c+16 -70 replies
4/8lib min_heap: add eqaware variant of min_heap_pop()include/linux/min_heap.h lib/min_heap.c+16 -70 replies
5/8lib min_heap: add eqaware variant of min_heap_pop_push()include/linux/min_heap.h lib/min_heap.c+17 -70 replies
6/8lib min_heap: add eqaware variant of min_heap_del()include/linux/min_heap.h lib/min_heap.c+16 -70 replies
7/8Documentation/core-api: min_heap: Document _eqaware variants of min-heap APIsDocumentation/core-api/min_heap.rst+20 -00 replies
8/8bcache: Fix the tail IO latency regression by using equality-aware min heap APIdrivers/md/bcache/alloc.c+8 -70 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [PATCH 0/8] Fix bcache regression with equality-aware heap APIs

This patch series introduces equality-aware variants of the min heap API that use a top-down heapify strategy to improve performance when many elements are equal under the comparison function. It also updates the documentation accordingly and modifies bcache to use the new APIs to fix a performance regression caused by the switch to the generic min heap library.

In particular, invalidate_buckets_lru() in bcache suffered from increased comparison overhead due to the bottom-up strategy introduced in commit 866898efbb25 ("bcache: remove heap-related macros and switch to generic min_heap"). The regression is addressed by switching to the equality-aware variants and using the inline versions to avoid function call overhead in this hot path.

---

To avoid duplicated effort and expedite resolution, Robert kindly agreed that I should submit my already-completed series instead. Many thanks to him for his cooperation and support.

Kuan-Wei Chiu (8):
lib min_heap: Add equal-elements-aware sift_down variant lib min_heap: Add typedef for sift_down function pointer lib min_heap: add eqaware variant of min_heapify_all()
lib min_heap: add eqaware variant of min_heap_pop()
lib min_heap: add eqaware variant of min_heap_pop_push() lib min_heap: add eqaware variant of min_heap_del() Documentation/core-api: min_heap: Document _eqaware variants of
min-heap APIs
bcache: Fix the tail IO latency regression by using equality-aware min
heap API

 Documentation/core-api/min_heap.rst |  20 +++++
 drivers/md/bcache/alloc.c           |  15 ++--
 include/linux/min_heap.h            | 131 +++++++++++++++++++++++-----
 lib/min_heap.c                      |  23 +++--
 4 files changed, 154 insertions(+), 35 deletions(-)
Signature · 1 line
2.34.1