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};