From: Nathan Bossart <nathandbossart@gmail.com>
To: John Naylor <john.naylor@enterprisedb.com>
Cc: Andres Freund <andres@anarazel.de>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Jelte Fennema <Jelte.Fennema@microsoft.com>
Cc: pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
Cc: Merlin Moncure <mmoncure@gmail.com>
Cc: Andrew Dunstan <andrew.dunstan@2ndquadrant.com>
Cc: Stephen Frost <sfrost@snowman.net>
Subject: Re: [PATCH] Optimize json_lex_string by batching character copying
Date: Mon, 22 Aug 2022 20:32:36 -0700
Message-ID: <20220823033236.GA1204962@nathanxps13> (raw)
In-Reply-To: <20220822212229.GA1129243@nathanxps13>
References: <1119852.1657554806@sss.pgh.pa.us>
<20220711160728.tljbnowfgxefdbli@awork3.anarazel.de>
<CAFBsxsGzaaGLF=Nuq61iRXTyspbO9rOjhSqFN=V6ozzmta5mXg@mail.gmail.com>
<CAFBsxsESLUyJ5spfOSyPrOvKUEYYNqsBosue9SV1j8ecgNXSKA@mail.gmail.com>
<20220815212304.GA251709@nathanxps13>
<CAFBsxsF8asF=qa2toXOceBgAYoKtftkL7tmE-WmCWxW-CRkeQg@mail.gmail.com>
<20220819204215.GA397534@nathanxps13>
<20220821054733.GA780295@nathanxps13>
<CAFBsxsH93DNy=x5Jiu37qFRyq==kz0fJbGjx835ZFyj-DMSXuw@mail.gmail.com>
<20220822212229.GA1129243@nathanxps13>
On Mon, Aug 22, 2022 at 02:22:29PM -0700, Nathan Bossart wrote:
> On Mon, Aug 22, 2022 at 09:35:34AM +0700, John Naylor wrote:
>> Not at all! However, the 32-bit-element changes are irrelevant for
>> json, and make review more difficult. I would suggest keeping those in
>> the other thread starting with whatever refactoring is needed. I can
>> always rebase over that.
>
> Yeah, I'll remove those to keep this thread focused.
Here's a new version of the patch with the 32-bit changes and calls to
lfind() removed.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.comAttachments:v8-0001-json_lex_string-SIMD.patch (text/x-diff, 12.4K) download
From dd7b3c3b0567d77a7f171d9cb4b6a8d3ee30ceec Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathandbossart@gmail.com>
Date: Sat, 20 Aug 2022 21:14:01 -0700
Subject: [PATCH v8 1/1] json_lex_string() SIMD
---
src/common/jsonapi.c | 11 +-
src/include/port/pg_lfind.h | 65 +++++++-
src/include/port/simd.h | 143 ++++++++++++++++++
.../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 | 91 ++++++++++-
7 files changed, 332 insertions(+), 10 deletions(-)
diff --git a/src/common/jsonapi.c b/src/common/jsonapi.cindex 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;
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.hindex fb125977b2..86342d71d8 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,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(Vector8) - 1);+ Vector8 chunk;++ for (i = 0; i < tail_idx; i += sizeof(Vector8))+ {+ vector8_load(&chunk, &base[i]);+ if (vector8_eq(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_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
*
diff --git a/src/include/port/simd.h b/src/include/port/simd.hindex a571e79f57..23f6269169 100644--- a/src/include/port/simd.h+++ b/src/include/port/simd.h@@ -25,6 +25,149 @@
#if (defined(__x86_64__) || defined(_M_AMD64))
#include <emmintrin.h>
#define USE_SSE2
+typedef __m128i Vector8;++/*+ * If no SIMD instructions are available, we emulate specialized vector+ * operations using uint64.+ */+#else+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_eq(const Vector8 v, const uint8 c);+static inline bool vector8_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_le(v, 0);+#endif+}++static inline bool+vector8_eq(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_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+ * (from https://graphics.stanford.edu/~seander/bithacks.html).+ */+ 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.outindex 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.sqlindex 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.sqlindex 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.cindex a000746fb8..efe6b60bc5 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(Vector8))+#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(Vector8))+#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};
--
2.25.1
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: nathandbossart@gmail.com, john.naylor@enterprisedb.com, andres@anarazel.de, tgl@sss.pgh.pa.us, Jelte.Fennema@microsoft.com, mmoncure@gmail.com, andrew.dunstan@2ndquadrant.com, sfrost@snowman.net
Subject: Re: [PATCH] Optimize json_lex_string by batching character copying
In-Reply-To: <20220823033236.GA1204962@nathanxps13>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox