Re: Improve eviction algorithm in ReorderBuffer

Hi,

Sorry for the late reply, I took two days off.

On Thu, Apr 11, 2024 at 6:20 AM Heikki Linnakangas <hlinnaka(at)iki(dot)fi> wrote:
>
> 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.
>

Thank you for the patch!

I agree with the direction that we replace binaryheap + index with the
existing pairing heap and revert the changes for binaryheap. Regarding
the patch, I'm not sure we can remove the MAX_HEAP_TXN_COUNT_THRESHOLD
logic because otherwise we need to remove and add the txn node (i.e.
O(log n)) for every memory update. I'm concerned it could cause some
performance degradation in a case where there are not many
transactions being decoded.

I'll do performance tests, and share the results soon.

Regards,

--
Masahiko Sawada
Amazon Web Services: https://aws.amazon.com