Horton

Thread

Commits

  1. Replace binary search in fmgr_isbuiltin with a lookup array.

  2. Add inline murmurhash32(uint32) function.

  1. Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-09-14T06:51:28Z

    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

  2. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Jeevan Ladhe <jeevan.ladhe@enterprisedb.com> — 2017-09-25T12:42:59Z

    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

  3. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    tushar <tushar.ahuja@enterprisedb.com> — 2017-09-27T11:59:32Z

    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

  4. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Robert Haas <robertmhaas@gmail.com> — 2017-09-27T15:18:14Z

    On Mon, Sep 25, 2017 at 8:42 AM, Jeevan Ladhe
<jeevan.ladhe@enterprisedb.com> 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

  5. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Robert Haas <robertmhaas@gmail.com> — 2017-09-27T15:30:28Z

    On Wed, Sep 27, 2017 at 11:18 AM, Robert Haas <robertmhaas@gmail.com> 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

  6. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Tom Lane <tgl@sss.pgh.pa.us> — 2017-09-27T15:50:56Z

    Robert Haas <robertmhaas@gmail.com> 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

  7. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-09-27T17:00:32Z

    On 2017-09-27 11:50:56 -0400, Tom Lane wrote:
> Robert Haas <robertmhaas@gmail.com> 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

  8. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Robert Haas <robertmhaas@gmail.com> — 2017-09-27T17:28:22Z

    On Wed, Sep 27, 2017 at 1:00 PM, Andres Freund <andres@anarazel.de> 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

  9. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-09-27T17:40:22Z

    On 2017-09-27 13:28:22 -0400, Robert Haas wrote:
> On Wed, Sep 27, 2017 at 1:00 PM, Andres Freund <andres@anarazel.de> 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

  10. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Tom Lane <tgl@sss.pgh.pa.us> — 2017-09-27T17:46:50Z

    Andres Freund <andres@anarazel.de> writes:
> On 2017-09-27 11:50:56 -0400, Tom Lane wrote:
>> Robert Haas <robertmhaas@gmail.com> 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

  11. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-09-27T18:31:56Z

    On 2017-09-27 13:46:50 -0400, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> writes:
> > 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.

The patch uses murmurhash32, i.e. a short and fast hash, already for
performance, and it shows up in profiles.

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.

Greetings,

Andres Freund

  12. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Tom Lane <tgl@sss.pgh.pa.us> — 2017-09-27T18:40:20Z

    Andres Freund <andres@anarazel.de> 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

  13. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-09-27T18:47:36Z

    On 2017-09-27 14:40:20 -0400, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> 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

  14. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Tom Lane <tgl@sss.pgh.pa.us> — 2017-09-27T18:58:36Z

    Andres Freund <andres@anarazel.de> 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 9999, containing zero or
an index into the table of FmgrBuiltin structs.  So 20000 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

  15. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-09-27T19:02:16Z

    On 2017-09-27 14:58:36 -0400, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> 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 9999, containing zero or
> an index into the table of FmgrBuiltin structs.  So 20000 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

  16. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Tom Lane <tgl@sss.pgh.pa.us> — 2017-09-27T19:06:15Z

    Andres Freund <andres@anarazel.de> 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 9999, containing zero or
>> an index into the table of FmgrBuiltin structs.  So 20000 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

  17. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-09-27T19:11:16Z

    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

  18. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Robert Haas <robertmhaas@gmail.com> — 2017-09-27T19:30:45Z

    On Wed, Sep 27, 2017 at 1:40 PM, Andres Freund <andres@anarazel.de> 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

  19. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-09-27T19:40:04Z

    On 2017-09-27 15:30:45 -0400, Robert Haas wrote:
> On Wed, Sep 27, 2017 at 1:40 PM, Andres Freund <andres@anarazel.de> 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

  20. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Tom Lane <tgl@sss.pgh.pa.us> — 2017-09-27T19:50:05Z

    Andres Freund <andres@anarazel.de> 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

  21. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    tushar <tushar.ahuja@enterprisedb.com> — 2017-09-28T06:05:11Z

    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

  22. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Tom Lane <tgl@sss.pgh.pa.us> — 2017-09-28T18:59:45Z

    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 10000, 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

  23. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-09-28T21:48:45Z

    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

  24. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Tom Lane <tgl@sss.pgh.pa.us> — 2017-09-28T22:52:28Z

    Andres Freund <andres@anarazel.de> 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

  25. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-09-28T22:56:36Z

    On 2017-09-28 18:52:28 -0400, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> 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

  26. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Tom Lane <tgl@sss.pgh.pa.us> — 2017-09-28T23:06:27Z

    Andres Freund <andres@anarazel.de> 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

  27. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-10-02T21:44:16Z

    On 2017-09-28 19:06:27 -0400, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> 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

  28. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Tom Lane <tgl@sss.pgh.pa.us> — 2017-10-02T21:57:51Z

    Andres Freund <andres@anarazel.de> 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

  29. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-10-02T22:01:36Z

    On 2017-10-02 17:57:51 -0400, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> 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

  30. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-10-04T07:33:17Z

    On 2017-10-02 15:01:36 -0700, Andres Freund wrote:
> On 2017-10-02 17:57:51 -0400, Tom Lane wrote:
> > Andres Freund <andres@anarazel.de> 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

  31. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Heikki Linnakangas <hlinnaka@iki.fi> — 2017-10-05T14:08:39Z

    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 <andres@anarazel.de> 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 */
  	bool		strict;			/* T if function is "strict" */
  	bool		retset;			/* 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

  32. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Andres Freund <andres@anarazel.de> — 2017-10-05T17:41:31Z

    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 */
>  	bool		strict;			/* T if function is "strict" */
>  	bool		retset;			/* 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

  33. Re: Binary search in fmgr_isbuiltin() is a bottleneck.

    Tom Lane <tgl@sss.pgh.pa.us> — 2017-10-05T18:54:02Z

    Andres Freund <andres@anarazel.de> 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