Missed opportunity for bsearch() in TransactionIdIsCurrentTransactionId()?
Hackorum builds and tests every patch posted to the lists, not only commitfest submissions. This is Hackorum's own CI rather than the PostgreSQL project's, and it is still under testing - please report anything that looks wrong.
You can run a PostgreSQL built from this patch straight from Docker, with no checkout and no build:
docker run --rm -p 5432:5432 ghcr.io/hackorum-dev/postgres-patch:t49952psql -h localhost -U postgresBuilt from patchset v3 (message #3), July 27, 2026 at 12:03 PM.
Every patchset is also pushed to a branch of our PostgreSQL fork, so you can check out the same tree CI built. Without a PostgreSQL checkout:
git clone --branch t49952_3 https://github.com/hackorum-dev/postgres.gitIn a checkout you already have, add the fork once:
git remote add hackorum https://github.com/hackorum-dev/postgres.gitthen, for this patchset and every later one:
git fetch hackorum t49952_3 && git checkout t49952_3Patchset v3 (message #3) is on t49952_3
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
Attachments:
use_bsearch_for_ParallelCurrentXids.difftext/x-diffDownload+3-23
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]/messages/by-id/82651.1720540558@antos, which adds one more XID array.
Does the attached patch seem worth being applied separately, or at all?
[1]: /messages/by-id/82651.1720540558@antos
--
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