Thread: Missed opportunity for bsearch() in TransactionIdIsCurrentTransactionId()?

I don't quite understand why TransactionIdIsCurrentTransactionId() implements
binary search in ParallelCurrentXids "from scratch" instead of using
bsearch().

If I read the code correctly, the contents of the ParallelCurrentXids is
composed in SerializeTransactionState(), which uses xidComparator:

    qsort(workspace, nxids, sizeof(TransactionId), xidComparator);

so it should be o.k. to use bsearch(..., xidComparator).

For example, ReorderBufferCopySnap() also uses xidComparator to sort the
'subxip' array, and HeapTupleSatisfiesHistoricMVCC() then uses
TransactionIdInArray() (which is effectively bsearch(..., xidComparator)) to
search for particular XID in the array.

-- 
Antonin Houska
Web: https://www.cybertec-postgresql.com

On Wed, Jul 10, 2024 at 05:00:13PM +0200, Antonin Houska wrote:
> I don't quite understand why TransactionIdIsCurrentTransactionId() implements
> binary search in ParallelCurrentXids "from scratch" instead of using
> bsearch().

I believe there are a number of open-coded binary searches in the tree.  My
concern with switching them to bsearch() would be the performance impact of
using a function pointer for the comparisons.  Perhaps we could add a
couple of inlined binary search implementations for common types to replace
many of the open-coded ones.

-- 
nathan

Nathan Bossart <nathandbossart@gmail.com> wrote:

> On Wed, Jul 10, 2024 at 05:00:13PM +0200, Antonin Houska wrote:
> > I don't quite understand why TransactionIdIsCurrentTransactionId() implements
> > binary search in ParallelCurrentXids "from scratch" instead of using
> > bsearch().
> 
> I believe there are a number of open-coded binary searches in the tree.

Not sure if there are many, but I could find some:

* TransactionIdIsCurrentTransactionId()

* RelationHasSysCache()

* pg_dump.c:getRoleName()

> My concern with switching them to bsearch() would be the performance impact
> of using a function pointer for the comparisons.  Perhaps we could add a
> couple of inlined binary search implementations for common types to replace
> many of the open-coded ones.

bsearch() appears to be used widely, but o.k., I don't insist on using it to
replace the existing open-coded searches.

What actually bothers me more than the absence of bsearch() is that
TransactionIdIsCurrentTransactionId() implements the binary search from
scratch. Even w/o bsearch(), it can still call TransactionIdInArray(). I ran
into the problem when working on [1], which adds one more XID array.

Does the attached patch seem worth being applied separately, or at all?

[1] https://www.postgresql.org/message-id/82651.1720540558%40antos

-- 
Antonin Houska
Web: https://www.cybertec-postgresql.com

On Fri, Jul 12, 2024 at 12:01:11PM +0200, Antonin Houska wrote:
> Nathan Bossart <nathandbossart@gmail.com> wrote:
>> My concern with switching them to bsearch() would be the performance impact
>> of using a function pointer for the comparisons.  Perhaps we could add a
>> couple of inlined binary search implementations for common types to replace
>> many of the open-coded ones.
> 
> bsearch() appears to be used widely, but o.k., I don't insist on using it to
> replace the existing open-coded searches.

Sorry, I didn't mean to say that I was totally against switching to
bsearch(), but I do think we need to understand whether there is any
performance impact before doing so, especially in hot paths.  It would be
nice if we could reduce the number of open-coded binary searches in some
fashion, and if we can maintain or improve performance by creating a
handful of static inline functions, that would be even better.  If there's
no apparent performance difference, bsearch() is probably fine.

-- 
nathan