Re: Improve eviction algorithm in ReorderBuffer

On Mon, 2024-04-08 at 21:29 +0900, Masahiko Sawada wrote:
> For v17, changes for #2 are smaller, but I'm concerned
> that the new API that requires a hash function to be able to use
> binaryheap_update_{up|down} might not be user friendly.

The only API change in 02 is accepting a hash callback rather than a
boolean in binaryheap_allocate(), so I don't see that as worse than
what's there now. It also directly fixes my complaint (hashing the
pointer) and does nothing more, so I think it's the right fix for now.

I do think that the API can be better (templated like simplehash), but
I don't think right now is a great time to change it.

> When it comes to performance overhead, I mentioned that there is some
> regression in the current binaryheap even without indexing.

As far as I can tell, you are just adding a single branch in that path,
and I would expect it to be a predictable branch, right?

Thank you for testing, but small differences in a microbenchmark aren't
terribly worrying for me. If other call sites are that sensitive to
binaryheap performance, the right answer is to have a templated version
that would not only avoid this unnecessary branch, but also inline the
comparator (which probably matters more).

Regards,
Jeff Davis