On Tue, Aug 16, 2022 at 4:23 AM Nathan Bossart <nathandboss...@gmail.com> wrote:
>
> On Mon, Aug 15, 2022 at 08:33:21PM +0700, John Naylor wrote:
> > +#ifdef USE_SSE2
> > + chunk = _mm_loadu_si128((const __m128i *) &base[i]);
> > +#else
> > + memcpy(&chunk, &base[i], sizeof(chunk));
> > +#endif /* USE_SSE2 */
>
> Perhaps there should be a macro or inline function for loading a vector so
> that these USE_SSE2 checks can be abstracted away, too.
This is done. Also:
- a complete overhaul of the pg_lfind8* tests
- using a typedef for the vector type
- some refactoring, name changes and other cleanups (a few of these
could also be applied to the 32-byte element path, but that is left
for future work)
TODO: json-specific tests of the new path
--
John Naylor
EDB: http://www.enterprisedb.com
diff --git a/src/common/jsonapi.c b/src/common/jsonapi.c
index fefd1d24d9..efcaedd682 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(Vector) &&
+ !pg_lfind8('\\', (uint8 *) p, sizeof(Vector)) &&
+ !pg_lfind8('"', (uint8 *) p, sizeof(Vector)) &&
+ !pg_lfind8_le(0x1F, (uint8 *) p, sizeof(Vector)))
+ p += sizeof(Vector);
+
+ for (; p < end; p++)
{
if (*p == '\\' || *p == '"')
break;
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index fb125977b2..bb4033c7fc 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -1,7 +1,7 @@
/*-------------------------------------------------------------------------
*
* 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 +15,68 @@
#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(Vector) - 1);
+ Vector chunk;
+
+ for (i = 0; i < tail_idx; i += sizeof(Vector))
+ {
+ vector_load(&chunk, &base[i]);
+ if (vector_eq_byte(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(Vector) - 1);
+ Vector chunk;
+
+ for (i = 0; i < tail_idx; i += sizeof(Vector))
+ {
+ vector_load(&chunk, &base[i]);
+ if (vector_le_byte(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 +88,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..56da8e27cd 100644
--- a/src/include/port/simd.h
+++ b/src/include/port/simd.h
@@ -25,6 +25,141 @@
#if (defined(__x86_64__) || defined(_M_AMD64))
#include <emmintrin.h>
#define USE_SSE2
+typedef __m128i Vector;
+
+#else
+typedef uint64 Vector;
+#endif /* (defined(__x86_64__) || defined(_M_AMD64)) */
+
+
+static inline void vector_load(Vector * v, const uint8 *s);
+static inline Vector vector_broadcast(const uint8 c);
+static inline bool vector_has_zero(const Vector v);
+static inline bool vector_le_byte(const Vector v, const uint8 c);
+static inline bool vector_eq_byte(const Vector v, const uint8 c);
+
+
+/* load a chunk of memory into a register */
+static inline void
+vector_load(Vector * v, const uint8 *s)
+{
+#ifdef USE_SSE2
+ *v = _mm_loadu_si128((const __m128i *) s);
+#else
+ memcpy(v, s, sizeof(Vector));
+#endif
+}
+
+/* return a vector with all bytes set to c */
+static inline Vector
+vector_broadcast(const uint8 c)
+{
+#ifdef USE_SSE2
+ return _mm_set1_epi8(c);
+#else
+ return ~UINT64CONST(0) / 0xFF * c;
#endif
+}
+
+/* return true if any bytes in the vector are zero */
+static inline bool
+vector_has_zero(const Vector v)
+{
+#ifdef USE_SSE2
+ return _mm_movemask_epi8(_mm_cmpeq_epi8(v, _mm_setzero_si128()));
+#else
+ return vector_le_byte(v, 0);
+#endif
+}
+
+static inline bool
+vector_eq_byte(const Vector v, const uint8 c)
+{
+ bool result;
+
+ /* pre-compute the result for assert checking */
+#ifdef USE_ASSERT_CHECKING
+ bool assert_result = false;
+ const uint8* s = (const uint8*) &v;
+
+ for (int i = 0; i < sizeof(Vector); i++)
+ {
+ if (s[i] == c)
+ {
+ assert_result = true;
+ break;
+ }
+ }
+#endif /* USE_ASSERT_CHECKING */
+
+#ifdef USE_SSE2
+ result = _mm_movemask_epi8(_mm_cmpeq_epi8(v, vector_broadcast(c)));
+#else
+ /* any bytes in v equal to c will evaluate to zero via XOR */
+ result = vector_has_zero(v ^ vector_broadcast(c));
+#endif /* USE_SSE2 */
+
+#ifdef USE_ASSERT_CHECKING
+ Assert(assert_result == result);
+#endif /* USE_ASSERT_CHECKING */
+
+ return result;
+}
+
+static inline bool
+vector_le_byte(const Vector v, const uint8 c)
+{
+ bool result = false;
+#ifdef USE_SSE2
+ __m128i sub;
+#endif
+
+#if !defined(USE_SSE2) || defined(USE_ASSERT_CHECKING)
+ const uint8* s = (const uint8*) &v;
+#endif
+
+ /* pre-compute the result for assert checking */
+#ifdef USE_ASSERT_CHECKING
+ bool assert_result = false;
+
+ for (int i = 0; i < sizeof(Vector); i++)
+ {
+ if (s[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, vector_broadcast(c));
+ result = vector_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 */
+ /* from https://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord */
+ if ((int64) v >= 0 && c < 0x80)
+ result = (v - vector_broadcast(c + 1)) & ~v & vector_broadcast(0x80);
+ else
+ {
+ /* one byte at a time */
+ for (int i = 0; i < sizeof(Vector); i++)
+ {
+ if (s[i] <= c)
+ {
+ result = true;
+ break;
+ }
+ }
+ }
+#endif
+
+#ifdef USE_ASSERT_CHECKING
+ Assert(assert_result == result);
+#endif /* USE_ASSERT_CHECKING */
+
+ 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..18ca9d0018 100644
--- a/src/test/modules/test_lfind/test_lfind.c
+++ b/src/test/modules/test_lfind/test_lfind.c
@@ -18,10 +18,97 @@
PG_MODULE_MAGIC;
-PG_FUNCTION_INFO_V1(test_lfind);
+/* workhorse for test_lfind8 */
+static void
+test_lfind8_internal(uint8 key)
+{
+ /* The byte searched for shouldn't be in the first vector-sized chunk, to make sure iteration works */
+#define LEN_NO_TAIL (2 * sizeof(Vector))
+#define LEN_WITH_TAIL (LEN_NO_TAIL + 3)
+
+ uint8 charbuf[LEN_WITH_TAIL];
+
+ 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(0xFD);
+
+ PG_RETURN_VOID();
+}
+
+/* workhorse for test_lfind8_le */
+static void
+test_lfind8_le_internal(uint8 key)
+{
+ /* The byte searched for shouldn't be in the first vector-sized chunk, to make sure iteration works */
+#define LEN_NO_TAIL (2 * sizeof(Vector))
+#define LEN_WITH_TAIL (LEN_NO_TAIL + 3)
+
+ uint8 charbuf[LEN_WITH_TAIL];
+
+ 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(0xFD);
+
+ 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};
