Re: Improve eviction algorithm in ReorderBuffer

On 10/04/2024 08:31, Amit Kapila wrote:
> On Wed, Apr 10, 2024 at 11:00 AM Heikki Linnakangas <hlinnaka(at)iki(dot)fi> wrote:
>>
>> On 10/04/2024 07:45, Michael Paquier wrote:
>>> On Tue, Apr 09, 2024 at 09:16:53PM -0700, Jeff Davis wrote:
>>>> On Wed, 2024-04-10 at 12:13 +0900, Michael Paquier wrote:
>>>>> Wouldn't the best way forward be to revert
>>>>> 5bec1d6bc5e3 and revisit the whole in v18?
>>>>
>>>> Also consider commits b840508644 and bcb14f4abc.
>>>
>>> Indeed. These are also linked.
>>
>> I don't feel the urge to revert this:
>>
>> - It's not broken as such, we're just discussing better ways to
>> implement it. We could also do nothing, and revisit this in v18. The
>> only must-fix issue is some compiler warnings IIUC.
>>
>> - It's a pretty localized change in reorderbuffer.c, so it's not in the
>> way of other patches or reverts. Nothing else depends on the binaryheap
>> changes yet either.
>>
>> - It seems straightforward to repeat the performance tests with whatever
>> alternative implementations we want to consider.
>>
>> My #1 choice would be to write a patch to switch the pairing heap,
>> performance test that, and revert the binary heap changes.
>>
>
> +1.

To move this forward, here's a patch to switch to a pairing heap. In my
very quick testing, with the performance test cases posted earlier in
this thread [1] [2], I'm seeing no meaningful performance difference
between this and what's in master currently.

Sawada-san, what do you think of this? To be sure, if you could also
repeat the performance tests you performed earlier, that'd be great. If
you agree with this direction, and you're happy with this patch, feel
free take it from here and commit this, and also revert commits
b840508644 and bcb14f4abc.

--
Heikki Linnakangas
Neon (https://neon.tech)