Re: [PATCH 3/3] bcache: Fix the tail IO latency regression due to the use of lib min_heap

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

On Fri, Jun 6, 2025 at 10:01 PM Kuan-Wei Chiu <[email protected]> wrote:
>
> On Fri, Jun 06, 2025 at 12:19:45AM -0700, Robert Pang wrote:
> > In 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.
>
> 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") ?
>
> >
> > 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.
> >
> > [1] https://lore.kernel.org/linux-bcache/wtfuhfntbi6yorxqtpcs4vg5w67mvyckp2a6jmxuzt2hvbw65t@gznwsae5653d/T/#me50a9ddd0386ce602b2f17415e02d33b8e29f533
> >
> > Signed-off-by: Robert Pang <[email protected]>
> > ---
> >  drivers/md/bcache/alloc.c | 14 +++++++-------
> >  1 file changed, 7 insertions(+), 7 deletions(-)
> >
> > diff --git a/drivers/md/bcache/alloc.c b/drivers/md/bcache/alloc.c
> > index 8998e61efa40..547d1cd0c7c2 100644
> > --- a/drivers/md/bcache/alloc.c
> > +++ b/drivers/md/bcache/alloc.c
> > @@ -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
>
> > +             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
> >