Thread

1. Use bsearch() instead of a manual binary search in syscache.c

   cca5507 <cca5507@qq.com> — 2025-11-08T07:59:02Z

   Hi, hackers!
   
   
   I make a patch for the $subject, which make the code simpler, thoughts?
   
   
   --
   Regards,
   ChangAo Chen

2. Re: Use bsearch() instead of a manual binary search in syscache.c

   Antonin Houska <ah@cybertec.at> — 2025-11-08T12:12:31Z

   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.
   
   [1] https://www.postgresql.org/message-id/36977.1720623613@antos
   
   -- 
   Antonin Houska
   Web: https://www.cybertec-postgresql.com
   
   
   
   

3. Re: Use bsearch() instead of a manual binary search in syscache.c

   Thomas Munro <thomas.munro@gmail.com> — 2025-11-08T13:24:34Z

   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().
   
   
   
   

4. Re: Use bsearch() instead of a manual binary search in syscache.c

   Tom Lane <tgl@sss.pgh.pa.us> — 2025-11-08T17:01:26Z

   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
   
   
   
   

5. Re: Use bsearch() instead of a manual binary search in syscache.c

   Thomas Munro <thomas.munro@gmail.com> — 2025-11-09T01:55:21Z

   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] are also said to speed up
   small integer tables, Unicode tables etc.
   
   [1] https://github.com/scandum/binary_search
   
   
   
   

6. Re: Use bsearch() instead of a manual binary search in syscache.c

   cca5507 <cca5507@qq.com> — 2025-11-09T07:50:29Z

   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