Re: bitscan forward/reverse on Windows
On Wed, Feb 8, 2023 at 3:14 PM John Naylor wrote: > > 0001 adds asserts to the existing coding. > > 0002 adds MSVC support. Tests pass on CI, but it's of course possible that there is some bug that prevents hitting the fastpath. I've mostly used the platform specific types, so some further cleanup might be needed. > > I've cleaned these up and verified on godbolt.org that they work as intended and still pass CI. I kept the Windows types as does other Winows code in the tree, but used bool instead of unsigned char because it's used like a boolean. > > 0003 is separate because I'm not quite sure how detailed to comment the #ifdef maze. Could be left out. > 0004 simplifies AllocSetFreeIndex() in the course of supporting MSVC. The output is identical to HEAD in non-assert builds using gcc. > > 0002 through 0004 could be squashed together. > > This plugs a hole in our platform-specific intrinsic support and is fairly straightforward. Review welcome, but if there is none I intend to commit in a week or two. I've committed 0001 separately, and squashed 0002 and 0004, deciding that 0003 didn't really add to readability. -- John Naylor EDB: http://www.enterprisedb.com
Re: bitscan forward/reverse on Windows
I wrote: > Attached is a quick-and-dirty attempt to add MSVC support for the rightmost/leftmost-one-pos functions. > > 0001 adds asserts to the existing coding. > 0002 adds MSVC support. Tests pass on CI, but it's of course possible that there is some bug that prevents hitting the fastpath. I've mostly used the platform specific types, so some further cleanup might be needed. I've cleaned these up and verified on godbolt.org that they work as intended and still pass CI. I kept the Windows types as does other Winows code in the tree, but used bool instead of unsigned char because it's used like a boolean. 0003 is separate because I'm not quite sure how detailed to comment the #ifdef maze. Could be left out. 0004 simplifies AllocSetFreeIndex() in the course of supporting MSVC. The output is identical to HEAD in non-assert builds using gcc. 0002 through 0004 could be squashed together. This plugs a hole in our platform-specific intrinsic support and is fairly straightforward. Review welcome, but if there is none I intend to commit in a week or two. -- John Naylor EDB: http://www.enterprisedb.com From eb2e7f6aad9447010f34ce8d7230be754c61f6fb Mon Sep 17 00:00:00 2001 From: John Naylor Date: Wed, 8 Feb 2023 12:34:13 +0700 Subject: [PATCH v4 3/4] Add more comments to #else directives WIP: squash or leave out --- src/include/port/pg_bitutils.h | 10 +- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h index 9150789aaf..04f2fe8d3e 100644 --- a/src/include/port/pg_bitutils.h +++ b/src/include/port/pg_bitutils.h @@ -18,7 +18,7 @@ #define HAVE_BITSCAN_FORWARD #define HAVE_BITSCAN_REVERSE -#else +#else /* ! _MSC_VER */ #if defined(HAVE__BUILTIN_CTZ) #define HAVE_BITSCAN_FORWARD #endif @@ -70,7 +70,7 @@ pg_leftmost_one_pos32(uint32 word) Assert(bitscan_result == result); return bitscan_result; -#else +#else /* ! HAVE_BITSCAN_REVERSE */ return result; #endif /* HAVE_BITSCAN_REVERSE */ } @@ -119,7 +119,7 @@ pg_leftmost_one_pos64(uint64 word) Assert(bitscan_result == result); return bitscan_result; -#else +#else /* ! HAVE_BITSCAN_REVERSE */ return result; #endif /* HAVE_BITSCAN_REVERSE */ } @@ -165,7 +165,7 @@ pg_rightmost_one_pos32(uint32 word) Assert(bitscan_result == result); return bitscan_result; -#else +#else /* ! HAVE_BITSCAN_FORWARD */ return result; #endif /* HAVE_BITSCAN_FORWARD */ } @@ -217,7 +217,7 @@ pg_rightmost_one_pos64(uint64 word) Assert(bitscan_result == result); return bitscan_result; -#else +#else /* ! HAVE_BITSCAN_FORWARD */ return result; #endif /* HAVE_BITSCAN_FORWARD */ } -- 2.39.1 From 4a84bb6980fa05ae3bde84179b8427799d6ee538 Mon Sep 17 00:00:00 2001 From: John Naylor Date: Fri, 3 Feb 2023 16:54:39 +0700 Subject: [PATCH v4 4/4] Rationalize platform support in AllocSetFreeIndex Previously, we directly tested for HAVE__BUILTIN_CLZ and copied the internals of pg_leftmost_one_pos32(), with a special fallback that does less work than the general fallback for that function. In the wake of , we have MSVC support for bitscan intrinsics, and a more general way to test for them, so just call pg_leftmost_one_pos32() directly. On gcc at least, there is no difference in the binary, showing that compilers can do constant folding across the boundary of an inlined function. --- src/backend/utils/mmgr/aset.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/src/backend/utils/mmgr/aset.c b/src/backend/utils/mmgr/aset.c index 740729b5d0..d12977b7b5 100644 --- a/src/backend/utils/mmgr/aset.c +++ b/src/backend/utils/mmgr/aset.c @@ -289,7 +289,7 @@ AllocSetFreeIndex(Size size) * or equivalently * pg_leftmost_one_pos32(size - 1) - ALLOC_MINBITS + 1 * - * However, rather than just calling that function, we duplicate the + * However, for platforms without intrinsic support, we duplicate the * logic here, allowing an additional optimization. It's reasonable * to assume that ALLOC_CHUNK_LIMIT fits in 16 bits, so we can unroll * the byte-at-a-time loop in pg_leftmost_one_pos32 and just handle @@ -299,8 +299,8 @@ AllocSetFreeIndex(Size size) * much trouble. *-- */ -#ifdef HAVE__BUILTIN_CLZ - idx = 31 - __builtin_clz((uint32) size - 1) - ALLOC_MINBITS + 1; +#ifdef HAVE_BITSCAN_REVERSE + idx = pg_leftmost_one_pos32(size - 1) - ALLOC_MINBITS + 1; #else uint32 t, tsize; -- 2.39.1 From 3b75d2b05a1ed02525b86152168151300a827613 Mon Sep 17 00:00:00 2001 From: John Naylor Date: Wed, 8 Feb 2023 12:05:58 +0700 Subject: [PATCH v4 2/4] Add MSVC support for bitscan reverse/forward --- src/include/port/pg_bitutils.h | 75 ++ 1 file changed, 67 insertions(+), 8 deletions(-) diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h index a5df4f1a35..9150789aaf 100644 --- a/src/include/port/pg_bitutils.h
bitscan forward/reverse on Windows
Attached is a quick-and-dirty attempt to add MSVC support for the
rightmost/leftmost-one-pos functions.
0001 adds asserts to the existing coding.
0002 adds MSVC support. Tests pass on CI, but it's of course possible that
there is some bug that prevents hitting the fastpath. I've mostly used
the platform specific types, so some further cleanup might be needed.
0003 tries one way to reduce the duplication that arose in 0002. Maybe
there is a better way.
--
John Naylor
EDB: http://www.enterprisedb.com
From 9390a74f1712d58c88ac513afff8d878071c040c Mon Sep 17 00:00:00 2001
From: John Naylor
Date: Tue, 24 Jan 2023 15:57:53 +0700
Subject: [PATCH v3 2/3] Add MSVC support for bitscan reverse/forward
---
src/include/port/pg_bitutils.h | 38 ++
1 file changed, 38 insertions(+)
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 9a53f53d11..ce04f4ffad 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -13,6 +13,10 @@
#ifndef PG_BITUTILS_H
#define PG_BITUTILS_H
+#ifdef _MSC_VER
+#include
+#endif
+
extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
extern PGDLLIMPORT const uint8 pg_number_of_ones[256];
@@ -27,6 +31,9 @@ pg_leftmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CLZ
int bitscan_result;
+#elif defined(_MSC_VER)
+ unsigned long bitscan_result;
+ unsigned char non_zero; // XXX can this be bool?
#endif
#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
@@ -45,6 +52,11 @@ pg_leftmost_one_pos32(uint32 word)
bitscan_result = 31 - __builtin_clz(word);
Assert(bitscan_result == result);
return bitscan_result;
+#elif defined(_MSC_VER)
+ non_zero = _BitScanReverse(_result, word);
+ Assert(non_zero);
+ Assert(bitscan_result == result);
+ return bitscan_result;
#else
return result;
#endif /* HAVE__BUILTIN_CLZ */
@@ -59,6 +71,9 @@ pg_leftmost_one_pos64(uint64 word)
{
#ifdef HAVE__BUILTIN_CLZ
int bitscan_result;
+#elif defined(_MSC_VER)
+ unsigned long bitscan_result;
+ unsigned char non_zero; // XXX can this be bool?
#endif
#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
@@ -83,6 +98,11 @@ pg_leftmost_one_pos64(uint64 word)
#endif /* HAVE_LONG_... */
Assert(bitscan_result == result);
return bitscan_result;
+#elif defined(_MSC_VER)
+ non_zero = _BitScanReverse64(_result, word);
+ Assert(non_zero);
+ Assert(bitscan_result == result);
+ return bitscan_result;
#else
return result;
#endif /* HAVE__BUILTIN_CLZ */
@@ -99,6 +119,10 @@ pg_rightmost_one_pos32(uint32 word)
#ifdef HAVE__BUILTIN_CTZ
const uint32 orig_word = word;
int bitscan_result;
+#elif defined(_MSC_VER)
+ const unsigned long orig_word = word;
+ unsigned long bitscan_result;
+ unsigned char non_zero; // XXX can this be bool?
#endif
#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
@@ -118,6 +142,11 @@ pg_rightmost_one_pos32(uint32 word)
bitscan_result = __builtin_ctz(orig_word);
Assert(bitscan_result == result);
return bitscan_result;
+#elif defined(_MSC_VER)
+ non_zero = _BitScanForward(_result, orig_word);
+ Assert(non_zero);
+ Assert(bitscan_result == result);
+ return bitscan_result;
#else
return result;
#endif /* HAVE__BUILTIN_CTZ */
@@ -133,6 +162,10 @@ pg_rightmost_one_pos64(uint64 word)
#ifdef HAVE__BUILTIN_CTZ
const uint64 orig_word = word;
int bitscan_result;
+#elif defined(_MSC_VER)
+ const unsigned __int64 orig_word = word;
+ unsigned long bitscan_result;
+ unsigned char non_zero; // XXX can this be bool?
#endif
#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
@@ -158,6 +191,11 @@ pg_rightmost_one_pos64(uint64 word)
#endif /* HAVE_LONG_... */
Assert(bitscan_result == result);
return bitscan_result;
+#elif defined(_MSC_VER)
+ non_zero = _BitScanForward64(_result, orig_word);
+ Assert(non_zero);
+ Assert(bitscan_result == result);
+ return bitscan_result;
#else
return result;
#endif /* HAVE__BUILTIN_CTZ */
--
2.39.0
From 88b98a3fe8d9b5f9a10a839e65b34c43c03e33b2 Mon Sep 17 00:00:00 2001
From: John Naylor
Date: Tue, 24 Jan 2023 14:39:26 +0700
Subject: [PATCH v3 1/3] Add asserts to verify bitscan intrinsics
---
src/include/port/pg_bitutils.h | 86 --
1 file changed, 60 insertions(+), 26 deletions(-)
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index a49a9c03d9..9a53f53d11 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -26,10 +26,11 @@ static inline int
pg_leftmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CLZ
- Assert(word != 0);
+ int bitscan_result;
+#endif
- return 31 - __builtin_clz(word);
-#else
+#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
+ int result;
int shift = 32 - 8;
Assert(word != 0);
@@ -37,7 +38,15 @@ pg_leftmost_one_pos32(uint32 word)
while ((word >>
