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

[Kuan-Wei Chiu <visitorckw@gmail.com>]

On Tue, May 20, 2025 at 08:13:47PM +0800, Coly Li wrote:
> 
> 
> > 2025年5月20日 19:51，Kuan-Wei Chiu <visitorckw@gmail.com> 写道：
> > 
> > On Sat, May 17, 2025 at 07:02:06PM +0800, Coly Li wrote:
> >> 
> >> 
> >>> 2025年5月17日 00:14，Kuan-Wei Chiu <visitorckw@gmail.com> 写道：
> >>> 
> >>> 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/20240121153649.2733274-6-visitorckw@gmail.com/
> >>>> 
> >>> 
> >>> 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?

Regards,
Kuan-Wei

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