On Sat, Dec 16, 2023 at 1:36 AM Euler Taveira <eu...@eulerto.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