Thread: [HACKERS] Binary search in fmgr_isbuiltin() is a bottleneck.
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Attachment
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
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Attachment
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Attachment
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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 Case 1 – TIME=300 PG HEAD =>tps = 7831.999245 (excluding connections establishing) Case 2- TIME=500 PG HEAD =>tps = 7817.781756 (excluding connections establishing) Case 3- TIME=1000 PG HEAD =>tps = 7817.173640 (excluding connections establishing) Case 4-TIME=1500 PG HEAD =>tps = 7764.607133 (excluding connections establishing)
After taking Median of 3 run -
PG HEAD+patch =>tps= 8008.895177 (2.26+% vs. head)
PG HEAD+patch =>tps= 8050.410040(2.98+% vs. head)
PG HEAD+patch => tps= 8011.784839(2.48+% vs. head)
PG HEAD+patch =>tps= 8013.421628(3.20+% vs. head)
-- regards,tushar
EnterpriseDB https://www.enterprisedb.com/
The Enterprise PostgreSQL Company
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
#include "postgres.h"
#include "fmgr.h"
#include "access/transam.h"
#include "portability/instr_time.h"
#include "utils/fmgrtab.h"
#include "utils/hashutils.h"
PG_MODULE_MAGIC;
static const FmgrBuiltin *
fmgr_isbuiltin_bsearch(Oid id)
{
int low = 0;
int high = fmgr_nbuiltins - 1;
/*
* Loop invariant: low is the first index that could contain target entry,
* and high is the last index that could contain it.
*/
while (low <= high)
{
int i = (high + low) / 2;
const FmgrBuiltin *ptr = &fmgr_builtins[i];
if (id == ptr->foid)
return ptr;
else if (id > ptr->foid)
low = i + 1;
else
high = i - 1;
}
return NULL;
}
/*
* Hashtable for fast lookup builtin functions.
*/
typedef struct BuiltinOidLookupEntry
{
Oid foid;
int status;
const FmgrBuiltin *builtin;
} BuiltinOidLookupEntry;
/* define hashtable mapping block numbers to PagetableEntry's */
#define SH_PREFIX oid2builtins
#define SH_ELEMENT_TYPE BuiltinOidLookupEntry
#define SH_KEY_TYPE Oid
#define SH_KEY foid
#define SH_HASH_KEY(tb, key) murmurhash32(key)
#define SH_EQUAL(tb, a, b) a == b
#define SH_SCOPE static inline
#define SH_DEFINE
#define SH_DECLARE
#include "lib/simplehash.h"
static oid2builtins_hash * oid2builtins = 0;
static const FmgrBuiltin *
fmgr_isbuiltin_hash(Oid id)
{
BuiltinOidLookupEntry *entry;
entry = oid2builtins_lookup(oid2builtins, id);
if (entry)
return entry->builtin;
else
return NULL;
}
static void
hash_setup(void)
{
int i;
oid2builtins = oid2builtins_create(TopMemoryContext,
fmgr_nbuiltins,
NULL);
for (i = 0; i < fmgr_nbuiltins; i++)
{
const FmgrBuiltin *ptr = &fmgr_builtins[i];
BuiltinOidLookupEntry *entry;
bool found;
entry = oid2builtins_insert(oid2builtins, ptr->foid, &found);
Assert(!found);
entry->builtin = ptr;
}
}
static int16 builtins_index[FirstBootstrapObjectId];
static const FmgrBuiltin *
fmgr_isbuiltin_index(Oid id)
{
int i;
if (id >= FirstBootstrapObjectId)
return NULL;
i = builtins_index[id];
if (i < 0)
return NULL;
return &fmgr_builtins[i];
}
static void
index_setup(void)
{
int i;
memset(builtins_index, -1, sizeof(builtins_index));
for (i = 0; i < fmgr_nbuiltins; i++)
{
const FmgrBuiltin *ptr = &fmgr_builtins[i];
builtins_index[ptr->foid] = i;
}
}
PG_FUNCTION_INFO_V1(test_lookups);
Datum
test_lookups(PG_FUNCTION_ARGS)
{
int rep_count = PG_GETARG_INT32(0);
instr_time start_time;
instr_time end_time;
int i;
INSTR_TIME_SET_CURRENT(start_time);
for (i = 0; i < rep_count; i++)
{
int ct = 0;
Oid fo;
for (fo = 1; fo < 10000; 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 < 10000; 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 < 10000; 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
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Attachment
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Attachment
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers