Use bsearch() instead of a manual binary search in syscache.c
Hi, hackers!
I make a patch for the $subject, which make the code simpler, thoughts?
--
Regards,
ChangAo Chen
Attachments:
v1-0001-Use-bsearch-instead-of-a-manual-binary-search-in-.patchapplication/octet-stream; charset=utf-8; name=v1-0001-Use-bsearch-instead-of-a-manual-binary-search-in-.patchDownload
From 7d54876dcf4e5d41871040b183cf4aa21b0ac390 Mon Sep 17 00:00:00 2001
From: ChangAo Chen <cca5507@qq.com>
Date: Sat, 8 Nov 2025 15:39:16 +0800
Subject: [PATCH v1] Use bsearch() instead of a manual binary search in
syscache.c
---
src/backend/utils/cache/syscache.c | 42 +++++++-----------------------
1 file changed, 10 insertions(+), 32 deletions(-)
diff --git a/src/backend/utils/cache/syscache.c b/src/backend/utils/cache/syscache.c
index 0e70a8020b7..f713c7a3abc 100644
--- a/src/backend/utils/cache/syscache.c
+++ b/src/backend/utils/cache/syscache.c
@@ -736,22 +736,11 @@ RelationInvalidatesSnapshotsOnly(Oid relid)
bool
RelationHasSysCache(Oid relid)
{
- int low = 0,
- high = SysCacheRelationOidSize - 1;
-
- while (low <= high)
- {
- int middle = low + (high - low) / 2;
-
- if (SysCacheRelationOid[middle] == relid)
- return true;
- if (SysCacheRelationOid[middle] < relid)
- low = middle + 1;
- else
- high = middle - 1;
- }
-
- return false;
+ return bsearch(&relid,
+ SysCacheRelationOid,
+ SysCacheRelationOidSize,
+ sizeof(Oid),
+ oid_compare) != NULL;
}
/*
@@ -761,22 +750,11 @@ RelationHasSysCache(Oid relid)
bool
RelationSupportsSysCache(Oid relid)
{
- int low = 0,
- high = SysCacheSupportingRelOidSize - 1;
-
- while (low <= high)
- {
- int middle = low + (high - low) / 2;
-
- if (SysCacheSupportingRelOid[middle] == relid)
- return true;
- if (SysCacheSupportingRelOid[middle] < relid)
- low = middle + 1;
- else
- high = middle - 1;
- }
-
- return false;
+ return bsearch(&relid,
+ SysCacheSupportingRelOid,
+ SysCacheSupportingRelOidSize,
+ sizeof(Oid),
+ oid_compare) != NULL;
}
--
2.51.2
cca5507 <cca5507@qq.com> wrote:
I make a patch for the $subject, which make the code simpler, thoughts?
I proposed something like that earlier [1]/messages/by-id/36977.1720623613@antos but did not get too far. The short
discussion might be useful for you though.
[1]: /messages/by-id/36977.1720623613@antos
--
Antonin Houska
Web: https://www.cybertec-postgresql.com
On Sun, Nov 9, 2025 at 1:12 AM Antonin Houska <ah@cybertec.at> wrote:
cca5507 <cca5507@qq.com> wrote:
I make a patch for the $subject, which make the code simpler, thoughts?
I proposed something like that earlier [1] but did not get too far. The short
discussion might be useful for you though.
One factor is that libc bsearch() implementations might not all be
header-only and inlineable. I vaguely recall that being discussed in
some round of hacking on qsort() and qunique().
Thomas Munro <thomas.munro@gmail.com> writes:
One factor is that libc bsearch() implementations might not all be
header-only and inlineable. I vaguely recall that being discussed in
some round of hacking on qsort() and qunique().
I'm quite certain that years ago we determined that bsearch()
was slower than a manually written-out loop, probably because of
exactly the point that the comparisons would be inline. Don't
know whether modern compilers have changed that conclusion.
There are places where we wouldn't care about such microscopic
performance details, but I think syscache.c is not one of them.
regards, tom lane
On Sun, Nov 9, 2025 at 6:01 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
I'm quite certain that years ago we determined that bsearch()
was slower than a manually written-out loop, probably because of
exactly the point that the comparisons would be inline. Don't
know whether modern compilers have changed that conclusion.
It looks like glibc's version is inlined, but others I checked aren't.
There are places where we wouldn't care about such microscopic
performance details, but I think syscache.c is not one of them.
So we'd probably need our own inline function to keep the playing
field level. Some tweaked algorithms[1]https://github.com/scandum/binary_search are also said to speed up
small integer tables, Unicode tables etc.
Hi,
Thanks for the explanation which helps me a lot!
The bsearch() got inlined according to compiler explorer:
https://godbolt.org/z/1x69zGMcn
So we'd probably need our own inline function to keep the playing
field level. Some tweaked algorithms[1] are also said to speed up
small integer tables, Unicode tables etc.
How about add a pg_bsearch() and #define bsearch(a,b,c,d,e) pg_bsearch(a,b,c,d,e) to use it?
--
Regards,
ChangAo Chen