On Wed, Aug 24, 2022 at 11:56 PM Nathan Bossart
<nathandboss...@gmail.com> wrote:
>
> On Wed, Aug 24, 2022 at 11:59:25AM +0700, John Naylor wrote:
> > It seems "scalar" would be a bad choice since it already means
> > (confusingly) operating on the least significant element of a vector.
> > I'm thinking of *_has and *_has_le, matching the already existing in
> > the earlier patch *_has_zero.
>
> That seems reasonable to me.
Okay, done that way, also in v9:
- a convenience macro in the test suite which is handy now and can be
used for 32-bit element tests if we like
- more tests
- pgindent and some additional comment smithing
- split out the json piece for a later commit
- For the following comment, pgindent will put spaced operands on a
separate line which is not great for readability. and our other
reference to the Stanford bithacks page keeps the in-page link, and I
see no reason to exclude it -- if it goes missing, the whole page will
still load. So I put back those two details.
+ * To find bytes <= c, we can use bitwise operations to find
bytes < c+1,
+ * but it only works if c+1 <= 128 and if the highest bit in v
is not set.
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord
I think I'll go ahead and commit 0001 in a couple days pending further comments.
--
John Naylor
EDB: http://www.enterprisedb.com
From 606c14de59a68ed88bff75f7250c37ad082fbd9f Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Thu, 25 Aug 2022 13:32:28 +0700
Subject: [PATCH v9 2/2] Speed up json_lex_string via vector operations
TODO: tests
---
src/common/jsonapi.c | 11 +++++++++--
1 file changed, 9 insertions(+), 2 deletions(-)
diff --git a/src/common/jsonapi.c b/src/common/jsonapi.c
index fefd1d24d9..87e1d0b192 100644
--- a/src/common/jsonapi.c
+++ b/src/common/jsonapi.c
@@ -19,6 +19,7 @@
#include "common/jsonapi.h"
#include "mb/pg_wchar.h"
+#include "port/pg_lfind.h"
#ifndef FRONTEND
#include "miscadmin.h"
@@ -844,7 +845,7 @@ json_lex_string(JsonLexContext *lex)
}
else
{
- char *p;
+ char *p = s;
if (hi_surrogate != -1)
return JSON_UNICODE_LOW_SURROGATE;
@@ -853,7 +854,13 @@ json_lex_string(JsonLexContext *lex)
* Skip to the first byte that requires special handling, so we
* can batch calls to appendBinaryStringInfo.
*/
- for (p = s; p < end; p++)
+ while (p < end - sizeof(Vector8) &&
+ !pg_lfind8('\\', (uint8 *) p, sizeof(Vector8)) &&
+ !pg_lfind8('"', (uint8 *) p, sizeof(Vector8)) &&
+ !pg_lfind8_le(0x1F, (uint8 *) p, sizeof(Vector8)))
+ p += sizeof(Vector8);
+
+ for (; p < end; p++)
{
if (*p == '\\' || *p == '"')
break;
--
2.36.1
From fe7d8f2471e2e0b37ccdc1a0a2d7fc5bb93af7d9 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathandboss...@gmail.com>
Date: Sat, 20 Aug 2022 21:14:01 -0700
Subject: [PATCH v9 1/2] Add optimized functions for linear search within byte
arrays
In similar vein to b6ef167564, add pg_lfind8() and pg_lfind8_le()
to search for bytes equal or less-than-or-equal to a given byte,
respectively. To abstract away platform details, add helper functions
and typedefs to simd.h.
John Naylor and Nathan Bossart, per suggestion from Andres Freund
Discussion: https://www.postgresql.org/message-id/CAFBsxsGzaaGLF%3DNuq61iRXTyspbO9rOjhSqFN%3DV6ozzmta5mXg%40mail.gmail.com
---
src/include/port/pg_lfind.h | 68 +++++++-
src/include/port/simd.h | 154 ++++++++++++++++++
.../test_lfind/expected/test_lfind.out | 18 +-
.../modules/test_lfind/sql/test_lfind.sql | 4 +-
.../modules/test_lfind/test_lfind--1.0.sql | 10 +-
src/test/modules/test_lfind/test_lfind.c | 100 +++++++++++-
6 files changed, 345 insertions(+), 9 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index fb125977b2..a4e13dffec 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -1,7 +1,8 @@
/*-------------------------------------------------------------------------
*
* pg_lfind.h
- * Optimized linear search routines.
+ * Optimized linear search routines using SIMD intrinsics where
+ * available.
*
* Copyright (c) 2022, PostgreSQL Global Development Group
*
@@ -15,6 +16,70 @@
#include "port/simd.h"
+/*
+ * pg_lfind8
+ *
+ * Return true if there is an element in 'base' that equals 'key', otherwise
+ * return false.
+ */
+static inline bool
+pg_lfind8(uint8 key, uint8 *base, uint32 nelem)
+{
+ uint32 i;
+
+ /* round down to multiple of vector length */
+ uint32 tail_idx = nelem & ~(sizeof(Vector8) - 1);
+ Vector8 chunk;
+
+ for (i = 0; i < tail_idx; i += sizeof(Vector8))
+ {
+ vector8_load(&chunk, &base[i]);
+ if (vector8_has(chunk, key))
+ return true;
+ }
+
+ /* Process the remaining elements one at a time. */
+ for (; i < nelem; i++)
+ {
+ if (key == base[i])
+ return true;
+ }
+
+ return false;
+}
+
+/*
+ * pg_lfind8_le
+ *
+ * Return true if there is an element in 'base' that is less than or equal to
+ * 'key', otherwise return false.
+ */
+static inline bool
+pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
+{
+ uint32 i;
+
+ /* round down to multiple of vector length */
+ uint32 tail_idx = nelem & ~(sizeof(Vector8) - 1);
+ Vector8 chunk;
+
+ for (i = 0; i < tail_idx; i += sizeof(Vector8))
+ {
+ vector8_load(&chunk, &base[i]);
+ if (vector8_has_le(chunk, key))
+ return true;
+ }
+
+ /* Process the remaining elements one at a time. */
+ for (; i < nelem; i++)
+ {
+ if (base[i] <= key)
+ return true;
+ }
+
+ return false;
+}
+
/*
* pg_lfind32
*
@@ -26,7 +91,6 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
{
uint32 i = 0;
- /* Use SIMD intrinsics where available. */
#ifdef USE_SSE2
/*
diff --git a/src/include/port/simd.h b/src/include/port/simd.h
index a571e79f57..56df989094 100644
--- a/src/include/port/simd.h
+++ b/src/include/port/simd.h
@@ -13,6 +13,12 @@
#ifndef SIMD_H
#define SIMD_H
+/*
+ * Note: VectorN in this file refers to a register where the element operands
+ * are N bits wide. The vector width is platform-specific, so users that care
+ * about that will need to inspect "sizeof(VectorN)".
+ */
+
/*
* SSE2 instructions are part of the spec for the 64-bit x86 ISA. We assume
* that compilers targeting this architecture understand SSE2 intrinsics.
@@ -25,6 +31,154 @@
#if (defined(__x86_64__) || defined(_M_AMD64))
#include <emmintrin.h>
#define USE_SSE2
+typedef __m128i Vector8;
+
+#else
+/*
+ * If no SIMD instructions are available, we can in some cases emulate vector
+ * operations using bitwise operations on unsigned integers.
+ */
+typedef uint64 Vector8;
#endif
+
+static inline void vector8_load(Vector8 *v, const uint8 *s);
+static inline Vector8 vector8_broadcast(const uint8 c);
+static inline bool vector8_has_zero(const Vector8 v);
+static inline bool vector8_has(const Vector8 v, const uint8 c);
+static inline bool vector8_has_le(const Vector8 v, const uint8 c);
+
+
+/*
+ * Functions for loading a chunk of memory into a vector.
+ */
+
+static inline void
+vector8_load(Vector8 *v, const uint8 *s)
+{
+#ifdef USE_SSE2
+ *v = _mm_loadu_si128((const __m128i *) s);
+#else
+ memcpy(v, s, sizeof(Vector8));
+#endif
+}
+
+
+/*
+ * Functions for creating a vector with all elements set to the same value.
+ */
+
+static inline Vector8
+vector8_broadcast(const uint8 c)
+{
+#ifdef USE_SSE2
+ return _mm_set1_epi8(c);
+#else
+ return ~UINT64CONST(0) / 0xFF * c;
+#endif
+}
+
+
+/*
+ * Functions for comparing vector elements to a given value.
+ */
+
+static inline bool
+vector8_has_zero(const Vector8 v)
+{
+#ifdef USE_SSE2
+ return _mm_movemask_epi8(_mm_cmpeq_epi8(v, _mm_setzero_si128()));
+#else
+ return vector8_has_le(v, 0);
+#endif
+}
+
+static inline bool
+vector8_has(const Vector8 v, const uint8 c)
+{
+ bool result;
+
+ /* pre-compute the result for assert checking */
+#ifdef USE_ASSERT_CHECKING
+ bool assert_result = false;
+
+ for (int i = 0; i < sizeof(Vector8); i++)
+ {
+ if (((const uint8 *) &v)[i] == c)
+ {
+ assert_result = true;
+ break;
+ }
+ }
+#endif /* USE_ASSERT_CHECKING */
+
+#ifdef USE_SSE2
+ result = _mm_movemask_epi8(_mm_cmpeq_epi8(v, vector8_broadcast(c)));
+#else
+ /* any bytes in v equal to c will evaluate to zero via XOR */
+ result = vector8_has_zero(v ^ vector8_broadcast(c));
+#endif
+
+ Assert(assert_result == result);
+ return result;
+}
+
+static inline bool
+vector8_has_le(const Vector8 v, const uint8 c)
+{
+ bool result = false;
+#ifdef USE_SSE2
+ __m128i sub;
+#endif
+
+ /* pre-compute the result for assert checking */
+#ifdef USE_ASSERT_CHECKING
+ bool assert_result = false;
+
+ for (int i = 0; i < sizeof(Vector8); i++)
+ {
+ if (((const uint8 *) &v)[i] <= c)
+ {
+ assert_result = true;
+ break;
+ }
+ }
+#endif /* USE_ASSERT_CHECKING */
+
+#ifdef USE_SSE2
+
+ /*
+ * Use saturating subtraction to find bytes <= c, which will present as
+ * NUL bytes in 'sub'.
+ */
+ sub = _mm_subs_epu8(v, vector8_broadcast(c));
+ result = vector8_has_zero(sub);
+#else
+
+ /*
+ * To find bytes <= c, we can use bitwise operations to find bytes < c+1,
+ * but it only works if c+1 <= 128 and if the highest bit in v is not set.
+ * Adapted from
+ * https://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord
+ */
+ if ((int64) v >= 0 && c < 0x80)
+ result = (v - vector8_broadcast(c + 1)) & ~v & vector8_broadcast(0x80);
+ else
+ {
+ /* one byte at a time */
+ for (int i = 0; i < sizeof(Vector8); i++)
+ {
+ if (((const uint8 *) &v)[i] <= c)
+ {
+ result = true;
+ break;
+ }
+ }
+ }
+#endif
+
+ Assert(assert_result == result);
+ return result;
+}
+
#endif /* SIMD_H */
diff --git a/src/test/modules/test_lfind/expected/test_lfind.out b/src/test/modules/test_lfind/expected/test_lfind.out
index 222c8fd7ff..1d4b14e703 100644
--- a/src/test/modules/test_lfind/expected/test_lfind.out
+++ b/src/test/modules/test_lfind/expected/test_lfind.out
@@ -4,9 +4,21 @@ CREATE EXTENSION test_lfind;
-- the operations complete without crashing or hanging and that none of their
-- internal sanity tests fail.
--
-SELECT test_lfind();
- test_lfind
-------------
+SELECT test_lfind8();
+ test_lfind8
+-------------
+
+(1 row)
+
+SELECT test_lfind8_le();
+ test_lfind8_le
+----------------
+
+(1 row)
+
+SELECT test_lfind32();
+ test_lfind32
+--------------
(1 row)
diff --git a/src/test/modules/test_lfind/sql/test_lfind.sql b/src/test/modules/test_lfind/sql/test_lfind.sql
index 899f1dd49b..766c640831 100644
--- a/src/test/modules/test_lfind/sql/test_lfind.sql
+++ b/src/test/modules/test_lfind/sql/test_lfind.sql
@@ -5,4 +5,6 @@ CREATE EXTENSION test_lfind;
-- the operations complete without crashing or hanging and that none of their
-- internal sanity tests fail.
--
-SELECT test_lfind();
+SELECT test_lfind8();
+SELECT test_lfind8_le();
+SELECT test_lfind32();
diff --git a/src/test/modules/test_lfind/test_lfind--1.0.sql b/src/test/modules/test_lfind/test_lfind--1.0.sql
index d82ab0567e..81801926ae 100644
--- a/src/test/modules/test_lfind/test_lfind--1.0.sql
+++ b/src/test/modules/test_lfind/test_lfind--1.0.sql
@@ -3,6 +3,14 @@
-- complain if script is sourced in psql, rather than via CREATE EXTENSION
\echo Use "CREATE EXTENSION test_lfind" to load this file. \quit
-CREATE FUNCTION test_lfind()
+CREATE FUNCTION test_lfind32()
+ RETURNS pg_catalog.void
+ AS 'MODULE_PATHNAME' LANGUAGE C;
+
+CREATE FUNCTION test_lfind8()
+ RETURNS pg_catalog.void
+ AS 'MODULE_PATHNAME' LANGUAGE C;
+
+CREATE FUNCTION test_lfind8_le()
RETURNS pg_catalog.void
AS 'MODULE_PATHNAME' LANGUAGE C;
diff --git a/src/test/modules/test_lfind/test_lfind.c b/src/test/modules/test_lfind/test_lfind.c
index a000746fb8..e0c905aad3 100644
--- a/src/test/modules/test_lfind/test_lfind.c
+++ b/src/test/modules/test_lfind/test_lfind.c
@@ -16,12 +16,108 @@
#include "fmgr.h"
#include "port/pg_lfind.h"
+/*
+ * Convenience macros for testing both vector and scalar operations. The 2x
+ * factor is to make sure iteration works
+ */
+#define LEN_NO_TAIL(vectortype) (2 * sizeof(vectortype))
+#define LEN_WITH_TAIL(vectortype) (LEN_NO_TAIL(vectortype) + 3)
+
PG_MODULE_MAGIC;
-PG_FUNCTION_INFO_V1(test_lfind);
+/* workhorse for test_lfind8 */
+static void
+test_lfind8_internal(uint8 key)
+{
+ uint8 charbuf[LEN_WITH_TAIL(Vector8)];
+ const int len_no_tail = LEN_NO_TAIL(Vector8);
+ const int len_with_tail = LEN_WITH_TAIL(Vector8);
+
+ memset(charbuf, 0xFF, len_with_tail);
+ /* search tail to test one-byte-at-a-time path */
+ charbuf[len_with_tail - 1] = key;
+ if (key > 0x00 && pg_lfind8(key - 1, charbuf, len_with_tail))
+ elog(ERROR, "pg_lfind8() found nonexistent element <= '0x%x'", key - 1);
+ if (key < 0xFF && !pg_lfind8(key, charbuf, len_with_tail))
+ elog(ERROR, "pg_lfind8() did not find existing element <= '0x%x'", key);
+ if (key < 0xFE && pg_lfind8(key + 1, charbuf, len_with_tail))
+ elog(ERROR, "pg_lfind8() found nonexistent element <= '0x%x'", key + 1);
+
+ memset(charbuf, 0xFF, len_with_tail);
+ /* search with vector operations */
+ charbuf[len_no_tail - 1] = key;
+ if (key > 0x00 && pg_lfind8(key - 1, charbuf, len_no_tail))
+ elog(ERROR, "pg_lfind8() found nonexistent element <= '0x%x'", key - 1);
+ if (key < 0xFF && !pg_lfind8(key, charbuf, len_no_tail))
+ elog(ERROR, "pg_lfind8() did not find existing element <= '0x%x'", key);
+ if (key < 0xFE && pg_lfind8(key + 1, charbuf, len_no_tail))
+ elog(ERROR, "pg_lfind8() found nonexistent element <= '0x%x'", key + 1);
+}
+
+PG_FUNCTION_INFO_V1(test_lfind8);
+Datum
+test_lfind8(PG_FUNCTION_ARGS)
+{
+ test_lfind8_internal(0);
+ test_lfind8_internal(1);
+ test_lfind8_internal(0x7F);
+ test_lfind8_internal(0x80);
+ test_lfind8_internal(0x81);
+ test_lfind8_internal(0xFD);
+ test_lfind8_internal(0xFE);
+ test_lfind8_internal(0xFF);
+
+ PG_RETURN_VOID();
+}
+
+/* workhorse for test_lfind8_le */
+static void
+test_lfind8_le_internal(uint8 key)
+{
+ uint8 charbuf[LEN_WITH_TAIL(Vector8)];
+ const int len_no_tail = LEN_NO_TAIL(Vector8);
+ const int len_with_tail = LEN_WITH_TAIL(Vector8);
+
+ memset(charbuf, 0xFF, len_with_tail);
+ /* search tail to test one-byte-at-a-time path */
+ charbuf[len_with_tail - 1] = key;
+ if (key > 0x00 && pg_lfind8_le(key - 1, charbuf, len_with_tail))
+ elog(ERROR, "pg_lfind8_le() found nonexistent element <= '0x%x'", key - 1);
+ if (key < 0xFF && !pg_lfind8_le(key, charbuf, len_with_tail))
+ elog(ERROR, "pg_lfind8_le() did not find existing element <= '0x%x'", key);
+ if (key < 0xFE && !pg_lfind8_le(key + 1, charbuf, len_with_tail))
+ elog(ERROR, "pg_lfind8_le() did not find existing element <= '0x%x'", key + 1);
+
+ memset(charbuf, 0xFF, len_with_tail);
+ /* search with vector operations */
+ charbuf[len_no_tail - 1] = key;
+ if (key > 0x00 && pg_lfind8_le(key - 1, charbuf, len_no_tail))
+ elog(ERROR, "pg_lfind8_le() found nonexistent element <= '0x%x'", key - 1);
+ if (key < 0xFF && !pg_lfind8_le(key, charbuf, len_no_tail))
+ elog(ERROR, "pg_lfind8_le() did not find existing element <= '0x%x'", key);
+ if (key < 0xFE && !pg_lfind8_le(key + 1, charbuf, len_no_tail))
+ elog(ERROR, "pg_lfind8_le() did not find existing element <= '0x%x'", key + 1);
+}
+
+PG_FUNCTION_INFO_V1(test_lfind8_le);
+Datum
+test_lfind8_le(PG_FUNCTION_ARGS)
+{
+ test_lfind8_le_internal(0);
+ test_lfind8_le_internal(1);
+ test_lfind8_le_internal(0x7F);
+ test_lfind8_le_internal(0x80);
+ test_lfind8_le_internal(0x81);
+ test_lfind8_le_internal(0xFD);
+ test_lfind8_le_internal(0xFE);
+ test_lfind8_le_internal(0xFF);
+
+ PG_RETURN_VOID();
+}
+PG_FUNCTION_INFO_V1(test_lfind32);
Datum
-test_lfind(PG_FUNCTION_ARGS)
+test_lfind32(PG_FUNCTION_ARGS)
{
#define TEST_ARRAY_SIZE 135
uint32 test_array[TEST_ARRAY_SIZE] = {0};
--
2.36.1
