Re: [HACKERS] What exactly is our CRC algorithm?
On 04/03/2015 05:28 AM, Abhijit Menon-Sen wrote: At 2015-04-03 00:33:10 +0300, hlinn...@iki.fi wrote: I came up with the attached. I like it very much. src/port/Makefile has (note src/srv): +# pg_crc32c_sse42.o and its _src.o version need CFLAGS_SSE42 +pg_crc32c_sse42.o: CFLAGS+=$(CFLAGS_SSE42) +pg_crc32c_sse42_srv.o: CFLAGS+=$(CFLAGS_SSE42) Other than that, this looks great. Thank you. BTW, we might want to move the traditional and legacy crc32 implementations out of src/common. They are only used in backend code now. I agree. Committed this now, after some further cleanup and reorganizing the autoconf stuff. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
At 2015-03-25 19:18:51 +0200, hlinn...@iki.fi wrote:
I think we'll need a version check there. […]
You want to write that or should I?
I'm not familiar with MSVC at all, so it would be nice if you did it.
How do you like this latest version of the patch otherwise?
I'm sorry, but I'm still not especially fond of it.
Apart from removing the startup check so that client programs can also
use the best available CRC32C implementation without jumping through
hoops, I don't feel that the other changes buy us very much.
Also, assuming that the point is that people who don't care about CRCs
deeply should nevertheless be able to produce special-purpose binaries
with only the optimal implementation included, we should probably have
some instructions about how to do that.
Thinking about what you were trying to do, I would find an arrangement
roughly like the following to be clearer to follow in terms of adding
new implementations and so on:
#if defined(USE_CRC_SSE42) || …can build SSE4.2 CRC code…
#define HAVE_CRC_SSE42 1
pg_crc32c_sse42() { … }
bool sse42_crc32c_available() { … }
pg_comp_crc32c = pg_crc32c_sse42;
#elif defined(USE_CRC_ARM) || …can build ARM CRC code…
#define HAVE_CRC_ARM 1
pg_crc32c_arm() { … }
bool arm_crc32c_available() { … }
pg_comp_crc32c = pg_crc32c_arm;
#endif
#define CRC_SELECTION 1
#if defined(USE_CRC_SSE42) || defined(USE_CRC_ARM) || …
#undef CRC_SELECTION
#endif
#ifdef CRC_SELECTION
pg_crc32c_sb8() { … }
pg_comp_crc32c_choose(…)
{
pg_comp_crc32c = pg_crc32c_sb8;
#ifdef HAVE_CRC_SSE42
if (sse42_crc32c_available())
pg_comp_crc32c = pg_crc32c_sse42;
#elif …
…
#endif
return pg_comp_crc32c(…);
}
pg_comp_crc32c = pg_crc32c_choose;
#endif
Then someone who wants to force the building of (only) the SSE4.2
implementation can build with -DUSE_CRC_SSE42. And if you turn on
USE_CRC_ARM when you can't build ARM code, it won't build. (The
HAVE_CRC_xxx #defines could also move to configure tests.)
If you don't specify any USE_CRC_xxx explicitly, then it'll build
whichever (probably) one it can, and select it at runtime if it's
available.
All that said, I do recognise that there are all relatively cosmetic
concerns, and I don't object seriously to any of it. On the contrary,
thanks for taking the time to review and work on the patch. Nobody
else has expressed an opinion, so I'll leave it to you to decide whether
to commit as-is, or if you want me to pursue the above approach instead.
In the realm of very minor nitpicking, here are a couple of points I
noticed in crc_instructions.h:
1. I think «if (pg_crc32_instructions_runtime_check())» would read
better if the function were named crc32c_instructions_available or
pg_crc32c_is_hw_accelerated, or something like that.
2. It documents pg_accumulate_crc32c_byte and
pg_accumulate_crc32c_uint64, but actually defines pg_asm_crc32b and
pg_asm_crc32q. If you update the code rather than the documentation,
_update_ may be slightly preferable to _accumulate_, and maybe the
suffixes should be _uint8 and _uint64.
3. The descriptions (e.g. Add one byte to the current crc value.)
should also probably read Update the current crc value for the given
byte/eight bytes of data.
Thanks.
-- Abhijit
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On Thu, Apr 2, 2015 at 5:33 PM, Heikki Linnakangas hlinn...@iki.fi wrote: It was added in gcc 4.2. That's good enough for me. I think it's fine to have optional optimizations that require gcc = 4.2, as long as older platforms don't break outright. We have a buildfarm animal that still uses gcc 2.95.3, which was released in 2001. I don't have a compiler of that vintage to test with, but I assume an old enough assembler would not know about the crc32q instruction and fail to compile. GCC from 2002 wouldn't support the symbolic operand names in inline assembly. binutils from 2007 (IIRC) wouldn't support the assembler instructions themselves. We could work around the latter by using the appropriate sequence of bytes. We could work around the former by using the old syntax for operands. I'm OK with not supporting the new instructions when building with an old compiler/assembler. But the build shouldn't fail with an old compiler/assembler. Using old syntax or raw bytes just to avoid failing on an ancient compiler seems ugly. I dunno about old syntax, but raw bytes seems like a bad idea, for sure. -- 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
Re: [HACKERS] What exactly is our CRC algorithm?
At 2015-04-03 00:33:10 +0300, hlinn...@iki.fi wrote: I came up with the attached. I like it very much. src/port/Makefile has (note src/srv): +# pg_crc32c_sse42.o and its _src.o version need CFLAGS_SSE42 +pg_crc32c_sse42.o: CFLAGS+=$(CFLAGS_SSE42) +pg_crc32c_sse42_srv.o: CFLAGS+=$(CFLAGS_SSE42) Other than that, this looks great. Thank you. BTW, we might want to move the traditional and legacy crc32 implementations out of src/common. They are only used in backend code now. I agree. -- Abhijit -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 04/02/2015 12:39 PM, Abhijit Menon-Sen wrote: At 2015-03-25 19:18:51 +0200, hlinn...@iki.fi wrote: I think we'll need a version check there. […] You want to write that or should I? I'm not familiar with MSVC at all, so it would be nice if you did it. Thinking more about the configure checks, I think the current approach of using inline assembly on gcc is not quite right. We're only using inline assembly to force producing SSE 4.2 code, even when -msse4.2 is not used. That feels wrong. And who's to say that the assembler supports the SSE instructions anyway? At least we'd need a configure check for that too. We have a buildfarm animal that still uses gcc 2.95.3, which was released in 2001. I don't have a compiler of that vintage to test with, but I assume an old enough assembler would not know about the crc32q instruction and fail to compile. I believe the GCC way to do this would be to put the SSE4.2-specific code into a separate source file, and compile that file with -msse4.2. And when you compile with -msse4.2, gcc actually also supports the _mm_crc32_u8/u64 intrinsics. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 2015-04-02 20:57:24 +0530, Abhijit Menon-Sen wrote: At 2015-04-02 17:58:23 +0300, hlinn...@iki.fi wrote: We're only using inline assembly to force producing SSE 4.2 code, even when -msse4.2 is not used. That feels wrong. Why? It feels OK to me (and to Andres, per earlier discussions about exactly this topic). Doing it this way allows the binary to run on a non-SSE4.2 platform (and not use the CRC instructions). Right. And SSE4.2 isn't that widespread yet. I believe the GCC way to do this would be to put the SSE4.2-specific code into a separate source file, and compile that file with -msse4.2. And when you compile with -msse4.2, gcc actually also supports the _mm_crc32_u8/u64 intrinsics. To me this seems like a somewhat pointless exercise. I actually think from a performance POV it's better to have all the functions in one source file, so the compiler can inline things into the trampoline if it feels like it. 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
Re: [HACKERS] What exactly is our CRC algorithm?
At 2015-04-02 17:58:23 +0300, hlinn...@iki.fi wrote: We're only using inline assembly to force producing SSE 4.2 code, even when -msse4.2 is not used. That feels wrong. Why? It feels OK to me (and to Andres, per earlier discussions about exactly this topic). Doing it this way allows the binary to run on a non-SSE4.2 platform (and not use the CRC instructions). Also, -msse4.2 was added to the compiler later than support for the instructions was added to the assembler. We have a buildfarm animal that still uses gcc 2.95.3, which was released in 2001. I don't have a compiler of that vintage to test with, but I assume an old enough assembler would not know about the crc32q instruction and fail to compile. GCC from 2002 wouldn't support the symbolic operand names in inline assembly. binutils from 2007 (IIRC) wouldn't support the assembler instructions themselves. We could work around the latter by using the appropriate sequence of bytes. We could work around the former by using the old syntax for operands. I believe the GCC way to do this would be to put the SSE4.2-specific code into a separate source file, and compile that file with -msse4.2. And when you compile with -msse4.2, gcc actually also supports the _mm_crc32_u8/u64 intrinsics. I have no objection to this. Building only that file with -msse4.2 would resolve the problem of the output binary requiring SSE4.2; and the only compilers to be excluded are old enough to be uninteresting at least to me personally. Have you done/are you doing this already, or do you want me to? I could use advice on how to add build flags to only one file, since I don't know of any precendent for that. -- Abhijit -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 02/12/2015 09:26 PM, Heikki Linnakangas wrote: On 02/11/2015 04:20 PM, Abhijit Menon-Sen wrote: At 2015-02-11 13:20:29 +0200, hlinnakan...@vmware.com wrote: I don't follow. I didn't change configure at all, compared to your patch. OK, I extrapolated a little too much. Your patch didn't actually include crc_instructions.h; Oh, I'm sorry. Here's the complete patch with crc_instructions.h I was just about to commit the attached, which is the same as the previous patch with just cosmetic comment changes, but then I realized that this probably doesn't compile with Visual Studio 2005 or older. The code does #ifdef _MSC_VER, and then uses the _mm_crc32_u64 intrinsic, but that intrinsic was added in Visual Studio 2008. I think we'll need a version check there. Or better yet, a direct configure test to check if the intrinsic exists - that way we get to also use it on Intel compilers, which I believe also has the same intrinsics. You want to write that or should I? How do you like this latest version of the patch otherwise? You had some criticism earlier, but I had forgotten to include the crc_instructions.h header file in that earlier version. - Heikki From f934cb017ad0270ded73feb4d3279e81a58a4149 Mon Sep 17 00:00:00 2001 From: Heikki Linnakangas heikki.linnakangas@iki.fi Date: Wed, 25 Mar 2015 18:44:07 +0200 Subject: [PATCH v2 1/1] Use Intel SSE4.2 CRC instructions where available. On x86, perform a runtime check to see if we're running on a CPU that supports SSE 4.2. If we are, we can use the special crc32b and crc32q instructions for the CRC-32C calculations. That greatly speeds up CRC calculation. Abhijit Menon-Sen, reviewed by Andres Freund and me. --- configure | 2 +- configure.in| 2 +- src/common/pg_crc.c | 113 +++ src/include/common/pg_crc.h | 20 -- src/include/pg_config.h.in | 3 + src/include/port/crc_instructions.h | 128 6 files changed, 248 insertions(+), 20 deletions(-) create mode 100644 src/include/port/crc_instructions.h diff --git a/configure b/configure index 2c9b3a7..87ceb0b 100755 --- a/configure +++ b/configure @@ -9204,7 +9204,7 @@ fi done -for ac_header in atomic.h crypt.h dld.h fp_class.h getopt.h ieeefp.h ifaddrs.h langinfo.h mbarrier.h poll.h pwd.h sys/ioctl.h sys/ipc.h sys/poll.h sys/pstat.h sys/resource.h sys/select.h sys/sem.h sys/shm.h sys/socket.h sys/sockio.h sys/tas.h sys/time.h sys/un.h termios.h ucred.h utime.h wchar.h wctype.h +for ac_header in atomic.h cpuid.h crypt.h dld.h fp_class.h getopt.h ieeefp.h ifaddrs.h langinfo.h mbarrier.h poll.h pwd.h sys/ioctl.h sys/ipc.h sys/poll.h sys/pstat.h sys/resource.h sys/select.h sys/sem.h sys/shm.h sys/socket.h sys/sockio.h sys/tas.h sys/time.h sys/un.h termios.h ucred.h utime.h wchar.h wctype.h do : as_ac_Header=`$as_echo ac_cv_header_$ac_header | $as_tr_sh` ac_fn_c_check_header_mongrel $LINENO $ac_header $as_ac_Header $ac_includes_default diff --git a/configure.in b/configure.in index b2c1ce7..bf604ea 100644 --- a/configure.in +++ b/configure.in @@ -1032,7 +1032,7 @@ AC_SUBST(UUID_LIBS) ## dnl sys/socket.h is required by AC_FUNC_ACCEPT_ARGTYPES -AC_CHECK_HEADERS([atomic.h crypt.h dld.h fp_class.h getopt.h ieeefp.h ifaddrs.h langinfo.h mbarrier.h poll.h pwd.h sys/ioctl.h sys/ipc.h sys/poll.h sys/pstat.h sys/resource.h sys/select.h sys/sem.h sys/shm.h sys/socket.h sys/sockio.h sys/tas.h sys/time.h sys/un.h termios.h ucred.h utime.h wchar.h wctype.h]) +AC_CHECK_HEADERS([atomic.h cpuid.h crypt.h dld.h fp_class.h getopt.h ieeefp.h ifaddrs.h langinfo.h mbarrier.h poll.h pwd.h sys/ioctl.h sys/ipc.h sys/poll.h sys/pstat.h sys/resource.h sys/select.h sys/sem.h sys/shm.h sys/socket.h sys/sockio.h sys/tas.h sys/time.h sys/un.h termios.h ucred.h utime.h wchar.h wctype.h]) # On BSD, test for net/if.h will fail unless sys/socket.h # is included first. diff --git a/src/common/pg_crc.c b/src/common/pg_crc.c index eba32d3..6675ae7 100644 --- a/src/common/pg_crc.c +++ b/src/common/pg_crc.c @@ -21,25 +21,113 @@ #include common/pg_crc.h -/* Accumulate one input byte */ -#ifdef WORDS_BIGENDIAN -#define CRC8(x) pg_crc32c_table[0][((crc 24) ^ (x)) 0xFF] ^ (crc 8) +#ifdef PG_HAVE_CRC32C_INSTRUCTIONS +static pg_crc32 pg_comp_crc32c_hw(pg_crc32 crc, const void *data, size_t len); +#endif + +#if !defined(PG_HAVE_CRC32C_INSTRUCTIONS) || defined(PG_CRC32C_INSTRUCTIONS_NEED_RUNTIME_CHECK) +static pg_crc32 pg_comp_crc32c_sb8(pg_crc32 crc, const void *data, size_t len); +static const uint32 pg_crc32c_table[8][256]; +#endif + +#ifdef PG_CRC32C_INSTRUCTIONS_NEED_RUNTIME_CHECK +/* + * When built with support for CRC instructions, but we need to perform a + * run-time check to determine whether we can actually use them, + * pg_comp_crc32c is a function pointer. It is initialized to + * pg_comp_crc32c_choose, which performs the runtime check, and
Re: [HACKERS] What exactly is our CRC algorithm?
On 03/25/2015 07:20 PM, Andres Freund wrote: On 2015-03-25 19:18:51 +0200, Heikki Linnakangas wrote: Or better yet, a direct configure test to check if the intrinsic exists - that way we get to also use it on Intel compilers, which I believe also has the same intrinsics. Maybe I'm missing something, but configure isn't run for msvc? Good point. On MSVC, we use the pre-built pg_config.h.win32 file instead. There are already a couple of cases like this in it: /* Define to 1 if you have the `rint' function. */ #if (_MSC_VER = 1800) #define HAVE_RINT 1 #endif I think we should do that for the CRC32 intrinsic too. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 2015-03-25 19:18:51 +0200, Heikki Linnakangas wrote: I was just about to commit the attached, which is the same as the previous patch with just cosmetic comment changes, but then I realized that this probably doesn't compile with Visual Studio 2005 or older. The code does #ifdef _MSC_VER, and then uses the _mm_crc32_u64 intrinsic, but that intrinsic was added in Visual Studio 2008. I think we'll need a version check there. Good catch. Or better yet, a direct configure test to check if the intrinsic exists - that way we get to also use it on Intel compilers, which I believe also has the same intrinsics. Maybe I'm missing something, but configure isn't run for msvc? Greetings, Andres Freund -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 02/11/2015 04:20 PM, Abhijit Menon-Sen wrote:
At 2015-02-11 13:20:29 +0200, hlinnakan...@vmware.com wrote:
I don't follow. I didn't change configure at all, compared to your
patch.
OK, I extrapolated a little too much. Your patch didn't actually include
crc_instructions.h;
Oh, I'm sorry. Here's the complete patch with crc_instructions.h
- Heikki
From bd4a90d339e21cd6ac517d077fe3a76abb5ef37d Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas heikki.linnakangas@iki.fi
Date: Tue, 10 Feb 2015 14:26:24 +0200
Subject: [PATCH 1/1] Use Intel SSE4.2 CRC instructions where available.
On x86, perform a runtime check to see if we're running on a CPU that
supports SSE 4.2. If we are, we can use the special crc32b and crc32q
instructions for the CRC-32C calculations. That greatly speeds up CRC
calculation.
Abhijit Menon-Sen, reviewed by Andres Freund and me.
---
configure | 2 +-
configure.in| 2 +-
src/common/pg_crc.c | 109 +---
src/include/common/pg_crc.h | 12 +++-
src/include/pg_config.h.in | 3 +
src/include/port/crc_instructions.h | 121
6 files changed, 235 insertions(+), 14 deletions(-)
create mode 100644 src/include/port/crc_instructions.h
diff --git a/configure b/configure
index fa271fe..c352128 100755
--- a/configure
+++ b/configure
@@ -9204,7 +9204,7 @@ fi
done
-for ac_header in atomic.h crypt.h dld.h fp_class.h getopt.h ieeefp.h ifaddrs.h langinfo.h mbarrier.h poll.h pwd.h sys/ioctl.h sys/ipc.h sys/poll.h sys/pstat.h sys/resource.h sys/select.h sys/sem.h sys/shm.h sys/socket.h sys/sockio.h sys/tas.h sys/time.h sys/un.h termios.h ucred.h utime.h wchar.h wctype.h
+for ac_header in atomic.h cpuid.h crypt.h dld.h fp_class.h getopt.h ieeefp.h ifaddrs.h langinfo.h mbarrier.h poll.h pwd.h sys/ioctl.h sys/ipc.h sys/poll.h sys/pstat.h sys/resource.h sys/select.h sys/sem.h sys/shm.h sys/socket.h sys/sockio.h sys/tas.h sys/time.h sys/un.h termios.h ucred.h utime.h wchar.h wctype.h
do :
as_ac_Header=`$as_echo ac_cv_header_$ac_header | $as_tr_sh`
ac_fn_c_check_header_mongrel $LINENO $ac_header $as_ac_Header $ac_includes_default
diff --git a/configure.in b/configure.in
index e6a49d1..588d626 100644
--- a/configure.in
+++ b/configure.in
@@ -1032,7 +1032,7 @@ AC_SUBST(UUID_LIBS)
##
dnl sys/socket.h is required by AC_FUNC_ACCEPT_ARGTYPES
-AC_CHECK_HEADERS([atomic.h crypt.h dld.h fp_class.h getopt.h ieeefp.h ifaddrs.h langinfo.h mbarrier.h poll.h pwd.h sys/ioctl.h sys/ipc.h sys/poll.h sys/pstat.h sys/resource.h sys/select.h sys/sem.h sys/shm.h sys/socket.h sys/sockio.h sys/tas.h sys/time.h sys/un.h termios.h ucred.h utime.h wchar.h wctype.h])
+AC_CHECK_HEADERS([atomic.h cpuid.h crypt.h dld.h fp_class.h getopt.h ieeefp.h ifaddrs.h langinfo.h mbarrier.h poll.h pwd.h sys/ioctl.h sys/ipc.h sys/poll.h sys/pstat.h sys/resource.h sys/select.h sys/sem.h sys/shm.h sys/socket.h sys/sockio.h sys/tas.h sys/time.h sys/un.h termios.h ucred.h utime.h wchar.h wctype.h])
# On BSD, test for net/if.h will fail unless sys/socket.h
# is included first.
diff --git a/src/common/pg_crc.c b/src/common/pg_crc.c
index eba32d3..b6db749 100644
--- a/src/common/pg_crc.c
+++ b/src/common/pg_crc.c
@@ -21,25 +21,113 @@
#include common/pg_crc.h
-/* Accumulate one input byte */
-#ifdef WORDS_BIGENDIAN
-#define CRC8(x) pg_crc32c_table[0][((crc 24) ^ (x)) 0xFF] ^ (crc 8)
+#ifdef PG_HAVE_CRC32C_INSTRUCTIONS
+static pg_crc32 pg_comp_crc32c_hw(pg_crc32 crc, const void *data, size_t len);
+#endif
+
+#if !defined(PG_HAVE_CRC32C_INSTRUCTIONS) || defined(PG_CRC32C_INSTRUCTIONS_NEED_RUNTIME_CHECK)
+static pg_crc32 pg_comp_crc32c_sb8(pg_crc32 crc, const void *data, size_t len);
+static const uint32 pg_crc32c_table[8][256];
+#endif
+
+#ifdef PG_CRC32C_INSTRUCTIONS_NEED_RUNTIME_CHECK
+/*
+ * When built with support for CRC instructions, but we need to perform a
+ * run-time check to determine whether we can actually use them,
+ * pg_comp_crc32c is a function pointer. It is initialized to
+ * pg_comp_crc32c_choose, which performs the runtime check, and changes the
+ * function pointer so that subsequent calls go directly to the hw-accelerated
+ * version, or the fallback slicing-by-8 version.
+ */
+static pg_crc32
+pg_comp_crc32c_choose(pg_crc32 crc, const void *data, size_t len)
+{
+ if (pg_crc32_instructions_runtime_check())
+ pg_comp_crc32c = pg_comp_crc32c_hw;
+ else
+ pg_comp_crc32c = pg_comp_crc32c_sb8;
+
+ return pg_comp_crc32c(crc, data, len);
+}
+
+pg_crc32 (*pg_comp_crc32c)(pg_crc32 crc, const void *data, size_t len) = pg_comp_crc32c_choose;
+
#else
-#define CRC8(x) pg_crc32c_table[0][(crc ^ (x)) 0xFF] ^ (crc 8)
+/*
+ * No need for a runtime check. Compile directly with the hw-accelerated
+ * or the slicing-by-8 version. (We trust that the compiler
+ * is smart enough to inline it here.)
+ */
+pg_crc32
+pg_comp_crc32c(pg_crc32 crc, const void *data, size_t len)
Re: [HACKERS] What exactly is our CRC algorithm?
At 2015-02-10 14:30:51 +0200, hlinnakan...@vmware.com wrote: I propose that we add a new header file in src/port, let's call it crc_instructions.h […] the point of the crc_instructions.h header is to hide the differences between compilers and architectures. Moving the assembly code/compiler intrinsics to a separate header is fine with me, but I really don't like the proposed implementation at all. Here are some comments: 1. I don't mind moving platform-specific tests for CRC32C instructions to configure, but if we only define PG_HAVE_CRC32C_INSTRUCTIONS, we would anyway have to reproduce all that platform-specific stuff in the header file. To do it properly, I think we should generate the right version of crc_instructions.h for the platform. Otherwise, what's the point? Might as well have only the complicated header. 2. At this point, I think we should stick with the _sse function rather than a generic _hw one to drive the platform-specific instructions. The structure of that function (n/8*(8bytes)+n%8*(bytes)) is specific to what works best for the SSE instructions. On another platform, we may need something very similar, or very different. With the proposed structure, _hw would inevitably become #ifdef'ed non-trivially, e.g. to run a single-byte loop at the start to align the main loop, but only for certain combinations of #defines. I think we should consider what makes the most sense when someone actually wants to add support for another platform/compiler, and not before. 3. I dislike everything about pg_crc32_instructions_runtime_check()—the name, the separate PG_CRC32C_INSTRUCTIONS_NEED_RUNTIME_CHECK #define, the fact that you try to do the test inline rather than at startup… Maybe you're trying to avoid checking separately at startup so that a program that links with code from src/common doesn't need to do its own test. But I don't think the results are worth it. As for omitting the slicing-by-8 tables, if there's a more compelling reason to do that than Gentoo users might like that ;-), I think it should be done with a straightforward -DUSE_CRC_SSE style arrangement rather than figuring out that you HAVE_CRC32C_INSTRUCTIONS but don't NEED_RUNTIME_CHECK. If you want to build special-purpose binaries, just pick whichever CRC implementation you like, done. I believe the CRC instructions are also available in 32-bit mode, so the check for __x86_64__ is not needed. Right? I'm not sure, but I guess you're right. It would be nice to use GCC's builtin intrinsics, __builtin_ia32_crc32* where available, but I guess those are only available if you build with -msse4.2, and that would defeat the point of the runtime check. Exactly. -- Abhijit -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 02/11/2015 11:28 AM, Abhijit Menon-Sen wrote: 1. I don't mind moving platform-specific tests for CRC32C instructions to configure, but if we only define PG_HAVE_CRC32C_INSTRUCTIONS, we would anyway have to reproduce all that platform-specific stuff in the header file. To do it properly, I think we should generate the right version of crc_instructions.h for the platform. Otherwise, what's the point? Might as well have only the complicated header. I don't follow. I didn't change configure at all, compared to your patch. 2. At this point, I think we should stick with the _sse function rather than a generic _hw one to drive the platform-specific instructions. The structure of that function (n/8*(8bytes)+n%8*(bytes)) is specific to what works best for the SSE instructions. On another platform, we may need something very similar, or very different. With the proposed structure, _hw would inevitably become #ifdef'ed non-trivially, e.g. to run a single-byte loop at the start to align the main loop, but only for certain combinations of #defines. I think we should consider what makes the most sense when someone actually wants to add support for another platform/compiler, and not before. Hmm, ok. The ARM CRC32C instruction is very similar to the SSE4.2 one, but I presume it does require alignment. 3. I dislike everything about pg_crc32_instructions_runtime_check()—the name, the separate PG_CRC32C_INSTRUCTIONS_NEED_RUNTIME_CHECK #define, the fact that you try to do the test inline rather than at startup… Maybe you're trying to avoid checking separately at startup so that a program that links with code from src/common doesn't need to do its own test. But I don't think the results are worth it. As a case in point, with your patch pg_xlogdump would not have used the CRC instruction, because it never called pg_choose_crc_impl(). Choose on first use is much more convenient than requiring every program to call a function. As for omitting the slicing-by-8 tables, if there's a more compelling reason to do that than Gentoo users might like that ;-), I think it should be done with a straightforward -DUSE_CRC_SSE style arrangement rather than figuring out that you HAVE_CRC32C_INSTRUCTIONS but don't NEED_RUNTIME_CHECK. If you want to build special-purpose binaries, just pick whichever CRC implementation you like, done. I stopped short of actually allowing you to force the use of SSE, e.g. with -DUSE_CRC_SSE, but my thinking was that that would force PG_HAVE_CRC32C_INSTRUCTIONS to be set, and NEEDS_RUNTIME_CHECK to be unset. I.e. those two #defines control what code is generated, but in the header file. I think what you're suggesting is that we'd instead have two mutually exclusive #defines, something like USE_CRC_SSE_ALWAYS and USE_CRC_SSE_WITH_RUNTIME_CHECK. It wouldn't be much different, but would require some places to check for both. It would be nice to use GCC's builtin intrinsics, __builtin_ia32_crc32* where available, but I guess those are only available if you build with -msse4.2, and that would defeat the point of the runtime check. Exactly. Hmm. Perhaps we should check for the built-in functions, and if they're available, use them and not set NEEDS_RUNTIME_CHECK. If you compile with -msse4.2, the code won't run without SSE4.2 anyway (or at least isn't guaranteed to run). - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 02/09/2015 03:20 PM, Abhijit Menon-Sen wrote: At 2015-02-09 12:52:41 +0200, hlinnakan...@vmware.com wrote: Do you have access to big-endian hardware to test this on? Yes, I tested it on a Linux/ppc system. I wasn't speculating when I said it does make a noticeable difference, though I'm afraid I did not keep the timings after submitting the revised patch. The speedup was some double-digit percentage, IIRC. Ok, that's good enough for me. Committed with a few more edits on comments and such. I'll start looking at the second patch now. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 01/09/2015 10:32 AM, Abhijit Menon-Sen wrote:
2. The sse4.2 patch has only some minor compile fixes.
I have built and tested both patches individually on little-endian
(amd64) and big-endian (ppc) systems. I verified that the _sse is
chosen at startup on the former, and _sb8 on the latter, and that
both implementations function correctly with respect to HEAD.
I'd like to arrange this somewhat differently, to keep the really
low-level assembler blocks and such separate from the higher level
parts. Especially now that pg_crc.c is in src/common and src/port, it
doesn't seem appropriate to have assembler code in there. Also, some of
the high-level code can be reused if we later add support e.g. for the
ARMv8 CRC instructions.
I propose that we add a new header file in src/port, let's call it
crc_instructions.h. That file contains the very low-level stuff, the
pg_asm_crc32q() and pg_asm_crc32b() inline functions, which just contain
the single assembler instruction. Or the corresponding mnemomic or macro
depending on the compiler; the point of the crc_instructions.h header is
to hide the differences between compilers and architectures.
If the CRC instructions are available, crc_instructions.h defines
PG_HAVE_CRC32C_INSTRUCTIONS, as well as the pg_asm_crc32q() and
pg_asm_crc32b() macros/functions. It also defines
pg_crc32_instructions_runtime_check(), to perform the runtime check to
determine whether the instructions can be used on the current platform
(i.e. if you're running on a CPU with SSE 4.2 support). There's another
symbol PG_CRC32C_INSTRUCTIONS_NEED_RUNTIME_CHECK, which indicates
whether the runtime check is needed. That's currently always defined
when PG_HAVE_CRC32C_INSTRUCTIONS is, but conceivably you might want to
build a version that skips the runtime check altogether, and doesn't
therefore require the slicing-by-8 fallback implementation at all.
Gentoo users might like that ;-), as well as possible future
architectures that always have CRC32 instructions.
Attached is a patch along those lines. I haven't done much testing, but
it demonstrates the code structure I have in mind.
A couple of remarks on your original patch, which also apply to the
attached version:
+static inline pg_crc32
+pg_asm_crc32b(pg_crc32 crc, unsigned char data)
+{
+#if defined(__GNUC__) defined(__x86_64__)
+ __asm__ (crc32b %[data], %[crc]\n : [crc] +r (crc) : [data] rm
(data));
+ return crc;
+#elif defined(_MSC_VER)
+ return _mm_crc32_u8(crc, data);
+#else
+ /* Can't generate crc32b, but keep the compiler quiet. */
+ return 0;
+#endif
I believe the CRC instructions are also available in 32-bit mode, so the
check for __x86_64__ is not needed. Right? Any CPU recent enough to have
these instructions certainly supports the x86-64 instruction set, but
you might nevertheless have compiled and be running in i386 mode.
It would be nice to use GCC's builtin intrinsics, __builtin_ia32_crc32*
where available, but I guess those are only available if you build with
-msse4.2, and that would defeat the point of the runtime check.
I believe the _mm_* mnemonics would also work with the Intel compiler.
- Heikki
From 7e16b0d5be39f832769da463f069c51afa04fb57 Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas heikki.linnakangas@iki.fi
Date: Tue, 10 Feb 2015 14:26:24 +0200
Subject: [PATCH 1/1] Use Intel SSE4.2 CRC instructions where available.
On x86, perform a runtime check to see if we're running on a CPU that
supports SSE 4.2. If we are, we can use the special crc32b and crc32q
instructions for the CRC-32C calculations. That greatly speeds up CRC
calculation.
Abhijit Menon-Sen, reviewed by Andres Freund and me.
---
configure | 2 +-
configure.in| 2 +-
src/common/pg_crc.c | 109
src/include/common/pg_crc.h | 12 -
src/include/pg_config.h.in | 3 ++
5 files changed, 114 insertions(+), 14 deletions(-)
diff --git a/configure b/configure
index fa271fe..c352128 100755
--- a/configure
+++ b/configure
@@ -9204,7 +9204,7 @@ fi
done
-for ac_header in atomic.h crypt.h dld.h fp_class.h getopt.h ieeefp.h ifaddrs.h langinfo.h mbarrier.h poll.h pwd.h sys/ioctl.h sys/ipc.h sys/poll.h sys/pstat.h sys/resource.h sys/select.h sys/sem.h sys/shm.h sys/socket.h sys/sockio.h sys/tas.h sys/time.h sys/un.h termios.h ucred.h utime.h wchar.h wctype.h
+for ac_header in atomic.h cpuid.h crypt.h dld.h fp_class.h getopt.h ieeefp.h ifaddrs.h langinfo.h mbarrier.h poll.h pwd.h sys/ioctl.h sys/ipc.h sys/poll.h sys/pstat.h sys/resource.h sys/select.h sys/sem.h sys/shm.h sys/socket.h sys/sockio.h sys/tas.h sys/time.h sys/un.h termios.h ucred.h utime.h wchar.h wctype.h
do :
as_ac_Header=`$as_echo ac_cv_header_$ac_header | $as_tr_sh`
ac_fn_c_check_header_mongrel $LINENO $ac_header $as_ac_Header $ac_includes_default
diff --git a/configure.in b/configure.in
index e6a49d1..588d626 100644
Re: [HACKERS] What exactly is our CRC algorithm?
On 02/08/2015 08:33 PM, Abhijit Menon-Sen wrote:
At 2015-02-08 18:46:30 +0200, hlinnakan...@vmware.com wrote:
So I propose to move pg_crc.c to src/common, and move the tables
from pg_crc_tables.h directly to pg_crc.c. Thoughts?
Sounds fine to me.
Ok, I've committed a patch that just moves the existing code to
common/pg_crc.c. I also moved pg_crc.h from include/utils to
include/utils. That'll need any external programs to change their
#include accordingly, but I think it was worth that. include/common is
clearly the correct home for that file, and the only reason to keep it
in include/utils would've been for backwards-compatibility.
Attached is a rebased version of the slicing-by-8 patch. I've made some
cosmetic changes. Most notably, I turned the bswap32() function into a
macro. Better to avoid the overhead of a function call, and it also
avoids building the function altogether on little-endian systems that
don't need it.
I'll continue review this.
At 2015-01-02 16:46:29 +0200, hlinnakan...@vmware.com wrote:
Would it even make sense to keep the crc variable in different byte
order, and only do the byte-swap once in END_CRC32() ?
...this certainly does make a noticeable difference. Will investigate.
Do you have access to big-endian hardware to test this on? It seems like
an obvious optimization to shave off that one instruction from the hot
loop, but if it turns out not to make any measurable difference, I'd
prefer to keep the tables in the same order on big and little endian
systems, reducing the amount of #ifdefs needed.
I tested this on my laptop by adding a BSWAP32() into the hot loop -
which is bogus on a little endian Intel system - and it seems to make
about 5% difference in a quick micro-benchmark. But it would be nice to
get some numbers from the kind of big endian systems that people run in
the real world.
- Heikki
diff --git a/config/c-compiler.m4 b/config/c-compiler.m4
index 90b56e7..509f961 100644
--- a/config/c-compiler.m4
+++ b/config/c-compiler.m4
@@ -193,6 +193,23 @@ fi])# PGAC_C_TYPES_COMPATIBLE
+# PGAC_C_BUILTIN_BSWAP32
+# -
+# Check if the C compiler understands __builtin_bswap32(),
+# and define HAVE__BUILTIN_BSWAP32 if so.
+AC_DEFUN([PGAC_C_BUILTIN_BSWAP32],
+[AC_CACHE_CHECK(for __builtin_bswap32, pgac_cv__builtin_bswap32,
+[AC_TRY_COMPILE([static unsigned long int x = __builtin_bswap32(0xaabbccdd);],
+[],
+[pgac_cv__builtin_bswap32=yes],
+[pgac_cv__builtin_bswap32=no])])
+if test x$pgac_cv__builtin_bswap32 = xyes ; then
+AC_DEFINE(HAVE__BUILTIN_BSWAP32, 1,
+ [Define to 1 if your compiler understands __builtin_bswap32.])
+fi])# PGAC_C_BUILTIN_BSWAP32
+
+
+
# PGAC_C_BUILTIN_CONSTANT_P
# -
# Check if the C compiler understands __builtin_constant_p(),
diff --git a/configure b/configure
index 8490eb7..fa271fe 100755
--- a/configure
+++ b/configure
@@ -10333,6 +10333,36 @@ if test x$pgac_cv__types_compatible = xyes ; then
$as_echo #define HAVE__BUILTIN_TYPES_COMPATIBLE_P 1 confdefs.h
fi
+{ $as_echo $as_me:${as_lineno-$LINENO}: checking for __builtin_bswap32 5
+$as_echo_n checking for __builtin_bswap32... 6; }
+if ${pgac_cv__builtin_bswap32+:} false; then :
+ $as_echo_n (cached) 6
+else
+ cat confdefs.h - _ACEOF conftest.$ac_ext
+/* end confdefs.h. */
+static unsigned long int x = __builtin_bswap32(0xaabbccdd);
+int
+main ()
+{
+
+ ;
+ return 0;
+}
+_ACEOF
+if ac_fn_c_try_compile $LINENO; then :
+ pgac_cv__builtin_bswap32=yes
+else
+ pgac_cv__builtin_bswap32=no
+fi
+rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
+fi
+{ $as_echo $as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_bswap32 5
+$as_echo $pgac_cv__builtin_bswap32 6; }
+if test x$pgac_cv__builtin_bswap32 = xyes ; then
+
+$as_echo #define HAVE__BUILTIN_BSWAP32 1 confdefs.h
+
+fi
{ $as_echo $as_me:${as_lineno-$LINENO}: checking for __builtin_constant_p 5
$as_echo_n checking for __builtin_constant_p... 6; }
if ${pgac_cv__builtin_constant_p+:} false; then :
diff --git a/configure.in b/configure.in
index b4bd09e..e6a49d1 100644
--- a/configure.in
+++ b/configure.in
@@ -1185,6 +1185,7 @@ PGAC_C_SIGNED
PGAC_C_FUNCNAME_SUPPORT
PGAC_C_STATIC_ASSERT
PGAC_C_TYPES_COMPATIBLE
+PGAC_C_BUILTIN_BSWAP32
PGAC_C_BUILTIN_CONSTANT_P
PGAC_C_BUILTIN_UNREACHABLE
PGAC_C_VA_ARGS
diff --git a/src/common/pg_crc.c b/src/common/pg_crc.c
index faf5a66..281707f 100644
--- a/src/common/pg_crc.c
+++ b/src/common/pg_crc.c
@@ -19,76 +19,1156 @@
#include c.h
+#include common/pg_crc.h
+
+#ifdef WORDS_BIGENDIAN
+#define CRC8(x) pg_crc32c_table[0][((crc 24) ^ (x)) 0xFF] ^ (crc 8)
+#else
+#define CRC8(x) pg_crc32c_table[0][(crc ^ (x)) 0xFF] ^ (crc 8)
+#endif
+
+/*
+ * This function computes a CRC using the slicing-by-8 algorithm, which
+ * uses an 8*256 lookup table to operate on eight bytes in parallel and
+ * recombine the results.
+ *
+ * Michael E. Kounavis, Frank L. Berry,
+ * Novel Table Lookup-Based Algorithms
Re: [HACKERS] What exactly is our CRC algorithm?
At 2015-02-09 12:52:41 +0200, hlinnakan...@vmware.com wrote: Ok, I've committed a patch that just moves the existing code to common/pg_crc.c […] Thanks, looks good. Attached is a rebased version of the slicing-by-8 patch. Looks OK too. Do you have access to big-endian hardware to test this on? Yes, I tested it on a Linux/ppc system. I wasn't speculating when I said it does make a noticeable difference, though I'm afraid I did not keep the timings after submitting the revised patch. The speedup was some double-digit percentage, IIRC. -- Abhijit -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
At 2015-02-08 18:46:30 +0200, hlinnakan...@vmware.com wrote: So I propose to move pg_crc.c to src/common, and move the tables from pg_crc_tables.h directly to pg_crc.c. Thoughts? Sounds fine to me. -- Abhijit -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 01/09/2015 10:32 AM, Abhijit Menon-Sen wrote: 1. The slicing-by-8 patch contains numerous changes: With this patch, CALC_CRC32C is no longer a pure macro, but includes a function call. That means that you can no longer just #include pg_crc.h and pg_crc_tables.h in an external program. We made that arrangement with two header files in 2012 [1], and added src/port/pg_crc.c which just #includes pg_crc_tables.h, so that the backend and frontend programs that use libpgport will have just one copy of the tables. Now that there's some actual code in pg_crc.c, I think we have to just give up on being able to get the CRC implementation without libpgport. It was a nice thought, but I doubt there are any programs out there that would have a problem with that. Anything that wants to read the WAL needs xlogreader.c anyway. But actually, we should now move pg_crc.c to src/common. It was a bit of a hack to have it in src/port in the first place, because it has nothing to do with portability, but src/common didn't exist back then. Now it does. So I propose to move pg_crc.c to src/common, and move the tables from pg_crc_tables.h directly to pg_crc.c. Thoughts? [1] http://www.postgresql.org/message-id/flat/CAAZKuFaNcf3=YtadkWwr8yHb+1axW2RepmQ2j8a9NNGkV7PN=w...@mail.gmail.com. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 2015-02-08 18:46:30 +0200, Heikki Linnakangas wrote: So I propose to move pg_crc.c to src/common, and move the tables from pg_crc_tables.h directly to pg_crc.c. Thoughts? +1. Greetings, Andres Freund -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
Hi Heikki.
I've attached two regenerated CRC patches, split up as before.
1. The slicing-by-8 patch contains numerous changes:
a. A configure test for __builtin_bswap32
b. A comment referencing the slicing-by-8 paper (which is behind a
paywall, unfortunately, so I haven't even read it). Are more
comments needed? If so, where/what kind?
c. A byte-reversed big-endian version of the 8*256 table. In Linux,
there's only one table that uses __constant_swab32, but for us
it's simpler to have two tables.
d. Thanks to (c), we can avoid the bswap32 in the hot loop.
e. On big-endian systems, FIN_CRC32C now bswap32()s the CRC before
finalising it. (We don't need to do this in INIT_CRC32C only
because the initialiser is 0x.)
2. The sse4.2 patch has only some minor compile fixes.
I have built and tested both patches individually on little-endian
(amd64) and big-endian (ppc) systems. I verified that the _sse is
chosen at startup on the former, and _sb8 on the latter, and that
both implementations function correctly with respect to HEAD.
Please let me know if there's anything else I need to do.
-- Abhijit
From a202673fa8e4e60e7fd5087fd8577a90a75e90ee Mon Sep 17 00:00:00 2001
From: Abhijit Menon-Sen a...@2ndquadrant.com
Date: Fri, 9 Jan 2015 10:38:47 +0530
Subject: Implement slicing-by-8 CRC calculation
The COMP_CRC32C macro now calls pg_comp_crc32c(), which processes eight
data bytes at a time. Its output is identical to the byte-at-a-time CRC
code. (This change does not apply to the LEGACY_CRC32 computation.)
Reviewers: Andres Freund, Heikki Linnakangas
Author: Abhijit Menon-Sen
---
config/c-compiler.m4 | 17 +
configure | 30 +
configure.in |1 +
src/include/pg_config.h.in|3 +
src/include/pg_config.h.win32 |3 +
src/include/utils/pg_crc.h| 11 +-
src/include/utils/pg_crc_tables.h | 1128 ++---
src/port/pg_crc.c | 105 +++-
8 files changed, 1228 insertions(+), 70 deletions(-)
diff --git a/config/c-compiler.m4 b/config/c-compiler.m4
index 90b56e7..509f961 100644
--- a/config/c-compiler.m4
+++ b/config/c-compiler.m4
@@ -193,6 +193,23 @@ fi])# PGAC_C_TYPES_COMPATIBLE
+# PGAC_C_BUILTIN_BSWAP32
+# -
+# Check if the C compiler understands __builtin_bswap32(),
+# and define HAVE__BUILTIN_BSWAP32 if so.
+AC_DEFUN([PGAC_C_BUILTIN_BSWAP32],
+[AC_CACHE_CHECK(for __builtin_bswap32, pgac_cv__builtin_bswap32,
+[AC_TRY_COMPILE([static unsigned long int x = __builtin_bswap32(0xaabbccdd);],
+[],
+[pgac_cv__builtin_bswap32=yes],
+[pgac_cv__builtin_bswap32=no])])
+if test x$pgac_cv__builtin_bswap32 = xyes ; then
+AC_DEFINE(HAVE__BUILTIN_BSWAP32, 1,
+ [Define to 1 if your compiler understands __builtin_bswap32.])
+fi])# PGAC_C_BUILTIN_BSWAP32
+
+
+
# PGAC_C_BUILTIN_CONSTANT_P
# -
# Check if the C compiler understands __builtin_constant_p(),
diff --git a/configure b/configure
index fce4908..27092ec 100755
--- a/configure
+++ b/configure
@@ -10324,6 +10324,36 @@ if test x$pgac_cv__types_compatible = xyes ; then
$as_echo #define HAVE__BUILTIN_TYPES_COMPATIBLE_P 1 confdefs.h
fi
+{ $as_echo $as_me:${as_lineno-$LINENO}: checking for __builtin_bswap32 5
+$as_echo_n checking for __builtin_bswap32... 6; }
+if ${pgac_cv__builtin_bswap32+:} false; then :
+ $as_echo_n (cached) 6
+else
+ cat confdefs.h - _ACEOF conftest.$ac_ext
+/* end confdefs.h. */
+static unsigned long int x = __builtin_bswap32(0xaabbccdd);
+int
+main ()
+{
+
+ ;
+ return 0;
+}
+_ACEOF
+if ac_fn_c_try_compile $LINENO; then :
+ pgac_cv__builtin_bswap32=yes
+else
+ pgac_cv__builtin_bswap32=no
+fi
+rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
+fi
+{ $as_echo $as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_bswap32 5
+$as_echo $pgac_cv__builtin_bswap32 6; }
+if test x$pgac_cv__builtin_bswap32 = xyes ; then
+
+$as_echo #define HAVE__BUILTIN_BSWAP32 1 confdefs.h
+
+fi
{ $as_echo $as_me:${as_lineno-$LINENO}: checking for __builtin_constant_p 5
$as_echo_n checking for __builtin_constant_p... 6; }
if ${pgac_cv__builtin_constant_p+:} false; then :
diff --git a/configure.in b/configure.in
index 6aa69fb..0206836 100644
--- a/configure.in
+++ b/configure.in
@@ -1176,6 +1176,7 @@ PGAC_C_SIGNED
PGAC_C_FUNCNAME_SUPPORT
PGAC_C_STATIC_ASSERT
PGAC_C_TYPES_COMPATIBLE
+PGAC_C_BUILTIN_BSWAP32
PGAC_C_BUILTIN_CONSTANT_P
PGAC_C_BUILTIN_UNREACHABLE
PGAC_C_VA_ARGS
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index 83f04e9..7962757 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -666,6 +666,9 @@
/* Define to 1 if you have the winldap.h header file. */
#undef HAVE_WINLDAP_H
+/* Define to 1 if your compiler understands __builtin_bswap32. */
+#undef HAVE__BUILTIN_BSWAP32
+
/* Define to 1 if your compiler understands
Re: [HACKERS] What exactly is our CRC algorithm?
On 01/01/2015 09:17 AM, Abhijit Menon-Sen wrote: Hi. OK, here are the patches with the various suggestions applied. I found that the alignment didn't seem to make much difference for the CRC32* instructions, so I changed to process (len/8)*8bytes followed by (len%8)*1bytes, the way the Linux kernel does. Ok. In the slicing-by-8 version, I wonder if it would be better to do single-byte loads to c0-c7, instead of two 4-byte loads and shifts. 4-byte loads are presumably faster than single byte loads, but then you'd avoid the shifts. And then you could go straight into the 8-bytes-at-a-time loop, without the initial single-byte processing to get the start address aligned. (the Linux implementation doesn't do that, so maybe it's a bad idea, but might be worth testing..) Looking at the Linux implementation, I think it only does the bswap once per call, not inside the hot loop. Would it even make sense to keep the crc variable in different byte order, and only do the byte-swap once in END_CRC32() ? The comments need some work. I note that there is no mention of the slicing-by-8 algorithm anywhere in the comments (in the first patch). Instead of checking for defined(__GNUC__) || defined(__clang__), should add an explicit configure test for __builtin_bswap32(). - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
Hi.
OK, here are the patches with the various suggestions applied.
I found that the alignment didn't seem to make much difference for the
CRC32* instructions, so I changed to process (len/8)*8bytes followed by
(len%8)*1bytes, the way the Linux kernel does.
-- Abhijit
From 82de6abbc05afabbf575941743b0ee355d2888ed Mon Sep 17 00:00:00 2001
From: Abhijit Menon-Sen a...@2ndquadrant.com
Date: Tue, 30 Dec 2014 12:41:19 +0530
Subject: Implement slice-by-8 CRC calculation
The COMP_CRC32C macro now calls pg_comp_crc32c(), which processes eight
data bytes at a time. Its output is identical to the byte-at-a-time CRC
code. (This change does not apply to the LEGACY_CRC32 computation.)
Reviewers: Andres Freund, Heikki Linnakangas
Author: Abhijit Menon-Sen
---
src/include/utils/pg_crc.h| 6 +-
src/include/utils/pg_crc_tables.h | 594 +-
src/port/pg_crc.c | 86 ++
3 files changed, 619 insertions(+), 67 deletions(-)
diff --git a/src/include/utils/pg_crc.h b/src/include/utils/pg_crc.h
index f871cba..55934e5 100644
--- a/src/include/utils/pg_crc.h
+++ b/src/include/utils/pg_crc.h
@@ -41,6 +41,8 @@
typedef uint32 pg_crc32;
+extern pg_crc32 pg_comp_crc32c(pg_crc32 crc, const void *data, size_t len);
+
/*
* CRC calculation using the CRC-32C (Castagnoli) polynomial.
*
@@ -51,7 +53,7 @@ typedef uint32 pg_crc32;
#define INIT_CRC32C(crc) ((crc) = 0x)
#define FIN_CRC32C(crc) ((crc) ^= 0x)
#define COMP_CRC32C(crc, data, len) \
- COMP_CRC32_NORMAL_TABLE(crc, data, len, pg_crc32c_table)
+ ((crc) = pg_comp_crc32c((crc), (char *) (data), (len)))
#define EQ_CRC32C(c1, c2) ((c1) == (c2))
/*
@@ -115,7 +117,7 @@ do { \
} while (0)
/* Constant tables for CRC-32C and CRC-32 polynomials */
-extern CRCDLLIMPORT const uint32 pg_crc32c_table[];
+extern CRCDLLIMPORT const uint32 pg_crc32c_table[8][256];
extern CRCDLLIMPORT const uint32 pg_crc32_table[];
#endif /* PG_CRC_H */
diff --git a/src/include/utils/pg_crc_tables.h b/src/include/utils/pg_crc_tables.h
index cb6b470..707b363 100644
--- a/src/include/utils/pg_crc_tables.h
+++ b/src/include/utils/pg_crc_tables.h
@@ -28,71 +28,535 @@
* This table is based on the so-called Castagnoli polynomial (the same
* that is used e.g. in iSCSI).
*/
-const uint32 pg_crc32c_table[256] = {
- 0x, 0xF26B8303, 0xE13B70F7, 0x1350F3F4,
- 0xC79A971F, 0x35F1141C, 0x26A1E7E8, 0xD4CA64EB,
- 0x8AD958CF, 0x78B2DBCC, 0x6BE22838, 0x9989AB3B,
- 0x4D43CFD0, 0xBF284CD3, 0xAC78BF27, 0x5E133C24,
- 0x105EC76F, 0xE235446C, 0xF165B798, 0x030E349B,
- 0xD7C45070, 0x25AFD373, 0x36FF2087, 0xC494A384,
- 0x9A879FA0, 0x68EC1CA3, 0x7BBCEF57, 0x89D76C54,
- 0x5D1D08BF, 0xAF768BBC, 0xBC267848, 0x4E4DFB4B,
- 0x20BD8EDE, 0xD2D60DDD, 0xC186FE29, 0x33ED7D2A,
- 0xE72719C1, 0x154C9AC2, 0x061C6936, 0xF477EA35,
- 0xAA64D611, 0x580F5512, 0x4B5FA6E6, 0xB93425E5,
- 0x6DFE410E, 0x9F95C20D, 0x8CC531F9, 0x7EAEB2FA,
- 0x30E349B1, 0xC288CAB2, 0xD1D83946, 0x23B3BA45,
- 0xF779DEAE, 0x05125DAD, 0x1642AE59, 0xE4292D5A,
- 0xBA3A117E, 0x4851927D, 0x5B016189, 0xA96AE28A,
- 0x7DA08661, 0x8FCB0562, 0x9C9BF696, 0x6EF07595,
- 0x417B1DBC, 0xB3109EBF, 0xA0406D4B, 0x522BEE48,
- 0x86E18AA3, 0x748A09A0, 0x67DAFA54, 0x95B17957,
- 0xCBA24573, 0x39C9C670, 0x2A993584, 0xD8F2B687,
- 0x0C38D26C, 0xFE53516F, 0xED03A29B, 0x1F682198,
- 0x5125DAD3, 0xA34E59D0, 0xB01EAA24, 0x42752927,
- 0x96BF4DCC, 0x64D4CECF, 0x77843D3B, 0x85EFBE38,
- 0xDBFC821C, 0x2997011F, 0x3AC7F2EB, 0xC8AC71E8,
- 0x1C661503, 0xEE0D9600, 0xFD5D65F4, 0x0F36E6F7,
- 0x61C69362, 0x93AD1061, 0x80FDE395, 0x72966096,
- 0xA65C047D, 0x5437877E, 0x4767748A, 0xB50CF789,
- 0xEB1FCBAD, 0x197448AE, 0x0A24BB5A, 0xF84F3859,
- 0x2C855CB2, 0xDEEEDFB1, 0xCDBE2C45, 0x3FD5AF46,
- 0x7198540D, 0x83F3D70E, 0x90A324FA, 0x62C8A7F9,
- 0xB602C312, 0x44694011, 0x5739B3E5, 0xA55230E6,
- 0xFB410CC2, 0x092A8FC1, 0x1A7A7C35, 0xE811FF36,
- 0x3CDB9BDD, 0xCEB018DE, 0xDDE0EB2A, 0x2F8B6829,
- 0x82F63B78, 0x709DB87B, 0x63CD4B8F, 0x91A6C88C,
- 0x456CAC67, 0xB7072F64, 0xA457DC90, 0x563C5F93,
- 0x082F63B7, 0xFA44E0B4, 0xE9141340, 0x1B7F9043,
- 0xCFB5F4A8, 0x3DDE77AB, 0x2E8E845F, 0xDCE5075C,
- 0x92A8FC17, 0x60C37F14, 0x73938CE0, 0x81F80FE3,
- 0x55326B08, 0xA759E80B, 0xB4091BFF, 0x466298FC,
- 0x1871A4D8, 0xEA1A27DB, 0xF94AD42F, 0x0B21572C,
- 0xDFEB33C7, 0x2D80B0C4, 0x3ED04330, 0xCCBBC033,
- 0xA24BB5A6, 0x502036A5, 0x4370C551, 0xB11B4652,
- 0x65D122B9, 0x97BAA1BA, 0x84EA524E, 0x7681D14D,
- 0x2892ED69, 0xDAF96E6A, 0xC9A99D9E, 0x3BC21E9D,
- 0xEF087A76, 0x1D63F975, 0x0E330A81, 0xFC588982,
- 0xB21572C9, 0x407EF1CA, 0x532E023E, 0xA145813D,
- 0x758FE5D6, 0x87E466D5, 0x94B49521, 0x66DF1622,
- 0x38CC2A06, 0xCAA7A905, 0xD9F75AF1, 0x2B9CD9F2,
- 0xFF56BD19, 0x0D3D3E1A, 0x1E6DCDEE, 0xEC064EED,
- 0xC38D26C4, 0x31E6A5C7, 0x22B65633, 0xD0DDD530,
- 0x0417B1DB, 0xF67C32D8, 0xE52CC12C, 0x1747422F,
- 0x49547E0B, 0xBB3FFD08, 0xA86F0EFC, 0x5A048DFF,
- 0x8ECEE914, 0x7CA56A17, 0x6FF599E3, 0x9D9E1AE0,
- 0xD3D3E1AB, 0x21B862A8,
Re: [HACKERS] What exactly is our CRC algorithm?
On 12/30/2014 09:40 AM, Abhijit Menon-Sen wrote: Hi. I'm re-attaching the two patches as produced by format-patch. I haven't listed any reviewers. It's either just Andres, or maybe a lot of people. Is anyone in a position to try out the patches on MSVC and see if they build and work sensibly, please? (Otherwise it may be better to remove those bits from the patch for now.) A couple of quick comments: bswap32 is unused on on little-endian systems. That will give a compiler warning. pg_comp_crc32c_sse processes one byte at a time, until the pointer is 4-bytes aligned. Then it processes 8 bytes at a time. So it fetches the 8-byte chunks from only 4-byte aligned addresses. Is that intentional? If unaligned access performs well, why bother with the initial byte-at-a-time processing at all? - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
At 2014-12-30 16:05:50 +0200, hlinnakan...@vmware.com wrote:
A couple of quick comments:
bswap32 is unused on on little-endian systems. That will give a
compiler warning.
Huh. I don't get a warning, even when I add -Wunused to the build flags.
But since you mention it, it would be better to write the function thus:
static inline uint32 cpu_to_le32(uint32 x)
{
#ifndef WORDS_BIGENDIAN
return x;
#elif defined(__GNUC__) || defined(__clang__)
return __builtin_bswap32(x);
#else
return ((x 24) 0xff00) |
((x 8) 0x00ff) |
((x 8) 0xff00) |
((x 24) 0x00ff);
#endif
}
pg_comp_crc32c_sse […] fetches the 8-byte chunks from only 4-byte
aligned addresses. Is that intentional?
Thanks for spotting that. I had meant to change the test to 7. But
again, now that you mention it, I'm not sure it's necessary. The CRC32*
instructions don't have the usual SSE alignment requirements, and I see
that the Linux kernel (among other implementations) process eight bytes
at a time from the start of the buffer and then process the remaining
bytes one at a time. I'll do a bit more research and post an update.
Thanks for having a look.
-- Abhijit
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 2014-12-30 21:36:19 +0530, Abhijit Menon-Sen wrote: Thanks for spotting that. I had meant to change the test to 7. But again, now that you mention it, I'm not sure it's necessary. The CRC32* instructions don't have the usual SSE alignment requirements, and I see that the Linux kernel (among other implementations) process eight bytes at a time from the start of the buffer and then process the remaining bytes one at a time. I'll do a bit more research and post an update. I'd done some quick and dirty benchmarking when writing my initial crc32c POC and I found that four byte aligned accesses were faster than ones not. But it really just was running it a couple times, nothing more. Greetings, Andres Freund -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
Hi,
On 2014-12-25 11:57:29 +0530, Abhijit Menon-Sen wrote:
-extern pg_crc32 pg_comp_crc32c(pg_crc32 crc, const void *data, size_t len);
+extern void pg_init_comp_crc32c(void);
How about pg_choose_crc_impl() or something?
+extern pg_crc32 (*pg_comp_crc32c)(pg_crc32 crc, const void *data, size_t
len);
/*
* CRC calculation using the CRC-32C (Castagnoli) polynomial.
diff --git a/src/port/pg_crc.c b/src/port/pg_crc.c
index 2f9857b..6be17b0 100644
--- a/src/port/pg_crc.c
+++ b/src/port/pg_crc.c
@@ -21,6 +21,13 @@
#include utils/pg_crc.h
#include utils/pg_crc_tables.h
+#if defined(HAVE_CPUID_H)
+#include cpuid.h
+#elif defined(_MSC_VER)
+#include intrin.h
+#include nmmintrin.h
+#endif
+
static inline uint32 bswap32(uint32 x)
{
#if defined(__GNUC__) || defined(__clang__)
@@ -39,8 +46,8 @@ static inline uint32 bswap32(uint32 x)
#define cpu_to_le32(x) x
#endif
-pg_crc32
-pg_comp_crc32c(pg_crc32 crc, const void *data, size_t len)
+static pg_crc32
+pg_comp_crc32c_sb8(pg_crc32 crc, const void *data, size_t len)
_sb8? Unless I miss something it's not slice by 8 but rather bytewise?
{
const unsigned char *p = data;
const uint32 *p8;
@@ -61,7 +68,6 @@ pg_comp_crc32c(pg_crc32 crc, const void *data, size_t len)
*/
p8 = (const uint32 *) p;
-
while (len = 8)
{
uint32 a = *p8++ ^ cpu_to_le32(crc);
@@ -101,8 +107,102 @@ pg_comp_crc32c(pg_crc32 crc, const void *data, size_t
len)
*/
p = (const unsigned char *) p8;
- while (len-- 0)
+ while (len 0)
+ {
crc = pg_crc32c_table[0][(crc ^ *p++) 0xFF] ^ (crc 8);
+ len--;
+ }
+
+ return crc;
+}
+static pg_crc32
+pg_asm_crc32b(pg_crc32 crc, unsigned char data)
+{
Should be marked inline.
+#ifdef __GNUC__
+ __asm__ (crc32b %[data], %[crc]\n : [crc] +r (crc) : [data] rm
(data));
Have you checked which version of gcc introduced named references to
input/output parameters?
return crc;
+#elif defined(_MSC_VER)
+ return _mm_crc32_u8(crc, data);
+#else
+#error Don't know how to generate crc32b instruction
+#endif
}
+
+static pg_crc32
+pg_asm_crc32q(uint64 crc, unsigned long long data)
+{
inline.
Greetings,
Andres Freund
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
At 2014-12-29 13:22:28 +0100, and...@2ndquadrant.com wrote:
How about pg_choose_crc_impl() or something?
Done.
_sb8? Unless I miss something it's not slice by 8 but rather bytewise?
This is meant to apply on top of the earlier patches I posted to
implement slice-by-8. I'll attach both here.
Should be marked inline.
Done (and the other one too).
+#ifdef __GNUC__
+ __asm__ (crc32b %[data], %[crc]\n : [crc] +r (crc) : [data] rm
(data));
Have you checked which version of gcc introduced named references to
input/output parameters?
No. The documentation calls them asmSymbolicNames, but I can't find
the term (or various likely alternatives, e.g. symbolic_operand may be
related) either in the release notes, the changelog, or the source (on
Github). Does anyone know, or know how to find out?
Meanwhile, I have attached the two patches with the other modifications.
-- Abhijit
diff --git a/src/include/utils/pg_crc.h b/src/include/utils/pg_crc.h
index f871cba..55934e5 100644
--- a/src/include/utils/pg_crc.h
+++ b/src/include/utils/pg_crc.h
@@ -41,6 +41,8 @@
typedef uint32 pg_crc32;
+extern pg_crc32 pg_comp_crc32c(pg_crc32 crc, const void *data, size_t len);
+
/*
* CRC calculation using the CRC-32C (Castagnoli) polynomial.
*
@@ -51,7 +53,7 @@ typedef uint32 pg_crc32;
#define INIT_CRC32C(crc) ((crc) = 0x)
#define FIN_CRC32C(crc) ((crc) ^= 0x)
#define COMP_CRC32C(crc, data, len) \
- COMP_CRC32_NORMAL_TABLE(crc, data, len, pg_crc32c_table)
+ ((crc) = pg_comp_crc32c((crc), (char *) (data), (len)))
#define EQ_CRC32C(c1, c2) ((c1) == (c2))
/*
@@ -115,7 +117,7 @@ do { \
} while (0)
/* Constant tables for CRC-32C and CRC-32 polynomials */
-extern CRCDLLIMPORT const uint32 pg_crc32c_table[];
+extern CRCDLLIMPORT const uint32 pg_crc32c_table[8][256];
extern CRCDLLIMPORT const uint32 pg_crc32_table[];
#endif /* PG_CRC_H */
diff --git a/src/include/utils/pg_crc_tables.h b/src/include/utils/pg_crc_tables.h
index cb6b470..f814c91 100644
--- a/src/include/utils/pg_crc_tables.h
+++ b/src/include/utils/pg_crc_tables.h
@@ -28,71 +28,519 @@
* This table is based on the so-called Castagnoli polynomial (the same
* that is used e.g. in iSCSI).
*/
-const uint32 pg_crc32c_table[256] = {
- 0x, 0xF26B8303, 0xE13B70F7, 0x1350F3F4,
- 0xC79A971F, 0x35F1141C, 0x26A1E7E8, 0xD4CA64EB,
- 0x8AD958CF, 0x78B2DBCC, 0x6BE22838, 0x9989AB3B,
- 0x4D43CFD0, 0xBF284CD3, 0xAC78BF27, 0x5E133C24,
- 0x105EC76F, 0xE235446C, 0xF165B798, 0x030E349B,
- 0xD7C45070, 0x25AFD373, 0x36FF2087, 0xC494A384,
- 0x9A879FA0, 0x68EC1CA3, 0x7BBCEF57, 0x89D76C54,
- 0x5D1D08BF, 0xAF768BBC, 0xBC267848, 0x4E4DFB4B,
- 0x20BD8EDE, 0xD2D60DDD, 0xC186FE29, 0x33ED7D2A,
- 0xE72719C1, 0x154C9AC2, 0x061C6936, 0xF477EA35,
- 0xAA64D611, 0x580F5512, 0x4B5FA6E6, 0xB93425E5,
- 0x6DFE410E, 0x9F95C20D, 0x8CC531F9, 0x7EAEB2FA,
- 0x30E349B1, 0xC288CAB2, 0xD1D83946, 0x23B3BA45,
- 0xF779DEAE, 0x05125DAD, 0x1642AE59, 0xE4292D5A,
- 0xBA3A117E, 0x4851927D, 0x5B016189, 0xA96AE28A,
- 0x7DA08661, 0x8FCB0562, 0x9C9BF696, 0x6EF07595,
- 0x417B1DBC, 0xB3109EBF, 0xA0406D4B, 0x522BEE48,
- 0x86E18AA3, 0x748A09A0, 0x67DAFA54, 0x95B17957,
- 0xCBA24573, 0x39C9C670, 0x2A993584, 0xD8F2B687,
- 0x0C38D26C, 0xFE53516F, 0xED03A29B, 0x1F682198,
- 0x5125DAD3, 0xA34E59D0, 0xB01EAA24, 0x42752927,
- 0x96BF4DCC, 0x64D4CECF, 0x77843D3B, 0x85EFBE38,
- 0xDBFC821C, 0x2997011F, 0x3AC7F2EB, 0xC8AC71E8,
- 0x1C661503, 0xEE0D9600, 0xFD5D65F4, 0x0F36E6F7,
- 0x61C69362, 0x93AD1061, 0x80FDE395, 0x72966096,
- 0xA65C047D, 0x5437877E, 0x4767748A, 0xB50CF789,
- 0xEB1FCBAD, 0x197448AE, 0x0A24BB5A, 0xF84F3859,
- 0x2C855CB2, 0xDEEEDFB1, 0xCDBE2C45, 0x3FD5AF46,
- 0x7198540D, 0x83F3D70E, 0x90A324FA, 0x62C8A7F9,
- 0xB602C312, 0x44694011, 0x5739B3E5, 0xA55230E6,
- 0xFB410CC2, 0x092A8FC1, 0x1A7A7C35, 0xE811FF36,
- 0x3CDB9BDD, 0xCEB018DE, 0xDDE0EB2A, 0x2F8B6829,
- 0x82F63B78, 0x709DB87B, 0x63CD4B8F, 0x91A6C88C,
- 0x456CAC67, 0xB7072F64, 0xA457DC90, 0x563C5F93,
- 0x082F63B7, 0xFA44E0B4, 0xE9141340, 0x1B7F9043,
- 0xCFB5F4A8, 0x3DDE77AB, 0x2E8E845F, 0xDCE5075C,
- 0x92A8FC17, 0x60C37F14, 0x73938CE0, 0x81F80FE3,
- 0x55326B08, 0xA759E80B, 0xB4091BFF, 0x466298FC,
- 0x1871A4D8, 0xEA1A27DB, 0xF94AD42F, 0x0B21572C,
- 0xDFEB33C7, 0x2D80B0C4, 0x3ED04330, 0xCCBBC033,
- 0xA24BB5A6, 0x502036A5, 0x4370C551, 0xB11B4652,
- 0x65D122B9, 0x97BAA1BA, 0x84EA524E, 0x7681D14D,
- 0x2892ED69, 0xDAF96E6A, 0xC9A99D9E, 0x3BC21E9D,
- 0xEF087A76, 0x1D63F975, 0x0E330A81, 0xFC588982,
- 0xB21572C9, 0x407EF1CA, 0x532E023E, 0xA145813D,
- 0x758FE5D6, 0x87E466D5, 0x94B49521, 0x66DF1622,
- 0x38CC2A06, 0xCAA7A905, 0xD9F75AF1, 0x2B9CD9F2,
- 0xFF56BD19, 0x0D3D3E1A, 0x1E6DCDEE, 0xEC064EED,
- 0xC38D26C4, 0x31E6A5C7, 0x22B65633, 0xD0DDD530,
- 0x0417B1DB, 0xF67C32D8, 0xE52CC12C, 0x1747422F,
- 0x49547E0B, 0xBB3FFD08, 0xA86F0EFC, 0x5A048DFF,
- 0x8ECEE914, 0x7CA56A17, 0x6FF599E3, 0x9D9E1AE0,
- 0xD3D3E1AB, 0x21B862A8, 0x32E8915C, 0xC083125F,
- 0x144976B4, 0xE622F5B7, 0xF5720643, 0x07198540,
- 0x590AB964,
Re: [HACKERS] What exactly is our CRC algorithm?
Hi.
I'm re-attaching the two patches as produced by format-patch. I haven't
listed any reviewers. It's either just Andres, or maybe a lot of people.
Is anyone in a position to try out the patches on MSVC and see if they
build and work sensibly, please? (Otherwise it may be better to remove
those bits from the patch for now.)
Thanks.
-- Abhijit
From d5a90d31f9c35fea2636ec6baf6acc66e91fd655 Mon Sep 17 00:00:00 2001
From: Abhijit Menon-Sen a...@2ndquadrant.com
Date: Tue, 30 Dec 2014 12:41:19 +0530
Subject: Implement slice-by-8 CRC calculation
The COMP_CRC32C macro now calls pg_comp_crc32c(), which processes eight
data bytes at a time. Its output is identical to the byte-at-a-time CRC
code. (This change does not apply to the LEGACY_CRC32 computation.)
Author: Abhijit Menon-Sen
---
src/include/utils/pg_crc.h| 6 +-
src/include/utils/pg_crc_tables.h | 578 +-
src/port/pg_crc.c | 87 ++
3 files changed, 604 insertions(+), 67 deletions(-)
diff --git a/src/include/utils/pg_crc.h b/src/include/utils/pg_crc.h
index f871cba..55934e5 100644
--- a/src/include/utils/pg_crc.h
+++ b/src/include/utils/pg_crc.h
@@ -41,6 +41,8 @@
typedef uint32 pg_crc32;
+extern pg_crc32 pg_comp_crc32c(pg_crc32 crc, const void *data, size_t len);
+
/*
* CRC calculation using the CRC-32C (Castagnoli) polynomial.
*
@@ -51,7 +53,7 @@ typedef uint32 pg_crc32;
#define INIT_CRC32C(crc) ((crc) = 0x)
#define FIN_CRC32C(crc) ((crc) ^= 0x)
#define COMP_CRC32C(crc, data, len) \
- COMP_CRC32_NORMAL_TABLE(crc, data, len, pg_crc32c_table)
+ ((crc) = pg_comp_crc32c((crc), (char *) (data), (len)))
#define EQ_CRC32C(c1, c2) ((c1) == (c2))
/*
@@ -115,7 +117,7 @@ do { \
} while (0)
/* Constant tables for CRC-32C and CRC-32 polynomials */
-extern CRCDLLIMPORT const uint32 pg_crc32c_table[];
+extern CRCDLLIMPORT const uint32 pg_crc32c_table[8][256];
extern CRCDLLIMPORT const uint32 pg_crc32_table[];
#endif /* PG_CRC_H */
diff --git a/src/include/utils/pg_crc_tables.h b/src/include/utils/pg_crc_tables.h
index cb6b470..f814c91 100644
--- a/src/include/utils/pg_crc_tables.h
+++ b/src/include/utils/pg_crc_tables.h
@@ -28,71 +28,519 @@
* This table is based on the so-called Castagnoli polynomial (the same
* that is used e.g. in iSCSI).
*/
-const uint32 pg_crc32c_table[256] = {
- 0x, 0xF26B8303, 0xE13B70F7, 0x1350F3F4,
- 0xC79A971F, 0x35F1141C, 0x26A1E7E8, 0xD4CA64EB,
- 0x8AD958CF, 0x78B2DBCC, 0x6BE22838, 0x9989AB3B,
- 0x4D43CFD0, 0xBF284CD3, 0xAC78BF27, 0x5E133C24,
- 0x105EC76F, 0xE235446C, 0xF165B798, 0x030E349B,
- 0xD7C45070, 0x25AFD373, 0x36FF2087, 0xC494A384,
- 0x9A879FA0, 0x68EC1CA3, 0x7BBCEF57, 0x89D76C54,
- 0x5D1D08BF, 0xAF768BBC, 0xBC267848, 0x4E4DFB4B,
- 0x20BD8EDE, 0xD2D60DDD, 0xC186FE29, 0x33ED7D2A,
- 0xE72719C1, 0x154C9AC2, 0x061C6936, 0xF477EA35,
- 0xAA64D611, 0x580F5512, 0x4B5FA6E6, 0xB93425E5,
- 0x6DFE410E, 0x9F95C20D, 0x8CC531F9, 0x7EAEB2FA,
- 0x30E349B1, 0xC288CAB2, 0xD1D83946, 0x23B3BA45,
- 0xF779DEAE, 0x05125DAD, 0x1642AE59, 0xE4292D5A,
- 0xBA3A117E, 0x4851927D, 0x5B016189, 0xA96AE28A,
- 0x7DA08661, 0x8FCB0562, 0x9C9BF696, 0x6EF07595,
- 0x417B1DBC, 0xB3109EBF, 0xA0406D4B, 0x522BEE48,
- 0x86E18AA3, 0x748A09A0, 0x67DAFA54, 0x95B17957,
- 0xCBA24573, 0x39C9C670, 0x2A993584, 0xD8F2B687,
- 0x0C38D26C, 0xFE53516F, 0xED03A29B, 0x1F682198,
- 0x5125DAD3, 0xA34E59D0, 0xB01EAA24, 0x42752927,
- 0x96BF4DCC, 0x64D4CECF, 0x77843D3B, 0x85EFBE38,
- 0xDBFC821C, 0x2997011F, 0x3AC7F2EB, 0xC8AC71E8,
- 0x1C661503, 0xEE0D9600, 0xFD5D65F4, 0x0F36E6F7,
- 0x61C69362, 0x93AD1061, 0x80FDE395, 0x72966096,
- 0xA65C047D, 0x5437877E, 0x4767748A, 0xB50CF789,
- 0xEB1FCBAD, 0x197448AE, 0x0A24BB5A, 0xF84F3859,
- 0x2C855CB2, 0xDEEEDFB1, 0xCDBE2C45, 0x3FD5AF46,
- 0x7198540D, 0x83F3D70E, 0x90A324FA, 0x62C8A7F9,
- 0xB602C312, 0x44694011, 0x5739B3E5, 0xA55230E6,
- 0xFB410CC2, 0x092A8FC1, 0x1A7A7C35, 0xE811FF36,
- 0x3CDB9BDD, 0xCEB018DE, 0xDDE0EB2A, 0x2F8B6829,
- 0x82F63B78, 0x709DB87B, 0x63CD4B8F, 0x91A6C88C,
- 0x456CAC67, 0xB7072F64, 0xA457DC90, 0x563C5F93,
- 0x082F63B7, 0xFA44E0B4, 0xE9141340, 0x1B7F9043,
- 0xCFB5F4A8, 0x3DDE77AB, 0x2E8E845F, 0xDCE5075C,
- 0x92A8FC17, 0x60C37F14, 0x73938CE0, 0x81F80FE3,
- 0x55326B08, 0xA759E80B, 0xB4091BFF, 0x466298FC,
- 0x1871A4D8, 0xEA1A27DB, 0xF94AD42F, 0x0B21572C,
- 0xDFEB33C7, 0x2D80B0C4, 0x3ED04330, 0xCCBBC033,
- 0xA24BB5A6, 0x502036A5, 0x4370C551, 0xB11B4652,
- 0x65D122B9, 0x97BAA1BA, 0x84EA524E, 0x7681D14D,
- 0x2892ED69, 0xDAF96E6A, 0xC9A99D9E, 0x3BC21E9D,
- 0xEF087A76, 0x1D63F975, 0x0E330A81, 0xFC588982,
- 0xB21572C9, 0x407EF1CA, 0x532E023E, 0xA145813D,
- 0x758FE5D6, 0x87E466D5, 0x94B49521, 0x66DF1622,
- 0x38CC2A06, 0xCAA7A905, 0xD9F75AF1, 0x2B9CD9F2,
- 0xFF56BD19, 0x0D3D3E1A, 0x1E6DCDEE, 0xEC064EED,
- 0xC38D26C4, 0x31E6A5C7, 0x22B65633, 0xD0DDD530,
- 0x0417B1DB, 0xF67C32D8, 0xE52CC12C, 0x1747422F,
- 0x49547E0B, 0xBB3FFD08, 0xA86F0EFC, 0x5A048DFF,
- 0x8ECEE914, 0x7CA56A17, 0x6FF599E3, 0x9D9E1AE0,
-
Re: [HACKERS] What exactly is our CRC algorithm?
On Thu, Dec 25, 2014 at 11:57:29AM +0530, Abhijit Menon-Sen wrote: Hi. Here's a proposed patch to use CPUID at startup to determine if the SSE4.2 CRC instructions are available, to use them instead of the slice-by-8 implementation (posted earlier). A few notes: 1. GCC has included cpuid.h since 4.3.0, so I figured it was safe to use. It can be replaced with some inline assembly otherwise. 2. I've also used the crc32b/crc32q instructions directly rather than using .bytes to encode the instructions; bintuils versions since 2007 or so have supported them. 3. I've included the MSVC implementation mostly as an example of how to extend this to different compilers/platforms. It's written according to the documentation for MSVC intrinsics, but I have not tested it. Suggestions/improvements are welcome. Uh, what happens if the system is compiled on a different CPU that it is run on? Seems we would need a run-time CPU test. -- Bruce Momjian br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com + Everyone has their own god. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On December 26, 2014 4:50:33 PM CET, Bruce Momjian br...@momjian.us wrote: On Thu, Dec 25, 2014 at 11:57:29AM +0530, Abhijit Menon-Sen wrote: Hi. Here's a proposed patch to use CPUID at startup to determine if the SSE4.2 CRC instructions are available, to use them instead of the slice-by-8 implementation (posted earlier). A few notes: 1. GCC has included cpuid.h since 4.3.0, so I figured it was safe to use. It can be replaced with some inline assembly otherwise. 2. I've also used the crc32b/crc32q instructions directly rather than using .bytes to encode the instructions; bintuils versions since 2007 or so have supported them. 3. I've included the MSVC implementation mostly as an example of how to extend this to different compilers/platforms. It's written according to the documentation for MSVC intrinsics, but I have not tested it. Suggestions/improvements are welcome. Uh, what happens if the system is compiled on a different CPU that it is run on? Seems we would need a run-time CPU test. That's the cpuid thing mentioned above. Andres -- Please excuse brevity and formatting - I am writing this on my mobile phone. Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On Fri, Dec 26, 2014 at 04:52:58PM +0100, Andres Freund wrote: On December 26, 2014 4:50:33 PM CET, Bruce Momjian br...@momjian.us wrote: On Thu, Dec 25, 2014 at 11:57:29AM +0530, Abhijit Menon-Sen wrote: Hi. Here's a proposed patch to use CPUID at startup to determine if the SSE4.2 CRC instructions are available, to use them instead of the slice-by-8 implementation (posted earlier). A few notes: 1. GCC has included cpuid.h since 4.3.0, so I figured it was safe to use. It can be replaced with some inline assembly otherwise. 2. I've also used the crc32b/crc32q instructions directly rather than using .bytes to encode the instructions; bintuils versions since 2007 or so have supported them. 3. I've included the MSVC implementation mostly as an example of how to extend this to different compilers/platforms. It's written according to the documentation for MSVC intrinsics, but I have not tested it. Suggestions/improvements are welcome. Uh, what happens if the system is compiled on a different CPU that it is run on? Seems we would need a run-time CPU test. That's the cpuid thing mentioned above. Oh, so cpuid is not a macro exported by the compiler but a C API. Good. -- Bruce Momjian br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com + Everyone has their own god. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On December 26, 2014 6:05:34 PM CET, Bruce Momjian br...@momjian.us wrote: On Fri, Dec 26, 2014 at 04:52:58PM +0100, Andres Freund wrote: On December 26, 2014 4:50:33 PM CET, Bruce Momjian br...@momjian.us wrote: On Thu, Dec 25, 2014 at 11:57:29AM +0530, Abhijit Menon-Sen wrote: Hi. Here's a proposed patch to use CPUID at startup to determine if the SSE4.2 CRC instructions are available, to use them instead of the slice-by-8 implementation (posted earlier). A few notes: 1. GCC has included cpuid.h since 4.3.0, so I figured it was safe to use. It can be replaced with some inline assembly otherwise. 2. I've also used the crc32b/crc32q instructions directly rather than using .bytes to encode the instructions; bintuils versions since 2007 or so have supported them. 3. I've included the MSVC implementation mostly as an example of how to extend this to different compilers/platforms. It's written according to the documentation for MSVC intrinsics, but I have not tested it. Suggestions/improvements are welcome. Uh, what happens if the system is compiled on a different CPU that it is run on? Seems we would need a run-time CPU test. That's the cpuid thing mentioned above. Oh, so cpuid is not a macro exported by the compiler but a C API. Good Neither, really. It's a instruction returning CPU capabilities. -- Please excuse brevity and formatting - I am writing this on my mobile phone. Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On Fri, Dec 26, 2014 at 04:52:58PM +0100, Andres Freund wrote: Uh, what if the system is compiled on a different CPU that it is run on? Seems we would need a run-time CPU test. That's the cpuid thing mentioned above. Is this something that could potentially change the data stored on disk? Does pg_upgrade need to check for changes in this area? Is the detection exposed by pg_controldata? Could this affect running the data directory on a different CPU? -- Bruce Momjian br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com + Everyone has their own god. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
At 2014-12-26 13:11:43 -0500, br...@momjian.us wrote: Is this something that could potentially change the data stored on disk? Does pg_upgrade need to check for changes in this area? Is the detection exposed by pg_controldata? Could this affect running the data directory on a different CPU? No to all. Subsequent to Heikki's change (already in master) to use the CRC-32C algorithm (instead of the earlier mistakenly-reflected-but-not-quite one), both the slice-by-8 software implementation posted earlier and the SSE4.2 CRC32* instructions will compute exactly the same value. (Yes, I have verified this in both cases.) -- Abhijit -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On Fri, Dec 26, 2014 at 11:52:41PM +0530, Abhijit Menon-Sen wrote: At 2014-12-26 13:11:43 -0500, br...@momjian.us wrote: Is this something that could potentially change the data stored on disk? Does pg_upgrade need to check for changes in this area? Is the detection exposed by pg_controldata? Could this affect running the data directory on a different CPU? No to all. Subsequent to Heikki's change (already in master) to use the CRC-32C algorithm (instead of the earlier mistakenly-reflected-but-not-quite one), both the slice-by-8 software implementation posted earlier and the SSE4.2 CRC32* instructions will compute exactly the same value. (Yes, I have verified this in both cases.) Uh, we didn't fully change all code to use the new algorithm because there were cases that the CRC was already stored on disk, e.g hstore, ltree. I assume you are only linking into Heikki's new code and will not change the places that use the old CRC method on disk --- just checking. -- Bruce Momjian br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com + Everyone has their own god. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
At 2014-12-26 13:48:40 -0500, br...@momjian.us wrote: I assume you are only linking into Heikki's new code and will not change the places that use the old CRC method on disk --- just checking. Correct. The legacy CRC computation code used by ltree etc. is completely unaffected by both my sets of changes. -- Abhijit -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
Hi.
Here's a proposed patch to use CPUID at startup to determine if the
SSE4.2 CRC instructions are available, to use them instead of the
slice-by-8 implementation (posted earlier).
A few notes:
1. GCC has included cpuid.h since 4.3.0, so I figured it was safe to
use. It can be replaced with some inline assembly otherwise.
2. I've also used the crc32b/crc32q instructions directly rather than
using .bytes to encode the instructions; bintuils versions since
2007 or so have supported them.
3. I've included the MSVC implementation mostly as an example of how to
extend this to different compilers/platforms. It's written according
to the documentation for MSVC intrinsics, but I have not tested it.
Suggestions/improvements are welcome.
-- Abhijit
diff --git a/src/backend/main/main.c b/src/backend/main/main.c
index 73c30c5..ae34876 100644
--- a/src/backend/main/main.c
+++ b/src/backend/main/main.c
@@ -37,6 +37,7 @@
#include utils/memutils.h
#include utils/pg_locale.h
#include utils/ps_status.h
+#include utils/pg_crc.h
const char *progname;
@@ -76,6 +77,12 @@ main(int argc, char *argv[])
argv = save_ps_display_args(argc, argv);
/*
+ * Select the fastest available CRC32 implementation for the
+ * platform.
+ */
+ pg_init_comp_crc32c();
+
+ /*
* If supported on the current platform, set up a handler to be called if
* the backend/postmaster crashes with a fatal signal or exception.
*/
diff --git a/src/include/utils/pg_crc.h b/src/include/utils/pg_crc.h
index 55934e5..c59c05b 100644
--- a/src/include/utils/pg_crc.h
+++ b/src/include/utils/pg_crc.h
@@ -41,7 +41,8 @@
typedef uint32 pg_crc32;
-extern pg_crc32 pg_comp_crc32c(pg_crc32 crc, const void *data, size_t len);
+extern void pg_init_comp_crc32c(void);
+extern pg_crc32 (*pg_comp_crc32c)(pg_crc32 crc, const void *data, size_t len);
/*
* CRC calculation using the CRC-32C (Castagnoli) polynomial.
diff --git a/src/port/pg_crc.c b/src/port/pg_crc.c
index 2f9857b..6be17b0 100644
--- a/src/port/pg_crc.c
+++ b/src/port/pg_crc.c
@@ -21,6 +21,13 @@
#include utils/pg_crc.h
#include utils/pg_crc_tables.h
+#if defined(HAVE_CPUID_H)
+#include cpuid.h
+#elif defined(_MSC_VER)
+#include intrin.h
+#include nmmintrin.h
+#endif
+
static inline uint32 bswap32(uint32 x)
{
#if defined(__GNUC__) || defined(__clang__)
@@ -39,8 +46,8 @@ static inline uint32 bswap32(uint32 x)
#define cpu_to_le32(x) x
#endif
-pg_crc32
-pg_comp_crc32c(pg_crc32 crc, const void *data, size_t len)
+static pg_crc32
+pg_comp_crc32c_sb8(pg_crc32 crc, const void *data, size_t len)
{
const unsigned char *p = data;
const uint32 *p8;
@@ -61,7 +68,6 @@ pg_comp_crc32c(pg_crc32 crc, const void *data, size_t len)
*/
p8 = (const uint32 *) p;
-
while (len = 8)
{
uint32 a = *p8++ ^ cpu_to_le32(crc);
@@ -101,8 +107,102 @@ pg_comp_crc32c(pg_crc32 crc, const void *data, size_t len)
*/
p = (const unsigned char *) p8;
- while (len-- 0)
+ while (len 0)
+ {
crc = pg_crc32c_table[0][(crc ^ *p++) 0xFF] ^ (crc 8);
+ len--;
+ }
+
+ return crc;
+}
+static pg_crc32
+pg_asm_crc32b(pg_crc32 crc, unsigned char data)
+{
+#ifdef __GNUC__
+ __asm__ (crc32b %[data], %[crc]\n : [crc] +r (crc) : [data] rm (data));
return crc;
+#elif defined(_MSC_VER)
+ return _mm_crc32_u8(crc, data);
+#else
+#error Don't know how to generate crc32b instruction
+#endif
}
+
+static pg_crc32
+pg_asm_crc32q(uint64 crc, unsigned long long data)
+{
+#ifdef __GNUC__
+ __asm__ (crc32q %[data], %[crc]\n : [crc] +r (crc) : [data] rm (data));
+ return crc;
+#elif defined(_MSC_VER)
+ return _mm_crc32_u64(crc, data);
+#else
+#error Don't know how to generate crc32q instruction
+#endif
+}
+
+static pg_crc32
+pg_comp_crc32c_sse(pg_crc32 crc, const void *data, size_t len)
+{
+ const unsigned char *p = data;
+ const uint64 *p8;
+
+ /*
+ * Handle initial bytes one at a time if necessary to ensure that
+ * the loop below starts with a pointer aligned to four bytes.
+ */
+
+ while (len 0 ((uintptr_t) p 3))
+ {
+ crc = pg_asm_crc32b(crc, *p++);
+ len--;
+ }
+
+ /*
+ * Process eight bytes of data at a time.
+ */
+
+ p8 = (const uint64 *) p;
+ while (len = 8)
+ {
+ crc = pg_asm_crc32q(crc, *p8++);
+ len -= 8;
+ }
+
+ /*
+ * Handle any remaining bytes one at a time.
+ */
+
+ p = (const unsigned char *) p8;
+ while (len 0)
+ {
+ crc = pg_asm_crc32b(crc, *p++);
+ len--;
+ }
+
+ return crc;
+}
+
+/*
+ * If (we can tell that) the CPU supports SSE4.2 instructions, we can
+ * use the CRC instruction, otherwise we fall back to slice-by-8 in
+ * software.
+ */
+
+void
+pg_init_comp_crc32c(void)
+{
+ unsigned int exx[4] = { 0, 0, 0, 0 };
+
+#if defined(__GNUC__) defined(HAVE_CPUID_H)
+ __get_cpuid(1, exx[0], exx[1], exx[2], exx[3]);
+#elif defined(_MSC_VER)
+ __cpuid(exx, 1);
+#endif
+
+ if (exx[2] (1 20))
+ pg_comp_crc32c = pg_comp_crc32c_sse;
+}
+
+pg_crc32 (*pg_comp_crc32c)(pg_crc32 crc, const void *data, size_t len) = pg_comp_crc32c_sb8;
diff --git a/configure
Re: [HACKERS] What exactly is our CRC algorithm?
On Thu, Nov 27, 2014 at 11:19:51AM +0530, Abhijit Menon-Sen wrote: At 2014-11-26 18:56:52 -0500, br...@momjian.us wrote: I would test it with fsync=off to remove the fsync delay. That will simulate an SSD or BBU controller. The earlier tests were run with fsync=off. I ran another round of the replay tests on the i7 server, this time replaying 30GB of WAL segments. master 16:08:03 16:16:23 08:20 16:19:33 16:28:03 08:30 16:32:20 16:41:17 08:57 16:42:42 16:51:22 08:40 8crc 16:52:11 16:59:48 07:37 17:01:07 17:08:30 07:23 17:22:16 17:30:11 07:55 17:31:29 17:39:06 07:37 These are just the results of the last four runs with each branch, but the difference was consistent over many more runs. To summarise: the slice-by-8 patch (a) increases pure CRC performance by a large margin, (b) has a positive effect on reading WAL during replay, (c) doesn't hurt XLogInsert in typical cases (which was the main worry). Thanks, these are good numbers. -- Bruce Momjian br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com + Everyone has their own god. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On Fri, Nov 21, 2014 at 07:49:45AM -0600, k...@rice.edu wrote: Hi, This indicates that another part of the system is the resource limit, not the CRC calculation. My money is on the I/O system. Try it using an in memory filesystem and see if that matters. Even if it is still the same results, at least the new version of CRC is no worse than the current version. I would test it with fsync=off to remove the fsync delay. That will simulate an SSD or BBU controller. -- Bruce Momjian br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com + Everyone has their own god. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
At 2014-11-26 18:56:52 -0500, br...@momjian.us wrote: I would test it with fsync=off to remove the fsync delay. That will simulate an SSD or BBU controller. The earlier tests were run with fsync=off. I ran another round of the replay tests on the i7 server, this time replaying 30GB of WAL segments. master 16:08:03 16:16:23 08:20 16:19:33 16:28:03 08:30 16:32:20 16:41:17 08:57 16:42:42 16:51:22 08:40 8crc 16:52:11 16:59:48 07:37 17:01:07 17:08:30 07:23 17:22:16 17:30:11 07:55 17:31:29 17:39:06 07:37 These are just the results of the last four runs with each branch, but the difference was consistent over many more runs. To summarise: the slice-by-8 patch (a) increases pure CRC performance by a large margin, (b) has a positive effect on reading WAL during replay, (c) doesn't hurt XLogInsert in typical cases (which was the main worry). -- Abhijit -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
At 2014-11-20 13:47:00 +0530, a...@2ndquadrant.com wrote: Suggestions for how to address (b) are welcome. With help from Andres, I set up a workload where XLogInsert* was at the top of my profiles: server with fsync and synchronous_commit off, and pgbench running a multiple-row insert into a single-text-column table with -M prepared -c 25 -t 25 -f script. Unfortunately I can't see much difference despite running things with slightly different parameters a few dozen times. For example, here are real/user/sys times from three runs each with HEAD and slice-by-8 on an otherwise-idle i7-3770 server with a couple of undistinguished Toshiba 7200rpm SATA disks in RAID-1: HEAD: 2m24.822s/0m18.776s/0m23.156s 3m34.586s/0m18.784s/0m24.324s 3m41.557s/0m18.640s/0m23.920s Slice-by-8: 2m26.977s/0m18.420s/0m22.884s 3m36.664s/0m18.376s/0m24.232s 3m43.930s/0m18.580s/0m24.560s I don't know how to interpret these results (especially the tendency for the tests to slow down as time passes, with every version). At best, it shows that the new CRC code doesn't hurt, at worst it's just irrelevant. Supporting the latter interpretation, using the hardware-CRC patch also gives similar results (but XLogInsert is not at the top of the profile). Hardware-CRC: 2m29.090s/0m18.652s/0m23.764s 3m30.188s/0m18.692s/0m25.332s 3m38.110s/0m20.424s/0m24.532s If anyone has other suggestions, I'm all ears. -- Abhijit -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 11/21/2014 12:11 PM, Abhijit Menon-Sen wrote: At 2014-11-20 13:47:00 +0530, a...@2ndquadrant.com wrote: Suggestions for how to address (b) are welcome. With help from Andres, I set up a workload where XLogInsert* was at the top of my profiles: server with fsync and synchronous_commit off, and pgbench running a multiple-row insert into a single-text-column table with -M prepared -c 25 -t 25 -f script. How wide is the row, in terms of bytes? You should see bigger improvement with wider rows, as you get longer contiguous chunks of data to CRC that way. With very narrow rows, you might not see much difference because the chunks are so small. Did you run these tests with a fresh checkout, including the WAL format patch I committed yesterday? That would make some difference to how many XLogRecData chunks there are for each insertion record. If that's the problem, it might be beneficial to memcpy() all the data to a temporary buffer, and calculate the CRC over the whole, instead of CRC'ing each XLogRecData chunk separately. XLogRecordAssemble() uses a scratch area, hdr_scratch, for building all the headers. You could check how much rmgr-specific data there is, and if there isn't much, just append the data to that scratch area too. Unfortunately I can't see much difference despite running things with slightly different parameters a few dozen times. For example, here are real/user/sys times from three runs each with HEAD and slice-by-8 on an otherwise-idle i7-3770 server with a couple of undistinguished Toshiba 7200rpm SATA disks in RAID-1: HEAD: 2m24.822s/0m18.776s/0m23.156s 3m34.586s/0m18.784s/0m24.324s 3m41.557s/0m18.640s/0m23.920s Slice-by-8: 2m26.977s/0m18.420s/0m22.884s 3m36.664s/0m18.376s/0m24.232s 3m43.930s/0m18.580s/0m24.560s I don't know how to interpret these results (especially the tendency for the tests to slow down as time passes, with every version). The user/sys times are very stable, but the real time is much higher and increases. Does that mean that it's blocked on I/O? - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 2014-11-21 13:01:50 +0200, Heikki Linnakangas wrote: On 11/21/2014 12:11 PM, Abhijit Menon-Sen wrote: At 2014-11-20 13:47:00 +0530, a...@2ndquadrant.com wrote: Suggestions for how to address (b) are welcome. With help from Andres, I set up a workload where XLogInsert* was at the top of my profiles: server with fsync and synchronous_commit off, and pgbench running a multiple-row insert into a single-text-column table with -M prepared -c 25 -t 25 -f script. How wide is the row, in terms of bytes? You should see bigger improvement with wider rows, as you get longer contiguous chunks of data to CRC that way. With very narrow rows, you might not see much difference because the chunks are so small. The primary goal, as I understood it, was to test very short records to test whether there's a regression due to slice-by-8. There doesn't seem to be any. It's, IIRC, trivial to reproduce significant performance benefits in workloads with lots of FPWs or large records (like COPY), but those weren't what you and Tom were concerned about... If that's the problem, it might be beneficial to memcpy() all the data to a temporary buffer, and calculate the CRC over the whole, instead of CRC'ing each XLogRecData chunk separately. XLogRecordAssemble() uses a scratch area, hdr_scratch, for building all the headers. You could check how much rmgr-specific data there is, and if there isn't much, just append the data to that scratch area too. I think that might very well make sense - but it's imo something better done separately from the smarter CRC algorithm. Greetings, Andres Freund -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 11/21/2014 01:06 PM, Andres Freund wrote: On 2014-11-21 13:01:50 +0200, Heikki Linnakangas wrote: On 11/21/2014 12:11 PM, Abhijit Menon-Sen wrote: At 2014-11-20 13:47:00 +0530, a...@2ndquadrant.com wrote: Suggestions for how to address (b) are welcome. With help from Andres, I set up a workload where XLogInsert* was at the top of my profiles: server with fsync and synchronous_commit off, and pgbench running a multiple-row insert into a single-text-column table with -M prepared -c 25 -t 25 -f script. How wide is the row, in terms of bytes? You should see bigger improvement with wider rows, as you get longer contiguous chunks of data to CRC that way. With very narrow rows, you might not see much difference because the chunks are so small. The primary goal, as I understood it, was to test very short records to test whether there's a regression due to slice-by-8. There doesn't seem to be any. Ah, OK. Mission accomplished, then. It's, IIRC, trivial to reproduce significant performance benefits in workloads with lots of FPWs or large records (like COPY), but those weren't what you and Tom were concerned about... Yeah. If that's the problem, it might be beneficial to memcpy() all the data to a temporary buffer, and calculate the CRC over the whole, instead of CRC'ing each XLogRecData chunk separately. XLogRecordAssemble() uses a scratch area, hdr_scratch, for building all the headers. You could check how much rmgr-specific data there is, and if there isn't much, just append the data to that scratch area too. I think that might very well make sense - but it's imo something better done separately from the smarter CRC algorithm. Agreed. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On Fri, Nov 21, 2014 at 12:11 PM, Abhijit Menon-Sen a...@2ndquadrant.com wrote: If anyone has other suggestions, I'm all ears. Do you have a WIP patch I could take a look at and tweak? Maybe there's something about the compilers code generation that could be improved. Regards, Ants Aasma -- Cybertec Schönig Schönig GmbH Gröhrmühlgasse 26 A-2700 Wiener Neustadt Web: http://www.postgresql-support.de -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
At 2014-11-20 09:52:01 +0530, a...@2ndquadrant.com wrote: To address (a), I am timing a standby restoring the same 11GB of WAL via restore_command with and without the CRC patch. I ran perf record -F 100 --call-graph=dwarf bin/postgres -D backup, where: (a) bin/postgres was compiled, as before, with CFLAGS=-O3 -msse4.2 and without --enable-debug. (b) backup is a basebackup of the original data directory before I ran pgbench; it has a recovery.conf with a restore_command to fetch the WAL generated during the pgbench run. I ran the test frice (as my daughter would say) with HEAD and the slice-by-8 patch, and counted the time between the first and last «restored log file NNN from archive» log messages. The number in parentheses shows the order in which I ran the tests. HEAD: 6m47s (1), 6m23s (2), 3m12s (6), 3m04s (7) 8CRC: 5m16s (3), 3m13s (4), 2m57s (5), 2m46s (8) In the unpatched server, the profile shows ValidXLogRecord at 50% in every case (54.81%, 59.41%, 58.82%, 59.05%). In the patched server, pg_comp_crc32c was at the top of the profile in three cases, with 10.29%, 12.01%, and 10.99%. In test (4), however, it was at 6.38%, and first place went to copy_user_enhanced_fast_string with 10.03% (which was in second place the other three times). I believe the wallclock runtime in these tests was influenced more by IO than CPU, but that the profile shows a worthwhile improvement anyway. I have the perf.data from each run, and I can rerun the tests if anyone wants to suggest a different strategy. Suggestions for how to address (b) are welcome. I'll think about how to do this, and work on the SSE4.2 patch meanwhile. -- Abhijit -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
At 2014-11-11 16:56:00 +0530, a...@2ndquadrant.com wrote:
I'm working on this (first speeding up the default calculation using
slice-by-N, then adding support for the SSE4.2 CRC instruction on
top).
I've done the first part in the attached patch, and I'm working on the
second (especially the bits to issue CPUID at startup and decide which
implementation to use).
As a benchmark, I ran pg_xlogdump --stats against 11GB of WAL data (674
segments) generated by running a total of 2M pgbench transactions on a
db initialised with scale factor 25. The tests were run on my i5-3230
CPU, and the code in each case was compiled with -O3 -msse4.2 (and
without --enable-debug). The profile was dominated by the CRC
calculation in ValidXLogRecord.
With HEAD's CRC code:
bin/pg_xlogdump --stats wal/00010001 29.81s user 3.56s system
77% cpu 43.274 total
bin/pg_xlogdump --stats wal/00010001 29.59s user 3.85s system
75% cpu 44.227 total
With slice-by-4 (a minor variant of the attached patch; the results are
included only for curiosity's sake, but I can post the code if needed):
bin/pg_xlogdump --stats wal/00010001 13.52s user 3.82s system
48% cpu 35.808 total
bin/pg_xlogdump --stats wal/00010001 13.34s user 3.96s system
48% cpu 35.834 total
With slice-by-8 (i.e. the attached patch):
bin/pg_xlogdump --stats wal/00010001 7.88s user 3.96s system
34% cpu 34.414 total
bin/pg_xlogdump --stats wal/00010001 7.85s user 4.10s system
34% cpu 35.001 total
(Note the progressive reduction in user time from ~29s to ~8s.)
Finally, just for comparison, here's what happens when we use the
hardware instruction via gcc's __builtin_ia32_crc32xx intrinsics
(i.e. the additional patch I'm working on):
bin/pg_xlogdump --stats wal/00010001 3.33s user 4.79s system
23% cpu 34.832 total
There are a number of potential micro-optimisations, I just wanted to
submit the obvious thing first and explore more possibilities later.
-- Abhijit
diff --git a/src/include/utils/pg_crc.h b/src/include/utils/pg_crc.h
index f871cba..55934e5 100644
--- a/src/include/utils/pg_crc.h
+++ b/src/include/utils/pg_crc.h
@@ -41,6 +41,8 @@
typedef uint32 pg_crc32;
+extern pg_crc32 pg_comp_crc32c(pg_crc32 crc, const void *data, size_t len);
+
/*
* CRC calculation using the CRC-32C (Castagnoli) polynomial.
*
@@ -51,7 +53,7 @@ typedef uint32 pg_crc32;
#define INIT_CRC32C(crc) ((crc) = 0x)
#define FIN_CRC32C(crc) ((crc) ^= 0x)
#define COMP_CRC32C(crc, data, len) \
- COMP_CRC32_NORMAL_TABLE(crc, data, len, pg_crc32c_table)
+ ((crc) = pg_comp_crc32c((crc), (char *) (data), (len)))
#define EQ_CRC32C(c1, c2) ((c1) == (c2))
/*
@@ -115,7 +117,7 @@ do { \
} while (0)
/* Constant tables for CRC-32C and CRC-32 polynomials */
-extern CRCDLLIMPORT const uint32 pg_crc32c_table[];
+extern CRCDLLIMPORT const uint32 pg_crc32c_table[8][256];
extern CRCDLLIMPORT const uint32 pg_crc32_table[];
#endif /* PG_CRC_H */
diff --git a/src/include/utils/pg_crc_tables.h b/src/include/utils/pg_crc_tables.h
index cb6b470..f814c91 100644
--- a/src/include/utils/pg_crc_tables.h
+++ b/src/include/utils/pg_crc_tables.h
@@ -28,71 +28,519 @@
* This table is based on the so-called Castagnoli polynomial (the same
* that is used e.g. in iSCSI).
*/
-const uint32 pg_crc32c_table[256] = {
- 0x, 0xF26B8303, 0xE13B70F7, 0x1350F3F4,
- 0xC79A971F, 0x35F1141C, 0x26A1E7E8, 0xD4CA64EB,
- 0x8AD958CF, 0x78B2DBCC, 0x6BE22838, 0x9989AB3B,
- 0x4D43CFD0, 0xBF284CD3, 0xAC78BF27, 0x5E133C24,
- 0x105EC76F, 0xE235446C, 0xF165B798, 0x030E349B,
- 0xD7C45070, 0x25AFD373, 0x36FF2087, 0xC494A384,
- 0x9A879FA0, 0x68EC1CA3, 0x7BBCEF57, 0x89D76C54,
- 0x5D1D08BF, 0xAF768BBC, 0xBC267848, 0x4E4DFB4B,
- 0x20BD8EDE, 0xD2D60DDD, 0xC186FE29, 0x33ED7D2A,
- 0xE72719C1, 0x154C9AC2, 0x061C6936, 0xF477EA35,
- 0xAA64D611, 0x580F5512, 0x4B5FA6E6, 0xB93425E5,
- 0x6DFE410E, 0x9F95C20D, 0x8CC531F9, 0x7EAEB2FA,
- 0x30E349B1, 0xC288CAB2, 0xD1D83946, 0x23B3BA45,
- 0xF779DEAE, 0x05125DAD, 0x1642AE59, 0xE4292D5A,
- 0xBA3A117E, 0x4851927D, 0x5B016189, 0xA96AE28A,
- 0x7DA08661, 0x8FCB0562, 0x9C9BF696, 0x6EF07595,
- 0x417B1DBC, 0xB3109EBF, 0xA0406D4B, 0x522BEE48,
- 0x86E18AA3, 0x748A09A0, 0x67DAFA54, 0x95B17957,
- 0xCBA24573, 0x39C9C670, 0x2A993584, 0xD8F2B687,
- 0x0C38D26C, 0xFE53516F, 0xED03A29B, 0x1F682198,
- 0x5125DAD3, 0xA34E59D0, 0xB01EAA24, 0x42752927,
- 0x96BF4DCC, 0x64D4CECF, 0x77843D3B, 0x85EFBE38,
- 0xDBFC821C, 0x2997011F, 0x3AC7F2EB, 0xC8AC71E8,
- 0x1C661503, 0xEE0D9600, 0xFD5D65F4, 0x0F36E6F7,
- 0x61C69362, 0x93AD1061, 0x80FDE395, 0x72966096,
- 0xA65C047D, 0x5437877E, 0x4767748A, 0xB50CF789,
- 0xEB1FCBAD, 0x197448AE, 0x0A24BB5A, 0xF84F3859,
- 0x2C855CB2, 0xDEEEDFB1, 0xCDBE2C45, 0x3FD5AF46,
- 0x7198540D, 0x83F3D70E, 0x90A324FA, 0x62C8A7F9,
- 0xB602C312, 0x44694011, 0x5739B3E5, 0xA55230E6,
- 0xFB410CC2, 0x092A8FC1, 0x1A7A7C35, 0xE811FF36,
-
Re: [HACKERS] What exactly is our CRC algorithm?
On 11/19/2014 05:58 PM, Abhijit Menon-Sen wrote: At 2014-11-11 16:56:00 +0530, a...@2ndquadrant.com wrote: I'm working on this (first speeding up the default calculation using slice-by-N, then adding support for the SSE4.2 CRC instruction on top). I've done the first part in the attached patch, and I'm working on the second (especially the bits to issue CPUID at startup and decide which implementation to use). As a benchmark, I ran pg_xlogdump --stats against 11GB of WAL data (674 segments) generated by running a total of 2M pgbench transactions on a db initialised with scale factor 25. That's an interesting choice of workload. That sure is heavy on the CRC calculation, but the speed of pg_xlogdump hardly matters in real life. With HEAD's CRC code: bin/pg_xlogdump --stats wal/00010001 29.81s user 3.56s system 77% cpu 43.274 total bin/pg_xlogdump --stats wal/00010001 29.59s user 3.85s system 75% cpu 44.227 total With slice-by-4 (a minor variant of the attached patch; the results are included only for curiosity's sake, but I can post the code if needed): bin/pg_xlogdump --stats wal/00010001 13.52s user 3.82s system 48% cpu 35.808 total bin/pg_xlogdump --stats wal/00010001 13.34s user 3.96s system 48% cpu 35.834 total With slice-by-8 (i.e. the attached patch): bin/pg_xlogdump --stats wal/00010001 7.88s user 3.96s system 34% cpu 34.414 total bin/pg_xlogdump --stats wal/00010001 7.85s user 4.10s system 34% cpu 35.001 total (Note the progressive reduction in user time from ~29s to ~8s.) Finally, just for comparison, here's what happens when we use the hardware instruction via gcc's __builtin_ia32_crc32xx intrinsics (i.e. the additional patch I'm working on): bin/pg_xlogdump --stats wal/00010001 3.33s user 4.79s system 23% cpu 34.832 total Impressive! It would be good to see separate benchmarks on WAL generation, and WAL replay. pg_xlogdump is probably close to WAL replay, but the WAL generation case is somewhat different, as WAL is generated in small pieces, and each piece is accumulated to the CRC separately. The slice-by-X algorithm might be less effective in that scenario. I have no doubt that it's still a lot faster than the byte-at-a-time operation, but would be nice to have numbers on it. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
Robert Haas robertmh...@gmail.com writes: On Wed, Nov 19, 2014 at 11:44 AM, Heikki Linnakangas hlinnakan...@vmware.com wrote: That's an interesting choice of workload. That sure is heavy on the CRC calculation, but the speed of pg_xlogdump hardly matters in real life. But isn't a workload that is heavy on CRC calculation exactly what we want here? That way we can see clearly how much benefit we're getting on that particular part of the computation. It'll still speed up other workloads, too, just not as much. Heikki's point is that it's an unrealistic choice of CRC chunk size. Maybe that doesn't matter very much, but it's unproven. 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
Re: [HACKERS] What exactly is our CRC algorithm?
On 11/19/2014 06:49 PM, Robert Haas wrote: On Wed, Nov 19, 2014 at 11:44 AM, Heikki Linnakangas hlinnakan...@vmware.com wrote: That's an interesting choice of workload. That sure is heavy on the CRC calculation, but the speed of pg_xlogdump hardly matters in real life. But isn't a workload that is heavy on CRC calculation exactly what we want here? That way we can see clearly how much benefit we're getting on that particular part of the computation. It'll still speed up other workloads, too, just not as much. Sure. But pg_xlogdump's way of using the CRC isn't necessarily representative of how the backend uses it. It's probably pretty close to WAL replay in the server, but even there the server might be hurt more by the extra cache used by the lookup tables. And a backend generating the WAL computes the CRC on smaller pieces than pg_xlogdump and WAL redo does. That said, the speedup is so large that I'm sure this is a big win in the server too, despite those factors. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 2014-11-19 19:12:22 +0200, Heikki Linnakangas wrote: On 11/19/2014 06:49 PM, Robert Haas wrote: On Wed, Nov 19, 2014 at 11:44 AM, Heikki Linnakangas hlinnakan...@vmware.com wrote: That's an interesting choice of workload. That sure is heavy on the CRC calculation, but the speed of pg_xlogdump hardly matters in real life. But isn't a workload that is heavy on CRC calculation exactly what we want here? That way we can see clearly how much benefit we're getting on that particular part of the computation. It'll still speed up other workloads, too, just not as much. Sure. But pg_xlogdump's way of using the CRC isn't necessarily representative of how the backend uses it. It's probably pretty close to WAL replay in the server, but even there the server might be hurt more by the extra cache used by the lookup tables. And a backend generating the WAL computes the CRC on smaller pieces than pg_xlogdump and WAL redo does. Right. Although it hugely depends on the checkpoint settings - if there's many FPWs it doesn't matter much. Obviously it won't be a fourfold performance improvement in the server, but given the profiles I've seen in the past I'm pretty sure it'll bee a benefit. That said, the speedup is so large that I'm sure this is a big win in the server too, despite those factors. Yep. I've done some fast and loose benchmarking in the past and it was quite noticeable. Made XLogInsert() nearly entirely drop from profiles. Greetings, Andres Freund -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
At 2014-11-19 19:12:22 +0200, hlinnakan...@vmware.com wrote: But pg_xlogdump's way of using the CRC isn't necessarily representative of how the backend uses it. It's probably pretty close to WAL replay in the server, but even there the server might be hurt more by the extra cache used by the lookup tables. Sure. As Robert said, my initial benchmark was designed to show the CRC improvements in isolation. I would be happy to conduct other tests and post the numbers. If I understand correctly, I need to demonstrate two things that are probably fine, but we don't have proof of: (a) that the improvements in pg_xlogdump performance translate to an improvement in the server when reading WAL. (b) that the slice-by-8 code doesn't hurt performance for writing WAL. To address (a), I am timing a standby restoring the same 11GB of WAL via restore_command with and without the CRC patch. My earlier tests showed that this time can vary quite a bit between runs even with no changes, but I expect to see an improvement anyway. Suggestions for how to address (b) are welcome. -- Abhijit -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
At 2014-11-04 14:40:36 +0100, and...@2ndquadrant.com wrote: On 2014-11-04 08:21:13 -0500, Robert Haas wrote: Are you going to get the slice-by-N stuff working next, to speed this up? I don't plan to do anything serious with it, but I've hacked up the crc code to use the hardware instruction. I'm working on this (first speeding up the default calculation using slice-by-N, then adding support for the SSE4.2 CRC instruction on top). -- Abhijit -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On Tue, Nov 11, 2014 at 6:26 AM, Abhijit Menon-Sen a...@2ndquadrant.com wrote: At 2014-11-04 14:40:36 +0100, and...@2ndquadrant.com wrote: On 2014-11-04 08:21:13 -0500, Robert Haas wrote: Are you going to get the slice-by-N stuff working next, to speed this up? I don't plan to do anything serious with it, but I've hacked up the crc code to use the hardware instruction. I'm working on this (first speeding up the default calculation using slice-by-N, then adding support for the SSE4.2 CRC instruction on top). Great! -- 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
Re: [HACKERS] What exactly is our CRC algorithm?
On 11/04/2014 03:21 PM, Robert Haas wrote: On Tue, Nov 4, 2014 at 4:47 AM, Heikki Linnakangas hlinnakan...@vmware.com wrote: I hear none, so committed with some small fixes. Are you going to get the slice-by-N stuff working next, to speed this up? I don't have any concrete plans, but yeah, that would be great. So definitely maybe. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On Tue, Nov 4, 2014 at 3:17 PM, Heikki Linnakangas hlinnakan...@vmware.com wrote: On 10/27/2014 06:02 PM, Heikki Linnakangas wrote: I came up with the attached patches. They do three things: 1. Get rid of the 64-bit CRC code. It's not used for anything, and haven't been for years, so it doesn't seem worth spending any effort to fix them. 2. Switch to CRC-32C (Castagnoli) for WAL and other places that don't need to remain compatible across major versions. Will this change allow database created before this commit to be started after this commit? With Regards, Amit Kapila. EnterpriseDB: http://www.enterprisedb.com
Re: [HACKERS] What exactly is our CRC algorithm?
On 11/07/2014 07:08 AM, Amit Kapila wrote: On Tue, Nov 4, 2014 at 3:17 PM, Heikki Linnakangas hlinnakan...@vmware.com wrote: On 10/27/2014 06:02 PM, Heikki Linnakangas wrote: I came up with the attached patches. They do three things: 1. Get rid of the 64-bit CRC code. It's not used for anything, and haven't been for years, so it doesn't seem worth spending any effort to fix them. 2. Switch to CRC-32C (Castagnoli) for WAL and other places that don't need to remain compatible across major versions. Will this change allow database created before this commit to be started after this commit? No. You could use pg_resetxlog to fix the WAL, but I think at least relmap files would still prevent you from starting up. You could use pg_upgrade. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 10/27/2014 06:02 PM, Heikki Linnakangas wrote: I came up with the attached patches. They do three things: 1. Get rid of the 64-bit CRC code. It's not used for anything, and haven't been for years, so it doesn't seem worth spending any effort to fix them. 2. Switch to CRC-32C (Castagnoli) for WAL and other places that don't need to remain compatible across major versions. 3. Use the same lookup table for hstore and ltree, as used for the legacy almost CRC-32 algorithm. The tables are identical, so might as well. Any objections? I hear none, so committed with some small fixes. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On Tue, Nov 4, 2014 at 4:47 AM, Heikki Linnakangas hlinnakan...@vmware.com wrote: I hear none, so committed with some small fixes. Are you going to get the slice-by-N stuff working next, to speed this up? -- 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
Re: [HACKERS] What exactly is our CRC algorithm?
On 2014-11-04 08:21:13 -0500, Robert Haas wrote: On Tue, Nov 4, 2014 at 4:47 AM, Heikki Linnakangas hlinnakan...@vmware.com wrote: I hear none, so committed with some small fixes. Are you going to get the slice-by-N stuff working next, to speed this up? I don't plan to do anything serious with it, but I've hacked up the crc code to use the hardware instruction. The results are quite good - crc vanishes entirely from the profile for most workloads. It's still visible for bulk copy, but that's pretty much it. Greetings, Andres Freund -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 10/09/2014 12:13 AM, Andres Freund wrote:
On 2014-10-08 22:13:46 +0300, Heikki Linnakangas wrote:
As far as I can tell, PostgreSQL's so-called CRC algorithm doesn't
correspond to any bit-by-bit CRC variant and polynomial. My math skills are
not strong enough to determine what the consequences of that are. It might
still be a decent checksum. Or not. I couldn't tell if the good error
detection properties of the normal CRC-32 polynomial apply to our algorithm
or not.
Additional interesting datapoints are that hstore and ltree contain the
same tables - but properly use the reflected computation.
Thoughts?
It clearly seems like a bad idea to continue with this - I don't think
anybody here knows which guarantees this gives us.
The question is how can we move away from this. There's unfortunately
two places that embed PGC32 that are likely to prove problematic when
fixing the algorithm: pg_trgm and tsgist both seem to include crc's in
their logic in a persistent way. I think we should provide
INIT/COMP/FIN_PG32 using the current algorithm for these.
Agreed, it's not worth breaking pg_upgrade for this.
If we're switching to a saner computation, we should imo also switch to
a better polynom - CRC-32C has better error detection capabilities than
CRC32 and is available in hardware. As we're paying the price pf
breaking compat anyway...
Agreed.
Arguably we could also say that given that there's been little evident
problems with the borked computation we could also switch to a much
faster hash instead of continuing to use crc...
I don't feel like taking the leap. Once we switch to slice-by-4/8 and/or
use a hardware instruction when available, CRC is fast enough.
I came up with the attached patches. They do three things:
1. Get rid of the 64-bit CRC code. It's not used for anything, and
haven't been for years, so it doesn't seem worth spending any effort to
fix them.
2. Switch to CRC-32C (Castagnoli) for WAL and other places that don't
need to remain compatible across major versions.
3. Use the same lookup table for hstore and ltree, as used for the
legacy almost CRC-32 algorithm. The tables are identical, so might as
well.
Any objections?
- Heikki
From 4fe6472976f2efc22035e802067a70d3cca61d79 Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas heikki.linnakan...@iki.fi
Date: Mon, 27 Oct 2014 12:01:19 +0200
Subject: [PATCH 1/2] Remove support for 64-bit CRC.
It hasn't been used for anything in backend code for a long time.
---
src/include/utils/pg_crc.h| 96 -
src/include/utils/pg_crc_tables.h | 416 --
2 files changed, 512 deletions(-)
diff --git a/src/include/utils/pg_crc.h b/src/include/utils/pg_crc.h
index 375c405..f43f4aa 100644
--- a/src/include/utils/pg_crc.h
+++ b/src/include/utils/pg_crc.h
@@ -10,9 +10,6 @@
* We use a normal (not reflected, in Williams' terms) CRC, using initial
* all-ones register contents and a final bit inversion.
*
- * The 64-bit variant is not used as of PostgreSQL 8.1, but we retain the
- * code for possible future use.
- *
*
* Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
@@ -56,97 +53,4 @@ do { \
/* Constant table for CRC calculation */
extern CRCDLLIMPORT const uint32 pg_crc32_table[];
-
-#ifdef PROVIDE_64BIT_CRC
-
-/*
- * If we use a 64-bit integer type, then a 64-bit CRC looks just like the
- * usual sort of implementation. However, we can also fake it with two
- * 32-bit registers. Experience has shown that the two-32-bit-registers code
- * is as fast as, or even much faster than, the 64-bit code on all but true
- * 64-bit machines. We use SIZEOF_VOID_P to check the native word width.
- */
-
-#if SIZEOF_VOID_P 8
-
-/*
- * crc0 represents the LSBs of the 64-bit value, crc1 the MSBs. Note that
- * with crc0 placed first, the output of 32-bit and 64-bit implementations
- * will be bit-compatible only on little-endian architectures. If it were
- * important to make the two possible implementations bit-compatible on
- * all machines, we could do a configure test to decide how to order the
- * two fields, but it seems not worth the trouble.
- */
-typedef struct pg_crc64
-{
- uint32 crc0;
- uint32 crc1;
-} pg_crc64;
-
-/* Initialize a CRC accumulator */
-#define INIT_CRC64(crc) ((crc).crc0 = 0x, (crc).crc1 = 0x)
-
-/* Finish a CRC calculation */
-#define FIN_CRC64(crc) ((crc).crc0 ^= 0x, (crc).crc1 ^= 0x)
-
-/* Accumulate some (more) bytes into a CRC */
-#define COMP_CRC64(crc, data, len) \
-do { \
- uint32 __crc0 = (crc).crc0; \
- uint32 __crc1 = (crc).crc1; \
- unsigned char *__data = (unsigned char *) (data); \
- uint32 __len = (len); \
-\
- while (__len-- 0) \
- { \
- int __tab_index = ((int) (__crc1 24) ^ *__data++) 0xFF; \
- __crc1 = pg_crc64_table1[__tab_index] ^ ((__crc1 8) | (__crc0 24)); \
- __crc0 =
Re: [HACKERS] What exactly is our CRC algorithm?
On 10/09/2014 01:23 AM, Gavin Flower wrote: On 09/10/14 10:13, Andres Freund wrote: If we're switching to a saner computation, we should imo also switch to a better polynom - CRC-32C has better error detection capabilities than CRC32 and is available in hardware. As we're paying the price pf breaking compat anyway... Arguably we could also say that given that there's been little evident problems with the borked computation we could also switch to a much faster hash instead of continuing to use crc... Could a 64 bit variant of some kind be useful as an option - in addition to a correct 32 bit? More bits allows you to detect more errors. That's the only advantage. I've never heard that being a problem, so no, I don't think that's a good idea. As most people have 64 bit processors and storage is less constrained now-a-days, as well as we tend to store much larger chunks of data. That's irrelevant to the CRC in the WAL. Each WAL record is CRC'd separately, and they tend to be very small (less than 8k typically) regardless of how large chunks of data you store in the database. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 2014-10-08 22:13:46 +0300, Heikki Linnakangas wrote: Hmm. So the simple, non-table driven, calculation gives the same result as using the lookup table using the reflected lookup code. That's expected; the lookup method is supposed to be the same, just faster. However, using the normal lookup code, but with a reflected lookup table, produces the same result as Postgres' algorithm. Indeed, that's what we do in PostgreSQL. But AFAICS, that's an incorrect combination. You're supposed to the non-reflected lookup table with the non-reflected lookup code; you can't mix and match. As far as I can tell, PostgreSQL's so-called CRC algorithm doesn't correspond to any bit-by-bit CRC variant and polynomial. My math skills are not strong enough to determine what the consequences of that are. It might still be a decent checksum. Or not. I couldn't tell if the good error detection properties of the normal CRC-32 polynomial apply to our algorithm or not. Additional interesting datapoints are that hstore and ltree contain the same tables - but properly use the reflected computation. Thoughts? It clearly seems like a bad idea to continue with this - I don't think anybody here knows which guarantees this gives us. The question is how can we move away from this. There's unfortunately two places that embed PGC32 that are likely to prove problematic when fixing the algorithm: pg_trgm and tsgist both seem to include crc's in their logic in a persistent way. I think we should provide INIT/COMP/FIN_PG32 using the current algorithm for these. If we're switching to a saner computation, we should imo also switch to a better polynom - CRC-32C has better error detection capabilities than CRC32 and is available in hardware. As we're paying the price pf breaking compat anyway... Arguably we could also say that given that there's been little evident problems with the borked computation we could also switch to a much faster hash instead of continuing to use crc... Greetings, Andres Freund -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] What exactly is our CRC algorithm?
On 09/10/14 10:13, Andres Freund wrote: On 2014-10-08 22:13:46 +0300, Heikki Linnakangas wrote: Hmm. So the simple, non-table driven, calculation gives the same result as using the lookup table using the reflected lookup code. That's expected; the lookup method is supposed to be the same, just faster. However, using the normal lookup code, but with a reflected lookup table, produces the same result as Postgres' algorithm. Indeed, that's what we do in PostgreSQL. But AFAICS, that's an incorrect combination. You're supposed to the non-reflected lookup table with the non-reflected lookup code; you can't mix and match. As far as I can tell, PostgreSQL's so-called CRC algorithm doesn't correspond to any bit-by-bit CRC variant and polynomial. My math skills are not strong enough to determine what the consequences of that are. It might still be a decent checksum. Or not. I couldn't tell if the good error detection properties of the normal CRC-32 polynomial apply to our algorithm or not. Additional interesting datapoints are that hstore and ltree contain the same tables - but properly use the reflected computation. Thoughts? It clearly seems like a bad idea to continue with this - I don't think anybody here knows which guarantees this gives us. The question is how can we move away from this. There's unfortunately two places that embed PGC32 that are likely to prove problematic when fixing the algorithm: pg_trgm and tsgist both seem to include crc's in their logic in a persistent way. I think we should provide INIT/COMP/FIN_PG32 using the current algorithm for these. If we're switching to a saner computation, we should imo also switch to a better polynom - CRC-32C has better error detection capabilities than CRC32 and is available in hardware. As we're paying the price pf breaking compat anyway... Arguably we could also say that given that there's been little evident problems with the borked computation we could also switch to a much faster hash instead of continuing to use crc... Greetings, Andres Freund Could a 64 bit variant of some kind be useful as an option - in addition to a correct 32 bit? As most people have 64 bit processors and storage is less constrained now-a-days, as well as we tend to store much larger chunks of data. Cheers, Gavin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
