Re: [PATCH 0/1] bcache: reduce front IO latency during GC

On Tue, May 20, 2025 at 09:13:09PM +0800, Coly Li wrote:
> 
> 
> > 2025年5月20日 20:26，Kuan-Wei Chiu <[email protected]> 写道：
> > 
> > On Tue, May 20, 2025 at 08:13:47PM +0800, Coly Li wrote:
> >> 
> >> 
> >>> 2025年5月20日 19:51，Kuan-Wei Chiu <[email protected]> 写道：
> >>> 
> >>> On Sat, May 17, 2025 at 07:02:06PM +0800, Coly Li wrote:
> >>>> 
> >>>> 
> >>>>> 2025年5月17日 00:14，Kuan-Wei Chiu <[email protected]> 写道：
> >>>>> 
> >>>>> On Thu, May 15, 2025 at 08:58:44PM -0700, Robert Pang wrote:
> >>>>>> Hi Kuan-Wei,
> >>>>>> 
> >>>>>> Thank you for your prompt response. I tested your suggested patch to
> >>>>>> inline the min heap operations for 8 hours and it is still ongoing.
> >>>>>> Unfortunately, basing on the results so far, it didn't resolve the
> >>>>>> regression, suggesting inlining isn't the issue.
> >>>>>> 
> >>>>>> After reviewing the commits in lib/min_heap.h, I noticed commit
> >>>>>> c641722 ("lib min_heap: optimize number of comparisons in
> >>>>>> min_heapify()") and it looked like a potential candidate. I reverted
> >>>>>> this commit (below) and ran the tests. While the test is still
> >>>>>> ongoing, the results for the past 3 hours show that the latency spikes
> >>>>>> during invalidate_buckets_lru() disappeared after this change,
> >>>>>> indicating that this commit is likely the root cause of the
> >>>>>> regression.
> >>>>>> 
> >>>>>> My hypothesis is that while commit c641722 was designed to reduce
> >>>>>> comparisons with randomized input [1], it might inadvertently increase
> >>>>>> comparisons when the input isn't as random. A scenario where this
> >>>>>> could happen is within invalidate_buckets_lru() before the cache is
> >>>>>> fully populated. In such cases, many buckets are unfilled, causing
> >>>>>> new_bucket_prio() to return zero, leading to more frequent
> >>>>>> compare-equal operations with other unfilled buckets. In the case when
> >>>>>> the cache is populated, the bucket priorities fall in a range with
> >>>>>> many duplicates. How will heap_sift() behave in such cases?
> >>>>>> 
> >>>>>> [1] https://lore.kernel.org/linux-bcache/[email protected]/
> >>>>>> 
> >>>>> 
> >>>>> You're very likely correct.
> >>>>> 
> >>>>> In scenarios where the majority of elements in the heap are identical,
> >>>>> the traditional top-down version of heapify finishes after just 2
> >>>>> comparisons. However, with the bottom-up version introduced by that
> >>>>> commit, it ends up performing roughly 2 * log₂(n) comparisons in the
> >>>>> same case.
> >>>> 
> >>>> For bcache scenario for ideal circumstances and best performance, the cached data
> >>>> and following requests should have spatial or temporal locality.
> >>>> 
> >>>> I guess it means for the heap usage, the input might not be typical random.
> >>>> 
> >>>> 
> >>>>> 
> >>>>> That said, reverting the commit would increase the number of
> >>>>> comparisons by about 2x in cases where all elements in the heap are
> >>>>> distinct, which was the original motivation for the change. I'm not
> >>>>> entirely sure what the best way would be to fix this regression without
> >>>>> negatively impacting the performance of the other use cases.
> >>>> 
> >>>> If the data read model are fully sequential or random, bcache cannot help too much.
> >>>> 
> >>>> So I guess maybe we still need to old heapify code? The new version is for full random input,
> >>>> and previous version for not that much random input.
> >>>> 
> >>> 
> >>> I think we have two options here. One is to add a classic heapify
> >>> function to min_heap.h, allowing users to choose based on whether they
> >>> expect many duplicate elements in the heap. While having two heapify
> >>> variants might be confusing from a library design perspective, we could
> >>> mitigate that with clear kernel-doc comments. The other option is to
> >>> revert to the old bcache heap code. I'm not sure which approach is
> >>> better.
> >>> 
> >> 
> >> I prefer to have two min_heap APIs, but how to name them, this is a question from me.
> >> 
> >> Also if the full-random min_heap version has no user in kernel, whether to keep it in kernel also is a question.
> > 
> > From the perspective of the number of comparisons in heapify, what
> > matters more is whether the data contains many equal elements, rather
> > than whether it's truly random. I assume that for most other kernel
> > users, their use cases don't typically involve a large number of equal
> > elements?
> > 
> 
> Yes, you are right.  Maybe dm-vdo also has similar I/O pattern?
> 
> Deduplication may also have duplicated items in heap I guess.
> 

Thanks for pointing out this potential issue.
I'll check with Matthew to confirm.

Regards,
Kuan-Wei

> Thanks.
> 
> 
> >> 
> >> Kent,
> >> Could you please offer your opinion?
> >> 
> >> Thanks.
> >> 
> >> Coly Li
> 
>