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 <and...@anarazel.de>
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 <and...@anarazel.de>
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
--- a/src/backend/utils/fmgr/fmgr.c
+++ b/src/backend/utils/fmgr/fmgr.c
@@ -26,6 +26,7 @@
#include "utils/acl.h"
#include "utils/builtins.h"
#include "utils/fmgrtab.h"
+#include "utils/hashutils.h"
#include "utils/guc.h"
#include "utils/lsyscache.h"
#include "utils/syscache.h"
@@ -36,6 +37,30 @@
PGDLLIMPORT needs_fmgr_hook_type needs_fmgr_hook = NULL;
PGDLLIMPORT fmgr_hook_type fmgr_hook = 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;
+
/*
* Hashtable for fast lookup of external C functions
*/
@@ -70,26 +95,32 @@ static Datum fmgr_security_definer(PG_FUNCTION_ARGS);
static const FmgrBuiltin *
fmgr_isbuiltin(Oid id)
{
- int low = 0;
- int high = fmgr_nbuiltins - 1;
+ BuiltinOidLookupEntry *entry;
- /*
- * 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)
+ /* 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;
+ }
}
- return NULL;
+
+ entry = oid2builtins_lookup(oid2builtins, id);
+ if (entry)
+ return entry->builtin;
+ else
+ return NULL;
}
/*
--
2.14.1.536.g6867272d5b.dirty
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
