Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Andres Freund writes: > On 2017-10-05 17:08:39 +0300, Heikki Linnakangas wrote: >> BTW, there's some alignment padding in FmgrBuiltin, when MAXIMUM_ALIGNOF==8. >> You could easily shrink the struct from 32 to 24 bytes by moving funcName to >> the end of the struct: > Yea, that's probably worthwhile, although I suspect it's not a huge save > overall. Do you just want to commit that? +1 >> If we care about cache efficiency here, we could move funcName out of the >> fmgr_builtins array, to a separate array of the same size. > When'd that be beneficial? fmgr_builtins is pretty much only used for > internal-language CREATE FUNCTIONs? In other cases oid bounds + mapping > array should filter out the access before fmgr_builtins is accessed. I'm -1 on this, it would complicate using the data structure to look up the name of a built-in function from its OID. (Don't know that anyone actually does that, but I see no reason to break their code if they do.) regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Hi,
On 2017-10-05 17:08:39 +0300, Heikki Linnakangas wrote:
> > I pushed a further cleaned up version of these two patches. If you see
> > a way to avoid initializing the "trailing" part of the
> > fmgr_builtin_oid_index in a different manner, I'm all ears ;)
>
> You could put a dummy entry at fmgr_builtins[0].
Right, I'd considered that somewhere upthread. Didn't really seem
better.
> BTW, there's some alignment padding in FmgrBuiltin, when MAXIMUM_ALIGNOF==8.
> You could easily shrink the struct from 32 to 24 bytes by moving funcName to
> the end of the struct:
>
> --- a/src/include/utils/fmgrtab.h
> +++ b/src/include/utils/fmgrtab.h
> @@ -25,11 +25,11 @@
> typedef struct
> {
> Oid foid; /* OID of the function
> */
> - const char *funcName; /* C name of the function */
> short nargs; /* 0..FUNC_MAX_ARGS, or -1 if
> variable count */
> boolstrict; /* T if function is "strict" */
> boolretset; /* T if function returns a set
> */
> PGFunction func; /* pointer to compiled function
> */
> + const char *funcName; /* C name of the function */
> } FmgrBuiltin;
>
> extern const FmgrBuiltin fmgr_builtins[];
Yea, that's probably worthwhile, although I suspect it's not a huge save
overall. Do you just want to commit that?
> If we care about cache efficiency here, we could move funcName out of the
> fmgr_builtins array, to a separate array of the same size. I believe
> funcName is only used when you create an internal-language function with
> CREATE FUNCTION, and having it in a separate array shouldn't hurt those
> lookups.
When'd that be beneficial? fmgr_builtins is pretty much only used for
internal-language CREATE FUNCTIONs? In other cases oid bounds + mapping
array should filter out the access before fmgr_builtins is accessed.
Greetings,
Andres Freund
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 10/04/2017 10:33 AM, Andres Freund wrote:
On 2017-10-02 15:01:36 -0700, Andres Freund wrote:
On 2017-10-02 17:57:51 -0400, Tom Lane wrote:
Andres Freund writes:
Done that way. It's a bit annoying, because we've to take care to
initialize the "unused" part of the array with a valid signalling it's
an unused mapping. Can't use 0 for that because fmgr_builtins[0] is a
valid entry.
The prototype code I posted further upthread just used -1 as the "unused"
marker. There's no reason the array can't be int16 rather than uint16,
and "if (index < 0)" is probably a faster test anyway.
Right, but whether we use -1 or UINT16_MAX or such doesn't matter. The
relevant bit is that we can't use 0, so we can't rely on the rest of the
array being zero initialized, but instead of to initialize all of it
explicitly. I've no real feelings about using -1 or UINT16_MAX - I'd be
very surprised if there's any sort of meaningful performance difference.
I pushed a further cleaned up version of these two patches. If you see
a way to avoid initializing the "trailing" part of the
fmgr_builtin_oid_index in a different manner, I'm all ears ;)
You could put a dummy entry at fmgr_builtins[0].
BTW, there's some alignment padding in FmgrBuiltin, when
MAXIMUM_ALIGNOF==8. You could easily shrink the struct from 32 to 24
bytes by moving funcName to the end of the struct:
--- a/src/include/utils/fmgrtab.h
+++ b/src/include/utils/fmgrtab.h
@@ -25,11 +25,11 @@
typedef struct
{
Oid foid; /* OID of the function
*/
- const char *funcName; /* C name of the function */
short nargs; /* 0..FUNC_MAX_ARGS, or -1 if
variable count */
boolstrict; /* T if function is "strict" */
boolretset; /* T if function returns a set
*/
PGFunction func; /* pointer to compiled function
*/
+ const char *funcName; /* C name of the function */
} FmgrBuiltin;
extern const FmgrBuiltin fmgr_builtins[];
If we care about cache efficiency here, we could move funcName out of
the fmgr_builtins array, to a separate array of the same size. I believe
funcName is only used when you create an internal-language function with
CREATE FUNCTION, and having it in a separate array shouldn't hurt those
lookups.
- Heikki
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 2017-10-02 15:01:36 -0700, Andres Freund wrote: > On 2017-10-02 17:57:51 -0400, Tom Lane wrote: > > Andres Freund writes: > > > Done that way. It's a bit annoying, because we've to take care to > > > initialize the "unused" part of the array with a valid signalling it's > > > an unused mapping. Can't use 0 for that because fmgr_builtins[0] is a > > > valid entry. > > > > The prototype code I posted further upthread just used -1 as the "unused" > > marker. There's no reason the array can't be int16 rather than uint16, > > and "if (index < 0)" is probably a faster test anyway. > > Right, but whether we use -1 or UINT16_MAX or such doesn't matter. The > relevant bit is that we can't use 0, so we can't rely on the rest of the > array being zero initialized, but instead of to initialize all of it > explicitly. I've no real feelings about using -1 or UINT16_MAX - I'd be > very surprised if there's any sort of meaningful performance difference. I pushed a further cleaned up version of these two patches. If you see a way to avoid initializing the "trailing" part of the fmgr_builtin_oid_index in a different manner, I'm all ears ;) Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 2017-10-02 17:57:51 -0400, Tom Lane wrote: > Andres Freund writes: > > Done that way. It's a bit annoying, because we've to take care to > > initialize the "unused" part of the array with a valid signalling it's > > an unused mapping. Can't use 0 for that because fmgr_builtins[0] is a > > valid entry. > > The prototype code I posted further upthread just used -1 as the "unused" > marker. There's no reason the array can't be int16 rather than uint16, > and "if (index < 0)" is probably a faster test anyway. Right, but whether we use -1 or UINT16_MAX or such doesn't matter. The relevant bit is that we can't use 0, so we can't rely on the rest of the array being zero initialized, but instead of to initialize all of it explicitly. I've no real feelings about using -1 or UINT16_MAX - I'd be very surprised if there's any sort of meaningful performance difference. Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Andres Freund writes: > Done that way. It's a bit annoying, because we've to take care to > initialize the "unused" part of the array with a valid signalling it's > an unused mapping. Can't use 0 for that because fmgr_builtins[0] is a > valid entry. The prototype code I posted further upthread just used -1 as the "unused" marker. There's no reason the array can't be int16 rather than uint16, and "if (index < 0)" is probably a faster test anyway. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 2017-09-28 19:06:27 -0400, Tom Lane wrote:
> Andres Freund writes:
> > On 2017-09-28 18:52:28 -0400, Tom Lane wrote:
> >> Uh, what? Access to fmgr_nbuiltins shouldn't be part of any critical path
> >> anymore after this change.
>
> > Indeed. But the size of the the oid -> fmgr_builtins index array is
> > relevant now. We could of course just make that dependent on
> > FirstBootstrapObjectId, but that'd waste some memory.
>
> Not enough to notice, considering there are pg_proc OIDs up in the 8K
> range already. We blow 2KB of never-accessed space for far less good
> reason than this.
Done that way. It's a bit annoying, because we've to take care to
initialize the "unused" part of the array with a valid signalling it's
an unused mapping. Can't use 0 for that because fmgr_builtins[0] is a
valid entry. We could introduce a dummy element at that position, but
that doesn't really seem nice either. Therefore the first attached
commit moves find_defined_symbol from genbki to Catalog.pm, so we can
easily extract FirstBootstrapObjectId in Gen_fmgrtab.pl.
Greetings,
Andres Freund
>From 16e35356cead73291d676764072abfebc2efa79b Mon Sep 17 00:00:00 2001
From: Andres Freund
Date: Mon, 2 Oct 2017 14:14:42 -0700
Subject: [PATCH 1/2] Move genbki.pl's find_defined_symbol to Catalog.pm.
Will be used in Gen_fmgrtab.pl in a followup commit.
---
src/backend/catalog/Catalog.pm | 35 ++-
src/backend/catalog/genbki.pl | 34 --
src/backend/utils/Makefile | 2 +-
3 files changed, 39 insertions(+), 32 deletions(-)
diff --git a/src/backend/catalog/Catalog.pm b/src/backend/catalog/Catalog.pm
index 7abfda3d3a..54f83533b6 100644
--- a/src/backend/catalog/Catalog.pm
+++ b/src/backend/catalog/Catalog.pm
@@ -19,7 +19,7 @@ use warnings;
require Exporter;
our @ISA = qw(Exporter);
our @EXPORT= ();
-our @EXPORT_OK = qw(Catalogs SplitDataLine RenameTempFile);
+our @EXPORT_OK = qw(Catalogs SplitDataLine RenameTempFile FindDefinedSymbol);
# Call this function with an array of names of header files to parse.
# Returns a nested data structure describing the data in the headers.
@@ -252,6 +252,39 @@ sub RenameTempFile
rename($temp_name, $final_name) || die "rename: $temp_name: $!";
}
+
+# Find a symbol defined in a particular header file and extract the value.
+#
+# The include path has to be passed as a reference to an array.
+sub FindDefinedSymbol
+{
+ my ($catalog_header, $include_path, $symbol) = @_;
+
+ for my $path (@$include_path)
+ {
+
+ # Make sure include path ends in a slash.
+ if (substr($path, -1) ne '/')
+ {
+ $path .= '/';
+ }
+ my $file = $path . $catalog_header;
+ next if !-f $file;
+ open(my $find_defined_symbol, '<', $file) || die "$file: $!";
+ while (<$find_defined_symbol>)
+ {
+ if (/^#define\s+\Q$symbol\E\s+(\S+)/)
+ {
+return $1;
+ }
+ }
+ close $find_defined_symbol;
+ die "$file: no definition found for $symbol\n";
+ }
+ die "$catalog_header: not found in any include directory\n";
+}
+
+
# verify the number of fields in the passed-in DATA line
sub check_natts
{
diff --git a/src/backend/catalog/genbki.pl b/src/backend/catalog/genbki.pl
index 2eebb061b7..256a9c9c93 100644
--- a/src/backend/catalog/genbki.pl
+++ b/src/backend/catalog/genbki.pl
@@ -87,9 +87,11 @@ open my $shdescr, '>', $shdescrfile . $tmpext
# NB: make sure that the files used here are known to be part of the .bki
# file's dependencies by src/backend/catalog/Makefile.
my $BOOTSTRAP_SUPERUSERID =
- find_defined_symbol('pg_authid.h', 'BOOTSTRAP_SUPERUSERID');
+ Catalog::FindDefinedSymbol('pg_authid.h', \@include_path,
+ 'BOOTSTRAP_SUPERUSERID');
my $PG_CATALOG_NAMESPACE =
- find_defined_symbol('pg_namespace.h', 'PG_CATALOG_NAMESPACE');
+ Catalog::FindDefinedSymbol('pg_namespace.h', \@include_path,
+ 'PG_CATALOG_NAMESPACE');
# Read all the input header files into internal data structures
my $catalogs = Catalog::Catalogs(@input_files);
@@ -500,34 +502,6 @@ sub emit_schemapg_row
return $row;
}
-# Find a symbol defined in a particular header file and extract the value.
-sub find_defined_symbol
-{
- my ($catalog_header, $symbol) = @_;
- for my $path (@include_path)
- {
-
- # Make sure include path ends in a slash.
- if (substr($path, -1) ne '/')
- {
- $path .= '/';
- }
- my $file = $path . $catalog_header;
- next if !-f $file;
- open(my $find_defined_symbol, '<', $file) || die "$file: $!";
- while (<$find_defined_symbol>)
- {
- if (/^#define\s+\Q$symbol\E\s+(\S+)/)
- {
-return $1;
- }
- }
- close $find_defined_symbol;
- die "$file: no definition found for $symbol\n";
- }
- die "$catalog_header: not found in any include directory\n";
-}
-
sub usage
{
die < $@
--
2.14.1.536.g6867272d5b.dirty
>From 2dfe8a94a8bea160e9cac512f0d3346fdc90cf44 Mon Sep 17 00:00:00 2001
From: Andres Freund
Date: Mon, 2 Oct 2017 14:27:05 -0700
Subject: [PATCH 2/2] Replace binary search in fmgr_isbuiltin w
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Andres Freund writes: > On 2017-09-28 18:52:28 -0400, Tom Lane wrote: >> Uh, what? Access to fmgr_nbuiltins shouldn't be part of any critical path >> anymore after this change. > Indeed. But the size of the the oid -> fmgr_builtins index array is > relevant now. We could of course just make that dependent on > FirstBootstrapObjectId, but that'd waste some memory. Not enough to notice, considering there are pg_proc OIDs up in the 8K range already. We blow 2KB of never-accessed space for far less good reason than this. >> I'm kind of -0.5 on that. I believe part of the argument for having >> things set up as they were was to allow external code to access the >> fmgr_builtins table (as my speed-test hack earlier today did). > You could still do that, you'd just end up with a second copy. Doesn't > seem bad for such an uncommon case. If I understand what you're proposing, it would involve the extension containing its *own* copy of the fmgr table, which seems pretty horrid. It wouldn't necessarily match the actual contents in the core executable. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 2017-09-28 18:52:28 -0400, Tom Lane wrote: > Andres Freund writes: > > I might be worse than you... But anyway, here's a patch doing > > so. Looking at profiles, it turned out that having the integer limits as > > extern variables in a different TU isn't a great idea. > > Uh, what? Access to fmgr_nbuiltins shouldn't be part of any critical path > anymore after this change. Indeed. But the size of the the oid -> fmgr_builtins index array is relevant now. We could of course just make that dependent on FirstBootstrapObjectId, but that'd waste some memory. > > So I moved what > > used to be fmgrtab.c to fmgrtab.h, and included it directly in fmgr.c. > > I'm kind of -0.5 on that. I believe part of the argument for having > things set up as they were was to allow external code to access the > fmgr_builtins table (as my speed-test hack earlier today did). You could still do that, you'd just end up with a second copy. Doesn't seem bad for such an uncommon case. Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Andres Freund writes: > I might be worse than you... But anyway, here's a patch doing > so. Looking at profiles, it turned out that having the integer limits as > extern variables in a different TU isn't a great idea. Uh, what? Access to fmgr_nbuiltins shouldn't be part of any critical path anymore after this change. > So I moved what > used to be fmgrtab.c to fmgrtab.h, and included it directly in fmgr.c. I'm kind of -0.5 on that. I believe part of the argument for having things set up as they were was to allow external code to access the fmgr_builtins table (as my speed-test hack earlier today did). While I'm not sure that anything really is using that API, I do not believe we'd gain any performance by removing it, so why do so? We can leave the table and the fmgr_nbuiltins variable completely as-is, and just add an index table, which fmgr.c could be aware is of size exactly "FirstBootstrapObjectId" entries. > Is this roughly what you were thinking of? I think you need the "no entry" values to be -1; 0 is a valid index into the fmgr table. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 2017-09-27 15:50:05 -0400, Tom Lane wrote: > ISTM it shouldn't be that hard to get Gen_fmgrtab.pl to emit an index > array of the sort we're talking about, along with the FmgrBuiltin array > it already prints out. I'm the world's worst Perl programmer but > I'm happy to take a stab at it if you don't want to. I might be worse than you... But anyway, here's a patch doing so. Looking at profiles, it turned out that having the integer limits as extern variables in a different TU isn't a great idea. So I moved what used to be fmgrtab.c to fmgrtab.h, and included it directly in fmgr.c. Is this roughly what you were thinking of? Greetings, Andres Freund >From 11fc054fda92fafc8b6c1ac66f70ecf059c61a9d Mon Sep 17 00:00:00 2001 From: Andres Freund Date: Tue, 26 Sep 2017 12:40:56 -0700 Subject: [PATCH] Speed up fmgr_isbuiltin() by keeping an oid -> builtin mapping. Turns out we have enough functions that the binary search is quite noticeable in profiles. To address that, have Gen_fmgrtab.pl build an oid -> fmgr_builtins index mapping. With that mapping fmgr_isbuiltin() just consists out of a comparison and two array lookups. To avoid having to reference extern variables, move the generated table to fmgrtab.h and include that from fmgr.c. Author: Andres Freund Discussion: https://postgr.es/m/20170914065128.a5sk7z4xde5uy...@alap3.anarazel.de --- src/backend/Makefile | 14 +-- src/backend/utils/Gen_fmgrtab.pl | 82 ++-- src/backend/utils/Makefile | 7 ++-- src/backend/utils/fmgr/fmgr.c| 27 ++--- src/include/fmgr.h | 16 src/include/utils/fmgrtab.h | 39 --- 6 files changed, 102 insertions(+), 83 deletions(-) delete mode 100644 src/include/utils/fmgrtab.h diff --git a/src/backend/Makefile b/src/backend/Makefile index aab676dbbd..f0eb5d8d78 100644 --- a/src/backend/Makefile +++ b/src/backend/Makefile @@ -142,6 +142,8 @@ utils/errcodes.h: utils/generate-errcodes.pl utils/errcodes.txt # see explanation in parser/Makefile utils/fmgrprotos.h: utils/fmgroids.h ; +utils/fmgrtab.h: utils/fmgroids.h ; + utils/fmgroids.h: utils/Gen_fmgrtab.pl catalog/Catalog.pm $(top_srcdir)/src/include/catalog/pg_proc.h $(MAKE) -C utils $(notdir $@) @@ -169,7 +171,7 @@ submake-schemapg: .PHONY: generated-headers -generated-headers: $(top_builddir)/src/include/parser/gram.h $(top_builddir)/src/include/catalog/schemapg.h $(top_builddir)/src/include/storage/lwlocknames.h $(top_builddir)/src/include/utils/errcodes.h $(top_builddir)/src/include/utils/fmgroids.h $(top_builddir)/src/include/utils/fmgrprotos.h $(top_builddir)/src/include/utils/probes.h +generated-headers: $(top_builddir)/src/include/parser/gram.h $(top_builddir)/src/include/catalog/schemapg.h $(top_builddir)/src/include/storage/lwlocknames.h $(top_builddir)/src/include/utils/errcodes.h $(top_builddir)/src/include/utils/fmgroids.h $(top_builddir)/src/include/utils/fmgrprotos.h $(top_builddir)/src/include/utils/fmgrtab.h $(top_builddir)/src/include/utils/probes.h $(top_builddir)/src/include/parser/gram.h: parser/gram.h prereqdir=`cd '$(dir $<)' >/dev/null && pwd` && \ @@ -201,6 +203,11 @@ $(top_builddir)/src/include/utils/fmgrprotos.h: utils/fmgrprotos.h cd '$(dir $@)' && rm -f $(notdir $@) && \ $(LN_S) "$$prereqdir/$(notdir $<)" . +$(top_builddir)/src/include/utils/fmgrtab.h: utils/fmgrtab.h + prereqdir=`cd '$(dir $<)' >/dev/null && pwd` && \ + cd '$(dir $@)' && rm -f $(notdir $@) && \ + $(LN_S) "$$prereqdir/$(notdir $<)" . + $(top_builddir)/src/include/utils/probes.h: utils/probes.h cd '$(dir $@)' && rm -f $(notdir $@) && \ $(LN_S) "../../../$(subdir)/utils/probes.h" . @@ -219,7 +226,7 @@ distprep: $(MAKE) -C catalog schemapg.h postgres.bki postgres.description postgres.shdescription $(MAKE) -C replication repl_gram.c repl_scanner.c syncrep_gram.c syncrep_scanner.c $(MAKE) -C storage/lmgr lwlocknames.h - $(MAKE) -C utils fmgrtab.c fmgroids.h fmgrprotos.h errcodes.h + $(MAKE) -C utils fmgroids.h fmgrprotos.h fmgrtab.h errcodes.h $(MAKE) -C utils/misc guc-file.c $(MAKE) -C utils/sort qsort_tuple.c @@ -312,6 +319,7 @@ clean: $(top_builddir)/src/include/storage/lwlocknames.h \ $(top_builddir)/src/include/utils/fmgroids.h \ $(top_builddir)/src/include/utils/fmgrprotos.h \ + $(top_builddir)/src/include/utils/fmgrtab.h \ $(top_builddir)/src/include/utils/probes.h ifeq ($(PORTNAME), cygwin) rm -f postgres.dll libpostgres.a @@ -341,7 +349,7 @@ maintainer-clean: distclean storage/lmgr/lwlocknames.h \ utils/fmgroids.h \ utils/fmgrprotos.h \ - utils/fmgrtab.c \ + utils/fmgrtab.h \ utils/errcodes.h \ utils/misc/guc-file.c \ utils/sort/qsort_tuple.c diff --git a/src/backend/utils/Gen_fmgrtab.pl b/src/backend/utils/Gen_fmgrtab.pl index 17851fe2a4..c09f8dedb1 100644 --- a/src/backend/utils/Gen_fmgrtab.pl +++ b/src/backend/utils/Gen_fmgrtab.pl @@
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
I wrote:
> [ we should use an index array ]
Just to prove the point, I threw together the attached trivial test case,
which time-trials the existing fmgr_isbuiltin implementation against both
the proposed hash implementation and a simple index array. On my machine,
with a repeat count of 1, I get
NOTICE: bsearch runtime 4234.087 ms
NOTICE: hash runtime 2542.636 ms
NOTICE: index runtime 165.184 ms
(These numbers are repeatable within 1% or so.)
It could be argued that trialling OIDs sequentially gives a bit of an
unfair advantage to the bsearch and index methods over the hash method,
because the former are going to suffer fewer cache misses that way.
But I don't see a randomized lookup order changing the conclusion much.
regards, tom lane
#include "postgres.h"
#include "fmgr.h"
#include "access/transam.h"
#include "portability/instr_time.h"
#include "utils/fmgrtab.h"
#include "utils/hashutils.h"
PG_MODULE_MAGIC;
static const FmgrBuiltin *
fmgr_isbuiltin_bsearch(Oid id)
{
int low = 0;
int high = fmgr_nbuiltins - 1;
/*
* Loop invariant: low is the first index that could contain target entry,
* and high is the last index that could contain it.
*/
while (low <= high)
{
int i = (high + low) / 2;
const FmgrBuiltin *ptr = &fmgr_builtins[i];
if (id == ptr->foid)
return ptr;
else if (id > ptr->foid)
low = i + 1;
else
high = i - 1;
}
return NULL;
}
/*
* Hashtable for fast lookup builtin functions.
*/
typedef struct BuiltinOidLookupEntry
{
Oid foid;
int status;
const FmgrBuiltin *builtin;
} BuiltinOidLookupEntry;
/* define hashtable mapping block numbers to PagetableEntry's */
#define SH_PREFIX oid2builtins
#define SH_ELEMENT_TYPE BuiltinOidLookupEntry
#define SH_KEY_TYPE Oid
#define SH_KEY foid
#define SH_HASH_KEY(tb, key) murmurhash32(key)
#define SH_EQUAL(tb, a, b) a == b
#define SH_SCOPE static inline
#define SH_DEFINE
#define SH_DECLARE
#include "lib/simplehash.h"
static oid2builtins_hash * oid2builtins = 0;
static const FmgrBuiltin *
fmgr_isbuiltin_hash(Oid id)
{
BuiltinOidLookupEntry *entry;
entry = oid2builtins_lookup(oid2builtins, id);
if (entry)
return entry->builtin;
else
return NULL;
}
static void
hash_setup(void)
{
int i;
oid2builtins = oid2builtins_create(TopMemoryContext,
fmgr_nbuiltins,
NULL);
for (i = 0; i < fmgr_nbuiltins; i++)
{
const FmgrBuiltin *ptr = &fmgr_builtins[i];
BuiltinOidLookupEntry *entry;
bool found;
entry = oid2builtins_insert(oid2builtins, ptr->foid, &found);
Assert(!found);
entry->builtin = ptr;
}
}
static int16 builtins_index[FirstBootstrapObjectId];
static const FmgrBuiltin *
fmgr_isbuiltin_index(Oid id)
{
int i;
if (id >= FirstBootstrapObjectId)
return NULL;
i = builtins_index[id];
if (i < 0)
return NULL;
return &fmgr_builtins[i];
}
static void
index_setup(void)
{
int i;
memset(builtins_index, -1, sizeof(builtins_index));
for (i = 0; i < fmgr_nbuiltins; i++)
{
const FmgrBuiltin *ptr = &fmgr_builtins[i];
builtins_index[ptr->foid] = i;
}
}
PG_FUNCTION_INFO_V1(test_lookups);
Datum
test_lookups(PG_FUNCTION_ARGS)
{
int rep_count = PG_GETARG_INT32(0);
instr_time start_time;
instr_time end_time;
int i;
INSTR_TIME_SET_CURRENT(start_time);
for (i = 0; i < rep_count; i++)
{
int ct = 0;
Oid fo;
for (fo = 1; fo < 1; fo++)
{
if (fmgr_isbuiltin_bsearch(fo))
ct++;
}
if (ct != fmgr_nbuiltins)
elog(ERROR, "got %d builtins instead of %d", ct, fmgr_nbuiltins);
}
INSTR_TIME_SET_CURRENT(end_time);
INSTR_TIME_SUBTRACT(end_time, start_time);
elog(NOTICE, "bsearch runtime %.3f ms",
1000.0 * INSTR_TIME_GET_DOUBLE(end_time));
hash_setup();
INSTR_TIME_SET_CURRENT(start_time);
for (i = 0; i < rep_count; i++)
{
int ct = 0;
Oid fo;
for (fo = 1; fo < 1; fo++)
{
if (fmgr_isbuiltin_hash(fo))
ct++;
}
if (ct != fmgr_nbuiltins)
elog(ERROR, "got %d builtins instead of %d", ct, fmgr_nbuiltins);
}
INSTR_TIME_SET_CURRENT(end_time);
INSTR_TIME_SUBTRACT(end_time, start_time);
elog(NOTICE, "hash runtime %.3f ms",
1000.0 * INSTR_TIME_GET_DOUBLE(end_time));
index_setup();
INSTR_TIME_SET_CURRENT(start_time);
for (i = 0; i < rep_count; i++)
{
int ct = 0;
Oid fo;
for (fo = 1; fo < 1; fo++)
{
if (fmgr_isbuiltin_index(fo))
ct++;
}
if (ct != fmgr_nbuiltins)
elog(ERROR, "got %d builtins instead of %d", ct, fmgr_nbuiltins);
}
INSTR_TIME_SET_CURRENT(end_time);
INSTR_TIME_SUBTRACT(end_time, start_time);
elog(NOTICE, "index runtime %.3f ms",
1000.0 * INSTR_TIME_GET_DOUBLE(end_time));
PG_RETURN_VOID();
}
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 09/27/2017 05:29 PM, tushar wrote: After discussion with Jeevan Ladhe, we created a sql query which contain lots of inbuild function and tested that against pgbench with master v/s patch and found an improvement I tested it again and found around +2% improvement ./pgbench -c 8 -j 8 -f /tmp/mytest.sql -T =TIME After taking Median of 3 run - Case 1 – TIME=300 PG HEAD =>tps = 7831.999245 (excluding connections establishing) PG HEAD+patch =>tps= 8008.895177 (2.26+% vs. head) Case 2- TIME=500 PG HEAD =>tps = 7817.781756 (excluding connections establishing) PG HEAD+patch =>tps= 8050.410040(2.98+% vs. head) Case 3- TIME=1000 PG HEAD =>tps = 7817.173640 (excluding connections establishing) PG HEAD+patch => tps= 8011.784839(2.48+% vs. head) Case 4-TIME=1500 PG HEAD =>tps = 7764.607133 (excluding connections establishing) PG HEAD+patch =>tps= 8013.421628(3.20+% vs. head) -- regards,tushar EnterpriseDB https://www.enterprisedb.com/ The Enterprise PostgreSQL Company
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Andres Freund writes: > On 2017-09-27 15:06:15 -0400, Tom Lane wrote: >> Yeah, constructing an index table of that sort on top of the existing >> FmgrBuiltin array could be done cheaply enough at startup. It irks me >> slightly that it's not part of the read-only text segment, but I can't >> say that there's any really measurable impact. > I don't think this case is significant enough to make it worthwhile, but > if we'd find one that is, we certainly could add code that builds the > hash's array once in memory, then serializes that into a .h file, which > then is included into the code. I can't immediately see more of these > coming up, but who knows? Actually ... a more defensible reason for having a precomputed constant table is that it removes any question about where is a safe place in the initialization sequence to inject "fmgr_startup". That would clearly have to go before anything that could conceivably try to call a SQL function. On the other hand, it has to go after elog.c setup (in case you get e.g. a malloc failure), which means you've now created a reason why it will never be safe for elog.c to include any fmgr calls. Maybe that's unsafe anyway, but I'd just as soon not introduce constraints of that kind just because we're too lazy to do this optimization properly. There definitely are places in startup that assume they can call built-in functions (relying on fmgr_isbuiltin) long before most of the transactional infrastructure is up. ISTM it shouldn't be that hard to get Gen_fmgrtab.pl to emit an index array of the sort we're talking about, along with the FmgrBuiltin array it already prints out. I'm the world's worst Perl programmer but I'm happy to take a stab at it if you don't want to. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 2017-09-27 15:30:45 -0400, Robert Haas wrote: > On Wed, Sep 27, 2017 at 1:40 PM, Andres Freund wrote: > > I don't think you can even measure the overhead of building the > > table. This is inserting ~8k rows in an accurately sized hashtable - a > > vanishingly small amount of time in comparison to the backend startup > > time (and even more so postmaster startup). My measurement shows it > > takes about 0.4 ms to build (gdb in, query, reset oid2builtins = 0, > > query - repeat a couple times). > > 0.4ms isn't negligible as a fraction of backend startup time, is it? Well, on linux you'd only have this on postmaster startup. > I think backend startup time is a few milliseconds. > > $ echo '\set x 1' > x.txt > $ pgbench -n -C -c 1 -f x.txt -T 10 > transaction type: x.txt > scaling factor: 1 > query mode: simple > number of clients: 1 > number of threads: 1 > duration: 10 s > number of transactions actually processed: 5091 > latency average = 1.965 ms > tps = 508.866931 (including connections establishing) > tps = 12909.303693 (excluding connections establishing) I had tried this with an actual simplistic query, and the difference was either nonexistant, or below in the noise. I didn't do a pgbench run that doesn't actually do anything in the backend - doesn't seem like a meaningful thing to measure? Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On Wed, Sep 27, 2017 at 1:40 PM, Andres Freund wrote: > I don't think you can even measure the overhead of building the > table. This is inserting ~8k rows in an accurately sized hashtable - a > vanishingly small amount of time in comparison to the backend startup > time (and even more so postmaster startup). My measurement shows it > takes about 0.4 ms to build (gdb in, query, reset oid2builtins = 0, > query - repeat a couple times). 0.4ms isn't negligible as a fraction of backend startup time, is it? I think backend startup time is a few milliseconds. $ echo '\set x 1' > x.txt $ pgbench -n -C -c 1 -f x.txt -T 10 transaction type: x.txt scaling factor: 1 query mode: simple number of clients: 1 number of threads: 1 duration: 10 s number of transactions actually processed: 5091 latency average = 1.965 ms tps = 508.866931 (including connections establishing) tps = 12909.303693 (excluding connections establishing) -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Hi, On 2017-09-27 15:06:15 -0400, Tom Lane wrote: > Yeah, constructing an index table of that sort on top of the existing > FmgrBuiltin array could be done cheaply enough at startup. It irks me > slightly that it's not part of the read-only text segment, but I can't > say that there's any really measurable impact. I don't think this case is significant enough to make it worthwhile, but if we'd find one that is, we certainly could add code that builds the hash's array once in memory, then serializes that into a .h file, which then is included into the code. I can't immediately see more of these coming up, but who knows? Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Andres Freund writes: > On 2017-09-27 14:58:36 -0400, Tom Lane wrote: >> Yeah, I'd been kind of wondering about that approach too. We could have, >> say, a table of int16s indexed by OIDs from 0 to , containing zero or >> an index into the table of FmgrBuiltin structs. So 2 bytes of >> constant data, and O(negligible) lookup time other than possible cache >> misses on this table. But a dynahash-ish hash table built for 2800+ >> entries would probably be about that size ... > Well dynahash is *way* too slow for this. But that's pretty much what > the simplehash approach is already doing, anyway. Right now I think the > correct approach would be to just add an fmgr_startup() function, called > by postmaster / backend startup if EXEC_BACKEND. Yeah, constructing an index table of that sort on top of the existing FmgrBuiltin array could be done cheaply enough at startup. It irks me slightly that it's not part of the read-only text segment, but I can't say that there's any really measurable impact. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 2017-09-27 14:58:36 -0400, Tom Lane wrote: > Andres Freund writes: > > Honestly before going there I'd rather just have > > an oid indexed array, computed at compile time. > > Yeah, I'd been kind of wondering about that approach too. We could have, > say, a table of int16s indexed by OIDs from 0 to , containing zero or > an index into the table of FmgrBuiltin structs. So 2 bytes of > constant data, and O(negligible) lookup time other than possible cache > misses on this table. But a dynahash-ish hash table built for 2800+ > entries would probably be about that size ... Well dynahash is *way* too slow for this. But that's pretty much what the simplehash approach is already doing, anyway. Right now I think the correct approach would be to just add an fmgr_startup() function, called by postmaster / backend startup if EXEC_BACKEND. Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Andres Freund writes: > Honestly before going there I'd rather just have > an oid indexed array, computed at compile time. Yeah, I'd been kind of wondering about that approach too. We could have, say, a table of int16s indexed by OIDs from 0 to , containing zero or an index into the table of FmgrBuiltin structs. So 2 bytes of constant data, and O(negligible) lookup time other than possible cache misses on this table. But a dynahash-ish hash table built for 2800+ entries would probably be about that size ... regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 2017-09-27 14:40:20 -0400, Tom Lane wrote: > Andres Freund writes: > > On 2017-09-27 13:46:50 -0400, Tom Lane wrote: > >> The other question that ought to be answered is whether a gperf hash > >> table would be faster. > > > Ugh, hacking together a quick input file for gperf, I'm *far* from > > convinced. The generated code does multiple lookups in significantly > > sized arrays, and assumes string input. The latter seems like a complete > > dealbreaker, and there doesn't seem to be an option to turn it off. > > Ugh. I'd never actually used gperf, and now I know why not ;-) Heh. > However, that's just the first tool that came to mind. Wikipedia's > article on perfect hashes links to our man Jenkins: > > http://burtleburtle.net/bob/hash/perfect.html > > which looks pretty promising. OTOH, that'd pretty much mean we'd have to include this code in our tree - we can't really expect everyone adding a function to download & compile this manually. Honestly before going there I'd rather just have an oid indexed array, computed at compile time. I've the slight feeling of forgoing the good for the perfect here... Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Andres Freund writes: > On 2017-09-27 13:46:50 -0400, Tom Lane wrote: >> The other question that ought to be answered is whether a gperf hash >> table would be faster. > Ugh, hacking together a quick input file for gperf, I'm *far* from > convinced. The generated code does multiple lookups in significantly > sized arrays, and assumes string input. The latter seems like a complete > dealbreaker, and there doesn't seem to be an option to turn it off. Ugh. I'd never actually used gperf, and now I know why not ;-) However, that's just the first tool that came to mind. Wikipedia's article on perfect hashes links to our man Jenkins: http://burtleburtle.net/bob/hash/perfect.html which looks pretty promising. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Andres Freund writes: > On 2017-09-27 11:50:56 -0400, Tom Lane wrote: >> Robert Haas writes: >>> I suppose an even better approach would be to build a perfect hash >>> table at compile time so that nothing needs to be built at run-time at >>> all, but I'm not sure it's worth the trouble. >> Yeah, I was wondering about that too. It would likely mean adding a >> compile time dependency on gperf or similar tool, but we could take >> our standard approach of shipping the output in tarballs, so that only >> developers would really need to install that tool. > I'd been wondering about that too, but I'm not sure I buy that it's > worth the effort. The only real argument I see is that there's probably > multiple cases where it'd be potentially beneficial, not just here. The other question that ought to be answered is whether a gperf hash table would be faster. In principle it could be because of guaranteed-no-collisions, but I have no experience with how fast the constructed hash functions might be compared to our regular one. To me, the real takeaway from this thread is that fmgr_isbuiltin() needs optimization at all; I'd have guessed it didn't matter. But now that we know that it does, it's worth looking hard at what we can squeeze out of it. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 2017-09-27 13:28:22 -0400, Robert Haas wrote: > On Wed, Sep 27, 2017 at 1:00 PM, Andres Freund wrote: > > We could relatively easily move it to be once-per-postmaster start for > > !EXEC_BACKEND builds. Constantly doing expensive binary searches is also > > pretty brute force ;) > > I think one useful way to look at it might be - > > How many fmgr searches does a backend need to do in order to make up > for the time spent building the hash table? > > How many fmgr searches, if any, do we do during backend startup as a > matter of course? > > If we're going to make up the time that it takes to build the hash > table by the time the user runs a handful of queries, there's really > no point in stressing about this. The use case where somebody > repeatedly connects and disconnects without running any significant > number of real queries is not an important one. I don't think you can even measure the overhead of building the table. This is inserting ~8k rows in an accurately sized hashtable - a vanishingly small amount of time in comparison to the backend startup time (and even more so postmaster startup). My measurement shows it takes about 0.4 ms to build (gdb in, query, reset oid2builtins = 0, query - repeat a couple times). Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On Wed, Sep 27, 2017 at 1:00 PM, Andres Freund wrote: > We could relatively easily move it to be once-per-postmaster start for > !EXEC_BACKEND builds. Constantly doing expensive binary searches is also > pretty brute force ;) I think one useful way to look at it might be - How many fmgr searches does a backend need to do in order to make up for the time spent building the hash table? How many fmgr searches, if any, do we do during backend startup as a matter of course? If we're going to make up the time that it takes to build the hash table by the time the user runs a handful of queries, there's really no point in stressing about this. The use case where somebody repeatedly connects and disconnects without running any significant number of real queries is not an important one. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 2017-09-27 11:50:56 -0400, Tom Lane wrote: > Robert Haas writes: > > I suppose an even better approach would be to build a perfect hash > > table at compile time so that nothing needs to be built at run-time at > > all, but I'm not sure it's worth the trouble. > > Yeah, I was wondering about that too. It would likely mean adding a > compile time dependency on gperf or similar tool, but we could take > our standard approach of shipping the output in tarballs, so that only > developers would really need to install that tool. I'd been wondering about that too, but I'm not sure I buy that it's worth the effort. The only real argument I see is that there's probably multiple cases where it'd be potentially beneficial, not just here. > Rebuilding a constant table during every backend start seems like a > pretty brute-force answer. We could relatively easily move it to be once-per-postmaster start for !EXEC_BACKEND builds. Constantly doing expensive binary searches is also pretty brute force ;) I've been wondering about not actually eagerly filling that hashtable, but using it for pretty much all of fmgr.c - but that seems like a good chunk more work... Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Robert Haas writes: > I suppose an even better approach would be to build a perfect hash > table at compile time so that nothing needs to be built at run-time at > all, but I'm not sure it's worth the trouble. Yeah, I was wondering about that too. It would likely mean adding a compile time dependency on gperf or similar tool, but we could take our standard approach of shipping the output in tarballs, so that only developers would really need to install that tool. Rebuilding a constant table during every backend start seems like a pretty brute-force answer. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On Wed, Sep 27, 2017 at 11:18 AM, Robert Haas wrote: > No, I think what Andres is saying is that we ought to build the hash > table before we ever reach this function, so that we don't have to > have a branch here to check whether it's been done. I don't see why > that's particularly hard -- it can be jammed into the startup sequence > someplace early, I assume. In EXEC_BACKEND builds it will have to be > redone in each child, but that's just a matter of sticking a call into > SubPostmasterMain() as well as PostMasterMain(). I suppose an even better approach would be to build a perfect hash table at compile time so that nothing needs to be built at run-time at all, but I'm not sure it's worth the trouble. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On Mon, Sep 25, 2017 at 8:42 AM, Jeevan Ladhe wrote: > As Andres has already pointed, may be we want to move above code in a > separate > function, and just call that function here in case the hash is not already > built. No, I think what Andres is saying is that we ought to build the hash table before we ever reach this function, so that we don't have to have a branch here to check whether it's been done. I don't see why that's particularly hard -- it can be jammed into the startup sequence someplace early, I assume. In EXEC_BACKEND builds it will have to be redone in each child, but that's just a matter of sticking a call into SubPostmasterMain() as well as PostMasterMain(). Aside from that issue, this seems like a pretty boring patch. If a hash table is faster than a binary search, then it is. Using simplehash makes sense for this application, I think, and I'm not really sure what else there is to say. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
On 09/14/2017 12:21 PM, Andres Freund wrote: Hi, Surprising myself I discovered that in workloads that do a large number of fmgr_info* lookups, fmgr_isbuiltin() is actually quite the bottleneck. After discussion with Jeevan Ladhe, we created a sql query which contain lots of inbuild function and tested that against pgbench with master v/s patch and found an improvement Virtual Machine configuration - Centos 6.5 x64 / 16 GB RAM / 8 VCPU core processor pgbench -c 8 -j 8 -f /tmy/mytest.sql -T 300 postgres PG Head - tps = 5309.810807 (excluding connections establishing). PG HEAD+patch - tps = 5751.745767(8.32+% vs. head) pgbench -c 8 -j 8 -f /tmp/mytest.sql -T 500 postgres PG Head - tps = 7701.176220(excluding connections establishing). PG HEAD+patch - tps = 7953.934043(3.27+% vs. head) -- regards,tushar EnterpriseDB https://www.enterprisedb.com/ The Enterprise PostgreSQL Company mytest.sql Description: application/sql -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
Hi Andres,
Another idea would be to have an array of FmgrBuiltin*, that we index by
> oid. That'd not be super small though, given that the space for function
> oids is sparse.
>
>
I totally agree here, as the oids are very much scattered having an
array is not feasible here.
> Thus what I've instead done is replacing the binary search in
> fmgr_isbuiltin() with a simplehash.h style hashtable. After that the
> lookup is still visible in the profile, but far less prominent.
>
> I'd like to move the hash creation out of fmgr_isbuiltin (to avoid
> having to check whether it's already created), but there's currently no
> convenient place to create the hash from. Now that we don't rely on
> the sortedness of fmgrtab.c we could remove a few lines from
> Gen_fmgrtab.pl, but I don't quite see the advantage. If we were
> interested in a faster by-name lookup we could sort it by name, but
> that'd be better solved by another hashtable...
>
I looked into these patches.
Seems patch 004 is already committed, commit id:
791961f59b792fbd4f0a992d3ccab47298e79103
About patch 0005:
The patch still applies cleanly.
There are no failures in ‘make check’
+ /* TODO: it'd be better if this were done separately */
+ if (unlikely(oid2builtins == NULL))
{
- int i = (high + low) / 2;
- const FmgrBuiltin *ptr = &fmgr_builtins[i];
+ int i;
- if (id == ptr->foid)
- return ptr;
- else if (id > ptr->foid)
- low = i + 1;
- else
- high = i - 1;
+ oid2builtins = oid2builtins_create(TopMemoryContext,
+ fmgr_nbuiltins,
+ NULL);
+ for (i = 0; i < fmgr_nbuiltins; i++)
+ {
+ const FmgrBuiltin *ptr = &fmgr_builtins[i];
+ bool found;
+
+ entry = oid2builtins_insert(oid2builtins, ptr->foid, &found);
+ Assert(!found);
+ entry->builtin = ptr;
+ }
As Andres has already pointed, may be we want to move above code in a
separate
function, and just call that function here in case the hash is not already
built.
Further I am thinking about doing some performance testing, Andres can you
please
point me how did you test it and what perf numbers you saw for this
particular patch(0005).
Regards,
Jeevan Ladhe
