Re: Improve eviction algorithm in ReorderBuffer

On Thu, 2024-04-04 at 10:55 -0700, Jeff Davis wrote:
>   * Make a proper indexed binary heap API that accepts a hash
> function
> and provides both heap methods and HT methods that operate based on
> values (transaction size and transaction ID, respectively).
>   * Get rid of ReorderBuffer->by_txn and use the indexed binary heap
> instead.

An alternative idea:

* remove the hash table from binaryheap.c

* supply a new callback to the binary heap with type like:

typedef void (*binaryheap_update_index)(
bh_node_type node,
int new_element_index);

* make the remove, update_up, and update_down methods take the element
index rather than the pointer

reorderbuffer.c would then do something like:

void
txn_update_heap_index(ReorderBufferTXN *txn, int new_element_index)
{
txn->heap_element_index = new_element_index;
}

...

txn_heap = binaryheap_allocate(..., txn_update_heap_index, ...);

and then binaryheap.c would effectively maintain txn-
>heap_element_index, so reorderbuffer.c can pass that to the APIs that
require the element index.

Another alternative is to keep the hash table in binaryheap.c, and
supply a hash function that hashes the xid. That leaves us with two
hash tables still, but it would be cleaner than hashing the pointer.
That might be best for right now, and we can consider these other ideas
later.

Regards,
Jeff Davis