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.
Cc: stable@xxxxxxxxxxxxxxx
---
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(-)
--
2.34.1
