Re: Improve eviction algorithm in ReorderBuffer

On Sat, Dec 16, 2023 at 1:36 AM Euler Taveira <euler(at)eulerto(dot)com> wrote:
>
> On Fri, Dec 15, 2023, at 9:11 AM, Masahiko Sawada wrote:
>
>
> I assume you mean to add ReorderBufferTXN entries to the binaryheap
> and then build it by comparing their sizes (i.e. txn->size). But
> ReorderBufferTXN entries are removed and deallocated once the
> transaction finished. How can we efficiently remove these entries from
> binaryheap? I guess it would be O(n) to find the entry among the
> unordered entries, where n is the number of transactions in the
> reorderbuffer.
>
>
> O(log n) for both functions: binaryheap_remove_first() and
> binaryheap_remove_node().

Right. The binaryheap_binaryheap_remove_first() removes the topmost
entry in O(log n), but the ReorderBufferTXN being removed is not
necessarily the topmost entry, since we remove the entry when the
transaction completes (committed or aborted). The
binaryheap_remove_node() removes the entry at the given Nth in O(log
n), but I'm not sure how we can know the indexes of each entry. I
think we can remember the index of newly added entry after calling
binaryheap_add_unordered() but once we call binaryheap_build() the
index is out-of-date. So I think that in the worst case we would need
to check all entries in order to remove an arbitrary entry in
binaryheap. It's O(n). I might be missing something though.

> I didn't read your patch but do you really need to
> free entries one by one? If not, binaryheap_free().

The patch doesn't touch on how to free entries. ReorderBufferTXN
entries are freed one by one after each of which completes (committed
or aborted).

Regards,

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