Re: Improve eviction algorithm in ReorderBuffer

On Tue, Apr 09, 2024 at 06:24:43PM -0700, Jeff Davis wrote:
> I had suggested that the heap could track the element indexes for
> efficient update/removal, but that would be a change to the
> binaryheap.h API, which would require some discussion (and possibly not
> be acceptable post-freeze).
> 
> But I think you're right: a pairing heap already solves the problem
> without modification. (Note: our pairing heap API doesn't explicitly
> support updating a key, so I think it would need to be done with
> remove/add.) So we might as well just do that right now rather than
> trying to fix the way the hash table is being used or trying to extend
> the binaryheap API.
> 
> Of course, we should measure to be sure there aren't bad cases around
> updating/removing a key, but I don't see a fundamental reason that it
> should be worse.

This is going to require a rewrite of 5bec1d6bc5e3 with a new
performance study, which strikes me as something that we'd better not
do after feature freeze.  Wouldn't the best way forward be to revert
5bec1d6bc5e3 and revisit the whole in v18?

I have added an open item, for now.
--
Michael