On Tue, Jan 14, 2020 at 12:21:41PM -0800, Jesse Zhang wrote:
> Hi David,
>
> On Tue, Jan 14, 2020 at 9:36 AM David Fetter <[email protected]> wrote:
> >
> > Folks,
> >
> > The recent patch for distinct windowing aggregates contained a partial
> > fix of the FIXME that didn't seem entirely right, so I extracted that
> > part, changed it to use compiler intrinsics, and submit it here.
>
> The changes in hash AM and SIMPLEHASH do look like a net positive
> improvement. My biggest cringe might be in pg_bitutils:
Thanks for looking at this!
> > diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
> > index 498e532308..cc9338da25 100644
> > --- a/src/include/port/pg_bitutils.h
> > +++ b/src/include/port/pg_bitutils.h
> > @@ -145,4 +145,32 @@ pg_rotate_right32(uint32 word, int n)
> > return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
> > }
> >
> > +/* ceil(lg2(num)) */
> > +static inline uint32
> > +ceil_log2_32(uint32 num)
> > +{
> > + return pg_leftmost_one_pos32(num-1) + 1;
> > +}
> > +
> > +static inline uint64
> > +ceil_log2_64(uint64 num)
> > +{
> > + return pg_leftmost_one_pos64(num-1) + 1;
> > +}
> > +
> > +/* calculate first power of 2 >= num
> > + * per https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
> > + * using BSR where available */
> > +static inline uint32
> > +next_power_of_2_32(uint32 num)
> > +{
> > + return ((uint32) 1) << (pg_leftmost_one_pos32(num-1) + 1);
> > +}
> > +
> > +static inline uint64
> > +next_power_of_2_64(uint64 num)
> > +{
> > + return ((uint64) 1) << (pg_leftmost_one_pos64(num-1) + 1);
> > +}
> > +
> > #endif /* PG_BITUTILS_H */
> >
>
> 1. Is ceil_log2_64 dead code?
Let's call it nascent code. I suspect there are places it could go, if
I look for them. Also, it seemed silly to have one without the other.
> 2. The new utilities added here (ceil_log2_32 and company,
> next_power_of_2_32 and company) all require num > 1, but don't clearly
> Assert (or at the very least document) so.
Assert()ed.
> 3. A couple of the callers can actively pass in an argument of 1, e.g.
> from _hash_spareindex in hashutil.c, while some other callers are iffy
> at best (simplehash.h maybe?)
What would you recommend be done about this?
> 4. It seems like you *really* would like an operation like LZCNT in x86
> (first appearing in Haswell) that is well defined on zero input. ISTM
> the alternatives are:
>
> a) Special case 1. That seems straightforward, but the branching cost
> on a seemingly unlikely condition seems to be a lot of performance
> loss
>
> b) Use architecture specific intrinsic (and possibly with CPUID
> shenanigans) like __builtin_ia32_lzcnt_u64 on x86 and use the CLZ
> intrinsic elsewhere. The CLZ GCC intrinsic seems to map to
> instructions that are well defined on zero in most ISA's other than
> x86, so maybe we can get away with special-casing x86?
b) seems much more attractive. Is there some way to tilt the tools so
that this happens? What should I be reading up on?
Best,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778
Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate
>From b542c9efb4f4ec3999a9e6a6b180d98fca3a5101 Mon Sep 17 00:00:00 2001
From: David Fetter <[email protected]>
Date: Tue, 14 Jan 2020 09:32:15 -0800
Subject: [PATCH v2] Use compiler intrinsics for bit ops in hash
To: hackers
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="------------2.24.1"
This is a multi-part message in MIME format.
--------------2.24.1
Content-Type: text/plain; charset=UTF-8; format=fixed
Content-Transfer-Encoding: 8bit
- In passing, fix the FIXME by centralizing those calls.
diff --git a/src/backend/access/hash/hashpage.c b/src/backend/access/hash/hashpage.c
index 55d85644a4..b1e04c0136 100644
--- a/src/backend/access/hash/hashpage.c
+++ b/src/backend/access/hash/hashpage.c
@@ -30,6 +30,7 @@
#include "access/hash.h"
#include "access/hash_xlog.h"
+#include "port/pg_bitutils.h"
#include "miscadmin.h"
#include "storage/lmgr.h"
#include "storage/predicate.h"
@@ -543,11 +544,7 @@ _hash_init_metabuffer(Buffer buf, double num_tuples, RegProcedure procid,
metap->hashm_ffactor = ffactor;
metap->hashm_bsize = HashGetMaxBitmapSize(page);
/* find largest bitmap array size that will fit in page size */
- for (i = _hash_log2(metap->hashm_bsize); i > 0; --i)
- {
- if ((1 << i) <= metap->hashm_bsize)
- break;
- }
+ i = pg_leftmost_one_pos32(metap->hashm_bsize);
Assert(i > 0);
metap->hashm_bmsize = 1 << i;
metap->hashm_bmshift = i + BYTE_TO_BIT;
@@ -570,7 +567,7 @@ _hash_init_metabuffer(Buffer buf, double num_tuples, RegProcedure procid,
* Set highmask as next immediate ((2 ^ x) - 1), which should be
* sufficient to cover num_buckets.
*/
- metap->hashm_highmask = (1 << (_hash_log2(num_buckets + 1))) - 1;
+ metap->hashm_highmask = next_power_of_2_32(num_buckets + 1) - 1;
metap->hashm_lowmask = (metap->hashm_highmask >> 1);
MemSet(metap->hashm_spares, 0, sizeof(metap->hashm_spares));
@@ -657,13 +654,12 @@ restart_expand:
* Can't split anymore if maxbucket has reached its maximum possible
* value.
*
- * Ideally we'd allow bucket numbers up to UINT_MAX-1 (no higher because
- * the calculation maxbucket+1 mustn't overflow). Currently we restrict
- * to half that because of overflow looping in _hash_log2() and
- * insufficient space in hashm_spares[]. It's moot anyway because an
- * index with 2^32 buckets would certainly overflow BlockNumber and hence
- * _hash_alloc_buckets() would fail, but if we supported buckets smaller
- * than a disk block then this would be an independent constraint.
+ * Ideally we'd allow bucket numbers up to UINT_MAX-1 (no higher because the
+ * calculation maxbucket+1 mustn't overflow). Currently we restrict to half
+ * that because of insufficient space in hashm_spares[]. It's moot anyway
+ * because an index with 2^32 buckets would certainly overflow BlockNumber
+ * and hence _hash_alloc_buckets() would fail, but if we supported buckets
+ * smaller than a disk block then this would be an independent constraint.
*
* If you change this, see also the maximum initial number of buckets in
* _hash_init().
diff --git a/src/backend/access/hash/hashsort.c b/src/backend/access/hash/hashsort.c
index 9cb41d62e7..322379788c 100644
--- a/src/backend/access/hash/hashsort.c
+++ b/src/backend/access/hash/hashsort.c
@@ -27,6 +27,7 @@
#include "access/hash.h"
#include "commands/progress.h"
+#include "port/pg_bitutils.h"
#include "miscadmin.h"
#include "pgstat.h"
#include "utils/tuplesort.h"
@@ -69,7 +70,7 @@ _h_spoolinit(Relation heap, Relation index, uint32 num_buckets)
* NOTE : This hash mask calculation should be in sync with similar
* calculation in _hash_init_metabuffer.
*/
- hspool->high_mask = (((uint32) 1) << _hash_log2(num_buckets + 1)) - 1;
+ hspool->high_mask = next_power_of_2_32(num_buckets + 1) - 1;
hspool->low_mask = (hspool->high_mask >> 1);
hspool->max_buckets = num_buckets - 1;
diff --git a/src/backend/access/hash/hashutil.c b/src/backend/access/hash/hashutil.c
index 9efc8016bc..738572ca40 100644
--- a/src/backend/access/hash/hashutil.c
+++ b/src/backend/access/hash/hashutil.c
@@ -17,6 +17,7 @@
#include "access/hash.h"
#include "access/reloptions.h"
#include "access/relscan.h"
+#include "port/pg_bitutils.h"
#include "storage/buf_internals.h"
#include "utils/lsyscache.h"
#include "utils/rel.h"
@@ -134,21 +135,6 @@ _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket,
return bucket;
}
-/*
- * _hash_log2 -- returns ceil(lg2(num))
- */
-uint32
-_hash_log2(uint32 num)
-{
- uint32 i,
- limit;
-
- limit = 1;
- for (i = 0; limit < num; limit <<= 1, i++)
- ;
- return i;
-}
-
/*
* _hash_spareindex -- returns spare index / global splitpoint phase of the
* bucket
@@ -159,7 +145,7 @@ _hash_spareindex(uint32 num_bucket)
uint32 splitpoint_group;
uint32 splitpoint_phases;
- splitpoint_group = _hash_log2(num_bucket);
+ splitpoint_group = ceil_log2_32(num_bucket);
if (splitpoint_group < HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)
return splitpoint_group;
diff --git a/src/include/access/hash.h b/src/include/access/hash.h
index 9fc0696096..298c05e6fe 100644
--- a/src/include/access/hash.h
+++ b/src/include/access/hash.h
@@ -450,7 +450,6 @@ extern uint32 _hash_datum2hashkey(Relation rel, Datum key);
extern uint32 _hash_datum2hashkey_type(Relation rel, Datum key, Oid keytype);
extern Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket,
uint32 highmask, uint32 lowmask);
-extern uint32 _hash_log2(uint32 num);
extern uint32 _hash_spareindex(uint32 num_bucket);
extern uint32 _hash_get_totalbuckets(uint32 splitpoint_phase);
extern void _hash_checkpage(Relation rel, Buffer buf, int flags);
diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h
index 5a6783f653..1a35a054d8 100644
--- a/src/include/lib/simplehash.h
+++ b/src/include/lib/simplehash.h
@@ -57,6 +57,8 @@
* backwards, unless they're empty or already at their optimal position.
*/
+#include "port/pg_bitutils.h"
+
/* helpers */
#define SH_MAKE_PREFIX(a) CppConcat(a,_)
#define SH_MAKE_NAME(name) SH_MAKE_NAME_(SH_MAKE_PREFIX(SH_PREFIX),name)
@@ -215,27 +217,6 @@ SH_SCOPE void SH_STAT(SH_TYPE * tb);
#ifndef SIMPLEHASH_H
#define SIMPLEHASH_H
-/* FIXME: can we move these to a central location? */
-
-/* calculate ceil(log base 2) of num */
-static inline uint64
-sh_log2(uint64 num)
-{
- int i;
- uint64 limit;
-
- for (i = 0, limit = 1; limit < num; i++, limit <<= 1)
- ;
- return i;
-}
-
-/* calculate first power of 2 >= num */
-static inline uint64
-sh_pow2(uint64 num)
-{
- return ((uint64) 1) << sh_log2(num);
-}
-
#ifdef FRONTEND
#define sh_error(...) pg_log_error(__VA_ARGS__)
#define sh_log(...) pg_log_info(__VA_ARGS__)
@@ -259,7 +240,7 @@ SH_COMPUTE_PARAMETERS(SH_TYPE * tb, uint32 newsize)
size = Max(newsize, 2);
/* round up size to the next power of 2, that's how bucketing works */
- size = sh_pow2(size);
+ size = next_power_of_2_64(size);
Assert(size <= SH_MAX_SIZE);
/*
@@ -434,7 +415,7 @@ SH_GROW(SH_TYPE * tb, uint32 newsize)
uint32 startelem = 0;
uint32 copyelem;
- Assert(oldsize == sh_pow2(oldsize));
+ Assert(oldsize == next_power_of_2_64(oldsize));
Assert(oldsize != SH_MAX_SIZE);
Assert(oldsize < newsize);
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 498e532308..f968bd65d7 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -145,4 +145,36 @@ pg_rotate_right32(uint32 word, int n)
return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
}
+/* ceil(lg2(num)) */
+static inline uint32
+ceil_log2_32(uint32 num)
+{
+ Assert(num > 1);
+ return pg_leftmost_one_pos32(num-1) + 1;
+}
+
+static inline uint64
+ceil_log2_64(uint64 num)
+{
+ Assert(num > 1);
+ return pg_leftmost_one_pos64(num-1) + 1;
+}
+
+/* calculate first power of 2 >= num
+ * per https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
+ * using BSR where available */
+static inline uint32
+next_power_of_2_32(uint32 num)
+{
+ Assert(num > 1);
+ return ((uint32) 1) << (pg_leftmost_one_pos32(num-1) + 1);
+}
+
+static inline uint64
+next_power_of_2_64(uint64 num)
+{
+ Assert(num > 1);
+ return ((uint64) 1) << (pg_leftmost_one_pos64(num-1) + 1);
+}
+
#endif /* PG_BITUTILS_H */
--------------2.24.1--
