Fix bcache regression with equality-aware heap APIs
Get series with b4
b4 am [email protected]Versions newest first
- v1 Latest8 patches 9 repliesIn review
Patches in v1 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/8 | lib min_heap: Add equal-elements-aware sift_down variantinclude/ lib/ | +58 | 2 replies | |
| 2/8 | lib min_heap: Add typedef for sift_down function pointerinclude/ | +3 | 0 replies | |
| 3/8 | lib min_heap: add eqaware variant of min_heapify_all()include/ lib/ | +16 | 0 replies | |
| 4/8 | lib min_heap: add eqaware variant of min_heap_pop()include/ lib/ | +16 | 0 replies | |
| 5/8 | lib min_heap: add eqaware variant of min_heap_pop_push()include/ lib/ | +17 | 0 replies | |
| 6/8 | lib min_heap: add eqaware variant of min_heap_del()include/ lib/ | +16 | 0 replies | |
| 7/8 | Documentation/core-api: min_heap: Document _eqaware variants of min-heap APIsDocumentation/ | +20 | 0 replies | |
| 8/8 | bcache: Fix the tail IO latency regression by using equality-aware min heap APIdrivers/ | +8 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.
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