Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.

2017-10-05 Thread Tom Lane 
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.

2017-10-05 Thread Andres Freund 
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.

2017-10-05 Thread Heikki Linnakangas 

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.

2017-10-04 Thread Andres Freund 
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.

2017-10-02 Thread Andres Freund 
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.

2017-10-02 Thread Tom Lane 
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.

2017-10-02 Thread Andres Freund 
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 <

Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.

2017-09-28 Thread Tom Lane 
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.

2017-09-28 Thread Andres Freund 
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.

2017-09-28 Thread Tom Lane 
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.

2017-09-28 Thread Andres Freund 
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
+++

Re: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.

2017-09-28 Thread Tom Lane 
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 = _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 = _builtins[i];
		BuiltinOidLookupEntry *entry;
		bool		found;

		entry = oid2builtins_insert(oid2builtins, ptr->foid, );
		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 _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 = _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.

2017-09-28 Thread tushar 

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.

2017-09-27 Thread Tom Lane 
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.

2017-09-27 Thread Andres Freund 
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.

2017-09-27 Thread Robert Haas 
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.

2017-09-27 Thread Andres Freund 
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.

2017-09-27 Thread Tom Lane 
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.

2017-09-27 Thread Andres Freund 
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.

2017-09-27 Thread Tom Lane 
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.

2017-09-27 Thread Andres Freund 
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.

2017-09-27 Thread Tom Lane 
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.

2017-09-27 Thread Tom Lane 
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.

2017-09-27 Thread Andres Freund 
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.

2017-09-27 Thread Robert Haas 
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.

2017-09-27 Thread Andres Freund 
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.

2017-09-27 Thread Tom Lane 
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.

2017-09-27 Thread Robert Haas 
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.

2017-09-27 Thread Robert Haas 
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.

2017-09-27 Thread tushar 

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.

2017-09-25 Thread Jeevan Ladhe 
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 = _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 = _builtins[i];
+ bool found;
+
+ entry = oid2builtins_insert(oid2builtins, ptr->foid, );
+ 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

[HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.

2017-09-14 Thread Andres Freund 
Hi,

Surprising myself I discovered that in workloads that do a large number
of fmgr_info* lookups, fmgr_isbuiltin() is actually quite the
bottleneck.

In my development build we have 2765 builtin functions, stored in a 88KB
array. Apparently the ~12 steps are quite noticeable. Generally binary
searches have quite a poor memory access pattern...

In the workload I playing around with right now (producing this wall of
performance fixes) the main source of lookups is
printtup_prepare_info(), which does a fmgr_info for every column. If you
have a large number of columns ...

I think we could conceivable deduplicate the output functions for
printtup to one FmgrInfo per type? I'd assume that it'd be good for
things besides reducing the overhead - alowing the respective function
to reuse fn_extra might be quite good.  I've not implemented that idea
at this point, I'm not 100% what the best way to do so is without also
causing slowdowns.

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.

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 was wondering about also replacing the C function hash with a
simplehash, but given that I've not seen this in profiles, I've not
bothered so far.

Greetings,

Andres Freund
>From 2b3e06380d5a339efc94e748aa57985d3bb80223 Mon Sep 17 00:00:00 2001
From: Andres Freund 
Date: Wed, 13 Sep 2017 18:43:46 -0700
Subject: [PATCH 4/8] Add inline murmurhash32(int32) function.

The function already existed in tidbitmap.c but more users requiring
fast hashing of 32bit ints are coming up.
---
 src/backend/nodes/tidbitmap.c | 20 ++--
 src/include/utils/hashutils.h | 18 ++
 2 files changed, 20 insertions(+), 18 deletions(-)

diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c
index c4e53adb0c..01d6bc5c11 100644
--- a/src/backend/nodes/tidbitmap.c
+++ b/src/backend/nodes/tidbitmap.c
@@ -45,6 +45,7 @@
 #include "nodes/tidbitmap.h"
 #include "storage/lwlock.h"
 #include "utils/dsa.h"
+#include "utils/hashutils.h"
 
 /*
  * The maximum number of tuples per page is not large (typically 256 with
@@ -237,30 +238,13 @@ static int	tbm_comparator(const void *left, const void *right);
 static int tbm_shared_comparator(const void *left, const void *right,
 	  void *arg);
 
-/*
- * Simple inline murmur hash implementation for the exact width required, for
- * performance.
- */
-static inline uint32
-hash_blockno(BlockNumber b)
-{
-	uint32		h = b;
-
-	h ^= h >> 16;
-	h *= 0x85ebca6b;
-	h ^= h >> 13;
-	h *= 0xc2b2ae35;
-	h ^= h >> 16;
-	return h;
-}
-
 /* define hashtable mapping block numbers to PagetableEntry's */
 #define SH_USE_NONDEFAULT_ALLOCATOR
 #define SH_PREFIX pagetable
 #define SH_ELEMENT_TYPE PagetableEntry
 #define SH_KEY_TYPE BlockNumber
 #define SH_KEY blockno
-#define SH_HASH_KEY(tb, key) hash_blockno(key)
+#define SH_HASH_KEY(tb, key) murmurhash32(key)
 #define SH_EQUAL(tb, a, b) a == b
 #define SH_SCOPE static inline
 #define SH_DEFINE
diff --git a/src/include/utils/hashutils.h b/src/include/utils/hashutils.h
index 56b7bfc9cb..35281689e8 100644
--- a/src/include/utils/hashutils.h
+++ b/src/include/utils/hashutils.h
@@ -20,4 +20,22 @@ hash_combine(uint32 a, uint32 b)
 	return a;
 }
 
+
+/*
+ * Simple inline murmur hash implementation hashing a 32 bit ingeger, for
+ * performance.
+ */
+static inline uint32
+murmurhash32(uint32 data)
+{
+	uint32		h = data;
+
+	h ^= h >> 16;
+	h *= 0x85ebca6b;
+	h ^= h >> 13;
+	h *= 0xc2b2ae35;
+	h ^= h >> 16;
+	return h;
+}
+
 #endif			/* HASHUTILS_H */
-- 
2.14.1.536.g6867272d5b.dirty

>From 703ddd56fb484692c84101d1731e60f9ea81193f Mon Sep 17 00:00:00 2001
From: Andres Freund 
Date: Wed, 13 Sep 2017 19:43:02 -0700
Subject: [PATCH 5/8] Replace binary search in fmgr_isbuiltin with hashtable.

Turns out we have enough functions that the binary search is quite
noticeable in profiles.

It'd be nice if there were a better place to build the hashtable than
the first pass through fmgr_isbuiltin() but there's currently none.
---
 src/backend/utils/fmgr/fmgr.c | 63 ---
 1 file changed, 47 insertions(+), 16 deletions(-)

diff --git a/src/backend/utils/fmgr/fmgr.c b/src/backend/utils/fmgr/fmgr.c
index a7b07827e0..87867f2183 100644