On Wed, May 21, 2025 at 02:57:26PM -0400, Matthew Sakai wrote: > > > On 5/21/25 11:04 AM, Kuan-Wei Chiu wrote: > > Hi Matthew, > > > > Recently noticed that the current heapify method in min_heap.h may > > degrade performance when the heap contains many compare-equal elements, > > compared to the previous version. > > > > In detail, the new heapify reduces the number of comparisons by about > > 50% when all elements are distinct. However, when all elements are > > equal, the comparison count can degrade from O(1) to O(log n). > > > > I don't have enough domain knowledge of dm-vdo, so I'd like to ask > > whether it uses heaps with many compare-equal elements. If so, I'll > > work on fixing the issue. > > > > Regards, > > Kuan-Wei > > Hi Kuan-Wei, > > dm-vdo uses heapify for two different operations, but in both cases we > define heap elements that can never be equal to each other. So I think this > is not an issue for dm-vdo. (We have not noticed any issues with this in our > regular testing, either.) > Thanks for confirming that dm-vdo won't encounter this issue.
We observed a regression in bcache caused by this behavior, and Coly was concerned that dm-vdo might be affected in a similar way. Fortunately, that doesn't seem to be the case. Regards, Kuan-Wei
