use rotate macro in more places
We've accumulated a few bit-twiddling hacks to get the compiler to
emit a rotate instruction. Since we have a macro for that, let's use
it, as in the attached. I thought the new call sites would look better
with a "left" version, so I added a new macro for that. That's not
necessary, however.
Some comments now look a bit too obvious to keep around, but maybe
they should be replaced with a "why", instead of a "what":
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey &
0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
--
John Naylor
EDB: http://www.enterprisedb.com
Attachments:
use-rotate-macros.patchtext/x-patch; charset=US-ASCII; name=use-rotate-macros.patchDownload
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index af6e9c42d8..ce8f6cd047 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -460,7 +460,7 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
bool isNull;
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
attr = slot_getattr(slot, att, &isNull);
diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 4d68a8b97b..6f9d0f9487 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -1841,7 +1841,7 @@ ExecHashGetHashValue(HashJoinTable hashtable,
bool isNull;
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
/*
* Get the join attribute value of the tuple
diff --git a/src/backend/executor/nodeMemoize.c b/src/backend/executor/nodeMemoize.c
index 55cdd5c4d9..e32e4c04e6 100644
--- a/src/backend/executor/nodeMemoize.c
+++ b/src/backend/executor/nodeMemoize.c
@@ -167,7 +167,7 @@ MemoizeHash_hash(struct memoize_hash *tb, const MemoizeKey *key)
for (int i = 0; i < numkeys; i++)
{
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
if (!pslot->tts_isnull[i]) /* treat nulls as having hash key 0 */
{
@@ -190,7 +190,7 @@ MemoizeHash_hash(struct memoize_hash *tb, const MemoizeKey *key)
for (int i = 0; i < numkeys; i++)
{
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
if (!pslot->tts_isnull[i]) /* treat nulls as having hash key 0 */
{
diff --git a/src/backend/utils/cache/catcache.c b/src/backend/utils/cache/catcache.c
index eb83088089..ec073e1ed0 100644
--- a/src/backend/utils/cache/catcache.c
+++ b/src/backend/utils/cache/catcache.c
@@ -26,6 +26,7 @@
#include "catalog/pg_type.h"
#include "common/hashfn.h"
#include "miscadmin.h"
+#include "port/pg_bitutils.h"
#ifdef CATCACHE_STATS
#include "storage/ipc.h" /* for on_proc_exit */
#endif
@@ -281,25 +282,18 @@ CatalogCacheComputeHashValue(CatCache *cache, int nkeys,
{
case 4:
oneHash = (cc_hashfunc[3]) (v4);
-
- hashValue ^= oneHash << 24;
- hashValue ^= oneHash >> 8;
+ hashValue ^= pg_rotate_left32(oneHash, 24);
/* FALLTHROUGH */
case 3:
oneHash = (cc_hashfunc[2]) (v3);
-
- hashValue ^= oneHash << 16;
- hashValue ^= oneHash >> 16;
+ hashValue ^= pg_rotate_left32(oneHash, 16);
/* FALLTHROUGH */
case 2:
oneHash = (cc_hashfunc[1]) (v2);
-
- hashValue ^= oneHash << 8;
- hashValue ^= oneHash >> 24;
+ hashValue ^= pg_rotate_left32(oneHash, 8);
/* FALLTHROUGH */
case 1:
oneHash = (cc_hashfunc[0]) (v1);
-
hashValue ^= oneHash;
break;
default:
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 44c74fb974..65aa5ec29d 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -285,12 +285,18 @@ extern int pg_popcount64(uint64 word);
extern uint64 pg_popcount(const char *buf, int bytes);
/*
- * Rotate the bits of "word" to the right by n bits.
+ * Rotate the bits of word to the right/left by n bits.
*/
static inline uint32
pg_rotate_right32(uint32 word, int n)
{
- return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
+ return (word >> n) | (word << (32 - n));
+}
+
+static inline uint32
+pg_rotate_left32(uint32 word, int n)
+{
+ return (word << n) | (word >> (32 - n));
}
#endif /* PG_BITUTILS_H */
John Naylor <john.naylor@enterprisedb.com> writes:
We've accumulated a few bit-twiddling hacks to get the compiler to
emit a rotate instruction. Since we have a macro for that, let's use
it, as in the attached. I thought the new call sites would look better
with a "left" version, so I added a new macro for that. That's not
necessary, however.
+1 --- I didn't look to see if you missed any spots, but this is
good as far as it goes.
Some comments now look a bit too obvious to keep around, but maybe
they should be replaced with a "why", instead of a "what":
Yeah. Maybe like "combine successive hashkeys by rotating"?
regards, tom lane
On Sat, 19 Feb 2022 20:07:58 +0700
John Naylor <john.naylor@enterprisedb.com> wrote:
We've accumulated a few bit-twiddling hacks to get the compiler to
emit a rotate instruction. Since we have a macro for that, let's use
it, as in the attached. I thought the new call sites would look better
with a "left" version, so I added a new macro for that. That's not
necessary, however.Some comments now look a bit too obvious to keep around, but maybe
they should be replaced with a "why", instead of a "what":/* rotate hashkey left 1 bit at each step */ - hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0); + hashkey = pg_rotate_left32(hashkey, 1);
I think we can use this macro also in hash_multirange, hash_range,
and JsonbHashScalarValue as in the attached patch. How about replacing
them with the macro, too.
For avoiding undefined behaviours, maybe it is better to use unsigned
int and bit mask as a following code in Linux does[1]https://github.com/torvalds/linux/blob/master/include/linux/bitops.h[2]https://lore.kernel.org/lkml/20190609164129.126354143@linuxfoundation.org/, though it
would be unnecessary if they are used properly as in the current
PostgreSQL code.
static inline __u32 rol32(__u32 word, unsigned int shift)
{
return (word << (shift & 31)) | (word >> ((-shift) & 31));
}
[1]: https://github.com/torvalds/linux/blob/master/include/linux/bitops.h
[2]: https://lore.kernel.org/lkml/20190609164129.126354143@linuxfoundation.org/
Regards,
Yugo Nagata
--
John Naylor
EDB: http://www.enterprisedb.com
--
Yugo NAGATA <nagata@sraoss.co.jp>
Attachments:
use-rotate-macros-v2.patchtext/x-diff; name=use-rotate-macros-v2.patchDownload
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index af6e9c42d8..ce8f6cd047 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -460,7 +460,7 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
bool isNull;
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
attr = slot_getattr(slot, att, &isNull);
diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 4d68a8b97b..6f9d0f9487 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -1841,7 +1841,7 @@ ExecHashGetHashValue(HashJoinTable hashtable,
bool isNull;
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
/*
* Get the join attribute value of the tuple
diff --git a/src/backend/executor/nodeMemoize.c b/src/backend/executor/nodeMemoize.c
index 55cdd5c4d9..e32e4c04e6 100644
--- a/src/backend/executor/nodeMemoize.c
+++ b/src/backend/executor/nodeMemoize.c
@@ -167,7 +167,7 @@ MemoizeHash_hash(struct memoize_hash *tb, const MemoizeKey *key)
for (int i = 0; i < numkeys; i++)
{
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
if (!pslot->tts_isnull[i]) /* treat nulls as having hash key 0 */
{
@@ -190,7 +190,7 @@ MemoizeHash_hash(struct memoize_hash *tb, const MemoizeKey *key)
for (int i = 0; i < numkeys; i++)
{
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
if (!pslot->tts_isnull[i]) /* treat nulls as having hash key 0 */
{
diff --git a/src/backend/utils/adt/jsonb_util.c b/src/backend/utils/adt/jsonb_util.c
index 291fb722e2..60442758b3 100644
--- a/src/backend/utils/adt/jsonb_util.c
+++ b/src/backend/utils/adt/jsonb_util.c
@@ -18,6 +18,7 @@
#include "common/hashfn.h"
#include "common/jsonapi.h"
#include "miscadmin.h"
+#include "port/pg_bitutils.h"
#include "utils/builtins.h"
#include "utils/datetime.h"
#include "utils/json.h"
@@ -1342,7 +1343,7 @@ JsonbHashScalarValue(const JsonbValue *scalarVal, uint32 *hash)
* the previous value left 1 bit, then XOR'ing in the new
* key/value/element's hash value.
*/
- *hash = (*hash << 1) | (*hash >> 31);
+ *hash = pg_rotate_left32(*hash, 1);
*hash ^= tmp;
}
diff --git a/src/backend/utils/adt/multirangetypes.c b/src/backend/utils/adt/multirangetypes.c
index 7b86421465..c8c1ee8fe9 100644
--- a/src/backend/utils/adt/multirangetypes.c
+++ b/src/backend/utils/adt/multirangetypes.c
@@ -2772,7 +2772,7 @@ hash_multirange(PG_FUNCTION_ARGS)
/* Merge hashes of flags and bounds */
range_hash = hash_uint32((uint32) flags);
range_hash ^= lower_hash;
- range_hash = (range_hash << 1) | (range_hash >> 31);
+ range_hash = pg_rotate_left32(range_hash, 1);
range_hash ^= upper_hash;
/*
diff --git a/src/backend/utils/adt/rangetypes.c b/src/backend/utils/adt/rangetypes.c
index c3e6c721e6..cbff4e93d5 100644
--- a/src/backend/utils/adt/rangetypes.c
+++ b/src/backend/utils/adt/rangetypes.c
@@ -35,6 +35,7 @@
#include "lib/stringinfo.h"
#include "libpq/pqformat.h"
#include "miscadmin.h"
+#include "port/pg_bitutils.h"
#include "utils/builtins.h"
#include "utils/date.h"
#include "utils/lsyscache.h"
@@ -1363,7 +1364,7 @@ hash_range(PG_FUNCTION_ARGS)
/* Merge hashes of flags and bounds */
result = hash_uint32((uint32) flags);
result ^= lower_hash;
- result = (result << 1) | (result >> 31);
+ result = pg_rotate_left32(result, 1);
result ^= upper_hash;
PG_RETURN_INT32(result);
diff --git a/src/backend/utils/cache/catcache.c b/src/backend/utils/cache/catcache.c
index eb83088089..ec073e1ed0 100644
--- a/src/backend/utils/cache/catcache.c
+++ b/src/backend/utils/cache/catcache.c
@@ -26,6 +26,7 @@
#include "catalog/pg_type.h"
#include "common/hashfn.h"
#include "miscadmin.h"
+#include "port/pg_bitutils.h"
#ifdef CATCACHE_STATS
#include "storage/ipc.h" /* for on_proc_exit */
#endif
@@ -281,25 +282,18 @@ CatalogCacheComputeHashValue(CatCache *cache, int nkeys,
{
case 4:
oneHash = (cc_hashfunc[3]) (v4);
-
- hashValue ^= oneHash << 24;
- hashValue ^= oneHash >> 8;
+ hashValue ^= pg_rotate_left32(oneHash, 24);
/* FALLTHROUGH */
case 3:
oneHash = (cc_hashfunc[2]) (v3);
-
- hashValue ^= oneHash << 16;
- hashValue ^= oneHash >> 16;
+ hashValue ^= pg_rotate_left32(oneHash, 16);
/* FALLTHROUGH */
case 2:
oneHash = (cc_hashfunc[1]) (v2);
-
- hashValue ^= oneHash << 8;
- hashValue ^= oneHash >> 24;
+ hashValue ^= pg_rotate_left32(oneHash, 8);
/* FALLTHROUGH */
case 1:
oneHash = (cc_hashfunc[0]) (v1);
-
hashValue ^= oneHash;
break;
default:
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 44c74fb974..65aa5ec29d 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -285,12 +285,18 @@ extern int pg_popcount64(uint64 word);
extern uint64 pg_popcount(const char *buf, int bytes);
/*
- * Rotate the bits of "word" to the right by n bits.
+ * Rotate the bits of word to the right/left by n bits.
*/
static inline uint32
pg_rotate_right32(uint32 word, int n)
{
- return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
+ return (word >> n) | (word << (32 - n));
+}
+
+static inline uint32
+pg_rotate_left32(uint32 word, int n)
+{
+ return (word << n) | (word >> (32 - n));
}
#endif /* PG_BITUTILS_H */
Yugo NAGATA <nagata@sraoss.co.jp> writes:
For avoiding undefined behaviours, maybe it is better to use unsigned
int and bit mask as a following code in Linux does[1][2], though it
would be unnecessary if they are used properly as in the current
PostgreSQL code.
I don't think that's an improvement. It would mask buggy calls.
regards, tom lane
On Sun, Feb 20, 2022 at 1:03 AM Yugo NAGATA <nagata@sraoss.co.jp> wrote:
I think we can use this macro also in hash_multirange, hash_range,
and JsonbHashScalarValue as in the attached patch. How about replacing
them with the macro, too.
Good find. I also found one more in hashfn.c.
On Sat, Feb 19, 2022 at 11:28 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Some comments now look a bit too obvious to keep around, but maybe
they should be replaced with a "why", instead of a "what":Yeah. Maybe like "combine successive hashkeys by rotating"?
Done that way.
Pushed, thank you both for looking!
--
John Naylor
EDB: http://www.enterprisedb.com