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

> 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.

Kent,
Could you please offer your opinion?

Thanks.

Coly Li