Speed up JSON escape processing with SIMD plus other optimisations

Started by David Rowleyover 1 year ago16 messages
#1David Rowley
dgrowleyml@gmail.com
2 attachment(s)

Currently the escape_json() function takes a cstring and char-by-char
checks each character in the string up to the NUL and adds the escape
sequence if the character requires it.

Because this function requires a NUL terminated string, we're having
to do a little more work in some places. For example, in
jsonb_put_escaped_value() we call pnstrdup() on the non-NUL-terminated
string to make a NUL-terminated string to pass to escape_json().

To make this faster, we can just have a version of escape_json which
takes a 'len' and stops after doing that many chars rather than
stopping when the NUL char is reached. Now there's no need to
pnstrdup() which saves some palloc()/memcpy() work.

There are also a few places where we do escape_json() with a "text"
typed Datum where we go and convert the text to a NUL-terminated
cstring so we can pass that along to ecape_json(). That's wasteful as
we could just pass the payload of the text Datum directly, and only
allocate memory if the text Datum needs to be de-toasted. That saves
a useless palloc/memcpy/pfree cycle.

Now, to make this more interesting, since we have a version of
escape_json which takes a 'len', we could start looking at more than 1
character at a time. If you look closely add escape_json() all the
special chars apart from " and \ are below the space character.
pg_lfind8() and pg_lfind8_le() allow processing of 16 bytes at a time,
so we only need to search the 16 bytes 3 times to ensure that no
special chars exist within. When that test fails, just go into
byte-at-a-time processing first copying over the portion of the string
that passed the vector test up until that point.

I've attached 2 patches:

0001 does everything I've described aside from SIMD.
0002 does SIMD

I've not personally done too much work in the area of JSON, so I don't
have any canned workloads to throw at this. I did try the following:

create table j1 (very_long_column_name_to_test_json_escape text);
insert into j1 select repeat('x', x) from generate_series(0,1024)x;
vacuum freeze j1;

bench.sql:
select row_to_json(j1)::jsonb from j1;

Master:
$ pgbench -n -f bench.sql -T 10 -M prepared postgres | grep tps
tps = 362.494309 (without initial connection time)
tps = 363.182458 (without initial connection time)
tps = 362.679654 (without initial connection time)

Master + 0001 + 0002
$ pgbench -n -f bench.sql -T 10 -M prepared postgres | grep tps
tps = 426.456885 (without initial connection time)
tps = 430.573046 (without initial connection time)
tps = 431.142917 (without initial connection time)

About 18% faster.

It would be much faster if we could also get rid of the
escape_json_cstring() call in the switch default case of
datum_to_json_internal(). row_to_json() would be heaps faster with
that done. I considered adding a special case for the "text" type
there, but in the end felt that we should just fix that with some
hypothetical other patch that changes how output functions work.
Others may feel it's worthwhile. I certainly could be convinced of it.

I did add a new regression test. I'm not sure I'd want to keep that,
but felt it's worth leaving in there for now.

Other things I considered were if doing 16 bytes at a time is too much
as it puts quite a bit of work into byte-at-a-time processing if just
1 special char exists in a 16-byte chunk. I considered doing SWAR [1]https://en.wikipedia.org/wiki/SWAR
processing to do the job of vector8_has_le() and vector8_has() byte
maybe with just uint32s. It might be worth doing that. However, I've
not done it yet as it raises the bar for this patch quite a bit. SWAR
vector processing is pretty much write-only code. Imagine trying to
write comments for the code in [2]https://dotat.at/@/2022-06-27-tolower-swar.html so that the average person could
understand what's going on!?

I'd be happy to hear from anyone that can throw these patches at a
real-world JSON workload to see if it runs more quickly.

Parking for July CF.

David

[1]: https://en.wikipedia.org/wiki/SWAR
[2]: https://dotat.at/@/2022-06-27-tolower-swar.html

Attachments:

v1-0001-Add-len-parameter-to-escape_json.patchapplication/octet-stream; name=v1-0001-Add-len-parameter-to-escape_json.patchDownload
From 695ab50057adb87caa95d8ca3ff77849f33ba399 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Tue, 21 May 2024 17:14:06 +1200
Subject: [PATCH v1 1/2] Add 'len' parameter to escape_json()

---
 contrib/hstore/hstore_io.c           |  41 +++-----
 src/backend/backup/backup_manifest.c |   2 +-
 src/backend/commands/explain.c       |  30 ++++--
 src/backend/parser/parse_jsontable.c |   2 +-
 src/backend/utils/adt/json.c         | 150 +++++++++++++++++----------
 src/backend/utils/adt/jsonb.c        |   2 +-
 src/backend/utils/adt/jsonfuncs.c    |  15 +--
 src/backend/utils/adt/jsonpath.c     |  15 ++-
 src/backend/utils/error/jsonlog.c    |   8 +-
 src/include/utils/json.h             |   4 +-
 10 files changed, 162 insertions(+), 107 deletions(-)

diff --git a/contrib/hstore/hstore_io.c b/contrib/hstore/hstore_io.c
index 999ddad76d..374b8d05ef 100644
--- a/contrib/hstore/hstore_io.c
+++ b/contrib/hstore/hstore_io.c
@@ -1343,23 +1343,20 @@ hstore_to_json_loose(PG_FUNCTION_ARGS)
 	int			count = HS_COUNT(in);
 	char	   *base = STRPTR(in);
 	HEntry	   *entries = ARRPTR(in);
-	StringInfoData tmp,
-				dst;
+	StringInfoData dst;
 
 	if (count == 0)
 		PG_RETURN_TEXT_P(cstring_to_text_with_len("{}", 2));
 
-	initStringInfo(&tmp);
 	initStringInfo(&dst);
 
 	appendStringInfoChar(&dst, '{');
 
 	for (i = 0; i < count; i++)
 	{
-		resetStringInfo(&tmp);
-		appendBinaryStringInfo(&tmp, HSTORE_KEY(entries, base, i),
-							   HSTORE_KEYLEN(entries, i));
-		escape_json(&dst, tmp.data);
+		escape_json(&dst,
+					HSTORE_KEY(entries, base, i),
+					HSTORE_KEYLEN(entries, i));
 		appendStringInfoString(&dst, ": ");
 		if (HSTORE_VALISNULL(entries, i))
 			appendStringInfoString(&dst, "null");
@@ -1372,13 +1369,13 @@ hstore_to_json_loose(PG_FUNCTION_ARGS)
 			appendStringInfoString(&dst, "false");
 		else
 		{
-			resetStringInfo(&tmp);
-			appendBinaryStringInfo(&tmp, HSTORE_VAL(entries, base, i),
-								   HSTORE_VALLEN(entries, i));
-			if (IsValidJsonNumber(tmp.data, tmp.len))
-				appendBinaryStringInfo(&dst, tmp.data, tmp.len);
+			char   *str = HSTORE_VAL(entries, base, i);
+			int		len = HSTORE_VALLEN(entries, i);
+
+			if (IsValidJsonNumber(str, len))
+				appendBinaryStringInfo(&dst, str, len);
 			else
-				escape_json(&dst, tmp.data);
+				escape_json(&dst, str, len);
 		}
 
 		if (i + 1 != count)
@@ -1398,32 +1395,28 @@ hstore_to_json(PG_FUNCTION_ARGS)
 	int			count = HS_COUNT(in);
 	char	   *base = STRPTR(in);
 	HEntry	   *entries = ARRPTR(in);
-	StringInfoData tmp,
-				dst;
+	StringInfoData dst;
 
 	if (count == 0)
 		PG_RETURN_TEXT_P(cstring_to_text_with_len("{}", 2));
 
-	initStringInfo(&tmp);
 	initStringInfo(&dst);
 
 	appendStringInfoChar(&dst, '{');
 
 	for (i = 0; i < count; i++)
 	{
-		resetStringInfo(&tmp);
-		appendBinaryStringInfo(&tmp, HSTORE_KEY(entries, base, i),
-							   HSTORE_KEYLEN(entries, i));
-		escape_json(&dst, tmp.data);
+		escape_json(&dst,
+					HSTORE_KEY(entries, base, i),
+					HSTORE_KEYLEN(entries, i));
 		appendStringInfoString(&dst, ": ");
 		if (HSTORE_VALISNULL(entries, i))
 			appendStringInfoString(&dst, "null");
 		else
 		{
-			resetStringInfo(&tmp);
-			appendBinaryStringInfo(&tmp, HSTORE_VAL(entries, base, i),
-								   HSTORE_VALLEN(entries, i));
-			escape_json(&dst, tmp.data);
+			escape_json(&dst,
+						HSTORE_VAL(entries, base, i),
+						HSTORE_VALLEN(entries, i));
 		}
 
 		if (i + 1 != count)
diff --git a/src/backend/backup/backup_manifest.c b/src/backend/backup/backup_manifest.c
index b360a13547..3da8da00d6 100644
--- a/src/backend/backup/backup_manifest.c
+++ b/src/backend/backup/backup_manifest.c
@@ -148,7 +148,7 @@ AddFileToBackupManifest(backup_manifest_info *manifest, Oid spcoid,
 		pg_verify_mbstr(PG_UTF8, pathname, pathlen, true))
 	{
 		appendStringInfoString(&buf, "{ \"Path\": ");
-		escape_json(&buf, pathname);
+		escape_json(&buf, pathname, pathlen);
 		appendStringInfoString(&buf, ", ");
 	}
 	else
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 94511a5a02..399025aed3 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -4661,13 +4661,15 @@ ExplainPropertyList(const char *qlabel, List *data, ExplainState *es)
 		case EXPLAIN_FORMAT_JSON:
 			ExplainJSONLineEnding(es);
 			appendStringInfoSpaces(es->str, es->indent * 2);
-			escape_json(es->str, qlabel);
+			escape_json_cstring(es->str, qlabel);
 			appendStringInfoString(es->str, ": [");
 			foreach(lc, data)
 			{
+				const char *str = (const char *) lfirst(lc);
+
 				if (!first)
 					appendStringInfoString(es->str, ", ");
-				escape_json(es->str, (const char *) lfirst(lc));
+				escape_json_cstring(es->str, str);
 				first = false;
 			}
 			appendStringInfoChar(es->str, ']');
@@ -4678,10 +4680,12 @@ ExplainPropertyList(const char *qlabel, List *data, ExplainState *es)
 			appendStringInfo(es->str, "%s: ", qlabel);
 			foreach(lc, data)
 			{
+				const char *str = (const char *) lfirst(lc);
+
 				appendStringInfoChar(es->str, '\n');
 				appendStringInfoSpaces(es->str, es->indent * 2 + 2);
 				appendStringInfoString(es->str, "- ");
-				escape_yaml(es->str, (const char *) lfirst(lc));
+				escape_yaml(es->str, str);
 			}
 			break;
 	}
@@ -4710,9 +4714,11 @@ ExplainPropertyListNested(const char *qlabel, List *data, ExplainState *es)
 			appendStringInfoChar(es->str, '[');
 			foreach(lc, data)
 			{
+				const char *str = (const char *) lfirst(lc);
+
 				if (!first)
 					appendStringInfoString(es->str, ", ");
-				escape_json(es->str, (const char *) lfirst(lc));
+				escape_json_cstring(es->str, str);
 				first = false;
 			}
 			appendStringInfoChar(es->str, ']');
@@ -4723,9 +4729,11 @@ ExplainPropertyListNested(const char *qlabel, List *data, ExplainState *es)
 			appendStringInfoString(es->str, "- [");
 			foreach(lc, data)
 			{
+				const char *str = (const char *) lfirst(lc);
+
 				if (!first)
 					appendStringInfoString(es->str, ", ");
-				escape_yaml(es->str, (const char *) lfirst(lc));
+				escape_yaml(es->str, str);
 				first = false;
 			}
 			appendStringInfoChar(es->str, ']');
@@ -4775,12 +4783,12 @@ ExplainProperty(const char *qlabel, const char *unit, const char *value,
 		case EXPLAIN_FORMAT_JSON:
 			ExplainJSONLineEnding(es);
 			appendStringInfoSpaces(es->str, es->indent * 2);
-			escape_json(es->str, qlabel);
+			escape_json_cstring(es->str, qlabel);
 			appendStringInfoString(es->str, ": ");
 			if (numeric)
 				appendStringInfoString(es->str, value);
 			else
-				escape_json(es->str, value);
+				escape_json_cstring(es->str, value);
 			break;
 
 		case EXPLAIN_FORMAT_YAML:
@@ -4882,7 +4890,7 @@ ExplainOpenGroup(const char *objtype, const char *labelname,
 			appendStringInfoSpaces(es->str, 2 * es->indent);
 			if (labelname)
 			{
-				escape_json(es->str, labelname);
+				escape_json_cstring(es->str, labelname);
 				appendStringInfoString(es->str, ": ");
 			}
 			appendStringInfoChar(es->str, labeled ? '{' : '[');
@@ -5090,10 +5098,10 @@ ExplainDummyGroup(const char *objtype, const char *labelname, ExplainState *es)
 			appendStringInfoSpaces(es->str, 2 * es->indent);
 			if (labelname)
 			{
-				escape_json(es->str, labelname);
+				escape_json_cstring(es->str, labelname);
 				appendStringInfoString(es->str, ": ");
 			}
-			escape_json(es->str, objtype);
+			escape_json_cstring(es->str, objtype);
 			break;
 
 		case EXPLAIN_FORMAT_YAML:
@@ -5297,7 +5305,7 @@ ExplainYAMLLineStarting(ExplainState *es)
 static void
 escape_yaml(StringInfo buf, const char *str)
 {
-	escape_json(buf, str);
+	escape_json_cstring(buf, str);
 }
 
 
diff --git a/src/backend/parser/parse_jsontable.c b/src/backend/parser/parse_jsontable.c
index b2519c2f32..03aac2f0cd 100644
--- a/src/backend/parser/parse_jsontable.c
+++ b/src/backend/parser/parse_jsontable.c
@@ -427,7 +427,7 @@ transformJsonTableColumn(JsonTableColumn *jtc, Node *contextItemExpr,
 		initStringInfo(&path);
 
 		appendStringInfoString(&path, "$.");
-		escape_json(&path, jtc->name);
+		escape_json_cstring(&path, jtc->name);
 
 		pathspec = makeStringConst(path.data, -1);
 	}
diff --git a/src/backend/utils/adt/json.c b/src/backend/utils/adt/json.c
index d719a61f16..7934cf62fb 100644
--- a/src/backend/utils/adt/json.c
+++ b/src/backend/utils/adt/json.c
@@ -286,7 +286,7 @@ datum_to_json_internal(Datum val, bool is_null, StringInfo result,
 			break;
 		default:
 			outputstr = OidOutputFunctionCall(outfuncoid, val);
-			escape_json(result, outputstr);
+			escape_json_cstring(result, outputstr);
 			pfree(outputstr);
 			break;
 	}
@@ -560,7 +560,7 @@ composite_to_json(Datum composite, StringInfo result, bool use_line_feeds)
 		needsep = true;
 
 		attname = NameStr(att->attname);
-		escape_json(result, attname);
+		escape_json_cstring(result, attname);
 		appendStringInfoChar(result, ':');
 
 		val = heap_getattr(tuple, i + 1, tupdesc, &isnull);
@@ -1391,7 +1391,6 @@ json_object(PG_FUNCTION_ARGS)
 				count,
 				i;
 	text	   *rval;
-	char	   *v;
 
 	switch (ndims)
 	{
@@ -1434,19 +1433,17 @@ json_object(PG_FUNCTION_ARGS)
 					(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
 					 errmsg("null value not allowed for object key")));
 
-		v = TextDatumGetCString(in_datums[i * 2]);
 		if (i > 0)
 			appendStringInfoString(&result, ", ");
-		escape_json(&result, v);
+		escape_json_from_text(&result,
+							  (text *) DatumGetPointer(in_datums[i * 2]));
 		appendStringInfoString(&result, " : ");
-		pfree(v);
 		if (in_nulls[i * 2 + 1])
 			appendStringInfoString(&result, "null");
 		else
 		{
-			v = TextDatumGetCString(in_datums[i * 2 + 1]);
-			escape_json(&result, v);
-			pfree(v);
+			escape_json_from_text(&result,
+								  (text *) DatumGetPointer(in_datums[i * 2 + 1]));
 		}
 	}
 
@@ -1483,7 +1480,6 @@ json_object_two_arg(PG_FUNCTION_ARGS)
 				val_count,
 				i;
 	text	   *rval;
-	char	   *v;
 
 	if (nkdims > 1 || nkdims != nvdims)
 		ereport(ERROR,
@@ -1512,20 +1508,17 @@ json_object_two_arg(PG_FUNCTION_ARGS)
 					(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
 					 errmsg("null value not allowed for object key")));
 
-		v = TextDatumGetCString(key_datums[i]);
 		if (i > 0)
 			appendStringInfoString(&result, ", ");
-		escape_json(&result, v);
+		escape_json_from_text(&result,
+							  (text *) DatumGetPointer(key_datums[i]));
+
 		appendStringInfoString(&result, " : ");
-		pfree(v);
 		if (val_nulls[i])
 			appendStringInfoString(&result, "null");
 		else
-		{
-			v = TextDatumGetCString(val_datums[i]);
-			escape_json(&result, v);
-			pfree(v);
-		}
+			escape_json_from_text(&result,
+								  (text *) DatumGetPointer(val_datums[i]));
 	}
 
 	appendStringInfoChar(&result, '}');
@@ -1541,52 +1534,101 @@ json_object_two_arg(PG_FUNCTION_ARGS)
 	PG_RETURN_TEXT_P(rval);
 }
 
+/*
+ * escape_json_char
+ *		Inline helper function for escape_json* functions
+ */
+static pg_attribute_always_inline void
+escape_json_char(StringInfo buf, char c)
+{
+	switch (c)
+	{
+		case '\b':
+			appendStringInfoString(buf, "\\b");
+			break;
+		case '\f':
+			appendStringInfoString(buf, "\\f");
+			break;
+		case '\n':
+			appendStringInfoString(buf, "\\n");
+			break;
+		case '\r':
+			appendStringInfoString(buf, "\\r");
+			break;
+		case '\t':
+			appendStringInfoString(buf, "\\t");
+			break;
+		case '"':
+			appendStringInfoString(buf, "\\\"");
+			break;
+		case '\\':
+			appendStringInfoString(buf, "\\\\");
+			break;
+		default:
+			if ((unsigned char) c < ' ')
+				appendStringInfo(buf, "\\u%04x", (int) c);
+			else
+				appendStringInfoCharMacro(buf, c);
+			break;
+	}
+}
 
 /*
- * Produce a JSON string literal, properly escaping characters in the text.
+ * escape_json_cstring
+ *		Produce a JSON string literal.  Same as escape_json() except takes a
+ *		NUL-terminated string as input.
  */
 void
-escape_json(StringInfo buf, const char *str)
+escape_json_cstring(StringInfo buf, const char *str)
 {
-	const char *p;
+	appendStringInfoCharMacro(buf, '"');
+
+	for (; *str != '\0'; str++)
+		escape_json_char(buf, *str);
 
 	appendStringInfoCharMacro(buf, '"');
-	for (p = str; *p; p++)
-	{
-		switch (*p)
-		{
-			case '\b':
-				appendStringInfoString(buf, "\\b");
-				break;
-			case '\f':
-				appendStringInfoString(buf, "\\f");
-				break;
-			case '\n':
-				appendStringInfoString(buf, "\\n");
-				break;
-			case '\r':
-				appendStringInfoString(buf, "\\r");
-				break;
-			case '\t':
-				appendStringInfoString(buf, "\\t");
-				break;
-			case '"':
-				appendStringInfoString(buf, "\\\"");
-				break;
-			case '\\':
-				appendStringInfoString(buf, "\\\\");
-				break;
-			default:
-				if ((unsigned char) *p < ' ')
-					appendStringInfo(buf, "\\u%04x", (int) *p);
-				else
-					appendStringInfoCharMacro(buf, *p);
-				break;
-		}
-	}
+}
+
+/*
+ * Produce a JSON string literal, properly escaping the possibly not
+ * NUL-terminated characters in 'str'.  'len' defines the number of bytes from
+ * 'str' to process.
+ */
+void
+escape_json(StringInfo buf, const char *str, int len)
+{
+	appendStringInfoCharMacro(buf, '"');
+
+	for (int i = 0; i < len; i++)
+		escape_json_char(buf, str[i]);
+
 	appendStringInfoCharMacro(buf, '"');
 }
 
+/*
+ * escape_json_from_text
+ *		Append 't' onto 'buf' and escape using escape_json.
+ *
+ * This is more efficient than calling text_to_cstring and appending the
+ * result as that could require an additional palloc and memcpy.
+ */
+void
+escape_json_from_text(StringInfo buf, const text *t)
+{
+	/* must cast away the const, unfortunately */
+	text *tunpacked = pg_detoast_datum_packed(unconstify(text *, t));
+	int len = VARSIZE_ANY_EXHDR(tunpacked);
+	char *str;
+
+	str = VARDATA_ANY(tunpacked);
+
+	escape_json(buf, str, len);
+
+	/* pfree any detoasted values */
+	if (tunpacked != t)
+		pfree(tunpacked);
+}
+
 /* Semantic actions for key uniqueness check */
 static JsonParseErrorType
 json_unique_object_start(void *_state)
diff --git a/src/backend/utils/adt/jsonb.c b/src/backend/utils/adt/jsonb.c
index e4562b3c6c..f24d8003be 100644
--- a/src/backend/utils/adt/jsonb.c
+++ b/src/backend/utils/adt/jsonb.c
@@ -354,7 +354,7 @@ jsonb_put_escaped_value(StringInfo out, JsonbValue *scalarVal)
 			appendBinaryStringInfo(out, "null", 4);
 			break;
 		case jbvString:
-			escape_json(out, pnstrdup(scalarVal->val.string.val, scalarVal->val.string.len));
+			escape_json(out, scalarVal->val.string.val, scalarVal->val.string.len);
 			break;
 		case jbvNumeric:
 			appendStringInfoString(out,
diff --git a/src/backend/utils/adt/jsonfuncs.c b/src/backend/utils/adt/jsonfuncs.c
index 83125b06a4..743d47dae6 100644
--- a/src/backend/utils/adt/jsonfuncs.c
+++ b/src/backend/utils/adt/jsonfuncs.c
@@ -3139,7 +3139,10 @@ populate_scalar(ScalarIOData *io, Oid typid, int32 typmod, JsValue *jsv,
 			str[len] = '\0';
 		}
 		else
-			str = json;			/* string is already null-terminated */
+		{
+			str = json; /* string is already null-terminated */
+			len = strlen(str);
+		}
 
 		/* If converting to json/jsonb, make string into valid JSON literal */
 		if ((typid == JSONOID || typid == JSONBOID) &&
@@ -3148,7 +3151,7 @@ populate_scalar(ScalarIOData *io, Oid typid, int32 typmod, JsValue *jsv,
 			StringInfoData buf;
 
 			initStringInfo(&buf);
-			escape_json(&buf, str);
+			escape_json(&buf, str, len);
 			/* free temporary buffer */
 			if (str != json)
 				pfree(str);
@@ -4425,7 +4428,7 @@ sn_object_field_start(void *state, char *fname, bool isnull)
 	 * Unfortunately we don't have the quoted and escaped string any more, so
 	 * we have to re-escape it.
 	 */
-	escape_json(_state->strval, fname);
+	escape_json_cstring(_state->strval, fname);
 
 	appendStringInfoCharMacro(_state->strval, ':');
 
@@ -4456,7 +4459,7 @@ sn_scalar(void *state, char *token, JsonTokenType tokentype)
 	}
 
 	if (tokentype == JSON_TOKEN_STRING)
-		escape_json(_state->strval, token);
+		escape_json_cstring(_state->strval, token);
 	else
 		appendStringInfoString(_state->strval, token);
 
@@ -5888,7 +5891,7 @@ transform_string_values_object_field_start(void *state, char *fname, bool isnull
 	 * Unfortunately we don't have the quoted and escaped string any more, so
 	 * we have to re-escape it.
 	 */
-	escape_json(_state->strval, fname);
+	escape_json_cstring(_state->strval, fname);
 	appendStringInfoCharMacro(_state->strval, ':');
 
 	return JSON_SUCCESS;
@@ -5914,7 +5917,7 @@ transform_string_values_scalar(void *state, char *token, JsonTokenType tokentype
 	{
 		text	   *out = _state->action(_state->action_state, token, strlen(token));
 
-		escape_json(_state->strval, text_to_cstring(out));
+		escape_json_from_text(_state->strval, out);
 	}
 	else
 		appendStringInfoString(_state->strval, token);
diff --git a/src/backend/utils/adt/jsonpath.c b/src/backend/utils/adt/jsonpath.c
index 11e6193e96..82d65e4d4f 100644
--- a/src/backend/utils/adt/jsonpath.c
+++ b/src/backend/utils/adt/jsonpath.c
@@ -523,6 +523,8 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 {
 	JsonPathItem elem;
 	int			i;
+	int32		len;
+	char	   *str;
 
 	check_stack_depth();
 	CHECK_FOR_INTERRUPTS();
@@ -533,7 +535,8 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 			appendStringInfoString(buf, "null");
 			break;
 		case jpiString:
-			escape_json(buf, jspGetString(v, NULL));
+			str = jspGetString(v, &len);
+			escape_json(buf, str, len);
 			break;
 		case jpiNumeric:
 			if (jspHasNext(v))
@@ -662,7 +665,8 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 		case jpiKey:
 			if (inKey)
 				appendStringInfoChar(buf, '.');
-			escape_json(buf, jspGetString(v, NULL));
+			str = jspGetString(v, &len);
+			escape_json(buf, str, len);
 			break;
 		case jpiCurrent:
 			Assert(!inKey);
@@ -674,7 +678,8 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 			break;
 		case jpiVariable:
 			appendStringInfoChar(buf, '$');
-			escape_json(buf, jspGetString(v, NULL));
+			str = jspGetString(v, &len);
+			escape_json(buf, str, len);
 			break;
 		case jpiFilter:
 			appendStringInfoString(buf, "?(");
@@ -732,7 +737,9 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 
 			appendStringInfoString(buf, " like_regex ");
 
-			escape_json(buf, v->content.like_regex.pattern);
+			escape_json(buf,
+						v->content.like_regex.pattern,
+						v->content.like_regex.patternlen);
 
 			if (v->content.like_regex.flags)
 			{
diff --git a/src/backend/utils/error/jsonlog.c b/src/backend/utils/error/jsonlog.c
index bd0124869d..bd21f6ef58 100644
--- a/src/backend/utils/error/jsonlog.c
+++ b/src/backend/utils/error/jsonlog.c
@@ -49,11 +49,11 @@ appendJSONKeyValue(StringInfo buf, const char *key, const char *value,
 		return;
 
 	appendStringInfoChar(buf, ',');
-	escape_json(buf, key);
+	escape_json_cstring(buf, key);
 	appendStringInfoChar(buf, ':');
 
 	if (escape_value)
-		escape_json(buf, value);
+		escape_json_cstring(buf, value);
 	else
 		appendStringInfoString(buf, value);
 }
@@ -143,9 +143,9 @@ write_jsonlog(ErrorData *edata)
 	 * First property does not use appendJSONKeyValue as it does not have
 	 * comma prefix.
 	 */
-	escape_json(&buf, "timestamp");
+	escape_json(&buf, "timestamp", strlen("timestamp"));
 	appendStringInfoChar(&buf, ':');
-	escape_json(&buf, log_time);
+	escape_json_cstring(&buf, log_time);
 
 	/* username */
 	if (MyProcPort)
diff --git a/src/include/utils/json.h b/src/include/utils/json.h
index 6d7f1b387d..8ede8d0bd6 100644
--- a/src/include/utils/json.h
+++ b/src/include/utils/json.h
@@ -17,7 +17,9 @@
 #include "lib/stringinfo.h"
 
 /* functions in json.c */
-extern void escape_json(StringInfo buf, const char *str);
+extern void escape_json_cstring(StringInfo buf, const char *str);
+extern void escape_json(StringInfo buf, const char *str, int len);
+extern void escape_json_from_text(StringInfo buf, const text *t);
 extern char *JsonEncodeDateTime(char *buf, Datum value, Oid typid,
 								const int *tzp);
 extern bool to_json_is_immutable(Oid typoid);
-- 
2.34.1

v1-0002-Use-SIMD-processing-for-escape_json.patchapplication/octet-stream; name=v1-0002-Use-SIMD-processing-for-escape_json.patchDownload
From d9dfd04b40c451cf28fc146d6242aa7f96e02db2 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Thu, 23 May 2024 10:53:23 +1200
Subject: [PATCH v1 2/2] Use SIMD processing for escape_json()

---
 src/backend/utils/adt/json.c       | 72 +++++++++++++++++++++++++++++-
 src/test/regress/expected/json.out | 44 ++++++++++++++++++
 src/test/regress/sql/json.sql      |  8 ++++
 3 files changed, 122 insertions(+), 2 deletions(-)

diff --git a/src/backend/utils/adt/json.c b/src/backend/utils/adt/json.c
index 7934cf62fb..a266f60ff3 100644
--- a/src/backend/utils/adt/json.c
+++ b/src/backend/utils/adt/json.c
@@ -19,6 +19,7 @@
 #include "funcapi.h"
 #include "libpq/pqformat.h"
 #include "miscadmin.h"
+#include "port/simd.h"
 #include "utils/array.h"
 #include "utils/builtins.h"
 #include "utils/date.h"
@@ -1597,11 +1598,78 @@ escape_json_cstring(StringInfo buf, const char *str)
 void
 escape_json(StringInfo buf, const char *str, int len)
 {
+	int i = 0;
+	int copypos = 0;
+
+	Assert(len >= 0);
+
 	appendStringInfoCharMacro(buf, '"');
 
-	for (int i = 0; i < len; i++)
-		escape_json_char(buf, str[i]);
+	for (;;)
+	{
+		Vector8 chunk;
+		int		vlen;
+
+		/*
+		 * Figure out how many bytes to process using SIMD.  Round 'len' down
+		 * to the previous multiple of sizeof(Vector8), assuming that's a
+		 * power-of-2.
+		 */
+		vlen = len & (int) (~(sizeof(Vector8) - 1));
+
+		/*
+		 * To speed this up try searching sizeof(Vector8) bytes at once for
+		 * special characters that we need to escape.  When we find one, we
+		 * fall out of this first loop and copy the parts we've vector
+		 * searched before processing the special-char vector byte-by-byte.
+		 * Once we're done with that, come back and try doing vector searching
+		 * again.  We'll also process the tail end of the string byte-by-byte.
+		 */
+		for (; i < vlen; i += sizeof(Vector8))
+		{
+			vector8_load(&chunk, (const uint8 *) &str[i]);
+
+			/*
+			 * Break on anything less than ' ' or if we find a '"' or '\\'.
+			 * Those need special handling.  That's done in the per-byte loop.
+			 */
+			if (vector8_has_le(chunk, (unsigned char) 0x1F) ||
+				vector8_has(chunk, (unsigned char) '"') ||
+				vector8_has(chunk, (unsigned char) '\\'))
+				break;
+		}
+
+		/*
+		 * Write to the destination up to the point of that we've vector
+		 * searched so far.  Do this only when switching into per-byte mode
+		 * rather than once every sizeof(Vector8) bytes.
+		 */
+		if (copypos < i)
+		{
+			appendBinaryStringInfo(buf, &str[copypos], i - copypos);
+			copypos = i;
+		}
+
+		/*
+		 * Per-byte loop for Vector8s containing special chars and for
+		 * processing the tail of the string.
+		 */
+		for (int b = 0; b < sizeof(Vector8); b++)
+		{
+			/* check if we've finished */
+			if (i == len)
+				goto done;
+
+			Assert(i < len);
+
+			escape_json_char(buf, str[i++]);
+		}
+
+		copypos = i;
+		/* We're not done yet.  Try the SIMD search again */
+	}
 
+done:
 	appendStringInfoCharMacro(buf, '"');
 }
 
diff --git a/src/test/regress/expected/json.out b/src/test/regress/expected/json.out
index aa29bc597b..bfcc26c531 100644
--- a/src/test/regress/expected/json.out
+++ b/src/test/regress/expected/json.out
@@ -55,6 +55,50 @@ SELECT ('"'||repeat('.', 12)||'abc\n"')::json; -- OK, legal escapes
  "............abc\n"
 (1 row)
 
+-- Stress testing of JSON escape code
+CREATE TABLE json_escape (very_long_column_name_to_test_json_escape text);
+INSERT INTO json_escape SELECT repeat('a', a) FROM generate_series(0,33) a;
+-- Test various lengths of strings to validate SIMD processing to escape
+-- special chars in the JSON.
+SELECT row_to_json(j)::jsonb FROM json_escape j;
+                                    row_to_json                                     
+------------------------------------------------------------------------------------
+ {"very_long_column_name_to_test_json_escape": ""}
+ {"very_long_column_name_to_test_json_escape": "a"}
+ {"very_long_column_name_to_test_json_escape": "aa"}
+ {"very_long_column_name_to_test_json_escape": "aaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+(34 rows)
+
 -- see json_encoding test for input with unicode escapes
 -- Numbers.
 SELECT '1'::json;				-- OK
diff --git a/src/test/regress/sql/json.sql b/src/test/regress/sql/json.sql
index ec57dfe707..0e7ca2f5af 100644
--- a/src/test/regress/sql/json.sql
+++ b/src/test/regress/sql/json.sql
@@ -12,6 +12,14 @@ SELECT '"\v"'::json;			-- ERROR, not a valid JSON escape
 SELECT ('"'||repeat('.', 12)||'abc"')::json; -- OK
 SELECT ('"'||repeat('.', 12)||'abc\n"')::json; -- OK, legal escapes
 
+-- Stress testing of JSON escape code
+CREATE TABLE json_escape (very_long_column_name_to_test_json_escape text);
+INSERT INTO json_escape SELECT repeat('a', a) FROM generate_series(0,33) a;
+
+-- Test various lengths of strings to validate SIMD processing to escape
+-- special chars in the JSON.
+SELECT row_to_json(j)::jsonb FROM json_escape j;
+
 -- see json_encoding test for input with unicode escapes
 
 -- Numbers.
-- 
2.34.1

#2David Rowley
dgrowleyml@gmail.com
In reply to: David Rowley (#1)
1 attachment(s)
Re: Speed up JSON escape processing with SIMD plus other optimisations

On Thu, 23 May 2024 at 13:23, David Rowley <dgrowleyml@gmail.com> wrote:

Master:
$ pgbench -n -f bench.sql -T 10 -M prepared postgres | grep tps
tps = 362.494309 (without initial connection time)
tps = 363.182458 (without initial connection time)
tps = 362.679654 (without initial connection time)

Master + 0001 + 0002
$ pgbench -n -f bench.sql -T 10 -M prepared postgres | grep tps
tps = 426.456885 (without initial connection time)
tps = 430.573046 (without initial connection time)
tps = 431.142917 (without initial connection time)

About 18% faster.

It would be much faster if we could also get rid of the
escape_json_cstring() call in the switch default case of
datum_to_json_internal(). row_to_json() would be heaps faster with
that done. I considered adding a special case for the "text" type
there, but in the end felt that we should just fix that with some
hypothetical other patch that changes how output functions work.
Others may feel it's worthwhile. I certainly could be convinced of it.

Just to turn that into performance numbers, I tried the attached
patch. The numbers came out better than I thought.

Same test as before:

master + 0001 + 0002 + attached hacks:
$ pgbench -n -f bench.sql -T 10 -M prepared postgres | grep tps
tps = 616.094394 (without initial connection time)
tps = 615.928236 (without initial connection time)
tps = 614.175494 (without initial connection time)

About 70% faster than master.

David

Attachments:

datum_to_json_internal.patch.txttext/plain; charset=US-ASCII; name=datum_to_json_internal.patch.txtDownload
diff --git a/src/backend/utils/adt/json.c b/src/backend/utils/adt/json.c
index a266f60ff3..b15f6c5e64 100644
--- a/src/backend/utils/adt/json.c
+++ b/src/backend/utils/adt/json.c
@@ -24,6 +24,7 @@
 #include "utils/builtins.h"
 #include "utils/date.h"
 #include "utils/datetime.h"
+#include "utils/fmgroids.h"
 #include "utils/json.h"
 #include "utils/jsonfuncs.h"
 #include "utils/lsyscache.h"
@@ -286,9 +287,15 @@ datum_to_json_internal(Datum val, bool is_null, StringInfo result,
 			pfree(jsontext);
 			break;
 		default:
-			outputstr = OidOutputFunctionCall(outfuncoid, val);
-			escape_json_cstring(result, outputstr);
-			pfree(outputstr);
+			/* special case common case for text types */
+			if (outfuncoid == F_TEXTOUT)
+				escape_json_from_text(result, (text *) DatumGetPointer(val));
+			else
+			{
+				outputstr = OidOutputFunctionCall(outfuncoid, val);
+				escape_json_cstring(result, outputstr);
+				pfree(outputstr);
+			}
 			break;
 	}
 }
#3Andrew Dunstan
andrew@dunslane.net
In reply to: David Rowley (#2)
Re: Speed up JSON escape processing with SIMD plus other optimisations

On 2024-05-22 We 22:15, David Rowley wrote:

On Thu, 23 May 2024 at 13:23, David Rowley <dgrowleyml@gmail.com> wrote:

Master:
$ pgbench -n -f bench.sql -T 10 -M prepared postgres | grep tps
tps = 362.494309 (without initial connection time)
tps = 363.182458 (without initial connection time)
tps = 362.679654 (without initial connection time)

Master + 0001 + 0002
$ pgbench -n -f bench.sql -T 10 -M prepared postgres | grep tps
tps = 426.456885 (without initial connection time)
tps = 430.573046 (without initial connection time)
tps = 431.142917 (without initial connection time)

About 18% faster.

It would be much faster if we could also get rid of the
escape_json_cstring() call in the switch default case of
datum_to_json_internal(). row_to_json() would be heaps faster with
that done. I considered adding a special case for the "text" type
there, but in the end felt that we should just fix that with some
hypothetical other patch that changes how output functions work.
Others may feel it's worthwhile. I certainly could be convinced of it.

Just to turn that into performance numbers, I tried the attached
patch. The numbers came out better than I thought.

Same test as before:

master + 0001 + 0002 + attached hacks:
$ pgbench -n -f bench.sql -T 10 -M prepared postgres | grep tps
tps = 616.094394 (without initial connection time)
tps = 615.928236 (without initial connection time)
tps = 614.175494 (without initial connection time)

About 70% faster than master.

That's all pretty nice! I'd take the win on this rather than wait for
some hypothetical patch that changes how output functions work.

cheers

andrew

--
Andrew Dunstan
EDB: https://www.enterprisedb.com

#4David Rowley
dgrowleyml@gmail.com
In reply to: Andrew Dunstan (#3)
3 attachment(s)
Re: Speed up JSON escape processing with SIMD plus other optimisations

On Fri, 24 May 2024 at 08:34, Andrew Dunstan <andrew@dunslane.net> wrote:

That's all pretty nice! I'd take the win on this rather than wait for
some hypothetical patch that changes how output functions work.

On re-think of that, even if we changed the output functions to write
directly to a StringInfo, we wouldn't get the same speedup. All it
would get us is a better ability to know the length of the string the
output function generated by looking at the StringInfoData.len before
and after calling the output function. That *would* allow us to use
the SIMD escaping, but not save the palloc/memcpy cycle for
non-toasted Datums. In other words, if we want this speedup then I
don't see another way other than this special case.

I've attached a rebased patch series which includes the 3rd patch in a
more complete form. This one also adds handling for varchar and
char(n) output functions. Ideally, these would also use textout() to
save from having the ORs in the if condition. The output function code
is the same in each.

Updated benchmarks from the test in [1]/messages/by-id/CAApHDvpLXwMZvbCKcdGfU9XQjGCDm7tFpRdTXuB9PVgpNUYfEQ@mail.gmail.com.

master @ 7c655a04a
$ for i in {1..3}; do pgbench -n -f bench.sql -T 10 -M prepared
postgres | grep tps; done
tps = 366.211426
tps = 359.707014
tps = 362.204383

master + 0001
$ for i in {1..3}; do pgbench -n -f bench.sql -T 10 -M prepared
postgres | grep tps; done
tps = 362.641668
tps = 367.986495
tps = 368.698193 (+1% vs master)

master + 0001 + 0002
$ for i in {1..3}; do pgbench -n -f bench.sql -T 10 -M prepared
postgres | grep tps; done
tps = 430.477314
tps = 425.173469
tps = 431.013275 (+18% vs master)

master + 0001 + 0002 + 0003
$ for i in {1..3}; do pgbench -n -f bench.sql -T 10 -M prepared
postgres | grep tps; done
tps = 606.702305
tps = 625.727031
tps = 617.164822 (+70% vs master)

David

[1]: /messages/by-id/CAApHDvpLXwMZvbCKcdGfU9XQjGCDm7tFpRdTXuB9PVgpNUYfEQ@mail.gmail.com

Attachments:

v2-0001-Add-len-parameter-to-escape_json.patchapplication/octet-stream; name=v2-0001-Add-len-parameter-to-escape_json.patchDownload
From e2b7fec5c3bdf12f8339309dd6b59f061e0d12dc Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Tue, 21 May 2024 17:14:06 +1200
Subject: [PATCH v2 1/3] Add 'len' parameter to escape_json()

---
 contrib/hstore/hstore_io.c           |  41 +++-----
 src/backend/backup/backup_manifest.c |   2 +-
 src/backend/commands/explain.c       |  30 ++++--
 src/backend/parser/parse_jsontable.c |   2 +-
 src/backend/utils/adt/json.c         | 150 +++++++++++++++++----------
 src/backend/utils/adt/jsonb.c        |   2 +-
 src/backend/utils/adt/jsonfuncs.c    |  15 +--
 src/backend/utils/adt/jsonpath.c     |  15 ++-
 src/backend/utils/error/jsonlog.c    |   8 +-
 src/include/utils/json.h             |   4 +-
 10 files changed, 162 insertions(+), 107 deletions(-)

diff --git a/contrib/hstore/hstore_io.c b/contrib/hstore/hstore_io.c
index 999ddad76d..374b8d05ef 100644
--- a/contrib/hstore/hstore_io.c
+++ b/contrib/hstore/hstore_io.c
@@ -1343,23 +1343,20 @@ hstore_to_json_loose(PG_FUNCTION_ARGS)
 	int			count = HS_COUNT(in);
 	char	   *base = STRPTR(in);
 	HEntry	   *entries = ARRPTR(in);
-	StringInfoData tmp,
-				dst;
+	StringInfoData dst;
 
 	if (count == 0)
 		PG_RETURN_TEXT_P(cstring_to_text_with_len("{}", 2));
 
-	initStringInfo(&tmp);
 	initStringInfo(&dst);
 
 	appendStringInfoChar(&dst, '{');
 
 	for (i = 0; i < count; i++)
 	{
-		resetStringInfo(&tmp);
-		appendBinaryStringInfo(&tmp, HSTORE_KEY(entries, base, i),
-							   HSTORE_KEYLEN(entries, i));
-		escape_json(&dst, tmp.data);
+		escape_json(&dst,
+					HSTORE_KEY(entries, base, i),
+					HSTORE_KEYLEN(entries, i));
 		appendStringInfoString(&dst, ": ");
 		if (HSTORE_VALISNULL(entries, i))
 			appendStringInfoString(&dst, "null");
@@ -1372,13 +1369,13 @@ hstore_to_json_loose(PG_FUNCTION_ARGS)
 			appendStringInfoString(&dst, "false");
 		else
 		{
-			resetStringInfo(&tmp);
-			appendBinaryStringInfo(&tmp, HSTORE_VAL(entries, base, i),
-								   HSTORE_VALLEN(entries, i));
-			if (IsValidJsonNumber(tmp.data, tmp.len))
-				appendBinaryStringInfo(&dst, tmp.data, tmp.len);
+			char   *str = HSTORE_VAL(entries, base, i);
+			int		len = HSTORE_VALLEN(entries, i);
+
+			if (IsValidJsonNumber(str, len))
+				appendBinaryStringInfo(&dst, str, len);
 			else
-				escape_json(&dst, tmp.data);
+				escape_json(&dst, str, len);
 		}
 
 		if (i + 1 != count)
@@ -1398,32 +1395,28 @@ hstore_to_json(PG_FUNCTION_ARGS)
 	int			count = HS_COUNT(in);
 	char	   *base = STRPTR(in);
 	HEntry	   *entries = ARRPTR(in);
-	StringInfoData tmp,
-				dst;
+	StringInfoData dst;
 
 	if (count == 0)
 		PG_RETURN_TEXT_P(cstring_to_text_with_len("{}", 2));
 
-	initStringInfo(&tmp);
 	initStringInfo(&dst);
 
 	appendStringInfoChar(&dst, '{');
 
 	for (i = 0; i < count; i++)
 	{
-		resetStringInfo(&tmp);
-		appendBinaryStringInfo(&tmp, HSTORE_KEY(entries, base, i),
-							   HSTORE_KEYLEN(entries, i));
-		escape_json(&dst, tmp.data);
+		escape_json(&dst,
+					HSTORE_KEY(entries, base, i),
+					HSTORE_KEYLEN(entries, i));
 		appendStringInfoString(&dst, ": ");
 		if (HSTORE_VALISNULL(entries, i))
 			appendStringInfoString(&dst, "null");
 		else
 		{
-			resetStringInfo(&tmp);
-			appendBinaryStringInfo(&tmp, HSTORE_VAL(entries, base, i),
-								   HSTORE_VALLEN(entries, i));
-			escape_json(&dst, tmp.data);
+			escape_json(&dst,
+						HSTORE_VAL(entries, base, i),
+						HSTORE_VALLEN(entries, i));
 		}
 
 		if (i + 1 != count)
diff --git a/src/backend/backup/backup_manifest.c b/src/backend/backup/backup_manifest.c
index b360a13547..3da8da00d6 100644
--- a/src/backend/backup/backup_manifest.c
+++ b/src/backend/backup/backup_manifest.c
@@ -148,7 +148,7 @@ AddFileToBackupManifest(backup_manifest_info *manifest, Oid spcoid,
 		pg_verify_mbstr(PG_UTF8, pathname, pathlen, true))
 	{
 		appendStringInfoString(&buf, "{ \"Path\": ");
-		escape_json(&buf, pathname);
+		escape_json(&buf, pathname, pathlen);
 		appendStringInfoString(&buf, ", ");
 	}
 	else
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 94511a5a02..399025aed3 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -4661,13 +4661,15 @@ ExplainPropertyList(const char *qlabel, List *data, ExplainState *es)
 		case EXPLAIN_FORMAT_JSON:
 			ExplainJSONLineEnding(es);
 			appendStringInfoSpaces(es->str, es->indent * 2);
-			escape_json(es->str, qlabel);
+			escape_json_cstring(es->str, qlabel);
 			appendStringInfoString(es->str, ": [");
 			foreach(lc, data)
 			{
+				const char *str = (const char *) lfirst(lc);
+
 				if (!first)
 					appendStringInfoString(es->str, ", ");
-				escape_json(es->str, (const char *) lfirst(lc));
+				escape_json_cstring(es->str, str);
 				first = false;
 			}
 			appendStringInfoChar(es->str, ']');
@@ -4678,10 +4680,12 @@ ExplainPropertyList(const char *qlabel, List *data, ExplainState *es)
 			appendStringInfo(es->str, "%s: ", qlabel);
 			foreach(lc, data)
 			{
+				const char *str = (const char *) lfirst(lc);
+
 				appendStringInfoChar(es->str, '\n');
 				appendStringInfoSpaces(es->str, es->indent * 2 + 2);
 				appendStringInfoString(es->str, "- ");
-				escape_yaml(es->str, (const char *) lfirst(lc));
+				escape_yaml(es->str, str);
 			}
 			break;
 	}
@@ -4710,9 +4714,11 @@ ExplainPropertyListNested(const char *qlabel, List *data, ExplainState *es)
 			appendStringInfoChar(es->str, '[');
 			foreach(lc, data)
 			{
+				const char *str = (const char *) lfirst(lc);
+
 				if (!first)
 					appendStringInfoString(es->str, ", ");
-				escape_json(es->str, (const char *) lfirst(lc));
+				escape_json_cstring(es->str, str);
 				first = false;
 			}
 			appendStringInfoChar(es->str, ']');
@@ -4723,9 +4729,11 @@ ExplainPropertyListNested(const char *qlabel, List *data, ExplainState *es)
 			appendStringInfoString(es->str, "- [");
 			foreach(lc, data)
 			{
+				const char *str = (const char *) lfirst(lc);
+
 				if (!first)
 					appendStringInfoString(es->str, ", ");
-				escape_yaml(es->str, (const char *) lfirst(lc));
+				escape_yaml(es->str, str);
 				first = false;
 			}
 			appendStringInfoChar(es->str, ']');
@@ -4775,12 +4783,12 @@ ExplainProperty(const char *qlabel, const char *unit, const char *value,
 		case EXPLAIN_FORMAT_JSON:
 			ExplainJSONLineEnding(es);
 			appendStringInfoSpaces(es->str, es->indent * 2);
-			escape_json(es->str, qlabel);
+			escape_json_cstring(es->str, qlabel);
 			appendStringInfoString(es->str, ": ");
 			if (numeric)
 				appendStringInfoString(es->str, value);
 			else
-				escape_json(es->str, value);
+				escape_json_cstring(es->str, value);
 			break;
 
 		case EXPLAIN_FORMAT_YAML:
@@ -4882,7 +4890,7 @@ ExplainOpenGroup(const char *objtype, const char *labelname,
 			appendStringInfoSpaces(es->str, 2 * es->indent);
 			if (labelname)
 			{
-				escape_json(es->str, labelname);
+				escape_json_cstring(es->str, labelname);
 				appendStringInfoString(es->str, ": ");
 			}
 			appendStringInfoChar(es->str, labeled ? '{' : '[');
@@ -5090,10 +5098,10 @@ ExplainDummyGroup(const char *objtype, const char *labelname, ExplainState *es)
 			appendStringInfoSpaces(es->str, 2 * es->indent);
 			if (labelname)
 			{
-				escape_json(es->str, labelname);
+				escape_json_cstring(es->str, labelname);
 				appendStringInfoString(es->str, ": ");
 			}
-			escape_json(es->str, objtype);
+			escape_json_cstring(es->str, objtype);
 			break;
 
 		case EXPLAIN_FORMAT_YAML:
@@ -5297,7 +5305,7 @@ ExplainYAMLLineStarting(ExplainState *es)
 static void
 escape_yaml(StringInfo buf, const char *str)
 {
-	escape_json(buf, str);
+	escape_json_cstring(buf, str);
 }
 
 
diff --git a/src/backend/parser/parse_jsontable.c b/src/backend/parser/parse_jsontable.c
index b2519c2f32..03aac2f0cd 100644
--- a/src/backend/parser/parse_jsontable.c
+++ b/src/backend/parser/parse_jsontable.c
@@ -427,7 +427,7 @@ transformJsonTableColumn(JsonTableColumn *jtc, Node *contextItemExpr,
 		initStringInfo(&path);
 
 		appendStringInfoString(&path, "$.");
-		escape_json(&path, jtc->name);
+		escape_json_cstring(&path, jtc->name);
 
 		pathspec = makeStringConst(path.data, -1);
 	}
diff --git a/src/backend/utils/adt/json.c b/src/backend/utils/adt/json.c
index d719a61f16..7934cf62fb 100644
--- a/src/backend/utils/adt/json.c
+++ b/src/backend/utils/adt/json.c
@@ -286,7 +286,7 @@ datum_to_json_internal(Datum val, bool is_null, StringInfo result,
 			break;
 		default:
 			outputstr = OidOutputFunctionCall(outfuncoid, val);
-			escape_json(result, outputstr);
+			escape_json_cstring(result, outputstr);
 			pfree(outputstr);
 			break;
 	}
@@ -560,7 +560,7 @@ composite_to_json(Datum composite, StringInfo result, bool use_line_feeds)
 		needsep = true;
 
 		attname = NameStr(att->attname);
-		escape_json(result, attname);
+		escape_json_cstring(result, attname);
 		appendStringInfoChar(result, ':');
 
 		val = heap_getattr(tuple, i + 1, tupdesc, &isnull);
@@ -1391,7 +1391,6 @@ json_object(PG_FUNCTION_ARGS)
 				count,
 				i;
 	text	   *rval;
-	char	   *v;
 
 	switch (ndims)
 	{
@@ -1434,19 +1433,17 @@ json_object(PG_FUNCTION_ARGS)
 					(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
 					 errmsg("null value not allowed for object key")));
 
-		v = TextDatumGetCString(in_datums[i * 2]);
 		if (i > 0)
 			appendStringInfoString(&result, ", ");
-		escape_json(&result, v);
+		escape_json_from_text(&result,
+							  (text *) DatumGetPointer(in_datums[i * 2]));
 		appendStringInfoString(&result, " : ");
-		pfree(v);
 		if (in_nulls[i * 2 + 1])
 			appendStringInfoString(&result, "null");
 		else
 		{
-			v = TextDatumGetCString(in_datums[i * 2 + 1]);
-			escape_json(&result, v);
-			pfree(v);
+			escape_json_from_text(&result,
+								  (text *) DatumGetPointer(in_datums[i * 2 + 1]));
 		}
 	}
 
@@ -1483,7 +1480,6 @@ json_object_two_arg(PG_FUNCTION_ARGS)
 				val_count,
 				i;
 	text	   *rval;
-	char	   *v;
 
 	if (nkdims > 1 || nkdims != nvdims)
 		ereport(ERROR,
@@ -1512,20 +1508,17 @@ json_object_two_arg(PG_FUNCTION_ARGS)
 					(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
 					 errmsg("null value not allowed for object key")));
 
-		v = TextDatumGetCString(key_datums[i]);
 		if (i > 0)
 			appendStringInfoString(&result, ", ");
-		escape_json(&result, v);
+		escape_json_from_text(&result,
+							  (text *) DatumGetPointer(key_datums[i]));
+
 		appendStringInfoString(&result, " : ");
-		pfree(v);
 		if (val_nulls[i])
 			appendStringInfoString(&result, "null");
 		else
-		{
-			v = TextDatumGetCString(val_datums[i]);
-			escape_json(&result, v);
-			pfree(v);
-		}
+			escape_json_from_text(&result,
+								  (text *) DatumGetPointer(val_datums[i]));
 	}
 
 	appendStringInfoChar(&result, '}');
@@ -1541,52 +1534,101 @@ json_object_two_arg(PG_FUNCTION_ARGS)
 	PG_RETURN_TEXT_P(rval);
 }
 
+/*
+ * escape_json_char
+ *		Inline helper function for escape_json* functions
+ */
+static pg_attribute_always_inline void
+escape_json_char(StringInfo buf, char c)
+{
+	switch (c)
+	{
+		case '\b':
+			appendStringInfoString(buf, "\\b");
+			break;
+		case '\f':
+			appendStringInfoString(buf, "\\f");
+			break;
+		case '\n':
+			appendStringInfoString(buf, "\\n");
+			break;
+		case '\r':
+			appendStringInfoString(buf, "\\r");
+			break;
+		case '\t':
+			appendStringInfoString(buf, "\\t");
+			break;
+		case '"':
+			appendStringInfoString(buf, "\\\"");
+			break;
+		case '\\':
+			appendStringInfoString(buf, "\\\\");
+			break;
+		default:
+			if ((unsigned char) c < ' ')
+				appendStringInfo(buf, "\\u%04x", (int) c);
+			else
+				appendStringInfoCharMacro(buf, c);
+			break;
+	}
+}
 
 /*
- * Produce a JSON string literal, properly escaping characters in the text.
+ * escape_json_cstring
+ *		Produce a JSON string literal.  Same as escape_json() except takes a
+ *		NUL-terminated string as input.
  */
 void
-escape_json(StringInfo buf, const char *str)
+escape_json_cstring(StringInfo buf, const char *str)
 {
-	const char *p;
+	appendStringInfoCharMacro(buf, '"');
+
+	for (; *str != '\0'; str++)
+		escape_json_char(buf, *str);
 
 	appendStringInfoCharMacro(buf, '"');
-	for (p = str; *p; p++)
-	{
-		switch (*p)
-		{
-			case '\b':
-				appendStringInfoString(buf, "\\b");
-				break;
-			case '\f':
-				appendStringInfoString(buf, "\\f");
-				break;
-			case '\n':
-				appendStringInfoString(buf, "\\n");
-				break;
-			case '\r':
-				appendStringInfoString(buf, "\\r");
-				break;
-			case '\t':
-				appendStringInfoString(buf, "\\t");
-				break;
-			case '"':
-				appendStringInfoString(buf, "\\\"");
-				break;
-			case '\\':
-				appendStringInfoString(buf, "\\\\");
-				break;
-			default:
-				if ((unsigned char) *p < ' ')
-					appendStringInfo(buf, "\\u%04x", (int) *p);
-				else
-					appendStringInfoCharMacro(buf, *p);
-				break;
-		}
-	}
+}
+
+/*
+ * Produce a JSON string literal, properly escaping the possibly not
+ * NUL-terminated characters in 'str'.  'len' defines the number of bytes from
+ * 'str' to process.
+ */
+void
+escape_json(StringInfo buf, const char *str, int len)
+{
+	appendStringInfoCharMacro(buf, '"');
+
+	for (int i = 0; i < len; i++)
+		escape_json_char(buf, str[i]);
+
 	appendStringInfoCharMacro(buf, '"');
 }
 
+/*
+ * escape_json_from_text
+ *		Append 't' onto 'buf' and escape using escape_json.
+ *
+ * This is more efficient than calling text_to_cstring and appending the
+ * result as that could require an additional palloc and memcpy.
+ */
+void
+escape_json_from_text(StringInfo buf, const text *t)
+{
+	/* must cast away the const, unfortunately */
+	text *tunpacked = pg_detoast_datum_packed(unconstify(text *, t));
+	int len = VARSIZE_ANY_EXHDR(tunpacked);
+	char *str;
+
+	str = VARDATA_ANY(tunpacked);
+
+	escape_json(buf, str, len);
+
+	/* pfree any detoasted values */
+	if (tunpacked != t)
+		pfree(tunpacked);
+}
+
 /* Semantic actions for key uniqueness check */
 static JsonParseErrorType
 json_unique_object_start(void *_state)
diff --git a/src/backend/utils/adt/jsonb.c b/src/backend/utils/adt/jsonb.c
index e4562b3c6c..f24d8003be 100644
--- a/src/backend/utils/adt/jsonb.c
+++ b/src/backend/utils/adt/jsonb.c
@@ -354,7 +354,7 @@ jsonb_put_escaped_value(StringInfo out, JsonbValue *scalarVal)
 			appendBinaryStringInfo(out, "null", 4);
 			break;
 		case jbvString:
-			escape_json(out, pnstrdup(scalarVal->val.string.val, scalarVal->val.string.len));
+			escape_json(out, scalarVal->val.string.val, scalarVal->val.string.len);
 			break;
 		case jbvNumeric:
 			appendStringInfoString(out,
diff --git a/src/backend/utils/adt/jsonfuncs.c b/src/backend/utils/adt/jsonfuncs.c
index 83125b06a4..743d47dae6 100644
--- a/src/backend/utils/adt/jsonfuncs.c
+++ b/src/backend/utils/adt/jsonfuncs.c
@@ -3139,7 +3139,10 @@ populate_scalar(ScalarIOData *io, Oid typid, int32 typmod, JsValue *jsv,
 			str[len] = '\0';
 		}
 		else
-			str = json;			/* string is already null-terminated */
+		{
+			str = json; /* string is already null-terminated */
+			len = strlen(str);
+		}
 
 		/* If converting to json/jsonb, make string into valid JSON literal */
 		if ((typid == JSONOID || typid == JSONBOID) &&
@@ -3148,7 +3151,7 @@ populate_scalar(ScalarIOData *io, Oid typid, int32 typmod, JsValue *jsv,
 			StringInfoData buf;
 
 			initStringInfo(&buf);
-			escape_json(&buf, str);
+			escape_json(&buf, str, len);
 			/* free temporary buffer */
 			if (str != json)
 				pfree(str);
@@ -4425,7 +4428,7 @@ sn_object_field_start(void *state, char *fname, bool isnull)
 	 * Unfortunately we don't have the quoted and escaped string any more, so
 	 * we have to re-escape it.
 	 */
-	escape_json(_state->strval, fname);
+	escape_json_cstring(_state->strval, fname);
 
 	appendStringInfoCharMacro(_state->strval, ':');
 
@@ -4456,7 +4459,7 @@ sn_scalar(void *state, char *token, JsonTokenType tokentype)
 	}
 
 	if (tokentype == JSON_TOKEN_STRING)
-		escape_json(_state->strval, token);
+		escape_json_cstring(_state->strval, token);
 	else
 		appendStringInfoString(_state->strval, token);
 
@@ -5888,7 +5891,7 @@ transform_string_values_object_field_start(void *state, char *fname, bool isnull
 	 * Unfortunately we don't have the quoted and escaped string any more, so
 	 * we have to re-escape it.
 	 */
-	escape_json(_state->strval, fname);
+	escape_json_cstring(_state->strval, fname);
 	appendStringInfoCharMacro(_state->strval, ':');
 
 	return JSON_SUCCESS;
@@ -5914,7 +5917,7 @@ transform_string_values_scalar(void *state, char *token, JsonTokenType tokentype
 	{
 		text	   *out = _state->action(_state->action_state, token, strlen(token));
 
-		escape_json(_state->strval, text_to_cstring(out));
+		escape_json_from_text(_state->strval, out);
 	}
 	else
 		appendStringInfoString(_state->strval, token);
diff --git a/src/backend/utils/adt/jsonpath.c b/src/backend/utils/adt/jsonpath.c
index 11e6193e96..82d65e4d4f 100644
--- a/src/backend/utils/adt/jsonpath.c
+++ b/src/backend/utils/adt/jsonpath.c
@@ -523,6 +523,8 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 {
 	JsonPathItem elem;
 	int			i;
+	int32		len;
+	char	   *str;
 
 	check_stack_depth();
 	CHECK_FOR_INTERRUPTS();
@@ -533,7 +535,8 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 			appendStringInfoString(buf, "null");
 			break;
 		case jpiString:
-			escape_json(buf, jspGetString(v, NULL));
+			str = jspGetString(v, &len);
+			escape_json(buf, str, len);
 			break;
 		case jpiNumeric:
 			if (jspHasNext(v))
@@ -662,7 +665,8 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 		case jpiKey:
 			if (inKey)
 				appendStringInfoChar(buf, '.');
-			escape_json(buf, jspGetString(v, NULL));
+			str = jspGetString(v, &len);
+			escape_json(buf, str, len);
 			break;
 		case jpiCurrent:
 			Assert(!inKey);
@@ -674,7 +678,8 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 			break;
 		case jpiVariable:
 			appendStringInfoChar(buf, '$');
-			escape_json(buf, jspGetString(v, NULL));
+			str = jspGetString(v, &len);
+			escape_json(buf, str, len);
 			break;
 		case jpiFilter:
 			appendStringInfoString(buf, "?(");
@@ -732,7 +737,9 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 
 			appendStringInfoString(buf, " like_regex ");
 
-			escape_json(buf, v->content.like_regex.pattern);
+			escape_json(buf,
+						v->content.like_regex.pattern,
+						v->content.like_regex.patternlen);
 
 			if (v->content.like_regex.flags)
 			{
diff --git a/src/backend/utils/error/jsonlog.c b/src/backend/utils/error/jsonlog.c
index bd0124869d..bd21f6ef58 100644
--- a/src/backend/utils/error/jsonlog.c
+++ b/src/backend/utils/error/jsonlog.c
@@ -49,11 +49,11 @@ appendJSONKeyValue(StringInfo buf, const char *key, const char *value,
 		return;
 
 	appendStringInfoChar(buf, ',');
-	escape_json(buf, key);
+	escape_json_cstring(buf, key);
 	appendStringInfoChar(buf, ':');
 
 	if (escape_value)
-		escape_json(buf, value);
+		escape_json_cstring(buf, value);
 	else
 		appendStringInfoString(buf, value);
 }
@@ -143,9 +143,9 @@ write_jsonlog(ErrorData *edata)
 	 * First property does not use appendJSONKeyValue as it does not have
 	 * comma prefix.
 	 */
-	escape_json(&buf, "timestamp");
+	escape_json(&buf, "timestamp", strlen("timestamp"));
 	appendStringInfoChar(&buf, ':');
-	escape_json(&buf, log_time);
+	escape_json_cstring(&buf, log_time);
 
 	/* username */
 	if (MyProcPort)
diff --git a/src/include/utils/json.h b/src/include/utils/json.h
index 6d7f1b387d..8ede8d0bd6 100644
--- a/src/include/utils/json.h
+++ b/src/include/utils/json.h
@@ -17,7 +17,9 @@
 #include "lib/stringinfo.h"
 
 /* functions in json.c */
-extern void escape_json(StringInfo buf, const char *str);
+extern void escape_json_cstring(StringInfo buf, const char *str);
+extern void escape_json(StringInfo buf, const char *str, int len);
+extern void escape_json_from_text(StringInfo buf, const text *t);
 extern char *JsonEncodeDateTime(char *buf, Datum value, Oid typid,
 								const int *tzp);
 extern bool to_json_is_immutable(Oid typoid);
-- 
2.34.1

v2-0002-Use-SIMD-processing-for-escape_json.patchapplication/octet-stream; name=v2-0002-Use-SIMD-processing-for-escape_json.patchDownload
From 36e226c368d2eb37c41124f52ef819bc626fd5a8 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Thu, 23 May 2024 10:53:23 +1200
Subject: [PATCH v2 2/3] Use SIMD processing for escape_json()

---
 src/backend/utils/adt/json.c       | 72 +++++++++++++++++++++++++++++-
 src/test/regress/expected/json.out | 44 ++++++++++++++++++
 src/test/regress/sql/json.sql      |  8 ++++
 3 files changed, 122 insertions(+), 2 deletions(-)

diff --git a/src/backend/utils/adt/json.c b/src/backend/utils/adt/json.c
index 7934cf62fb..a266f60ff3 100644
--- a/src/backend/utils/adt/json.c
+++ b/src/backend/utils/adt/json.c
@@ -19,6 +19,7 @@
 #include "funcapi.h"
 #include "libpq/pqformat.h"
 #include "miscadmin.h"
+#include "port/simd.h"
 #include "utils/array.h"
 #include "utils/builtins.h"
 #include "utils/date.h"
@@ -1597,11 +1598,78 @@ escape_json_cstring(StringInfo buf, const char *str)
 void
 escape_json(StringInfo buf, const char *str, int len)
 {
+	int i = 0;
+	int copypos = 0;
+
+	Assert(len >= 0);
+
 	appendStringInfoCharMacro(buf, '"');
 
-	for (int i = 0; i < len; i++)
-		escape_json_char(buf, str[i]);
+	for (;;)
+	{
+		Vector8 chunk;
+		int		vlen;
+
+		/*
+		 * Figure out how many bytes to process using SIMD.  Round 'len' down
+		 * to the previous multiple of sizeof(Vector8), assuming that's a
+		 * power-of-2.
+		 */
+		vlen = len & (int) (~(sizeof(Vector8) - 1));
+
+		/*
+		 * To speed this up try searching sizeof(Vector8) bytes at once for
+		 * special characters that we need to escape.  When we find one, we
+		 * fall out of this first loop and copy the parts we've vector
+		 * searched before processing the special-char vector byte-by-byte.
+		 * Once we're done with that, come back and try doing vector searching
+		 * again.  We'll also process the tail end of the string byte-by-byte.
+		 */
+		for (; i < vlen; i += sizeof(Vector8))
+		{
+			vector8_load(&chunk, (const uint8 *) &str[i]);
+
+			/*
+			 * Break on anything less than ' ' or if we find a '"' or '\\'.
+			 * Those need special handling.  That's done in the per-byte loop.
+			 */
+			if (vector8_has_le(chunk, (unsigned char) 0x1F) ||
+				vector8_has(chunk, (unsigned char) '"') ||
+				vector8_has(chunk, (unsigned char) '\\'))
+				break;
+		}
+
+		/*
+		 * Write to the destination up to the point of that we've vector
+		 * searched so far.  Do this only when switching into per-byte mode
+		 * rather than once every sizeof(Vector8) bytes.
+		 */
+		if (copypos < i)
+		{
+			appendBinaryStringInfo(buf, &str[copypos], i - copypos);
+			copypos = i;
+		}
+
+		/*
+		 * Per-byte loop for Vector8s containing special chars and for
+		 * processing the tail of the string.
+		 */
+		for (int b = 0; b < sizeof(Vector8); b++)
+		{
+			/* check if we've finished */
+			if (i == len)
+				goto done;
+
+			Assert(i < len);
+
+			escape_json_char(buf, str[i++]);
+		}
+
+		copypos = i;
+		/* We're not done yet.  Try the SIMD search again */
+	}
 
+done:
 	appendStringInfoCharMacro(buf, '"');
 }
 
diff --git a/src/test/regress/expected/json.out b/src/test/regress/expected/json.out
index aa29bc597b..bfcc26c531 100644
--- a/src/test/regress/expected/json.out
+++ b/src/test/regress/expected/json.out
@@ -55,6 +55,50 @@ SELECT ('"'||repeat('.', 12)||'abc\n"')::json; -- OK, legal escapes
  "............abc\n"
 (1 row)
 
+-- Stress testing of JSON escape code
+CREATE TABLE json_escape (very_long_column_name_to_test_json_escape text);
+INSERT INTO json_escape SELECT repeat('a', a) FROM generate_series(0,33) a;
+-- Test various lengths of strings to validate SIMD processing to escape
+-- special chars in the JSON.
+SELECT row_to_json(j)::jsonb FROM json_escape j;
+                                    row_to_json                                     
+------------------------------------------------------------------------------------
+ {"very_long_column_name_to_test_json_escape": ""}
+ {"very_long_column_name_to_test_json_escape": "a"}
+ {"very_long_column_name_to_test_json_escape": "aa"}
+ {"very_long_column_name_to_test_json_escape": "aaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+(34 rows)
+
 -- see json_encoding test for input with unicode escapes
 -- Numbers.
 SELECT '1'::json;				-- OK
diff --git a/src/test/regress/sql/json.sql b/src/test/regress/sql/json.sql
index ec57dfe707..0e7ca2f5af 100644
--- a/src/test/regress/sql/json.sql
+++ b/src/test/regress/sql/json.sql
@@ -12,6 +12,14 @@ SELECT '"\v"'::json;			-- ERROR, not a valid JSON escape
 SELECT ('"'||repeat('.', 12)||'abc"')::json; -- OK
 SELECT ('"'||repeat('.', 12)||'abc\n"')::json; -- OK, legal escapes
 
+-- Stress testing of JSON escape code
+CREATE TABLE json_escape (very_long_column_name_to_test_json_escape text);
+INSERT INTO json_escape SELECT repeat('a', a) FROM generate_series(0,33) a;
+
+-- Test various lengths of strings to validate SIMD processing to escape
+-- special chars in the JSON.
+SELECT row_to_json(j)::jsonb FROM json_escape j;
+
 -- see json_encoding test for input with unicode escapes
 
 -- Numbers.
-- 
2.34.1

v2-0003-Special-case-text-type-conversion-in-datum_to_jso.patchapplication/octet-stream; name=v2-0003-Special-case-text-type-conversion-in-datum_to_jso.patchDownload
From bb25974cd77c5afb273c0acfbf150d35da0ea0cd Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Thu, 23 May 2024 15:12:59 +1200
Subject: [PATCH v2 3/3] Special-case text type conversion in
 datum_to_json_internal

---
 src/backend/utils/adt/json.c | 13 ++++++++++---
 1 file changed, 10 insertions(+), 3 deletions(-)

diff --git a/src/backend/utils/adt/json.c b/src/backend/utils/adt/json.c
index a266f60ff3..371881dfd0 100644
--- a/src/backend/utils/adt/json.c
+++ b/src/backend/utils/adt/json.c
@@ -24,6 +24,7 @@
 #include "utils/builtins.h"
 #include "utils/date.h"
 #include "utils/datetime.h"
+#include "utils/fmgroids.h"
 #include "utils/json.h"
 #include "utils/jsonfuncs.h"
 #include "utils/lsyscache.h"
@@ -286,9 +287,15 @@ datum_to_json_internal(Datum val, bool is_null, StringInfo result,
 			pfree(jsontext);
 			break;
 		default:
-			outputstr = OidOutputFunctionCall(outfuncoid, val);
-			escape_json_cstring(result, outputstr);
-			pfree(outputstr);
+			/* special-case text types to save useless palloc/memcpy cycles */
+			if (outfuncoid == F_TEXTOUT || outfuncoid ==  F_VARCHAROUT || outfuncoid == F_BPCHAROUT)
+				escape_json_from_text(result, (text *) DatumGetPointer(val));
+			else
+			{
+				outputstr = OidOutputFunctionCall(outfuncoid, val);
+				escape_json_cstring(result, outputstr);
+				pfree(outputstr);
+			}
 			break;
 	}
 }
-- 
2.34.1

#5Melih Mutlu
m.melihmutlu@gmail.com
In reply to: David Rowley (#4)
Re: Speed up JSON escape processing with SIMD plus other optimisations

Hi David,

Thanks for the patch.

In 0001 patch, I see that there are some escape_json() calls with
NUL-terminated strings and gets the length by calling strlen(), like below:

- escape_json(&buf, "timestamp");

+ escape_json(&buf, "timestamp", strlen("timestamp"));

Wouldn't using escape_json_cstring() be better instead? IIUC there isn't
much difference between escape_json() and escape_json_cstring(), right? We
would avoid strlen() with escape_json_cstring().

Regards,
--
Melih Mutlu
Microsoft

#6Andrew Dunstan
andrew@dunslane.net
In reply to: Melih Mutlu (#5)
Re: Speed up JSON escape processing with SIMD plus other optimisations

On 2024-06-11 Tu 08:08, Melih Mutlu wrote:

Hi David,

Thanks for the patch.

In 0001 patch, I see that there are some escape_json() calls with
NUL-terminated strings and gets the length by calling strlen(), like
below:

- escape_json(&buf, "timestamp");
+ escape_json(&buf, "timestamp", strlen("timestamp"));

 Wouldn't using escape_json_cstring() be better instead? IIUC there
isn't much difference between escape_json() and escape_json_cstring(),
right? We would avoid strlen() with escape_json_cstring().

or maybe use sizeof("timestamp") - 1

cheers

andrew

--
Andrew Dunstan
EDB:https://www.enterprisedb.com

#7David Rowley
dgrowleyml@gmail.com
In reply to: Melih Mutlu (#5)
Re: Speed up JSON escape processing with SIMD plus other optimisations

Thanks for having a look.

On Wed, 12 Jun 2024 at 00:08, Melih Mutlu <m.melihmutlu@gmail.com> wrote:

In 0001 patch, I see that there are some escape_json() calls with NUL-terminated strings and gets the length by calling strlen(), like below:

- escape_json(&buf, "timestamp");
+ escape_json(&buf, "timestamp", strlen("timestamp"));

Wouldn't using escape_json_cstring() be better instead? IIUC there isn't much difference between escape_json() and escape_json_cstring(), right? We would avoid strlen() with escape_json_cstring().

It maybe would be better, but not for this reason. Most compilers will
be able to perform constant folding to transform the
strlen("timestamp") into 9. You can see that's being done by both gcc
and clang in [1]https://godbolt.org/z/xqj4rKara.

It might be better to use escape_json_cstring() regardless of that as
the SIMD only kicks in when there are >= 16 chars, so there might be a
few more instructions calling the SIMD version for such a short
string. Probably, if we're worried about performance here we could
just not bother passing the string through the escape function to
search for something we know isn't there and just
appendBinaryStringInfo \""timestamp\":" directly.

I don't really have a preference as to which of these we use. I doubt
the JSON escaping rules would ever change sufficiently that the latter
of these methods would be a bad idea. I just doubt it's worth the
debate as I imagine the performance won't matter that much.

David

[1]: https://godbolt.org/z/xqj4rKara

#8David Rowley
dgrowleyml@gmail.com
In reply to: David Rowley (#7)
3 attachment(s)
Re: Speed up JSON escape processing with SIMD plus other optimisations

I've attached a rebased set of patches. The previous set no longer applied.

David

Attachments:

v3-0001-Add-len-parameter-to-escape_json.patchapplication/octet-stream; name=v3-0001-Add-len-parameter-to-escape_json.patchDownload
From f67eafe621ba8612c1d69a0a957707554bd88670 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Tue, 21 May 2024 17:14:06 +1200
Subject: [PATCH v3 1/3] Add 'len' parameter to escape_json()

---
 contrib/hstore/hstore_io.c           |  41 +++-----
 src/backend/backup/backup_manifest.c |   2 +-
 src/backend/commands/explain.c       |  30 ++++--
 src/backend/parser/parse_jsontable.c |   2 +-
 src/backend/utils/adt/json.c         | 150 +++++++++++++++++----------
 src/backend/utils/adt/jsonb.c        |   2 +-
 src/backend/utils/adt/jsonfuncs.c    |  12 +--
 src/backend/utils/adt/jsonpath.c     |  15 ++-
 src/backend/utils/error/jsonlog.c    |   8 +-
 src/include/utils/json.h             |   4 +-
 10 files changed, 159 insertions(+), 107 deletions(-)

diff --git a/contrib/hstore/hstore_io.c b/contrib/hstore/hstore_io.c
index 999ddad76d..374b8d05ef 100644
--- a/contrib/hstore/hstore_io.c
+++ b/contrib/hstore/hstore_io.c
@@ -1343,23 +1343,20 @@ hstore_to_json_loose(PG_FUNCTION_ARGS)
 	int			count = HS_COUNT(in);
 	char	   *base = STRPTR(in);
 	HEntry	   *entries = ARRPTR(in);
-	StringInfoData tmp,
-				dst;
+	StringInfoData dst;
 
 	if (count == 0)
 		PG_RETURN_TEXT_P(cstring_to_text_with_len("{}", 2));
 
-	initStringInfo(&tmp);
 	initStringInfo(&dst);
 
 	appendStringInfoChar(&dst, '{');
 
 	for (i = 0; i < count; i++)
 	{
-		resetStringInfo(&tmp);
-		appendBinaryStringInfo(&tmp, HSTORE_KEY(entries, base, i),
-							   HSTORE_KEYLEN(entries, i));
-		escape_json(&dst, tmp.data);
+		escape_json(&dst,
+					HSTORE_KEY(entries, base, i),
+					HSTORE_KEYLEN(entries, i));
 		appendStringInfoString(&dst, ": ");
 		if (HSTORE_VALISNULL(entries, i))
 			appendStringInfoString(&dst, "null");
@@ -1372,13 +1369,13 @@ hstore_to_json_loose(PG_FUNCTION_ARGS)
 			appendStringInfoString(&dst, "false");
 		else
 		{
-			resetStringInfo(&tmp);
-			appendBinaryStringInfo(&tmp, HSTORE_VAL(entries, base, i),
-								   HSTORE_VALLEN(entries, i));
-			if (IsValidJsonNumber(tmp.data, tmp.len))
-				appendBinaryStringInfo(&dst, tmp.data, tmp.len);
+			char   *str = HSTORE_VAL(entries, base, i);
+			int		len = HSTORE_VALLEN(entries, i);
+
+			if (IsValidJsonNumber(str, len))
+				appendBinaryStringInfo(&dst, str, len);
 			else
-				escape_json(&dst, tmp.data);
+				escape_json(&dst, str, len);
 		}
 
 		if (i + 1 != count)
@@ -1398,32 +1395,28 @@ hstore_to_json(PG_FUNCTION_ARGS)
 	int			count = HS_COUNT(in);
 	char	   *base = STRPTR(in);
 	HEntry	   *entries = ARRPTR(in);
-	StringInfoData tmp,
-				dst;
+	StringInfoData dst;
 
 	if (count == 0)
 		PG_RETURN_TEXT_P(cstring_to_text_with_len("{}", 2));
 
-	initStringInfo(&tmp);
 	initStringInfo(&dst);
 
 	appendStringInfoChar(&dst, '{');
 
 	for (i = 0; i < count; i++)
 	{
-		resetStringInfo(&tmp);
-		appendBinaryStringInfo(&tmp, HSTORE_KEY(entries, base, i),
-							   HSTORE_KEYLEN(entries, i));
-		escape_json(&dst, tmp.data);
+		escape_json(&dst,
+					HSTORE_KEY(entries, base, i),
+					HSTORE_KEYLEN(entries, i));
 		appendStringInfoString(&dst, ": ");
 		if (HSTORE_VALISNULL(entries, i))
 			appendStringInfoString(&dst, "null");
 		else
 		{
-			resetStringInfo(&tmp);
-			appendBinaryStringInfo(&tmp, HSTORE_VAL(entries, base, i),
-								   HSTORE_VALLEN(entries, i));
-			escape_json(&dst, tmp.data);
+			escape_json(&dst,
+						HSTORE_VAL(entries, base, i),
+						HSTORE_VALLEN(entries, i));
 		}
 
 		if (i + 1 != count)
diff --git a/src/backend/backup/backup_manifest.c b/src/backend/backup/backup_manifest.c
index b360a13547..3da8da00d6 100644
--- a/src/backend/backup/backup_manifest.c
+++ b/src/backend/backup/backup_manifest.c
@@ -148,7 +148,7 @@ AddFileToBackupManifest(backup_manifest_info *manifest, Oid spcoid,
 		pg_verify_mbstr(PG_UTF8, pathname, pathlen, true))
 	{
 		appendStringInfoString(&buf, "{ \"Path\": ");
-		escape_json(&buf, pathname);
+		escape_json(&buf, pathname, pathlen);
 		appendStringInfoString(&buf, ", ");
 	}
 	else
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 94511a5a02..399025aed3 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -4661,13 +4661,15 @@ ExplainPropertyList(const char *qlabel, List *data, ExplainState *es)
 		case EXPLAIN_FORMAT_JSON:
 			ExplainJSONLineEnding(es);
 			appendStringInfoSpaces(es->str, es->indent * 2);
-			escape_json(es->str, qlabel);
+			escape_json_cstring(es->str, qlabel);
 			appendStringInfoString(es->str, ": [");
 			foreach(lc, data)
 			{
+				const char *str = (const char *) lfirst(lc);
+
 				if (!first)
 					appendStringInfoString(es->str, ", ");
-				escape_json(es->str, (const char *) lfirst(lc));
+				escape_json_cstring(es->str, str);
 				first = false;
 			}
 			appendStringInfoChar(es->str, ']');
@@ -4678,10 +4680,12 @@ ExplainPropertyList(const char *qlabel, List *data, ExplainState *es)
 			appendStringInfo(es->str, "%s: ", qlabel);
 			foreach(lc, data)
 			{
+				const char *str = (const char *) lfirst(lc);
+
 				appendStringInfoChar(es->str, '\n');
 				appendStringInfoSpaces(es->str, es->indent * 2 + 2);
 				appendStringInfoString(es->str, "- ");
-				escape_yaml(es->str, (const char *) lfirst(lc));
+				escape_yaml(es->str, str);
 			}
 			break;
 	}
@@ -4710,9 +4714,11 @@ ExplainPropertyListNested(const char *qlabel, List *data, ExplainState *es)
 			appendStringInfoChar(es->str, '[');
 			foreach(lc, data)
 			{
+				const char *str = (const char *) lfirst(lc);
+
 				if (!first)
 					appendStringInfoString(es->str, ", ");
-				escape_json(es->str, (const char *) lfirst(lc));
+				escape_json_cstring(es->str, str);
 				first = false;
 			}
 			appendStringInfoChar(es->str, ']');
@@ -4723,9 +4729,11 @@ ExplainPropertyListNested(const char *qlabel, List *data, ExplainState *es)
 			appendStringInfoString(es->str, "- [");
 			foreach(lc, data)
 			{
+				const char *str = (const char *) lfirst(lc);
+
 				if (!first)
 					appendStringInfoString(es->str, ", ");
-				escape_yaml(es->str, (const char *) lfirst(lc));
+				escape_yaml(es->str, str);
 				first = false;
 			}
 			appendStringInfoChar(es->str, ']');
@@ -4775,12 +4783,12 @@ ExplainProperty(const char *qlabel, const char *unit, const char *value,
 		case EXPLAIN_FORMAT_JSON:
 			ExplainJSONLineEnding(es);
 			appendStringInfoSpaces(es->str, es->indent * 2);
-			escape_json(es->str, qlabel);
+			escape_json_cstring(es->str, qlabel);
 			appendStringInfoString(es->str, ": ");
 			if (numeric)
 				appendStringInfoString(es->str, value);
 			else
-				escape_json(es->str, value);
+				escape_json_cstring(es->str, value);
 			break;
 
 		case EXPLAIN_FORMAT_YAML:
@@ -4882,7 +4890,7 @@ ExplainOpenGroup(const char *objtype, const char *labelname,
 			appendStringInfoSpaces(es->str, 2 * es->indent);
 			if (labelname)
 			{
-				escape_json(es->str, labelname);
+				escape_json_cstring(es->str, labelname);
 				appendStringInfoString(es->str, ": ");
 			}
 			appendStringInfoChar(es->str, labeled ? '{' : '[');
@@ -5090,10 +5098,10 @@ ExplainDummyGroup(const char *objtype, const char *labelname, ExplainState *es)
 			appendStringInfoSpaces(es->str, 2 * es->indent);
 			if (labelname)
 			{
-				escape_json(es->str, labelname);
+				escape_json_cstring(es->str, labelname);
 				appendStringInfoString(es->str, ": ");
 			}
-			escape_json(es->str, objtype);
+			escape_json_cstring(es->str, objtype);
 			break;
 
 		case EXPLAIN_FORMAT_YAML:
@@ -5297,7 +5305,7 @@ ExplainYAMLLineStarting(ExplainState *es)
 static void
 escape_yaml(StringInfo buf, const char *str)
 {
-	escape_json(buf, str);
+	escape_json_cstring(buf, str);
 }
 
 
diff --git a/src/backend/parser/parse_jsontable.c b/src/backend/parser/parse_jsontable.c
index 8a72e498e8..7a8aa4a2d3 100644
--- a/src/backend/parser/parse_jsontable.c
+++ b/src/backend/parser/parse_jsontable.c
@@ -427,7 +427,7 @@ transformJsonTableColumn(JsonTableColumn *jtc, Node *contextItemExpr,
 		initStringInfo(&path);
 
 		appendStringInfoString(&path, "$.");
-		escape_json(&path, jtc->name);
+		escape_json_cstring(&path, jtc->name);
 
 		pathspec = makeStringConst(path.data, -1);
 	}
diff --git a/src/backend/utils/adt/json.c b/src/backend/utils/adt/json.c
index d719a61f16..7934cf62fb 100644
--- a/src/backend/utils/adt/json.c
+++ b/src/backend/utils/adt/json.c
@@ -286,7 +286,7 @@ datum_to_json_internal(Datum val, bool is_null, StringInfo result,
 			break;
 		default:
 			outputstr = OidOutputFunctionCall(outfuncoid, val);
-			escape_json(result, outputstr);
+			escape_json_cstring(result, outputstr);
 			pfree(outputstr);
 			break;
 	}
@@ -560,7 +560,7 @@ composite_to_json(Datum composite, StringInfo result, bool use_line_feeds)
 		needsep = true;
 
 		attname = NameStr(att->attname);
-		escape_json(result, attname);
+		escape_json_cstring(result, attname);
 		appendStringInfoChar(result, ':');
 
 		val = heap_getattr(tuple, i + 1, tupdesc, &isnull);
@@ -1391,7 +1391,6 @@ json_object(PG_FUNCTION_ARGS)
 				count,
 				i;
 	text	   *rval;
-	char	   *v;
 
 	switch (ndims)
 	{
@@ -1434,19 +1433,17 @@ json_object(PG_FUNCTION_ARGS)
 					(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
 					 errmsg("null value not allowed for object key")));
 
-		v = TextDatumGetCString(in_datums[i * 2]);
 		if (i > 0)
 			appendStringInfoString(&result, ", ");
-		escape_json(&result, v);
+		escape_json_from_text(&result,
+							  (text *) DatumGetPointer(in_datums[i * 2]));
 		appendStringInfoString(&result, " : ");
-		pfree(v);
 		if (in_nulls[i * 2 + 1])
 			appendStringInfoString(&result, "null");
 		else
 		{
-			v = TextDatumGetCString(in_datums[i * 2 + 1]);
-			escape_json(&result, v);
-			pfree(v);
+			escape_json_from_text(&result,
+								  (text *) DatumGetPointer(in_datums[i * 2 + 1]));
 		}
 	}
 
@@ -1483,7 +1480,6 @@ json_object_two_arg(PG_FUNCTION_ARGS)
 				val_count,
 				i;
 	text	   *rval;
-	char	   *v;
 
 	if (nkdims > 1 || nkdims != nvdims)
 		ereport(ERROR,
@@ -1512,20 +1508,17 @@ json_object_two_arg(PG_FUNCTION_ARGS)
 					(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
 					 errmsg("null value not allowed for object key")));
 
-		v = TextDatumGetCString(key_datums[i]);
 		if (i > 0)
 			appendStringInfoString(&result, ", ");
-		escape_json(&result, v);
+		escape_json_from_text(&result,
+							  (text *) DatumGetPointer(key_datums[i]));
+
 		appendStringInfoString(&result, " : ");
-		pfree(v);
 		if (val_nulls[i])
 			appendStringInfoString(&result, "null");
 		else
-		{
-			v = TextDatumGetCString(val_datums[i]);
-			escape_json(&result, v);
-			pfree(v);
-		}
+			escape_json_from_text(&result,
+								  (text *) DatumGetPointer(val_datums[i]));
 	}
 
 	appendStringInfoChar(&result, '}');
@@ -1541,52 +1534,101 @@ json_object_two_arg(PG_FUNCTION_ARGS)
 	PG_RETURN_TEXT_P(rval);
 }
 
+/*
+ * escape_json_char
+ *		Inline helper function for escape_json* functions
+ */
+static pg_attribute_always_inline void
+escape_json_char(StringInfo buf, char c)
+{
+	switch (c)
+	{
+		case '\b':
+			appendStringInfoString(buf, "\\b");
+			break;
+		case '\f':
+			appendStringInfoString(buf, "\\f");
+			break;
+		case '\n':
+			appendStringInfoString(buf, "\\n");
+			break;
+		case '\r':
+			appendStringInfoString(buf, "\\r");
+			break;
+		case '\t':
+			appendStringInfoString(buf, "\\t");
+			break;
+		case '"':
+			appendStringInfoString(buf, "\\\"");
+			break;
+		case '\\':
+			appendStringInfoString(buf, "\\\\");
+			break;
+		default:
+			if ((unsigned char) c < ' ')
+				appendStringInfo(buf, "\\u%04x", (int) c);
+			else
+				appendStringInfoCharMacro(buf, c);
+			break;
+	}
+}
 
 /*
- * Produce a JSON string literal, properly escaping characters in the text.
+ * escape_json_cstring
+ *		Produce a JSON string literal.  Same as escape_json() except takes a
+ *		NUL-terminated string as input.
  */
 void
-escape_json(StringInfo buf, const char *str)
+escape_json_cstring(StringInfo buf, const char *str)
 {
-	const char *p;
+	appendStringInfoCharMacro(buf, '"');
+
+	for (; *str != '\0'; str++)
+		escape_json_char(buf, *str);
 
 	appendStringInfoCharMacro(buf, '"');
-	for (p = str; *p; p++)
-	{
-		switch (*p)
-		{
-			case '\b':
-				appendStringInfoString(buf, "\\b");
-				break;
-			case '\f':
-				appendStringInfoString(buf, "\\f");
-				break;
-			case '\n':
-				appendStringInfoString(buf, "\\n");
-				break;
-			case '\r':
-				appendStringInfoString(buf, "\\r");
-				break;
-			case '\t':
-				appendStringInfoString(buf, "\\t");
-				break;
-			case '"':
-				appendStringInfoString(buf, "\\\"");
-				break;
-			case '\\':
-				appendStringInfoString(buf, "\\\\");
-				break;
-			default:
-				if ((unsigned char) *p < ' ')
-					appendStringInfo(buf, "\\u%04x", (int) *p);
-				else
-					appendStringInfoCharMacro(buf, *p);
-				break;
-		}
-	}
+}
+
+/*
+ * Produce a JSON string literal, properly escaping the possibly not
+ * NUL-terminated characters in 'str'.  'len' defines the number of bytes from
+ * 'str' to process.
+ */
+void
+escape_json(StringInfo buf, const char *str, int len)
+{
+	appendStringInfoCharMacro(buf, '"');
+
+	for (int i = 0; i < len; i++)
+		escape_json_char(buf, str[i]);
+
 	appendStringInfoCharMacro(buf, '"');
 }
 
+/*
+ * escape_json_from_text
+ *		Append 't' onto 'buf' and escape using escape_json.
+ *
+ * This is more efficient than calling text_to_cstring and appending the
+ * result as that could require an additional palloc and memcpy.
+ */
+void
+escape_json_from_text(StringInfo buf, const text *t)
+{
+	/* must cast away the const, unfortunately */
+	text *tunpacked = pg_detoast_datum_packed(unconstify(text *, t));
+	int len = VARSIZE_ANY_EXHDR(tunpacked);
+	char *str;
+
+	str = VARDATA_ANY(tunpacked);
+
+	escape_json(buf, str, len);
+
+	/* pfree any detoasted values */
+	if (tunpacked != t)
+		pfree(tunpacked);
+}
+
 /* Semantic actions for key uniqueness check */
 static JsonParseErrorType
 json_unique_object_start(void *_state)
diff --git a/src/backend/utils/adt/jsonb.c b/src/backend/utils/adt/jsonb.c
index e4562b3c6c..f24d8003be 100644
--- a/src/backend/utils/adt/jsonb.c
+++ b/src/backend/utils/adt/jsonb.c
@@ -354,7 +354,7 @@ jsonb_put_escaped_value(StringInfo out, JsonbValue *scalarVal)
 			appendBinaryStringInfo(out, "null", 4);
 			break;
 		case jbvString:
-			escape_json(out, pnstrdup(scalarVal->val.string.val, scalarVal->val.string.len));
+			escape_json(out, scalarVal->val.string.val, scalarVal->val.string.len);
 			break;
 		case jbvNumeric:
 			appendStringInfoString(out,
diff --git a/src/backend/utils/adt/jsonfuncs.c b/src/backend/utils/adt/jsonfuncs.c
index 48c3f88140..fd3c6b8f43 100644
--- a/src/backend/utils/adt/jsonfuncs.c
+++ b/src/backend/utils/adt/jsonfuncs.c
@@ -3142,8 +3142,8 @@ populate_scalar(ScalarIOData *io, Oid typid, int32 typmod, JsValue *jsv,
 		}
 		else
 		{
-			/* string is already null-terminated */
 			str = unconstify(char *, json);
+			len = strlen(str);
 		}
 
 		/* If converting to json/jsonb, make string into valid JSON literal */
@@ -3153,7 +3153,7 @@ populate_scalar(ScalarIOData *io, Oid typid, int32 typmod, JsValue *jsv,
 			StringInfoData buf;
 
 			initStringInfo(&buf);
-			escape_json(&buf, str);
+			escape_json(&buf, str, len);
 			/* free temporary buffer */
 			if (str != json)
 				pfree(str);
@@ -4446,7 +4446,7 @@ sn_object_field_start(void *state, char *fname, bool isnull)
 	 * Unfortunately we don't have the quoted and escaped string any more, so
 	 * we have to re-escape it.
 	 */
-	escape_json(_state->strval, fname);
+	escape_json_cstring(_state->strval, fname);
 
 	appendStringInfoCharMacro(_state->strval, ':');
 
@@ -4477,7 +4477,7 @@ sn_scalar(void *state, char *token, JsonTokenType tokentype)
 	}
 
 	if (tokentype == JSON_TOKEN_STRING)
-		escape_json(_state->strval, token);
+		escape_json_cstring(_state->strval, token);
 	else
 		appendStringInfoString(_state->strval, token);
 
@@ -5909,7 +5909,7 @@ transform_string_values_object_field_start(void *state, char *fname, bool isnull
 	 * Unfortunately we don't have the quoted and escaped string any more, so
 	 * we have to re-escape it.
 	 */
-	escape_json(_state->strval, fname);
+	escape_json_cstring(_state->strval, fname);
 	appendStringInfoCharMacro(_state->strval, ':');
 
 	return JSON_SUCCESS;
@@ -5935,7 +5935,7 @@ transform_string_values_scalar(void *state, char *token, JsonTokenType tokentype
 	{
 		text	   *out = _state->action(_state->action_state, token, strlen(token));
 
-		escape_json(_state->strval, text_to_cstring(out));
+		escape_json_from_text(_state->strval, out);
 	}
 	else
 		appendStringInfoString(_state->strval, token);
diff --git a/src/backend/utils/adt/jsonpath.c b/src/backend/utils/adt/jsonpath.c
index 11e6193e96..82d65e4d4f 100644
--- a/src/backend/utils/adt/jsonpath.c
+++ b/src/backend/utils/adt/jsonpath.c
@@ -523,6 +523,8 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 {
 	JsonPathItem elem;
 	int			i;
+	int32		len;
+	char	   *str;
 
 	check_stack_depth();
 	CHECK_FOR_INTERRUPTS();
@@ -533,7 +535,8 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 			appendStringInfoString(buf, "null");
 			break;
 		case jpiString:
-			escape_json(buf, jspGetString(v, NULL));
+			str = jspGetString(v, &len);
+			escape_json(buf, str, len);
 			break;
 		case jpiNumeric:
 			if (jspHasNext(v))
@@ -662,7 +665,8 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 		case jpiKey:
 			if (inKey)
 				appendStringInfoChar(buf, '.');
-			escape_json(buf, jspGetString(v, NULL));
+			str = jspGetString(v, &len);
+			escape_json(buf, str, len);
 			break;
 		case jpiCurrent:
 			Assert(!inKey);
@@ -674,7 +678,8 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 			break;
 		case jpiVariable:
 			appendStringInfoChar(buf, '$');
-			escape_json(buf, jspGetString(v, NULL));
+			str = jspGetString(v, &len);
+			escape_json(buf, str, len);
 			break;
 		case jpiFilter:
 			appendStringInfoString(buf, "?(");
@@ -732,7 +737,9 @@ printJsonPathItem(StringInfo buf, JsonPathItem *v, bool inKey,
 
 			appendStringInfoString(buf, " like_regex ");
 
-			escape_json(buf, v->content.like_regex.pattern);
+			escape_json(buf,
+						v->content.like_regex.pattern,
+						v->content.like_regex.patternlen);
 
 			if (v->content.like_regex.flags)
 			{
diff --git a/src/backend/utils/error/jsonlog.c b/src/backend/utils/error/jsonlog.c
index bd0124869d..bd21f6ef58 100644
--- a/src/backend/utils/error/jsonlog.c
+++ b/src/backend/utils/error/jsonlog.c
@@ -49,11 +49,11 @@ appendJSONKeyValue(StringInfo buf, const char *key, const char *value,
 		return;
 
 	appendStringInfoChar(buf, ',');
-	escape_json(buf, key);
+	escape_json_cstring(buf, key);
 	appendStringInfoChar(buf, ':');
 
 	if (escape_value)
-		escape_json(buf, value);
+		escape_json_cstring(buf, value);
 	else
 		appendStringInfoString(buf, value);
 }
@@ -143,9 +143,9 @@ write_jsonlog(ErrorData *edata)
 	 * First property does not use appendJSONKeyValue as it does not have
 	 * comma prefix.
 	 */
-	escape_json(&buf, "timestamp");
+	escape_json(&buf, "timestamp", strlen("timestamp"));
 	appendStringInfoChar(&buf, ':');
-	escape_json(&buf, log_time);
+	escape_json_cstring(&buf, log_time);
 
 	/* username */
 	if (MyProcPort)
diff --git a/src/include/utils/json.h b/src/include/utils/json.h
index 6d7f1b387d..8ede8d0bd6 100644
--- a/src/include/utils/json.h
+++ b/src/include/utils/json.h
@@ -17,7 +17,9 @@
 #include "lib/stringinfo.h"
 
 /* functions in json.c */
-extern void escape_json(StringInfo buf, const char *str);
+extern void escape_json_cstring(StringInfo buf, const char *str);
+extern void escape_json(StringInfo buf, const char *str, int len);
+extern void escape_json_from_text(StringInfo buf, const text *t);
 extern char *JsonEncodeDateTime(char *buf, Datum value, Oid typid,
 								const int *tzp);
 extern bool to_json_is_immutable(Oid typoid);
-- 
2.34.1

v3-0002-Use-SIMD-processing-for-escape_json.patchapplication/octet-stream; name=v3-0002-Use-SIMD-processing-for-escape_json.patchDownload
From 490f83765f7765659d5efc4218da6ef807853d79 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Thu, 23 May 2024 10:53:23 +1200
Subject: [PATCH v3 2/3] Use SIMD processing for escape_json()

---
 src/backend/utils/adt/json.c       | 72 +++++++++++++++++++++++++++++-
 src/test/regress/expected/json.out | 44 ++++++++++++++++++
 src/test/regress/sql/json.sql      |  8 ++++
 3 files changed, 122 insertions(+), 2 deletions(-)

diff --git a/src/backend/utils/adt/json.c b/src/backend/utils/adt/json.c
index 7934cf62fb..a266f60ff3 100644
--- a/src/backend/utils/adt/json.c
+++ b/src/backend/utils/adt/json.c
@@ -19,6 +19,7 @@
 #include "funcapi.h"
 #include "libpq/pqformat.h"
 #include "miscadmin.h"
+#include "port/simd.h"
 #include "utils/array.h"
 #include "utils/builtins.h"
 #include "utils/date.h"
@@ -1597,11 +1598,78 @@ escape_json_cstring(StringInfo buf, const char *str)
 void
 escape_json(StringInfo buf, const char *str, int len)
 {
+	int i = 0;
+	int copypos = 0;
+
+	Assert(len >= 0);
+
 	appendStringInfoCharMacro(buf, '"');
 
-	for (int i = 0; i < len; i++)
-		escape_json_char(buf, str[i]);
+	for (;;)
+	{
+		Vector8 chunk;
+		int		vlen;
+
+		/*
+		 * Figure out how many bytes to process using SIMD.  Round 'len' down
+		 * to the previous multiple of sizeof(Vector8), assuming that's a
+		 * power-of-2.
+		 */
+		vlen = len & (int) (~(sizeof(Vector8) - 1));
+
+		/*
+		 * To speed this up try searching sizeof(Vector8) bytes at once for
+		 * special characters that we need to escape.  When we find one, we
+		 * fall out of this first loop and copy the parts we've vector
+		 * searched before processing the special-char vector byte-by-byte.
+		 * Once we're done with that, come back and try doing vector searching
+		 * again.  We'll also process the tail end of the string byte-by-byte.
+		 */
+		for (; i < vlen; i += sizeof(Vector8))
+		{
+			vector8_load(&chunk, (const uint8 *) &str[i]);
+
+			/*
+			 * Break on anything less than ' ' or if we find a '"' or '\\'.
+			 * Those need special handling.  That's done in the per-byte loop.
+			 */
+			if (vector8_has_le(chunk, (unsigned char) 0x1F) ||
+				vector8_has(chunk, (unsigned char) '"') ||
+				vector8_has(chunk, (unsigned char) '\\'))
+				break;
+		}
+
+		/*
+		 * Write to the destination up to the point of that we've vector
+		 * searched so far.  Do this only when switching into per-byte mode
+		 * rather than once every sizeof(Vector8) bytes.
+		 */
+		if (copypos < i)
+		{
+			appendBinaryStringInfo(buf, &str[copypos], i - copypos);
+			copypos = i;
+		}
+
+		/*
+		 * Per-byte loop for Vector8s containing special chars and for
+		 * processing the tail of the string.
+		 */
+		for (int b = 0; b < sizeof(Vector8); b++)
+		{
+			/* check if we've finished */
+			if (i == len)
+				goto done;
+
+			Assert(i < len);
+
+			escape_json_char(buf, str[i++]);
+		}
+
+		copypos = i;
+		/* We're not done yet.  Try the SIMD search again */
+	}
 
+done:
 	appendStringInfoCharMacro(buf, '"');
 }
 
diff --git a/src/test/regress/expected/json.out b/src/test/regress/expected/json.out
index aa29bc597b..bfcc26c531 100644
--- a/src/test/regress/expected/json.out
+++ b/src/test/regress/expected/json.out
@@ -55,6 +55,50 @@ SELECT ('"'||repeat('.', 12)||'abc\n"')::json; -- OK, legal escapes
  "............abc\n"
 (1 row)
 
+-- Stress testing of JSON escape code
+CREATE TABLE json_escape (very_long_column_name_to_test_json_escape text);
+INSERT INTO json_escape SELECT repeat('a', a) FROM generate_series(0,33) a;
+-- Test various lengths of strings to validate SIMD processing to escape
+-- special chars in the JSON.
+SELECT row_to_json(j)::jsonb FROM json_escape j;
+                                    row_to_json                                     
+------------------------------------------------------------------------------------
+ {"very_long_column_name_to_test_json_escape": ""}
+ {"very_long_column_name_to_test_json_escape": "a"}
+ {"very_long_column_name_to_test_json_escape": "aa"}
+ {"very_long_column_name_to_test_json_escape": "aaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+ {"very_long_column_name_to_test_json_escape": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+(34 rows)
+
 -- see json_encoding test for input with unicode escapes
 -- Numbers.
 SELECT '1'::json;				-- OK
diff --git a/src/test/regress/sql/json.sql b/src/test/regress/sql/json.sql
index ec57dfe707..0e7ca2f5af 100644
--- a/src/test/regress/sql/json.sql
+++ b/src/test/regress/sql/json.sql
@@ -12,6 +12,14 @@ SELECT '"\v"'::json;			-- ERROR, not a valid JSON escape
 SELECT ('"'||repeat('.', 12)||'abc"')::json; -- OK
 SELECT ('"'||repeat('.', 12)||'abc\n"')::json; -- OK, legal escapes
 
+-- Stress testing of JSON escape code
+CREATE TABLE json_escape (very_long_column_name_to_test_json_escape text);
+INSERT INTO json_escape SELECT repeat('a', a) FROM generate_series(0,33) a;
+
+-- Test various lengths of strings to validate SIMD processing to escape
+-- special chars in the JSON.
+SELECT row_to_json(j)::jsonb FROM json_escape j;
+
 -- see json_encoding test for input with unicode escapes
 
 -- Numbers.
-- 
2.34.1

v3-0003-Special-case-text-type-conversion-in-datum_to_jso.patchapplication/octet-stream; name=v3-0003-Special-case-text-type-conversion-in-datum_to_jso.patchDownload
From 9c5caba16f1ebe046e61dc08b92917f4cf603b2f Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Thu, 23 May 2024 15:12:59 +1200
Subject: [PATCH v3 3/3] Special-case text type conversion in
 datum_to_json_internal

---
 src/backend/utils/adt/json.c | 13 ++++++++++---
 1 file changed, 10 insertions(+), 3 deletions(-)

diff --git a/src/backend/utils/adt/json.c b/src/backend/utils/adt/json.c
index a266f60ff3..371881dfd0 100644
--- a/src/backend/utils/adt/json.c
+++ b/src/backend/utils/adt/json.c
@@ -24,6 +24,7 @@
 #include "utils/builtins.h"
 #include "utils/date.h"
 #include "utils/datetime.h"
+#include "utils/fmgroids.h"
 #include "utils/json.h"
 #include "utils/jsonfuncs.h"
 #include "utils/lsyscache.h"
@@ -286,9 +287,15 @@ datum_to_json_internal(Datum val, bool is_null, StringInfo result,
 			pfree(jsontext);
 			break;
 		default:
-			outputstr = OidOutputFunctionCall(outfuncoid, val);
-			escape_json_cstring(result, outputstr);
-			pfree(outputstr);
+			/* special-case text types to save useless palloc/memcpy cycles */
+			if (outfuncoid == F_TEXTOUT || outfuncoid ==  F_VARCHAROUT || outfuncoid == F_BPCHAROUT)
+				escape_json_from_text(result, (text *) DatumGetPointer(val));
+			else
+			{
+				outputstr = OidOutputFunctionCall(outfuncoid, val);
+				escape_json_cstring(result, outputstr);
+				pfree(outputstr);
+			}
 			break;
 	}
 }
-- 
2.34.1

#9Heikki Linnakangas
hlinnaka@iki.fi
In reply to: David Rowley (#8)
1 attachment(s)
Re: Speed up JSON escape processing with SIMD plus other optimisations

On 02/07/2024 07:49, David Rowley wrote:

I've attached a rebased set of patches. The previous set no longer applied.

I looked briefly at the first patch. Seems reasonable.

One little thing that caught my eye is that in populate_scalar(), you
sometimes make a temporary copy of the string to add the
null-terminator, but then call escape_json() which doesn't need the
null-terminator anymore. See attached patch to avoid that. However, it's
not clear to me how to reach that codepath, or if it reachable at all. I
tried to add a NOTICE there and ran the regression tests, but got no
failures.

--
Heikki Linnakangas
Neon (https://neon.tech)

Attachments:

avoid-possibly-unreachable-palloc.patch.txttext/plain; charset=UTF-8; name=avoid-possibly-unreachable-palloc.patch.txtDownload
diff --git a/src/backend/utils/adt/jsonfuncs.c b/src/backend/utils/adt/jsonfuncs.c
index fd3c6b8f432..55c0fc4d73d 100644
--- a/src/backend/utils/adt/jsonfuncs.c
+++ b/src/backend/utils/adt/jsonfuncs.c
@@ -3133,18 +3133,6 @@ populate_scalar(ScalarIOData *io, Oid typid, int32 typmod, JsValue *jsv,
 
 		json = jsv->val.json.str;
 		Assert(json);
-		if (len >= 0)
-		{
-			/* Need to copy non-null-terminated string */
-			str = palloc(len + 1 * sizeof(char));
-			memcpy(str, json, len);
-			str[len] = '\0';
-		}
-		else
-		{
-			str = unconstify(char *, json);
-			len = strlen(str);
-		}
 
 		/* If converting to json/jsonb, make string into valid JSON literal */
 		if ((typid == JSONOID || typid == JSONBOID) &&
@@ -3153,12 +3141,24 @@ populate_scalar(ScalarIOData *io, Oid typid, int32 typmod, JsValue *jsv,
 			StringInfoData buf;
 
 			initStringInfo(&buf);
-			escape_json(&buf, str, len);
-			/* free temporary buffer */
-			if (str != json)
-				pfree(str);
+			if (len >= 0)
+				escape_json(&buf, json, len);
+			else
+				escape_json_cstring(&buf, json);
 			str = buf.data;
 		}
+		else if (len >= 0)
+		{
+			/* Need to copy non-null-terminated string */
+			str = palloc(len + 1 * sizeof(char));
+			memcpy(str, json, len);
+			str[len] = '\0';
+		}
+		else
+		{
+			/* string is already null-terminated */
+			str = unconstify(char *, json);
+		}
 	}
 	else
 	{
#10David Rowley
dgrowleyml@gmail.com
In reply to: Heikki Linnakangas (#9)
1 attachment(s)
Re: Speed up JSON escape processing with SIMD plus other optimisations

On Wed, 24 Jul 2024 at 22:55, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

On 02/07/2024 07:49, David Rowley wrote:

I've attached a rebased set of patches. The previous set no longer applied.

I looked briefly at the first patch. Seems reasonable.

One little thing that caught my eye is that in populate_scalar(), you
sometimes make a temporary copy of the string to add the
null-terminator, but then call escape_json() which doesn't need the
null-terminator anymore. See attached patch to avoid that. However, it's
not clear to me how to reach that codepath, or if it reachable at all. I
tried to add a NOTICE there and ran the regression tests, but got no
failures.

Thanks for noticing that. It seems like a good simplification
regardless. I've incorporated it.

I made another pass over the 0001 and 0003 patches and after a bit of
renaming, I pushed the result. I ended up keeping escape_json() as-is
and giving the new function the name escape_json_with_len(). The text
version is named ecape_json_text(). I think originally I did it the
other way as thought I'd have been able to adjust more locations than
I did. Having it this way around is slightly less churn.

I did another round of testing on the SIMD patch (attached as v5-0001)
as I wondered if the SIMD loop maybe shouldn't wait too long before
copying the bytes to the destination string. I had wondered if the
JSON string was very large that if we looked ahead too far that by the
time we flush those bytes out to the destination buffer, we'd have
started eviction of L1 cachelines for parts of the buffer that are
still to be flushed. I put this to the test (test 3) and found that
with a 1MB JSON string it is faster to flush every 512 bytes than it
is to only flush after checking the entire 1MB. With a 10kB JSON
string (test 2), the extra code to flush every 512 bytes seems to slow
things down. I'm a bit undecided about whether the flushing is
worthwhile or not. It really depend on the length of JSON strings we'd
like to optimise for. It might be possible to get the best of both but
I think it might require manually implementing portions of
appendBinaryStringInfo(). I'd rather not go there. Does anyone have
any thoughts about that?

Test 2 (10KB) does show a ~261% performance increase but dropped to
~227% flushing every 512 bytes. Test 3 (1MB) increased performance by
~99% without early flushing and increased to ~156% flushing every 512
bytes.

bench.sql: select row_to_json(j1)::jsonb from j1;

## Test 1 (variable JSON strings up to 1KB)
create table j1 (very_long_column_name_to_test_json_escape text);
insert into j1 select repeat('x', x) from generate_series(0,1024)x;
vacuum freeze j1;

master @ 17a5871d:
$ for i in {1..3}; do pgbench -n -f bench.sql -T 10 -M prepared
postgres | grep tps; done
tps = 364.410386 (without initial connection time)
tps = 367.914165 (without initial connection time)
tps = 365.794513 (without initial connection time)

master + v5-0001
$ for i in {1..3}; do pgbench -n -f bench.sql -T 10 -M prepared
postgres | grep tps; done
tps = 683.570613 (without initial connection time)
tps = 685.206578 (without initial connection time)
tps = 679.014056 (without initial connection time)

## Test 2 (10KB JSON strings)
create table j1 (very_long_column_name_to_test_json_escape text);
insert into j1 select repeat('x', 1024*10) from generate_series(0,1024)x;
vacuum freeze j1;

master @ 17a5871d:
$ for i in {1..3}; do pgbench -n -f bench.sql -T 10 -M prepared
postgres | grep tps; done
tps = 23.872630 (without initial connection time)
tps = 26.232014 (without initial connection time)
tps = 26.495739 (without initial connection time)

master + v5-0001
$ for i in {1..3}; do pgbench -n -f bench.sql -T 10 -M prepared
postgres | grep tps; done
tps = 96.813515 (without initial connection time)
tps = 96.023632 (without initial connection time)
tps = 99.630428 (without initial connection time)

master + v5-0001 ESCAPE_JSON_MAX_LOOKHEAD 512
$ for i in {1..3}; do pgbench -n -f bench.sql -T 10 -M prepared
postgres | grep tps; done
tps = 83.597442 (without initial connection time)
tps = 85.045554 (without initial connection time)
tps = 82.105907 (without initial connection time)

## Test 3 (1MB JSON strings)
create table j1 (very_long_column_name_to_test_json_escape text);
insert into j1 select repeat('x', 1024*1024) from generate_series(0,10)x;
vacuum freeze j1;

master @ 17a5871d:
$ for i in {1..3}; do pgbench -n -f bench.sql -T 10 -M prepared
postgres | grep tps; done
tps = 18.885922 (without initial connection time)
tps = 18.829701 (without initial connection time)
tps = 18.889369 (without initial connection time)

master v5-0001
$ for i in {1..3}; do pgbench -n -f bench.sql -T 10 -M prepared
postgres | grep tps; done
tps = 37.464967 (without initial connection time)
tps = 37.536676 (without initial connection time)
tps = 37.561387 (without initial connection time)

master + v5-0001 ESCAPE_JSON_MAX_LOOKHEAD 512
$ for i in {1..3}; do pgbench -n -f bench.sql -T 10 -M prepared
postgres | grep tps; done
tps = 48.296320 (without initial connection time)
tps = 48.118151 (without initial connection time)
tps = 48.507530 (without initial connection time)

David

Attachments:

v5-0001-Optimize-escaping-of-JSON-strings-using-SIMD.patchapplication/octet-stream; name=v5-0001-Optimize-escaping-of-JSON-strings-using-SIMD.patchDownload
From 58a913589b0b89a8c5ece50b5f8de6c9321a8366 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Thu, 23 May 2024 10:53:23 +1200
Subject: [PATCH v5] Optimize escaping of JSON strings using SIMD

Here we adjust escape_json_with_len() to make use of SIMD to allow
processing of up to 16-bytes at a time rather than processing a single
byte at a time.  This has been shown to speed up escaping of JSON
strings significantly, especially when no escaping is required.

Reviewed-by: Melih Mutlu
Discussion: https://postgr.es/m/CAApHDvpLXwMZvbCKcdGfU9XQjGCDm7tFpRdTXuB9PVgpNUYfEQ@mail.gmail.com
---
 src/backend/utils/adt/json.c       | 82 +++++++++++++++++++++++++++++-
 src/test/regress/expected/json.out | 48 +++++++++++++++++
 src/test/regress/sql/json.sql      |  7 +++
 3 files changed, 135 insertions(+), 2 deletions(-)

diff --git a/src/backend/utils/adt/json.c b/src/backend/utils/adt/json.c
index be7bc46038..4e86d734e4 100644
--- a/src/backend/utils/adt/json.c
+++ b/src/backend/utils/adt/json.c
@@ -19,6 +19,7 @@
 #include "funcapi.h"
 #include "libpq/pqformat.h"
 #include "miscadmin.h"
+#include "port/simd.h"
 #include "utils/array.h"
 #include "utils/builtins.h"
 #include "utils/date.h"
@@ -1603,11 +1604,88 @@ escape_json(StringInfo buf, const char *str)
 void
 escape_json_with_len(StringInfo buf, const char *str, int len)
 {
+	int			i = 0;
+	int			copypos = 0;
+	int			vlen;
+
+	Assert(len >= 0);
+
+	/*
+	 * Figure out how many bytes to process using SIMD.  Round 'len' down to
+	 * the previous multiple of sizeof(Vector8), assuming that's a power-of-2.
+	 */
+	vlen = len & (int) (~(sizeof(Vector8) - 1));
+
 	appendStringInfoCharMacro(buf, '"');
 
-	for (int i = 0; i < len; i++)
-		escape_json_char(buf, str[i]);
+	for (;;)
+	{
+		/*
+		 * To speed this up try searching sizeof(Vector8) bytes at once for
+		 * special characters that we need to escape.  When we find one, we
+		 * fall out of the Vector8 loop and copy the portion we've vector
+		 * searched and then we process sizeof(Vector8) bytes one byte at a
+		 * time.  Once done, come back and try doing vector searching again.
+		 * We'll also process any remaining bytes at the tail end of the
+		 * string byte-by-byte.  This optimization assumes special characters
+		 * are not that common.
+		 */
+		for (; i < vlen; i += sizeof(Vector8))
+		{
+			Vector8		chunk;
+
+			vector8_load(&chunk, (const uint8 *) &str[i]);
+
+			/*
+			 * Break on anything less than ' ' or if we find a '"' or '\\'.
+			 * Those need special handling.  That's done in the per-byte loop.
+			 */
+			if (vector8_has_le(chunk, (unsigned char) 0x1F) ||
+				vector8_has(chunk, (unsigned char) '"') ||
+				vector8_has(chunk, (unsigned char) '\\'))
+				break;
+
+/* #define ESCAPE_JSON_MAX_LOOKHEAD 512 */
+#ifdef ESCAPE_JSON_MAX_LOOKHEAD
+			if (i - copypos >= ESCAPE_JSON_MAX_LOOKHEAD)
+			{
+				appendBinaryStringInfo(buf, &str[copypos], i - copypos);
+				copypos = i;
+			}
+#endif
+		}
+
+		/*
+		 * Write to the destination up to the point of that we've vector
+		 * searched so far.  Do this only when switching into per-byte mode
+		 * rather than once every sizeof(Vector8) bytes.
+		 */
+		if (copypos < i)
+		{
+			appendBinaryStringInfo(buf, &str[copypos], i - copypos);
+			copypos = i;
+		}
+
+		/*
+		 * Per-byte loop for Vector8s containing special chars and for
+		 * processing the tail of the string.
+		 */
+		for (int b = 0; b < sizeof(Vector8); b++)
+		{
+			/* check if we've finished */
+			if (i == len)
+				goto done;
+
+			Assert(i < len);
+
+			escape_json_char(buf, str[i++]);
+		}
+
+		copypos = i;
+		/* We're not done yet.  Try the vector search again */
+	}
 
+done:
 	appendStringInfoCharMacro(buf, '"');
 }
 
diff --git a/src/test/regress/expected/json.out b/src/test/regress/expected/json.out
index aa29bc597b..c8e9b97f0a 100644
--- a/src/test/regress/expected/json.out
+++ b/src/test/regress/expected/json.out
@@ -55,6 +55,54 @@ SELECT ('"'||repeat('.', 12)||'abc\n"')::json; -- OK, legal escapes
  "............abc\n"
 (1 row)
 
+-- Test various lengths of strings to validate SIMD processing to escape
+-- special chars in the JSON.
+SELECT row_to_json(j)::jsonb FROM (
+  SELECT left(E'abcdefghijklmnopqrstuvwxyz0123456"\t78', a) AS very_long_column_name_to_test_json_escape
+  FROM generate_series(0,37) a
+) j;
+                                       row_to_json                                        
+------------------------------------------------------------------------------------------
+ {"very_long_column_name_to_test_json_escape": ""}
+ {"very_long_column_name_to_test_json_escape": "a"}
+ {"very_long_column_name_to_test_json_escape": "ab"}
+ {"very_long_column_name_to_test_json_escape": "abc"}
+ {"very_long_column_name_to_test_json_escape": "abcd"}
+ {"very_long_column_name_to_test_json_escape": "abcde"}
+ {"very_long_column_name_to_test_json_escape": "abcdef"}
+ {"very_long_column_name_to_test_json_escape": "abcdefg"}
+ {"very_long_column_name_to_test_json_escape": "abcdefgh"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghi"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghij"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijk"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijkl"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklm"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmn"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmno"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnop"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopq"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqr"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrs"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrst"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstu"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuv"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvw"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwx"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxy"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz01"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz012"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0123"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz01234"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz012345"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0123456"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0123456\""}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0123456\"\t"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0123456\"\t7"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0123456\"\t78"}
+(38 rows)
+
 -- see json_encoding test for input with unicode escapes
 -- Numbers.
 SELECT '1'::json;				-- OK
diff --git a/src/test/regress/sql/json.sql b/src/test/regress/sql/json.sql
index ec57dfe707..9bf33115d4 100644
--- a/src/test/regress/sql/json.sql
+++ b/src/test/regress/sql/json.sql
@@ -12,6 +12,13 @@ SELECT '"\v"'::json;			-- ERROR, not a valid JSON escape
 SELECT ('"'||repeat('.', 12)||'abc"')::json; -- OK
 SELECT ('"'||repeat('.', 12)||'abc\n"')::json; -- OK, legal escapes
 
+-- Test various lengths of strings to validate SIMD processing to escape
+-- special chars in the JSON.
+SELECT row_to_json(j)::jsonb FROM (
+  SELECT left(E'abcdefghijklmnopqrstuvwxyz0123456"\t78', a) AS very_long_column_name_to_test_json_escape
+  FROM generate_series(0,37) a
+) j;
+
 -- see json_encoding test for input with unicode escapes
 
 -- Numbers.
-- 
2.34.1

#11David Rowley
dgrowleyml@gmail.com
In reply to: David Rowley (#10)
2 attachment(s)
Re: Speed up JSON escape processing with SIMD plus other optimisations

On Sun, 28 Jul 2024 at 00:51, David Rowley <dgrowleyml@gmail.com> wrote:

I did another round of testing on the SIMD patch (attached as v5-0001)
as I wondered if the SIMD loop maybe shouldn't wait too long before
copying the bytes to the destination string. I had wondered if the
JSON string was very large that if we looked ahead too far that by the
time we flush those bytes out to the destination buffer, we'd have
started eviction of L1 cachelines for parts of the buffer that are
still to be flushed. I put this to the test (test 3) and found that
with a 1MB JSON string it is faster to flush every 512 bytes than it
is to only flush after checking the entire 1MB. With a 10kB JSON
string (test 2), the extra code to flush every 512 bytes seems to slow
things down.

I'd been wondering why test 2 (10KB) with v5-0001
ESCAPE_JSON_MAX_LOOKHEAD 512 was not better than v5-0001. It occurred
to me that when using 10KB vs 1MB and flushing the buffer every 512
bytes that enlargeStringInfo() is called more often proportionally to
the length of the string. Doing that causes more repalloc/memcpy work
in stringinfo.c.

We can reduce the repalloc/memcpy work by calling enlargeStringInfo()
once at the beginning of escape_json_with_len(). We already know the
minimum length we're going to append so we might as well do that.

After making that change, doing the 512-byte flushing no longer slows
down test 2.

Here are the results of testing v6-0001. I've added test 4, which
tests a very short string to ensure there are no performance
regressions when we can't do SIMD. Test 2 patched came out 3.74x
faster than master.

## Test 1:
echo "select row_to_json(j1)::jsonb from j1;" > test1.sql
for i in {1..3}; do pgbench -n -f test1.sql -T 10 -M prepared postgres
| grep tps; done

master @ e6a963748:
tps = 339.560611
tps = 344.649009
tps = 343.246659

v6-0001:
tps = 610.734018
tps = 628.297298
tps = 630.028225

v6-0001 ESCAPE_JSON_MAX_LOOKHEAD 512:
tps = 557.562866
tps = 626.476618
tps = 618.665045

## Test 2:
echo "select row_to_json(j2)::jsonb from j2;" > test2.sql
for i in {1..3}; do pgbench -n -f test2.sql -T 10 -M prepared postgres
| grep tps; done

master @ e6a963748:
tps = 25.633934
tps = 18.580632
tps = 25.395866

v6-0001:
tps = 89.325752
tps = 91.277016
tps = 86.289533

v6-0001 ESCAPE_JSON_MAX_LOOKHEAD 512:
tps = 85.194479
tps = 90.054279
tps = 85.483279

## Test 3:
echo "select row_to_json(j3)::jsonb from j3;" > test3.sql
for i in {1..3}; do pgbench -n -f test3.sql -T 10 -M prepared postgres
| grep tps; done

master @ e6a963748:
tps = 18.863420
tps = 18.866374
tps = 18.791395

v6-0001:
tps = 38.990681
tps = 37.893820
tps = 38.057235

v6-0001 ESCAPE_JSON_MAX_LOOKHEAD 512:
tps = 46.076842
tps = 46.400413
tps = 46.165491

## Test 4:
echo "select row_to_json(j4)::jsonb from j4;" > test4.sql
for i in {1..3}; do pgbench -n -f test4.sql -T 10 -M prepared postgres
| grep tps; done

master @ e6a963748:
tps = 1700.888458
tps = 1684.753818
tps = 1690.262772

v6-0001:
tps = 1721.821561
tps = 1699.189207
tps = 1663.618117

v6-0001 ESCAPE_JSON_MAX_LOOKHEAD 512:
tps = 1701.565562
tps = 1706.310398
tps = 1687.585128

I'm pretty happy with this now so I'd like to commit this and move on
to other work. Doing "#define ESCAPE_JSON_MAX_LOOKHEAD 512", seems
like the right thing. If anyone else wants to verify my results or
take a look at the patch, please do so.

David

Attachments:

setup.sqlapplication/octet-stream; name=setup.sqlDownload
v6-0001-Optimize-escaping-of-JSON-strings-using-SIMD.patchapplication/octet-stream; name=v6-0001-Optimize-escaping-of-JSON-strings-using-SIMD.patchDownload
From 02ae2dc0f53dbefab972e5efb47821e66a6cd678 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Thu, 23 May 2024 10:53:23 +1200
Subject: [PATCH v6] Optimize escaping of JSON strings using SIMD

Here we adjust escape_json_with_len() to make use of SIMD to allow
processing of up to 16-bytes at a time rather than processing a single
byte at a time.  This has been shown to speed up escaping of JSON
strings significantly, especially when no escaping is required.

Reviewed-by: Melih Mutlu
Discussion: https://postgr.es/m/CAApHDvpLXwMZvbCKcdGfU9XQjGCDm7tFpRdTXuB9PVgpNUYfEQ@mail.gmail.com
---
 src/backend/utils/adt/json.c       | 89 +++++++++++++++++++++++++++++-
 src/test/regress/expected/json.out | 48 ++++++++++++++++
 src/test/regress/sql/json.sql      |  7 +++
 3 files changed, 142 insertions(+), 2 deletions(-)

diff --git a/src/backend/utils/adt/json.c b/src/backend/utils/adt/json.c
index be7bc46038..eb5548384e 100644
--- a/src/backend/utils/adt/json.c
+++ b/src/backend/utils/adt/json.c
@@ -19,6 +19,7 @@
 #include "funcapi.h"
 #include "libpq/pqformat.h"
 #include "miscadmin.h"
+#include "port/simd.h"
 #include "utils/array.h"
 #include "utils/builtins.h"
 #include "utils/date.h"
@@ -1603,11 +1604,95 @@ escape_json(StringInfo buf, const char *str)
 void
 escape_json_with_len(StringInfo buf, const char *str, int len)
 {
+	int			i = 0;
+	int			copypos = 0;
+	int			vlen;
+
+	Assert(len >= 0);
+
+	/*
+	 * Since we know the minimum length we'll need to append, let's just
+	 * enlarge the buffer now rather than than incrementally making more space
+	 * when we run out.  Add two extra bytes for the enclosing quotes.
+	 */
+	enlargeStringInfo(buf, len + 2);
+
+	/*
+	 * Figure out how many bytes to process using SIMD.  Round 'len' down to
+	 * the previous multiple of sizeof(Vector8), assuming that's a power-of-2.
+	 */
+	vlen = len & (int) (~(sizeof(Vector8) - 1));
+
 	appendStringInfoCharMacro(buf, '"');
 
-	for (int i = 0; i < len; i++)
-		escape_json_char(buf, str[i]);
+	for (;;)
+	{
+		/*
+		 * To speed this up try searching sizeof(Vector8) bytes at once for
+		 * special characters that we need to escape.  When we find one, we
+		 * fall out of the Vector8 loop and copy the portion we've vector
+		 * searched and then we process sizeof(Vector8) bytes one byte at a
+		 * time.  Once done, come back and try doing vector searching again.
+		 * We'll also process any remaining bytes at the tail end of the
+		 * string byte-by-byte.  This optimization assumes special characters
+		 * are not that common.
+		 */
+		for (; i < vlen; i += sizeof(Vector8))
+		{
+			Vector8		chunk;
+
+			vector8_load(&chunk, (const uint8 *) &str[i]);
+
+			/*
+			 * Break on anything less than ' ' or if we find a '"' or '\\'.
+			 * Those need special handling.  That's done in the per-byte loop.
+			 */
+			if (vector8_has_le(chunk, (unsigned char) 0x1F) ||
+				vector8_has(chunk, (unsigned char) '"') ||
+				vector8_has(chunk, (unsigned char) '\\'))
+				break;
+
+/* #define ESCAPE_JSON_MAX_LOOKHEAD 512 */
+#ifdef ESCAPE_JSON_MAX_LOOKHEAD
+			if (i - copypos >= ESCAPE_JSON_MAX_LOOKHEAD)
+			{
+				appendBinaryStringInfo(buf, &str[copypos], i - copypos);
+				copypos = i;
+			}
+#endif
+		}
+
+		/*
+		 * Write to the destination up to the point of that we've vector
+		 * searched so far.  Do this only when switching into per-byte mode
+		 * rather than once every sizeof(Vector8) bytes.
+		 */
+		if (copypos < i)
+		{
+			appendBinaryStringInfo(buf, &str[copypos], i - copypos);
+			copypos = i;
+		}
+
+		/*
+		 * Per-byte loop for Vector8s containing special chars and for
+		 * processing the tail of the string.
+		 */
+		for (int b = 0; b < sizeof(Vector8); b++)
+		{
+			/* check if we've finished */
+			if (i == len)
+				goto done;
+
+			Assert(i < len);
+
+			escape_json_char(buf, str[i++]);
+		}
+
+		copypos = i;
+		/* We're not done yet.  Try the vector search again */
+	}
 
+done:
 	appendStringInfoCharMacro(buf, '"');
 }
 
diff --git a/src/test/regress/expected/json.out b/src/test/regress/expected/json.out
index aa29bc597b..c8e9b97f0a 100644
--- a/src/test/regress/expected/json.out
+++ b/src/test/regress/expected/json.out
@@ -55,6 +55,54 @@ SELECT ('"'||repeat('.', 12)||'abc\n"')::json; -- OK, legal escapes
  "............abc\n"
 (1 row)
 
+-- Test various lengths of strings to validate SIMD processing to escape
+-- special chars in the JSON.
+SELECT row_to_json(j)::jsonb FROM (
+  SELECT left(E'abcdefghijklmnopqrstuvwxyz0123456"\t78', a) AS very_long_column_name_to_test_json_escape
+  FROM generate_series(0,37) a
+) j;
+                                       row_to_json                                        
+------------------------------------------------------------------------------------------
+ {"very_long_column_name_to_test_json_escape": ""}
+ {"very_long_column_name_to_test_json_escape": "a"}
+ {"very_long_column_name_to_test_json_escape": "ab"}
+ {"very_long_column_name_to_test_json_escape": "abc"}
+ {"very_long_column_name_to_test_json_escape": "abcd"}
+ {"very_long_column_name_to_test_json_escape": "abcde"}
+ {"very_long_column_name_to_test_json_escape": "abcdef"}
+ {"very_long_column_name_to_test_json_escape": "abcdefg"}
+ {"very_long_column_name_to_test_json_escape": "abcdefgh"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghi"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghij"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijk"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijkl"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklm"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmn"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmno"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnop"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopq"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqr"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrs"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrst"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstu"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuv"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvw"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwx"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxy"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz01"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz012"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0123"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz01234"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz012345"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0123456"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0123456\""}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0123456\"\t"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0123456\"\t7"}
+ {"very_long_column_name_to_test_json_escape": "abcdefghijklmnopqrstuvwxyz0123456\"\t78"}
+(38 rows)
+
 -- see json_encoding test for input with unicode escapes
 -- Numbers.
 SELECT '1'::json;				-- OK
diff --git a/src/test/regress/sql/json.sql b/src/test/regress/sql/json.sql
index ec57dfe707..9bf33115d4 100644
--- a/src/test/regress/sql/json.sql
+++ b/src/test/regress/sql/json.sql
@@ -12,6 +12,13 @@ SELECT '"\v"'::json;			-- ERROR, not a valid JSON escape
 SELECT ('"'||repeat('.', 12)||'abc"')::json; -- OK
 SELECT ('"'||repeat('.', 12)||'abc\n"')::json; -- OK, legal escapes
 
+-- Test various lengths of strings to validate SIMD processing to escape
+-- special chars in the JSON.
+SELECT row_to_json(j)::jsonb FROM (
+  SELECT left(E'abcdefghijklmnopqrstuvwxyz0123456"\t78', a) AS very_long_column_name_to_test_json_escape
+  FROM generate_series(0,37) a
+) j;
+
 -- see json_encoding test for input with unicode escapes
 
 -- Numbers.
-- 
2.34.1

#12David Rowley
dgrowleyml@gmail.com
In reply to: David Rowley (#11)
5 attachment(s)
Re: Speed up JSON escape processing with SIMD plus other optimisations

On Thu, 1 Aug 2024 at 16:15, David Rowley <dgrowleyml@gmail.com> wrote:

I'm pretty happy with this now so I'd like to commit this and move on
to other work. Doing "#define ESCAPE_JSON_MAX_LOOKHEAD 512", seems
like the right thing. If anyone else wants to verify my results or
take a look at the patch, please do so.

I did some more testing on this on a few different machines; apple M2
Ultra, AMD 7945HX and with a Raspberry Pi 4.

I've attached the results as graphs with the master time normalised to
1. I tried out quite a few different values for flushing the buffer,
256 bytes in powers of 2 up to 8192 bytes. It seems like each machine
has its own preference to what this should be set to, but no machine
seems to be too picky about the exact value. They're all small enough
values to fit in L1d cache on each of the CPUs. Test 4 shouldn't
change much as there's no SIMD going on in that test. You might notice
a bit of noise from all machines for test 4, apart from the M2. You
can assume a similar level of noise for tests 1 to 3 on each of the
machines. The Raspberry Pi does seem to prefer not flushing the
buffer until the end (listed as "patched" in the graphs). I suspect
that's because that CPU does better with less code. I've not taken
these results quite as seriously since it's likely a platform that we
wouldn't want to prefer when it comes to tuning optimisations. I was
mostly interested in not seeing regressions.

I think, if nobody else thinks differently, I'll rename
ESCAPE_JSON_MAX_LOOKHEAD to ESCAPE_JSON_FLUSH_AFTER and set it to 512.
The exact value does not seem to matter too much and 512 seems fine.
It's better for the M2 than the 7945HX, but not by much.

I've also attached the script I ran to get these results and also the
full results.

David

Attachments:

json_simd_results.txttext/plain; charset=US-ASCII; name=json_simd_results.txtDownload
Zen4_7945HX_Linux.pngimage/png; name=Zen4_7945HX_Linux.pngDownload
raspberrypi4.pngimage/png; name=raspberrypi4.pngDownload
�PNG


IHDR�����sRGB���gAMA���a	pHYs�����e��IDATx^��	�Us��_�mJ��bI�D=Q"��D�,!�"k!I��.IJ�li!���V����5����s����3���L�y�^�5����{g�����~�_���L���	 ���@�Dr@&"�2���r�����d���6p�@���w&z�
��Z�r��J�*V�B;��c�[���K����y��V�@w��!-_y��u[E����+[��U�D��+W.���������c��ow���y���l���83m����{�=��s�;������+�t����B�lj��=�y�f�5k�}�����sg�4i����y��������������k��f={��u��y���:d�G�N�@�C �QB�@�|���1�bcc���j�����wo�;w�w&k�1c�-]��;Y�Y@�|�\�i���#�*V�h�>��N+Q�bn��i���}�E����w���Tu���_��U��3Y��5kl��q�?@��r�k\w�q���[�b��q��Z�����g'���-ZX����3�k����K��������~K�������^Cn��}��G�����3�a
9�*���0�z��V�~�$�r[�l�?���;-�iM�49,�RZ���HSh8e�[�b�wderds
�.��2;��3�3	�-[�Zr@�o���.�R�Jyg��M-\��;�:T8y�d��}kR,���8
s�1v�9�xG	�>w���@j-Z��>�l�(��
�a����3������O?�t����8J���g��=��9��S��
�bbb��#Kq����M{��v�5���!YC8�k�C��3g�����#�%JX���]�OJ�m�fs�������+����N���3��Z�j�I'�t�t����4�u��Enm;?$L��2������?3=�[(��k(,��;���*���m��$7�AUQ?���-^��v���n/X���.]�=�^'O�<�|4�?���_�>��K���F?�Q���'�h��Us�?������$�:���n7et��u��J���5����|�%��k�g������:u��|��t��%K������?w-���P�FS�������*T�`��{��I����Z�`�}����Q���#1�A���~ht�}�
���/w�V������d5T�pP��W��4iU�Kr������u��������I�8Q��y�f�>}����;��gON�d���6h� ��?���]+�B=��O�t�o���}���}�aV\\�m����Ho����>���EC�7z�h�5q��D��
D�t�������z��n=�>?L�����#F��/�l���O���s�����{���
����C���*�Z����8�>��7��u
��0U��+���d����;=�B���qa��M�^q�������.~���.���^z��Y�GU)X	����B
?����hB��k����p���������#}n=����W�V�\�������=h�l��}S�o ��
�4�R!Trv��m�|��M�81�k���HT������?�`��������I�M` �b��.�
���~�[0�G���V�\�$�b
I�C�p�����-x@���`Q_��#�V�(����]0*��k��6K� �</����D�Fj��+���v���j�'U�)RE����y�"E�3I)0�����}P������������S�U>��S-x��s
�t�r���}1��X
�|z?����V�s�w�y��
��K?u=��{n��B�W~u�>;�����^�~��v�
7X��u]�����>(:������
.��U ������s���][�>�����A�B]��9���ZB�^���(��D�����}F�k��2e���J���|
���H�C��{��7��=�����w�����^�z�����X�S���p�	������N������������Z
���D���I�+���\pAb�]j����*'L������4���SNq������q�UV��������BL���oF��a���w�����_yG�BN
{Y�G@Z�\�XZLS_}�U�VL��\kH)�Ea���#]��Sh����:�,��}hS��P�f��n_�R~x��A����@j{Uk�m��v�[oK�*�[�ZwM�30X��/^<��[�a����z�-Z��A���_a�B3�Nj����5�n��/8�	�^|Z3��t!�����h�;}ozOj��/?��2��K-����=h
:}��<��H�=����5��S���t���g��7X��P8�����3����Q�F��(�3�)���k�A�w�M���9��~p��A�KJ��i�<?8�}FF��_r�+�����0Z�M�1T�\fr���n��s@�w�>��&� k�e�,@���dO?�t����>k�;w�>��UZ�����*x�Q�X�����Z���JUg>�~H�X~ �������.�U]�	
�"]�L�U��MC$z}
3����\8�S[��k�����_�U(�]g�a��[AS0�UX���TU}�}�zmb
E�����;E��CDK�w�������A�>����&��?���;2��H��2�>W�^�=�-��w�MRa��}E2(%���BA�_�������z�8J(8���[\x�\U��f�E�E�C�Z[�������Pk��a\4T
�`P�DZ�L���Ac8
�492�*,�rz^�*�4�5%
`��)�D
�t������L>u����/��bx�D-���O��u��Q5��'Z
#�X�g��A�~��5��60U�]J�_jDx?��3��S'����T��@�HR�?W�gzT��G @6� G�I�&M�}����-�pG��j�T������-%�G��y�8��`jM��{��'��������������*~2�FL��Z3���Sk�^#j�\WL����6c�h�J�*E���]�]Fr�|�[�.9
##������jH�7��6�~7z��]�S ���^����L)��H
/5��o����
Q������JU\��u���,8�Q@����;�c�=���"���
�{�����v��!�Zm>�%Z�����{����S��00��:\o���}��G.�IM](
F+�R��L��Ok��
�Z(#
��~��n�����&��-�M�{�����p��O!i����T�)]O`k�I����G���"���Ljs�����#���E���S��kH��@�����=	2����&�S��z����.����Vx����kZ�qjS���������/Ux�X�}��.H��:j�(�>}�w&)���}��T-�jO�4T2dHb����-[�����5j�=�<U
>��CI*������%0RZ�_�S}��z��7�}tj���C��!�:��q���F(~��^���/R�f�r����
��~'4pBtz�~��}l)G���G�=FR�S���O���Q����\��_������y�{����~�7n�������~�@�@���MRT�X������)���*n�t���U�)HP��PI�\Ja\8z�W_}u��C

������^x�W}7g�7�2R
J�R���\K/�h�	�B�!���Zs/�t
�SvCQ�bj>+=&��1������i��C,D�E�DV�_��(���x�m���)�R��i��~�E�����_jt���@�lD���bIUQ>�>��Skh��U���m��a�-p�(�PX�n]W�	-���Y37}���������C������\$�D���������M�~)�
��)��U�W��)�=ztb����
��
@6G�*G@�-�����������E��Z0SZ�L��\(H�mj��Z^Z;M����{�����e5����^Sp�g�v��������_�����@����^U��}��-���	���h��T���E������N�������|)	��S�5�Uk�N4��i�����B�1c�������$�_��-����^�����
9�!�`
9i��w�}�������qjKl������K�uUSN�X�^C�8��8�T�S�u�l=�����+��p��K.qm�����:
�X�x�w&4�j&w����'m;fJ�C��!���HU>��j�]i2�B]�����s��[�u?� '!� RH��������Knh�Z�.M����u��qm�)���J�����}{��W/�g�����?�����")R�w�N2C��)rt
U3R��S{m��j
�[9��]
\CP��~���cM��iRn$�{G9�)�;
6t��OA�?�v ����4I2�VAUsm���;
M��8q������N?Sd�6Y
�����T���&7�A�\4��&�����;J�^K)��FZ��o�>[�v�w����i���y������(��OU=*`U�d���JB�\�������Hh��N9���8���O?��	rdc
=*W��%P(4u��d�i��J,����J)SK�&��
OUQ��������N�zH����$�R�����D��Zr��e����k��Dm�
�|������$�*O����Z�l��(T����o�����>�U6+PY�|y�(��Rk	*��i���*O$�v��n�)�D�����\�q���j��nG���ZW��<�`��)�C*p
�GA�&=���VU��0
��E��V�)�I)�S����?���R�A>UER!� ��o�M�p�>c��v
��;�<W%H!U���������Dx����;��,+N���f`����*9?���j��%iU�)����(�$V{��R����c
�����9y��� )��.��������<�A�A�u��S��������6����p�=�\���_ �=�n�m#F�H��:(�sH��<���p��>���h�����j`������v�`�>?���$�e
a���];�w��T�P�J�,����O�6-��h��s9V��4R
d*U�����8S%��^xXEU����&�=TUW*��@��L[�f��|j�T���"����z�D|����/�$�D*(�F;��3�4+V��{�?������:m���n_����s����t�a�jSu�MN%��6�?�&w��u
z�����n3g�L�)(��������E���W���W��m����}�?�F��dX�nWK�D��#�v�����}��Q���7U���Q���P5�O�_�n]+S���������������X������-����������U���"#��������3}��/i���B�y��o9r����D�.L	�vS��J3x�B(�8
�����?���U�)�SU�*�t^��yn��F�X��N�Sp ���?����,��Ihm9�o����VR�������N��o�=dfp �u����z�
����~p;����7��M2�{Q��B]��)0S����OM��]k��5K���*�t}
M��+�S��K����`�?���~��v�����*�`�Hr���u�a�O�c�)���@�@����U�����H��j
�jSp���`.����iS4i
��VO7�&�*�������.
���B��[`Kgr.�����;R��n���[�}�YoM���V�\%�n����M��D�W��X��}w��7�+���}��~�G����6�6k�U@NF �QB!�e�]�B�@�
��Mn|���]��*���M!�B8���eK{��g���?xh�*�T���/U����v�5�����z��m:V�N�&M�����������{T������<zM=w������_�,�y
�Z�jeg�uVb��>U>�y�qk���k����G}��x�	�Y���^L���s��u�����O�����.�y��'��g���9�D���/s�,l��!���w��w�I���&M�dc��q�
8^�r ��BFkj@�O-��v@vA �����T_��j��h���6r���;c�;x��;.Y��U�P���drHwqqq��/������3	Sq�-��\rH��Z��=m��an�F��]��o����w���V�^���trH�B�
����m��Yn��;�[����k
4����{gr69����k�������;wn���+�j���� �T!W�lY+X��;�$���:�Z�nm�_~���
�������`T���@�Dr@&"�2�����LD d"9 ���@�Dr@&"�2�����LD d"9 ���@�Dr@&"�2�����LD d"9 ���@�D�����$����6������ _^�[/:��]��;�r �a�Y�	�����Q~kx^^�8�����i��7�{�1�T��������/o��v�M�8�����{Fg��a����Z�li����@����Xo/c�Z�9�drico���]z����gO[�x�;�j�*�������/�'�|������Gc��%��iT������g�}�����@.�F�a�;w�c�9��~�m��u�����{�}���V�\9��������bc#O����k�W�v��F����7��^{�5+P���8z�3�7nl������hA ���msUp�v��n�����?n��w�*T����N{��W�H�"���_����n��*�V�\iU�Tqm��|��X�b�u]�����\,_���O�n_|�]u�U�c:�[��U�^��N�U �n�:��z�)�X�R�������@r�^+S��w�q��������hm����.]jg�q���)�����V�~}����l��5��K/�E]d�K�v�����)�L�g��e����:u���hk������{�e���I<x�������{��s�u�i���u�����_�_�������i���x�
w]��/���k�RYz.�G�����C]C���h�"<x��v=��g��M�6y�DF"�K�+���&L��WT�h(Z�M��'�|rTk����������ns���������E�����Lo '���_\P6`�������'�#�<b�G��i���p*���!�h�wh�_�}���.8���^~�e�)`�����oo-Z��q�������y�������Q#��U��%G����o���n��_=1G�s6������������`�������]�S��/_>��HrHCF�i�����5k�p-J�����8�r4�
����H�2������i�?��[JJ�M)tRE���>�1*<k����S5�n�={��t�B��7z���)�8p��s�9��'����U���:�y������5�A�<W\q�M�4���_��{T�������Y���T���W/w����C�I\����~s�����>�x�������r���>}?��������b�
.����a����2�Ru��j�C��-�hR��m��%n_�[��?��PN�\K�(�JR{���"�������{�-5�u���sU�)�R���S
h<�����'�x�=��C�v�[�7�O�Wu[����C�V�^=�ov�O?���X���}����l��n��pa[��	q��/����k�`��n-�H�RO����*��~���k����SO=���~�L��7�|���SW���#W|��i��[���/vX�z�)��7�wk��f�o{���.
�����[�+:t����5|�p���C���e��#@F���Z�(�xj�~����J��r��y���_=������~���{�����nIx�
]�
�]aV�5�yU�������S�g
����9�n��FW������]�tqm��=�����tI+u�i9U�)8�)/PU��y�>�l�H���xS�����JJ���A ���q����.,S�$^[zf�����o�F��~���?Z�����{G��v�)����Q���YT(\��K��@�p��s��f����tS�g` 'j
�[eU!��8����+����	��;������^'��:
���#O�<Q]2�\:RJ��_�_r����^e�*;Mo���+�M��6��FC����$ s�*U�����{ ���-����~oZ_NC�2JpP����b��k����K.��n��v78R-���r��H�u�].?Pe�\�@ �N��R�W^y���UUr����F����c��n"���t�^���]�������E������w�yv�Yg�m��v�-���\���_��Mp?~|�pN��VXU����^uH*Q�b�Z�M�'��T�Z��i��������]D��0���)�={�tk����6o�<7�TY@���������p��wMZ����'Nt�\)���s���fK��7�q�nmxM`MnSe^���!s����8���*V��ZV�6m�81%5��?~W��e��lR:�OiI�@��~���w��W�
�PE8ZK.��
��G
O��r>=^Uu?��=�������K�k��|��v�	'���6m��";!�KU��\a\�r�\���(�]�-�J^5!e��)n�2����q��1�����u�Bu��[��~��G��?ZW^��ZsNUv������:�4156�����N;�j��is�������������������l����}#� �K�?����y����m[7E�k��}����������;��M�v*w��F"kD�*�d���n�8�LV��������#U��:>�^��Z��p?�i�j��
��ZU����X���m��.���$��*<U�i��O�i���k��s�����~�z�)x[�b�[o^x�j����N>�?��T�/��Q�\y�h1��%K&���.��S9����������
.���O<��W��U��d�K/��--��RU�U�P�J�.�~*
{���l���n]x�9v������&>V�����������;�-������wE@j�]�r��MrZNB�>}�z����e��q�[G�����/Z�J��c�u����E��7N%J����~����;���[]K��z��'��Y�f��I��x�JS�Z��]�V�Z���g����&��j��k�qa����]��;��c]0����F��������/�����s�q�Q�����J9w7�p��;��
�|z;vt���������r�'��r��������[�,�\~n^{����p���
�Dr@&�ep���������?X.o{��N����<�Ns��|��>`�����2N��Z�+iYE�A 8����v��Y3��3I��f+��3�2���q�n�~��+�����r�[w��
1x9���������v�w^�������!=�<`�-�����q�|�-�igX����1�o�������+�]]5���C���@p����}���{�Q�J����CZ����4�;J���g���r���~�8b��<d�]���;��<cKw�v�_��xg#�n{������R���������l���xG2r�#f���Z��M�Q���ly���e�����W�c�m����O����=���|�C��f1�f������o�pRn�S1��v���U��������W���-o���#��
9�iw�Q���?C�q2b�?��������;2����������M	�ji��H�,[��Hord2U��d��������������;S.n���������M�=��@�L��PL���`���[��3U��=��B��-���F ��fl�o��|���}:q���g����{{)[��[�D��������F�@�8r�������O/����m������u^�I������YL�"D�@���o�lq�hq�Z%lK�Y��1���}��g�n�$�(4���%����F=e6�e���f�'{7�ML���[l���dr������s����gq+_������-v^c��~��o���9������~
���m������M�������{��
��d���|5jy{�� ��U%�������Ybq�ZxGI��{������������A����j�������-~���Ax
�B�����z{�y?��&��~��l���$ �dK��~��R�-�u����'o'��_�@�C ���c�x{)�����K'��x���H@ 8�����I'�����(r��^����^:!��r�#&�Y���w��I'1��|r9 ��z�K?�����-�����R������m�l���6~�x������?w�\��{�wO�����sJq��4 ���d-B���U����?��#G��3�[B�������n�[o����+g�r��n�l[�f�d�w���}'�v��-j�%O-��+��%�1����������<�Z�M�����~IZ\���m��\�%O�\�U��}����yG�kue>+��9�����0���eo��3G��%m�w�-W�<��t�'���&�S��w�"
�t�E�Y�n�l��������Y��-��w��i��Ow��"E�X�&M�]�vV�R%�9�C �<9p��;�����s�E��C,���#���b���M��}����Ma�~���k��o���]�\X7m�4��������8��u�M�<�^~�e+_��
4�=V���Y��C����o�g��3�
��i=�������y����_����������[����m#��+^����]�^x�������{�q��]z��������YS����^;x���O���y��V�ti�~V�lHY����#R'l �
�7�|��U�f�f�����������v���s[����W�^6�|�������@v����K�����d"�
�{����O{���]�iz�s����=�^ ��3g�5j�����$l W�`�TW��D����kdw����{�n�H^�C��Rm��;w�
6xgD*�@n���6i�$���/l����Y�������5�@-�O>���{��V�bE�����������w��5�
���4XA?z�!�����<��o����'v�g$�~ =n����y��m���
<��fr��Yc�:u�:u���5h��z��m[�l��q8�:t��v=���ns��{���8�:uj�������?������*�����]�v�I'�d%K���d=�'O�-Z��a�\a�ZJ�5k���t�2�R�v�w�#�<b���K,H��1c��<`/��R�Z�M�6Y�6m\8����w��i��}{�z�O(?���������������kW{������q��X���W=���o��g�s-[�����������w��[n�%�}j�gx�}��/����iU W�H�Z������d��z�����SO�o���U�)���I�8p�}��Gn�7��;���_��3g��7�Wz���k�����V�pa�98{�l�������!C��/�t�
��:?������w������?�|���Om�������.��2���\�r�{��V�JW����Z��U���'L���W���T5�����v�=r�H�=V��k�siI2]s�o���}F�w����[nr��;U���Y���y*��AT�\�|�\��%�\�f}����t����.pm�*.��;�(P�n��&{��]���Ia�o������/v��i���'��������OU��-R
���s�9.\SHv�1����{�kU�P������z�W��\�R%���y����_�*�D�r{��q�2v�X�Z�_�E]�����T���WyS�L��H~�����^~�ew��{��Y�\9{��W\�-�.�@N}�:t�����������ov���B����6l�lO3@zS����@�)j��m�^z���3'I��O�������J�*����
�J�(��#�9T�4k�,r)X;����[��J��u���g�i[�n���G���p�	�Q]��g����^:���:j�j��/��F��}U��������O-��j�r�Xz�@��T���*���~*o������"X
�B)Z�hb��~y����n�g�y�����rU��mS�k�>��
0��wdv�k��BN�LA�������`�B�p����SEu�(��g��o[U�=���l��v�y�yGH��9�s�D�F��1z,@fPG_�B����T��c
����zoC�uk�)�S���L��v�c�����p��'���
��s�����Z+N�UCmW_}�m����q
��o���xj�
EA�_%���*���?�[�O���lz����k����*xk���+0:����np�4Da��nm} ��
�����B��~U��EU1��?��M;�Zo�F������k�[�v�4�5�j5Q�w�����u����I�O����������i����Ij��hx�_Q��KS �/A�G^}�Uk���=���n���15�W�2@f���%K�xGI����.\��5�Ttn���n_���F<�@A��\F�`��v�)�����'i�
������:{���\��Zj'-S�L������>�p��B�P�`�Tr111���z��V�^=W��N�K�M��5�d��I��2��#�T7a�7�R�E���[���#����z\r�������X��R��?v������r����=��~mjh`���J��]����S��k��'��+W�.��Bw�_��a�����p*��.�oX_�[o�ew�q�Kv/�����{�����������sS:2��O5hRSGB)P��n����o��6W&��n�Mu��Y.�������Z�l��CQ���M�[pV�Z5�����D�v�����S�s��i����S'?~������j���5h��]�7U�������Z����U�:� ���G���gOw?�_�����]��G��"m���K��G� �3�~��7{��7��[������Z�jeS�Lq�T����s���_���P��=���nR���?�ZD��T�%��iS7UUb�_����Z���+��aC�������9$�4�J�*����Sn��79��c��'�pA���3��[nq���R�W]�5j�����'�7��J�r��z�q�����^�^Ok���R*�{���]P��[�vmw�Z��s�����*����k�9�MT�������{�/��/�/4\e�"E\��F���M%��E�l
4�U�w�qn���.U���)���>��k��Eb���(u_}������T�����m��
�>��K]�
�Dm��7ov����W�^����T�&z��]����~����A������w�����������i��
(�����4i�����[�/�.�w�u~U!R/W��#��
w�}��0d���E	5}��;�t�:���*�T���6� �Z7��%�-[��`�{V%��,n�@�[��;J^��X�J�zG	jk���l�m#�=���fS�{)���Y�����]�������U(R�z���%�;����-�E~[]��J���8;8s��t-a��Q�
��g�N;����s��2N��X��:{Gi����GqC(��3 ���BN��*i��?��R���h�G��9�S�,Q��]�����z����C��������Qr�7>���l��y������nSi������� {(p���^�������Qr���)#Z����_�:��4�A�&j���xh
I����hp�y�Y�{F���*�cE��l�k]��"�3D5�At��C��i$�v�r����E�;�<[�b��Z��MZ�H\M� �c�C������k
�'�,\���n��6M1QW�bE7*���o'�<Qr�����/��S����sm�����[7�����~��7�?�5i��MZ� MiY��y�j��v����3�<����[[�����
�U �m�6{�������>
�n��F��e�w���
����l��5n�~Jbbbl�����~���%�:t�f���5h��q��ow�����������3\k+k�)r�s��P�^=�]��.`��}�|��C��k�.�]��-Z�{V �J�lM�[�-����r![�%��}�Kn���k�o������Z�<y�gr��R�J�{��g?���
>�j���6��\r��1c�U�VV�P!����-�������&�j�>��d�����w[�>}�����m��yg��+�@������_�M�)�}���k���?,..�;�\�r
�T��e��i?&&�m���m�&MrSZ$H6���+�
4�J�,��
*������}�|����n�u��Y��U�H�"��9W���B���k{g�������Gy������r���+_��M�<����m�����A�i_���v��i|���)S�{6 g�j�C���]��M��U�V�xq0`��� :i.s���
6��)Sl���v������;v��U ;����b�����M���'����M��C�v��g�I'�d�\r����K�{�n;x��=�����}{��u�� �:4o�����v����~�������������w/��KU 7m�4�_��u���V�Z�������m��5��k��/�`{���n�������C����3I���+�����<���g��{��
@�u �r�Jk�����7��5k�~*|��U_�b���g���U����ZY��j����^x�jq7xG�C�����[���3f�Q�����{1 ��:�5j�[/N��������;�
,���@X/��R�������������
d51��x{);��wor������-�yG#n�g��
���
����3��>�l���;-���-�U�^�.��bWA�o�>�,�u�m����,v�zor��]s���{���>�w�n�K�Nv�S���n��&N�����f�������m��yg������-i��������_w]���s�=����������$�e�M��ZR-��������L���~v������U �c���V�lY7�!%��"E�� O�X��,nk�� kS�4z�h�����M�6nxezQ��t�R4hP�P(������a����G����
������q��E��~'��/����l��?��������~D?��`1��]�*�S+j��y���nK�?=F�@���l����)�������C?��U+�; �����]k_�>d�g��m��������d/��v���5�>��������w�Dc���w�}7�*��]��Q#[�h�w�~��7{��W]@���������vs>��;��s�w��.8�T���k��B�P��������NU�u����k������S��ot��[o�e��g|E|T)Y�B�����r��%S�@��c�X�����m������^��_a����=�������B:n��X{i�~��!���X��<�mc�X���.��������1�c�w�/^���R�J��m[��(&L�+�������������Pz~���.k���=����3W�\���W������v����m���k���������;��3C~���-����a�:t��^��?��C��S�)W�������9m-�@._�|v�e����]��PNe��,\�0q��%�\����n�d;����C��#�
�6$��/���8d�q���MY��N���=��@a��R^p���t����-�(Z
m��yv�	'��W_��*�U�R�.��"w�e��yg���<�x��w6ez�_~������:9���zxg�q�k���K�T����H���J����m��v�W�������>_m����;��}�@��@�|��������p�^��h�n^���GUI+V���Z�^�
���_+V���(,R���i��7��r�?��/�(���+��RL%T��az�&M�����]X8z=Up���{�:x)
B�s�5����]��E�z��|�I7!5T���[��%J���&���`���QR
�T����c�=�;�<U,��=�������)�k���M�4�]kF/�����T���6U����U�V.|����T�j�*����K��D���_�����Y���l�6D^��iW��'8:���'��4�ZK��p�
��C�<yr��T���$hZ{.�A�
�4�@���JS��(�k���=��#!h��^�z�}����8�'{
����2�S������}���5�\��-�5�u��n������6l�0�T�-��*t�s�-5��:qZ�/�_��@NK�)�����������m���Az�� Uq�L��"����}�@4�v���6`�+U��wR����c89����&[wG��!�$�2\*.����N;�*T���bn�2
Pe�+��6���(�����v��!C��/�t�
�t��?��*�Da�;������?�>��S7�@������
�~�!��	�WF=����S���k��W
������	�l�b]�t����=���#]�^O����4�B�W;v���@Uw={�t��i���zu���j���'��R.9?����J�:t(1����;���{~0�������S�NI��dn���
�P����Y�uU��u��q��g�YR]���Z�j��M_�~����H��1��Y yq�C��G����R�����_�P����*14�UZ;_UpjO�h��B1-���J�)�N~��.�����4�@9K��U�p�j%
5�U�j�,Y��;V���#��k}5U�R��w�}��-�Nj�U%�^O!�:����)S�x�2�i���.
YP{�ZDu�*�z��W�g���y~��n�i��V�L�/
��J7}f����+�S0�kQx8p�@�f�W.���Q���T��i�������vcUEf��m�8B�5�T�)��V���T]�@J�q�)U���Q���������*�y�f�3%*dRu�"�����{��G��n��n����)@S��Z���~���8�^Gm��@-����FU������O��WH��TciXg�}&7�|�w�>����SP��K-���;w�t����^{�5���:rZNA��SUV.�V�^��_��n�T�����
�2Z�9%���Uy�>mJpuA���Y����v�j�{�N�����T�
1��/�@Te����?��~�����H)���jS�\�<y�~ ����R`�`.��\�t�H)lTF#�����O��@��$S�=}�� H��e�������F��SO=���i?xh��TU5��VAa0�w�_~����P��_������s���v��'��+��{� ����@N���}��K�������g�u�M7�d���w�4&Lp�/@fSU�*����)pR�f�f��N�T��{�����i*DS����W��'
�������'���P����$������+�M��jwU�_��V���S@���p�R#��H!��K��2&������R���g���uM�����_��`�,����V����8-��>^�A�a%�����E�De�������������c�=�J%�
%���E�R-���P*�?�~*�U�%OA��S����|��R���!�}V�\�n��VW��Al�����D�h��{�[NU��:p�����<T��^C��|Z{/�
6��$U-�`r��]���u �~bM�P�?�ZN�4�M��_R�q�&�=��K��V
(�|�MJj��?~W%����+��^����>��
��o������~�v����=�l����c�r���w�~��x�,�*����k_T��A�<4��tk��x��a��p����u�����`Jm�*�Q�������i���U	O{�)�Hm%����>��Uj_[�x�����>�lZK.\��nW��*T�}Z�/�V_=V���)��6��
��h��RBU��rK���tNH�a*�����2���H1b�
�/J��\�/�~!�S���=z�?�h>U�)�T��m[W����OMT�y����8Z(|{p�\�������
n������������
�-�
@Z(,S[�B������o�T�<4 %�SN9������r��u�]��e��u�vR���i�K�,��F�_Wn���n�E(��BM�M�8e&��us��~�l�2q�F8#G�t��E�m���MJ����*V��~j�C�*U����s��*:S���#�y)�@N)��@-|�
���`}�*��8]%�J/�6��U��R�<
!U�*����k��	U��/��o�%��a%�
���r�|����y��j�����5�\����7�k,��yg�x�B3�d�Z�'���o�>>�T���:Dc������{��G���S����h����)��
�Bk� ����S��+�'�����/tU�nx�*Be���S��E�,��<��:�=�\7)Vk�i�������N��U�z���
�P�c�NN}6z��3�w����V���S����>]=&-�nV�?�����
(u����Ww���r*U��>g�C���X�u�JN�	(�Y��+���}�O�����u�H)S��*��khS'�������w��)xSn�� 8��L
��i���sy����X��:u����j�����j���5h��Q
�T!��k�h;vt����~��6�q��:�D����+�[�~���T�i�6l�`������F�J����)����i����z�
���7o��������|�}�%�lT���f�X�.���*��gt�W�-�E�)�D�BE�*�C_��	S������>l��[pP}����?n
�P9e�����]��GdWk����R6g+�g$ c)�R��*���zL������O>���7o�:�$8#Q����L��Z'U�&�G�V��2Uy�r�-.��s�����Q���o�>��FiP���s�7����Z�zZ#N��(tO?��
��j���*�����t}&

���g�\s�;
U���M���c����nS��O����rA��5
�P���E�p
O�����{�J��
����$��/�sW ��2����*�@N���r�k�>��h���9��t�M�O�hs��W��	���>s�����ZM(��M��C�����pA���Zk���X!@v�?��v������q��6h� k����DN�-l��1.��[U,����H��+�Ut)�)$��������������������}��������K���w�$������k�l���a��B�&M������|�.�w�u��W�W���RG9�BD��Zg/�������q��![`��*Q��|��\��Z���y����e�\��5A%{�e��`*	��O���B��������tQ�����������]��\����P����~b�gr���T��t7T���Y���Q�2j@v��u3�Y�"�����gU�������-nQ+�(y�K?`�+��%�1�������%�%�hXK�)�������v��l�������Q�*)l�k$,>��;����-�e Z]��J�����f�F]K�j���7D�!�D�w!��U4���	�������;���o��;�8�O��r���w���dj�T�����MA����]v�e.aTI�6��Lp�����KA�J�.ZN3y�d���W�B"	��C������L:�b����T�b��b�[�z�
��E_�
cZ����t��)Z�������]Q�G�������2��A��{w���rHM[Qp�����}���{��La'@j�m��bgT���
�?Ecw[��/-v����5���������7�������X�u{X?v5���l�H�S����>��o��|����9S��U��>NM>UE����]����I������C���e��#�|�����]�T���:YL����Y�=#��/{G��Y��m(��;J�l��^�����Kp��Nv��{G�[W�E�~������C1����F��9&�=U2�T���*m[���������v|������K�q�N������������2S4��!����������[q�D���t���6M�������kzrC��T������X��xG���/jK�O��D��!�ON��.��Y�5����%OZ��^�Q��}Fg�]�Y�8���#��������*����y�v�Efr���6��9�WW��wd���o���Z�;2+q�K+���w����o�5������z{)�wf{o/A��]�����Q�V�lo�+�������>�����t���p���Q��k���"T��_V<���]��N�;�;J���*���kxG�L��]H����1�������]��m��t=��W��-1)O1=>o1�R��w��������7���-��}�s��&G��!�K��� ������������7Y��������Tc�s^d�g'p� �K'�*��G7�C^}�UW%��$���������������t����n���o\E�F0GK�ZQ�?f�<�J�.=�N?�;0���+��i�(y�����~�;Jp���B���'Q��vV`�`�(y��y��Wo������^X��w���
��g&L��
�U�6��l����������}�s,������U��b.o�!SE�w!i��8P�v�[�m�(A��6�~�
���;J^Z�6��*�]��� ;����&~���^:�z�E�?:�����={��N[�%�<YVUk+�1������Lxw�q�m��������������<���Li����F��u,O��i���Y�l���A
���!LY�Y�#$
�*V��ZV5�6�a�(�;��3l��Y�b�
�lRK�,��S���������Da�ro'�l���@r��@���~����i=��u�Z�\��{����o����]�v�G}�B�@:>|���U��-Z��D#�@�-�����p�"�K�?���
]��m�Z���m��-a7
b�i_k�)�����t������.����C�[��������k���n�)� ������ZP�\*�:n��Q�p�Bw��M+Y�d�����M��
*�k���*��|�M����M?�����cU�W�|y���Ri��������q�e��O?�dO>���D?;w�lc��M�dU��NO�3�T*X������U�E��y�����>^?u�*��z�-[�h���~v�����-���I�������
����z��m�5�|��M�fqq���r��9UiM�:�.��b{����l���~�a���7�|c�
��.�wR�-Y��Z�nm3g�t�C<��O�8��b%J�pk�i;��c����g��9]T����T�6o�<k��������+�B���'���J���_w�A{��a����1c�Xll�����
����p�B�P���l���/��o������cE�qm�y���\�r���^�Z[����w��9Y����5k���O���K{g�V�Xa�f������i����5+\���v���:r���^C.�_���n+VL����
@����Z�2el����v�ZwNA��U�F��>����U��q�V�P!�,�sE�{��V�fM[�t�����s�}��}���v��g��$..��O�n;vt�]�j��@��6 '��e�Q�Fv�
7��\�[�-\�v�=�����;w�w�a�j��3fX��������
�lQr'�x�����|�A+Q���+W��w�n�>���������g�����3�����T�R����-UC��\���m��-�r�J{�����Skj�v�l��u��[7�H��@.%���g�B�rB���a���+W.�S���������e���v����}�����b�6����+9r �oW�l�~�cl]f�oY����M��)o���s�Wr���\���m����y�f�S���������c�_����5����^������.]:��N�:��uk�8q�<x�{d�4s�L�����N��m�w�������~���z_�g���+��n�>oLL����k����.�����_�������{gjwg�@.w��.D;����O��f������x{+o��y�@
�F����6m���M��[�.>>��.]j�
����{gh����{�n�(mf��a�}��w���;�����m��X��v���7nl��gN5)8*�v�m6k�,�������o�?��.\���c���n�U���3�5jd�-�� ��+V���_~9����o��V�X1w�p�M�fO>��m���;��������+��o���V�Zek�����'��7���W^y%��e$9pT:��c����s�{�[�J�\�T���}'L��nALlll�U�T5�~�z������~�)��q��T�����w6<U�}��wv�������?���������N��^z�4h���q�2�U�@�H�r��K/��.���b�x�b�d��;w����s��R�Jyg#���'�x�z�!��?����C����������*;����~ ��z����e��ex�1����)�����4$@k����p�E��,�K�R���j�����O>�3�8�
>P;d ��j3�I���6i�������:uj������Z0�k��s�5*�0]��E�z��"���z�����[]���'�l%K���FFA�0�1�}^C�������5����\���+W�;{�B�
y{�@�X{��Il/Uc -��
7X��:c���"9|�pi��PA^r4@B�$���r����������#�<r���}��W�^v�}�%>N�I�^�-�O�>!C9U�=���y���t�e��!�>u]��[n�%���
6���_~���gtT���t�����U��BN?$L)\<��S����;�X�2e���i�@�U��?�
�P�����,X��d��9�#)���b����[G�B�
�-	�Q�n�\e�+
�Px�M�:'
���7�{���/���+p�m?�����U�)HR��u�>��S7qT������e�]���PC&�^�j�>����7���]�G�k���N�����?�{'�0�.]���?���{����
3�����;��;�G%P0��gO��[o���zu����Y��=������������[o�$�zO
�M�-P���Mk��[_.5�/_���������@�(j_��a����/q��*���Li"������u����6�+S��B*=W�f��m_|��[?�{��.$S��p�j����/�`P������n�������j�m���{��4��������h��N�:�J�P�FM�2�{��p����v�t�.S������_m��F��&Zj��g(��g�PO��>K���~\&�N�^�����{�&�+��������T�$@V����V��Mm���Us��Z0H�j�������!���}������+��	��n����gJT���:�\W\q�k���[�n];��3�Zk��)xn�-Z�hb���8�^Gm��@-���a�5r�������O-��j��K.��q����|���Q��i
���>���k�)��sj
��R\*��H
��z}��-����NoQr�v�r���=��K-�+0]�vuC�}�bMp������9����1��~������'��FJa����
�P��)T��Za�RHu�	'xG)S����V�T��E���W!����6Zz
���,X��e������"��P�O?�d�7>,�������T��JExA��������Pa��2#D��wY��Jp�(dU�
SE��8�7Nj�l�����
E�f����kcT��BU�=��������@'
������	��R���i�F�[>�V\p�����Vy��8���B*Z/�zj
�J�(����~��� ����}�����>p����S�Y�
��Z�|y[�z�O�U)H�@�J�[J���3��{�q�����r��n���4eT�
���N��Ho~����������j��~�\m�_ZE�i���UU^�EuZ�h����}���9s\��u�4�TC|�A����'���29
�u���[�~f$U�i�9��j}8U�%�N�U��$W��g����E��;w�L6S���������h�bR��i`���{�����|�-�@N��@M���
}�j_�_����
���u��m��d]
����u����.�S{��\��
�N9���"�p�_���������J��`�i�K�,��F�_Wn���n�E(��BM�M��0��jx�?m5�QM<�e�����X����jS���#!�@Ne�Z�P#h�k+Zp��qn�n�m��5T��l'Th��c��I�L���o����bM�u��R^�|�r���(o�tSU�)��f��`�p��T1bD�`M�_��Y�Nk��m�dW�f^x���p����f�F���BN� .��R�M�8��~ ���o�u�����^����{]�"�o��}GJT��I-��f�c�+��H%K�t���1���N!�6&u���:t����p
��(p��U�����k���E��K���1M�?~���C����E�\
��������OF;v���Q�
���h`�w���C�Y�����L����>��#w�h��N���o�*@���]���O>q���>U'�u�Y���P�������*�S���9Cmz?]XU �/�e����3�D��1G2u���(�w����pLUZj��v����H-��?�����_��*U���2@+Vto���O<�����y�-���O����3�F����_o.-J�*e�?��{Nu8^{�����F���jH����~�������]�^y��]�������((����]s�5�\4��z����������R�����	�����&��"Q&O�l�_~��nk��ubH�QR_�p��[��
4��6m�B(��M�3f�����y��%	p.=��s.`U{m�����B2M�������W/��I���kW���O�+�=���w��I^O����~����M+P��;�S��I>|x��A�����No�������T��_��_��V�V�ZY�|����R��&]V�+>�Y7
z��
��?�������	UN�L��� ���p��nf1K"[�x�����J��Y������w��������������K���Fx{�a-����Rp[?��-����v�#3xG��P����Q�;J�w�A�g[d�����g�������9�����0���eo��3B����B��H��d�V_��6��e��.�Wj&T�9A�*����������O>����J{��']Y�zp����W)��9	���
6�����J4����v�t}����\��5����r�����/�l�r�0�#�q�Z��E5%C��W���%_�c���uL��y ��*�Su�W_}e.tS0�z�)+Z��wkR����!E�qI��������g5��2��g6����!�@n���nr�E]���Ki��ZY5
w��U�o�>�,�j�T�\��5:��]����5>��
i���]"�&��AT�\LL������;����q�4aU���+�u�_���x���B����=�������{��Qry��u-�
�v����
O��}�=���
�
.l*T��S����c��r��6
s�}�=���
����c
6��O>��t�bC��x��Ga����C��:��+�p�r��9�������s����n�Z���m��V�^��w�y�
|P��<���v�e�y�r��9�����[����D��x�b���m���nS���1c\e\�����Ge�8�u '������n��Av����UW]���o�����g�����+X���(�
�|'�p������n:t�=��CV�L��+�wO��@@t�������m�l��-a7���9]��5k���O>i����<y���%K��5m���r@Nu �r�J����;�j�*�,�HD�������#m��)V�bE8p�����ys��=/^�{ ��*���{���;��)b={������N=�T;�������������l/�������q�F������.���TT�\��y]u���*�+Z����U����[�b�w@��
�r��e�]w��-[�^}�U��a�w���}������-j��-mg���x�&o���6|����o�%n:����z�>�j��X��m������d����!�r�����O?��d[�v��r�-6m�4�_��u���~�������y�|�����s����gq+_������-v^c��~��o����p.i
F?`��h���1q����������s���V��k7�m���.��~�n6l��	��/l ���/�����W���m��n����c��v�UW�����y�|��\n�����}3�m�f��n	/V�p[���g��-j�%5m�\�3�S�(4�>}�<�(�|�f���9o�����<����6���;��)S��mi��<z> ��Y���=t�m}�v���+����n��L�t���o�p��A�m��>��S(�}u����^�F������Jo/y��C< g��/^�`?��C�7=������mG�v�����v�z�L��;�O��_����o�������{{����rk����R6g�o@�r���]?����f|����P�dU��m\��������������R�w�����1����Ez�H�����R�n_��6�t���_�Z���2f�������cd���@�@ d��"�r����
���T������l>p���e�������A�{���W� g�*��`�~���k��������I�s���}�"o_�6q�����,~G��7��e�Y�9���v2�������{w+]�t�[�:u�u��6q�D;x0k��9���;����m�:�������_?]�W||�
2�=��7%k���N�:����>{��ak�������{m���v�]wY���c���:����m����Wd6m�d��7��=�*�;p��}�������F�=��n��\`'�x�=����k�.���#v]����^r�|��G����]0��M���KK�.�A����,��e����F������]���� L?_�uk����=���;���m�� V�g2{�l����5n�8�c�����|�f'�FT�\�����o���z�N8�w�\�rv�=�X�n��v������W�fM7iU����W_}�u{�D�&��m��x�n^�����K�>�|�����������l��Y������?��q+\���3��}��t���3g�5j��-Z��Ar^>�����zg�Se��'�k-[�ta����S������[�~}�5�U���M��W^y�}��7�j�*�|�'Ovy���+���+�G���+�K��9���|�����'&��/v	�3�<�6����6l���U�f#G�t����]t�E���G�8����~���x��,������?��������m�����9�1�c�w�/^���R�J�R�c����&L�(��Dlllb��S%�2�+�L����w����BNc�������;?u�Tw�@3f�p�.��b������oy�����s�i��f/���5h����q��y�
M���@�.+K���:|��W.l���T5Lt�-��T�o����g�Y�\��F����/��(I��=��,U���0��m��8�G�w�SVq�����>�,*:B��+��2��?���>����h��I�&������c�=��%��u^�O�6�v����:t����8O:�$��T�Rn�5Q�l�Vc�A�b4�8���l���-��*�S���?���D]�~q���u_=�_7�r��V�zuW�����*�����	��N�"E�X�bn_���)�Q��?@�jwU���R:��*���(�|���q�!�W���1{�����s�u���I<x�}��������B��
����F�J2�@��s����'�|2�����{�O�>n�3r�}��V�`A�������������{g��y����x�L]�2)us�S�P!o/4U�������\��2���*���q�F��II�����1�/�*��)��� ����o��M��������d��2�U�#_#N�t-�q�����/������\+�����`h���.@��s����� 	�cZ�n����������#�<r��
�z��e��w_������h��\�B9��j���7p���I����)��K��.H����sR���_~��=�k(�Z?�T���M�^[��S�-��M�Xu�;v�p��O�cST`��6����<y���@���������������9�b��V�^}��x��>����R+�������l1��>��e��e6�e�6�&�v������ywL_[�D�����
�0Z[LA��%+T���r������J��uN���oZ�n��!���_�cn���t�r�j�w�y�\Z���O?��+W�����o���.s�Q�!z�C��G}�����*�48�]�v.tRu�*��5�K�.�{Q��u���h�E���,���@)<������U1�����>��r�0���k-_�|���m�������q*;�����Za#�|�r����^����T���@�=�WU�VT��^�j���p�B�6\r�Ru�����}���u�������Jd�i��G�A?vKs(W���U�{�Hj_��a����/q��*���LVix������u��<�6�+����]H������~��v�9�X���]H��GEK�\^x��52��V
@P�h��%�����7o�����4h3���c�0����S'�n�I3P5e��Q�������U���L��Z�M��LGs��
�����.\�5i	�@�����������3��nI��9}����)lSy�~A�����i1>�G�LM�6u_�J/���n�:�g�i���������P.�W Z�nZ/-p+S��U�V��Jj�T ��U���+
PE��������^�T�u����}�r+%��Su�B�+���N?�t�������[��>[�n��&P���-��VT~���8�^GY�(�	��i��Z0EUt�0U��%�V�Zv�%��L(�>��o��;����^�i����Sh����[A�*u��]	�,R#��Q}y����[Pe�J
��T��uN%����^-��/T�d�q��a{v��U��*y{�����,N~44d%
`4��w��.���bMp���Q�������?�pbkj����k��B.�d
U���E�\�SO=�N8��(e
��*�f�Q���U�����V����p���0z�y�yG�@���O�������
���Rk���������'��V�q�S�����`��%J��g�y�&L��~y���.66�]�{����@�!����6z;p��*Lij��8�M�Y�faCUd)�P���6*0z��g����w�N4��������EC^4��k
������7����Ua�M��R�����OA�2��H���s��|��Y��W�zu����4tBm���
����@N�������l�27�Am��&Mr��%U�r�)���@]�~i	��lds����](H�@e�[������{�q�����r��v�����5M�`�;����72��n��K7�V!�r)	��i����j-?������*��<ZGP!���2U��u��i_��)�Tr>�-k�l���]���'��� �#����2J����3��n��������E���,$����m�~h��TQ��F��ZNUo�m��`.������4�3�*��P����Ten���]�\�����V�Z'NA���{������-Ri������@���Lm�ZW����r�[0�>Zs-L��R����
E��]w�k��D��R;�XhZ��%K������[�p�p�>�P�`3��������l�������/_n����k/�CE��8un��MojS���pN*�^jS��^G��uNy#6�S��aC������E����NB�f
���L�	n�T����
.���WxLk�i����T���q�4}USRe��!�5M~U��Z.��m�8�Uk�]x���JP�-�[DUE8j��L��S����^SC/���|:���<W��iy5�qjE�\}G
r��S��Q2��*S �pLm���S�MSK�t�b:t��}8o
{��`��U��o��C���sk�)��sk��&}�?�
Z2�j�l���k�U�6w���pMU~�0��cGw�n��K��y�w����������O����>��#w����������9d��6l��n��W^y���Q����tQ�������*��Zs��m��:�R������0t�P��y���/z���f�GB����w;8s����m�;Fy@0�QZ;N��+SU�Z?�]|����'���G�=Q����ZY�JW]��b����M4���'�pA��1���[\����}���K(���_o.-�����?��s��qv�����S;�Z-5�B��O?��B?��P��u�:w�����DAa�~���k�q�2��u=zz
8u-���Pm�jK����D]U$���^~��nHG��u��.��Ha9�D*D����:<��?2���������=C���#��w���������T�R�n]4h�5m���?��G�9��K��� �7o^�G�s�=�6Q��
�|
�4����V�^���I=_��]��O?M���\z���{'y=�����];k�6m�@���OA\�&M\{h�����{WX�u�2�>'�g}�����NTV�fMw��6\U$f%��Uk �mk��b�D��e���-�Y��#���-nQ+�(y�K?`�+��%�1����������<�Z�M�����~f�[xfKw��Gf.���W�Ha�]��w�����������[]��J��*�;0i�wZ�3+Z�{�{��\�]$/��.T!�P:�j���7D�!�D�w!�m$�o2H�+�����A�����!�p��l
�QIm�)�q�l���<|!U2J��={��g�}���w��T�j��)�2[�_K����,�n�7iu �� �/V�Pn����#q ������KY����<�T����`�z;@�u ��W_��a��H�"��eK���B��6M����&n+�@HW=gV��w�r�Mx���N9CT����{m���n�o��n��\MIn�t���������im�U��8pS(�o�>�R�@HF�f�f������m���B@�U ��g��5.d��q
�p�I�&���i�d	�Z����.����J���x/�,Qr�s���y��j��T������7on��������W�^��G�e�7o����kV�@w?d}QrE��j������m����YH\\�
>����[�j�w6�4�v���V�J�T���dj+V����HT�\�<y�������{���B#�����>���[]��SO=���z��S�w�)�X�R������r����m�J��v�i��s���#����c���
�_��������^�n�l�����Y3�����q�������t���v�gX�B������r
��6mj%K�<l{���l���6t�Pk����t�I!��oz=���\�r6a�7��|������������O?�������S�����M�8��
9�fQ���p����[�z�������`M���}���Sa���[m��]���_�)�O>�$m��L�I�Xj����O�����!2
��,Y���9������}�
��~�m+Q������z��m111����r�+�A��2e�]r�%��m��!Q����3�����W�^v�e�y�$�W�v��-[��������{�����;t����?�;BF;�WW���j�(y����������J������%ok�mM�g��-�u��R�����^�r��Z��#�������6W��;2[g}vG����.��;J0q���@�(yuK�e��������Xj'���%o�il��5�#d&�.���E���������
����|��������,H��
6��e�a��������j���+]h7y�d�dua+�4U��������(��l��n
����5�r�����S'�����n��;R��6d�}O���e	��))�v�}�Y��Y�
Z���yG��;�^�9��w�����y{)�����^�|���3>���w�qO����wd�����v�R�(yg:���R�;J�����~�w���.����y���3�b���;J^�jX���������H9S4��F�6d'�{�� �
�����y�7@@SU��ice���-���U��O�>��{���7���?����Mfr��sg����*��<y�x� +�����,Y�%�x�����J����PX;��������������Q���x{)�y�o�3������������v��l�������Q�*)l�kT���w����4�VW�����+�=8s��t-a��Q�
��g����E���������6�����-�
�����>���+�=��c?��������W�4����������U�����z��1�K/���c�d����m����)B�M$��\����'��Y�fY���m���V�^=;����e:t�Q�F��.p�9�V�n]+\��]s�56f�k���{.=�����.��v������Pt~����95pd$��4d`��A.���������[�.]���nr!]��s�����%J�c�=f���}���������?��>�l���-XLL�G�����5���]D�I���]��ZN���oW���];���K]��O�B9�k6q�D[�z�u���L�9"�S�o��-�g���m�+Vt��v�ra�'�|�Ze���n�8�����#�����@Z���k���_�&M��@h�3mj��0a������e�P�B����y��SO=e�[�v�0���n����N��/���s�1��_?�����G ;HU ���J���~�
����[�\�r�����|�I��w��*�}��d���k�j������?�x�lRj�
7�O?C
��`��
��a�l������-���z����)9 ���@�5`�*���v������������5�+9���U�����XL\�������/6�>^���]��{E g �!��u����fo��������[��������c�[���'����GfM3g�t���;��m��yg�������������f�{����A����=�\���{��o�I�;�c;u���G�������]���Gdbbb�O�>�9F���
M������E]dm���?���
��F����C��~��Da���������6m���M��[�N����Km��A��~�,|�|��7l��\����;�}�v7n��h�"��d���.�����E?�5m����)S�X��=�����zn���~���o:t�5n��>��C�E*�@.66�:w�l�_�-^��;���v�m6k�,�o������
.lc���w�}7�*����c�5�E�yg���~�W_}�X?����n�\��>��;��s�w��.8�Te\�n�\��eK�={��\�OU���[o�e������+��7����w{gB�s�9��7�x�M�:��_}�/���������HE�����]���[�@��Y����c����;��/~�V�R%�n��cGw�	&��&=��)��'�R����_�@�y�����O�I'�d�r�r�W�z����_�SO=���.Y��{dBe�w�}�ZxU!��SO��'��n��:��
�t�������*K�,��
M����+��_|���+��o�"E��p�����o���"2Uk�{��n���\z��v��`�n���q�F�7o��p�	v��W[��y�[�S�J�>���l�2���u�&M������M�X�u��i�\aY(
�~�����/\�v���{���z�j��j��V�T)����������B�}�����D�-Z����3\y!k���LUN��s���S�����Z�b��������'..��g�}U���FQ��g���k��T)��=��f��m���
<�Uo���S���8�'���� =��Q��}���5�\4����'�t�RC�d���:�,+Q��w6)�\�������?�p�������&���]�/�����Va���|��y��N�<y���E��4�����������?V��m��%��_��_P��`��=�����ZZ���np�������`h���.@��s�,�/�Q4�@���J�0Q���}{{��GB4P�U�^�����K|����=
B���P��Zq�Z���}���5���b�5�u��n������6l�0�~�����SX��Q����P�a���|zmU��=UEc����y�����*��zp�,����*Z�NT����3R`)��PAb(Qrz�7�|����+�n�:��%�\��u�6M�H��[����?����N�
*x�><�<�M�:'
���7�M7d����/��7����?�J9Q���;��������O?��
3��i
2u&��2��	�WM�|��G]8��J�^���s���.U�R���K�����s�9�V�Z�^O����4�BC<�,U�i���S���^]���5k���?��J�����O.8T+�<�����O}�������o'�|������O����>���/����;�<����"RC:�9u���}~���w�`�o��.�S@���T�!�]��o��
��_���W]uUbh&
�4<@!��S�����PLk�)��sEJ�2�v����w��B2
3��;�[�LS;��4��Vu.�}TP��0������1M�
4v�X@)�R��pI��z=��/���5h����SB�i����4dA��Z�M���*��g���y~��n_^e��q��A��BKMc�w�k��*�^{�5��+,����]��I��Z_��k���="eQrJ ��*��f�c�X��������7�<��Us��� H�j�*�����C�5Q������B�`��:�������H��J�u
�4����O�n���o��u��3���[�zg(@S��Z��M?LTE�O��6XQ�X���U����)���SKj�Z�\wdpx��D]��I��j�9s����q��I^7����~�z{�������6�a���Ty�
E���$����'��_��9��
�������Y����v�j�{�N2=Sk��R���w�����QUc
f>��c{���[S#���_�Mr��(T��Za�RU��
���#�WJ`�g0�z^b~���h�)���^+[�l�m�)�����z�U�)��~ph��)5���;Vh����&�Q��YU�z��n�����r�p�m��ni7?�LI��d*��q���Y�8�#IUa�HSg��0Em���5[-�����{��f�MS!�*��}�Y�����#DJa������Y4�ES�t����	�Z+.�R�����vW�q�5�CTd��2u�&�FJ�B8
��OM=U�lj��`z~��*��s�Z���K��s���p?�����c�+�U���#�D�9}��gV�����o�/��A���@fS`��B�R�.d�i-3�M*�Q�g�����[ouRZ�_�
� �T����{���U��*Q����P�u�4!5�d[�PD*��r�;��\j
W��F�P�����:���N��������*����^Ck���z����@N��
�n��&�������%�zf��uJ	�}HY���49Sk�)�� M>�tT�<*�9��#
�S�W~��QFRE���S����S�[r[�4XS�*�pk����'�*A����>��Uj_[�x��d�vS[�5U���CQF�J?�/\�m4��F���ZKP�{��P��5Su �E
��:N�#>��C��i1B�F���SUs=z�p�����2��j]������o��h��h,X�Um��#WI5`�����\EWZ�S.��H�Z5x ��r.tYP(��BM�M�8����[7�g��-�j����|���`�[�z�w6������Q�+TTF�	��Hm��K�^��9����R��K�\��S[�
�$��K�:�����\�rB�K�|SIk��MQO�>P}9����\ +	�g($�4iR��p�[+U���������c]xLk�i����T���!����VK1bD�`Ma�_|au��q����]�f��^��5�"��QU���RS!7e���&�j}�H�Sa���^Sk�����t�J�M���M}���U���+��e�\u�h�E�a���V��������'�p����!U�Z�-��!dEZ�L���1����J!�6-���K����w��)�Q���-8�V���"�5���k���S���^�b�u�������T�^�{T�5j��4h�Zn���;71\S�����c���5���S��w����g���~�������[o��ZN��a�{��w]��"/���
�[S�5i�6�OU��=��D?���::��E�R�*��l�<��s��Y������O���K}��k�v�MIT��B5�kJ���������Nro4\�1@V�0Jk��z��.S��*��]|��n@������w�W�c �VV�R��4
�*V������H�R`
oT�t�-���O���j�~J���O�I�ZwM���9��g�^{�{=�s��SC�=���.(�.)�RWd�������((����]s�5�\4T�
@�������n`F�M���T5�����{P��k�O����.�>������nH`_}�U���>��O���^x!�u�RU��r�Hz�uZU@vS�n]4h���R�"
{Z�h��"`��Qd���s�c>D��R�&���y���dZ����V�^=�������}���BEJ������w����������j���[� �I�&�=4�s�u��+��:s���[4�9�=���?'��w2t�P�Y��;�^�9h�;}����i�
VU=��9���D��P��a�����z�)�#��g���X4q����@?����_]p���]a��$�Z7��%�-vY��`�{V%��,n�@�[��;J^��X�J�zG	jk���l�m#�=���fS�{)���Y�����]�������U(R�z���%�;����-�L[]��J���c88s��t-a��Q�
��g����E���������6����9��m�M���%��s+xG��/�
9j*�����~����@��U������hY����]�������+�p�j����������s��>��U��Tr�s~������������O>�z�����J�*�E�4�C����Z�d/��?���X��e��YE���T�P�F������`��E����@�����v|�|�Q�(W�X��\i��R�I�B��U�V6�|��k�kU��}�v[�p�1�j:�=�-T��_t�=|�i�=Z�t�[��G�r�Tr�4.W�U�+V�r����b�!�
���"�z���y������!���O����%����~��l�b
6t��S��\}��v�-���m���@���1��� A������?��MJ���W/[�z������=�����O?Y�"E,o����9W��\����h����K7��S�Nn`�6��\r������\u�U�y��.���+����y���������v��g�M�:����o���S����O2���R�
*��g�y���ice��u��u.��m��V�V-�����*)+\�����Kn�>��D�iM��5k�M����^��7�����������=���8�w�y��_?��o�w+����������`�=z�������k��<`��]�v���U�Vn�={���9]�����s����[���;��������o'N��U����C����?���O����tQr�����W_��U��[�n.l+V��kK�9s��O�f����n��o��^�uw��o�I���,�@n����r�JW�v��7Z��y�y�'���O>�.��2��+�;_�re�^��-Y���U�_Qr�rS�v�I'Y��%�����S�����ke����&Le��u������@��r��U?`���3f��*U��V������U�������*Q�d�
�3�8����[�b�;�}�v�={�����K,_�|n_A�/���*��:�,�X ��*�+P��]q��n�:{��l��Q��sg����.�.��q[�l�A�Y��H�"n]9?�r���H4h`�[���c��M7�d�����}�Q+_��kS}��'����w�X�7onW^y��h g�:�S�����nt�Vo��v=z�������������O���^�]��j��6U��Uu���V�^���
jM}��Wm��i��iS�H��@.%ZkN�r {[�-���}����I����1�iW��J@��!����������W_}e;w�����`��8{w����X��,&���Kc���l��8���!U��������?�U�����Z�L����:t�{4��,���2�����:@Vu �t�R{��m��A�u�V�lx��Z�lY;��c�3 ;8�9��1�\ ��{w+]�t�[�:u�u��6q�D������9���;����m���=����/�_�~���M�6�0=��;9k���N�:����>{��ak�������2�&M���i(i��mm��Y��/�~O���;{�����s�u���<������+2Qr������_��3����roB��7\|���������i�}����Q���+����+Z���,G�����G�]w�em��qaPzQ~��&?�����"9111���?���	o���.T��w�������J��2�|�����C�n�h�5
,������7��m���w<���3��o����y��ooO<�DT�CQr����������~�6lh��~�����k�.;������nsA���������I���|B�O* 
���o�?��.\�,���n�U���3�5jd�-�� %�|���R���n����e��6{�l�;��=�������[�~�z�	���;��F9����m��Un�k_v�e��gO�*�P��w��/����9����O�}������c��:��T�^�o���+�0n��%��O<�%�����}����Y������;�8+^��a[�J�\��B�0a��X����Ull�����;BJTM8`�+P��H�Q���5���
���z��O���|���S����w��J8uz����m*({��W�:��@��t�B�
.�Sx�?V�z]��q����.���a
�|�h���=��3�J�*.��Dd%Hy�����F!�����[�Y�"��4�{��Ss���o�&Mr��ZL�=�X��:�y��V��;w��*"S�&��T�L��]s�5��`����YsCJ�)`���;\�L��~�(F2oA�
����g'�p�8p�m�b��Y�R�\9``��@��*��g�w kPn�\CB��C�T�X1q��]��}U�u��7��O>���8���C
�������������S�er-�z�Q�F�����k��h^O��O>�f��*���}���{���j-9Z���?�p�X�����I��n����PS���s�5Q8���Pu��6�8�v�i.t�����g���n�6U�E"�@NI����������{�
+u�)=<�JT@����1���p�
�%QUS����Q����t�0��������Py��������������=)�k������'d(�V\
#�����u��tNk������t}��rK��i6l�{����w��Q��Z@�����������^{����S3��P?`�5������uD����?�g6lpa�*�N:�$w.=D������+����>��^���C8��������%�JP�v�R�2e�X�������2�*��1xx���Zi�����9��M�JC��/���+p�m�JT)'�F��\ju�P��+W�����o��d�4j����&�*��7o�����v���.EU���,���v���~��g��#G�tK������O.:w��`�Tu��L��iP��9u��zj��i�?�|�+�8��)i-?�J19�7ov?�9��3-�v��'�}k�VR��5�I��Rl���??T���-}n/��������1�������\}���B%����/_��*1�]�v�/�����^�#AED�|���_�P����*14�U��E����R��6�+����]H��������uv����,>�;wn�Z�����.T+g�)��[�v��%K�t��k���{�
�;e���n���������T	��S�p�A�. �2e��(s��Z0��������U���_�b�����lRC�j���{=]�fd$�U�q #F����Sp*z�!~��V���Y(��B��Q��%��:����_D%���)��Q!�^\�*��&�`o��v��Y�5�T�����Z�j.TR��V�Z%V]i�1�+�����?�uSr����}?�I�BU�)�R����������u���*x@�4o����2��DU���:
�$�0�P�����o�Te�ZRk��e�\r���3�������(�S����>��l�^[4��� M���B*�T0��m�����PU�
�B��T���F��9U6*S���:U>FZ)u '��k���{���?�2��P��o���+�T
��B�
y���t���z����)�*�T�
1u��U��%���?��~8�55R
���*U��Z3M��#��*�	��IFEJa���n��(���*��[56)�S���TQ��Y4����$��>�`T�~�
3���G��Q������k]��n��BW�/���{�BD������7�t���GU@F"U��O�������g��*��y�7ED�@fSU�?�2xS����f���
�T���{���*7
�T������u�XEC�������Y4�)����+��V\p�����V-�
��k�'�j�6O�(�+Q��w�2��{��WC-�e&-��5�4��(�CYMIU����N_��i�E�����:�-���n��9����)���$i �B��-\��Sht�=������Y�re���[]����j����G���[���Sp�u����:u��!���sZg�����i����*����)���~Ru���&M��B��PVUpjeU%����?�^;�dW�z��W�v)Iu ��W��O?�����Z} Y�*���������
Qk�i�0�YjM�O<1���|
y��K?4�H
�����U�>�����i��S��W��={��L���NU�z�Pv���*�t�H&�Z�`���NUE�I%�����u���1�@N	����oYe}���KqSz��_@j),S[�����.�S��5�������Z�xq�$�`j�����\��Z(SKm��S���%K������[�pa�����BM�
Ga�B�Pa�6U��-X�_����>}���w�������I-_��~��7�~�(|����������\�0}?=��KU{��BQ`�f�����Z0X�����j}8���\�n�������� +�)$S`�O0
'��RA���4�S�0�Zn�n��<Uf�%OQ�������P��&�j��*
�����w���*A
�nU��Q�2�K��z�zM
��h�c��J�t\�)@�<yr��
�>�q�o�N�l,�?�m#1��!K���~�OHR�hQ�T*�Y"�%%D!��,Y��]��E���HI�d�%�2v�1����9�sf�3c������:�v�9��y�9������&M�d5j���+z{�g��� �^C�S�
JM�865�~�zb��Ms��o�@���}�������]�hY��S �pL�T�(�S���}��u3v��M�������4[�*��|�I7��.�[3�>��s.{�D�*U���v�5�z���|F����k
�4����>���zB�u����{��x����q:^��������_���~��Y�EX��qjr=�-[��}������^�re��%�R��Ma�;=����q���g�q��y���UD���zk�k�^��
��Kc�M�>��~�=�q��	]~S�+�S���*U���
�����85(���q��R8��,��S�V�����{nR�@wJu�LL�N�
\u�*���+�*�D�t���e��@3w*���u��	\���k�����C��u����SU`
6t?/�S��.]���0q�U�zuri���{����((1b��t�Mn[fR������N=�* T �Yp�z&���~_���~_O�M�Q���o�����=z���5k�������}V]������L�	��@Ne�:�f(	6�@vw�����1c�i��.��9�Z�rUV
��TUU.<���U\)`�0��
x�b�F�r���������>����+�B�s��C�=��i��?��b�o��MH��2�;���uM�:�y��+��8s�M���~��I����;�����-)mW]��i]A��k�@MA����{��X�~}���P^�q�5��M�t��?tO��+���HMT�,fyh�]�����o�,v���o-e9K��r^�����GwzK��w�'����6f�Gy+��{�Y�V��������y�����ldZ���o���mcTh�>R;�J������~���Q����5��'�E��.����B�6�qm@�xs�a[�5��
���R���*y�5����BN}��5k�&rPy�����@N4c����m��E���+����S��1#h�;w�EGG{g����/�sbN��8���4��O?�dK�,q�j ���k�>�����ip@�U:?�����*�;��5��x���SO���;�����[�n�M3OhB�}\U&��Z)��[(g���s���.)�9��U�J�8���j���={�D4m��)SRl�G����{g�E�r��u"2�=R;���7��������Z�j��ys+X���@(|r�v�;wn����
x[��W �������V�^m�������@.W�\��iS+R������	;��@.66��=�\����M�:����z����M�8�f�����;��������W �*�n��f[�v�������s�Y�F��V�ZA�B�}��yg���IJ�,iu����t�w�R�������m��)��������5 ���@�Dr &&��u�f����;vx[�f��5��S'���K,G���O�>�n�:�d'r`��Y6f�o-�t�z�
�e���m�������V�����d3g��-Z��M��-i���g�y�p�;w��7Z\\��m������W/��a�wdr'Ill��7�|�A[�v��5m�}��g6{�lk�����+���v��n����m���n;�S��������e�]r�}�y�����l�@�$P5[���������N;����w��o����H����-����xZ�v�WE�����=N5
�Z�����j�}�a�k_k/���n�1�����;�]����������;��<`�'O���{{�Fv.�
*�E]�m=��k��KoE6����m�[��7\��<�,�oog����M.|�H\���x��<|����N���K�w�}�&r(S���5�v�����+^��*T��z��Z���m���k�.o+�`bWu������;-v�#�]����p��������Y��k���M�<�d=i
���_o;vt�S�9Rm�)T�0OE�����]�Z�Z�,g���on����-Z�"""�rR�{�y��e�>wtew�]���v��M���?�ykh��c�����)�tY�����;���	��Kk���
<����>uS]<���������[;��{���c_��^j�R����|�'"�~��;�x����R���!o	��
���Y�\91b��^���o��b;v��^��*��_��i�R��v|�-�D�3�����Dl��;��}?���6��{K@�8�yc�M�O�K�8�l!��w��k��&L�`�|����[����X^{��V�^={���]�S?t�����Z�n�*�-6)M&��C9r����{v�}�y{Bw��[�h���P�?��f�U�~�x��������gEO?b�.�a��'�]��!�,��u�Z�6��j��+�����`%���R�3�m�>���Z�6+�yK�qQWo)^�����e�yk)[{MW�^�vo�l��X�����������=�o��vE��������p��g��_+����yk)�s~Y�zeeo
i�u�E����B�6�qmdi�6���u�+�
�6��Z���k�]����Z��?x����u!/���p7�Z4Vx�b����/��Q;���Y���r�E\��w���|U�>|�UoU�R�����x[����@����6���	 �h\��?�>�����[qo+�.�q]���F���;�j����������d��N��0N/Z`���������Bn�������������Yg���Ab������o\�a�f�l��a���GTT��?q�D�9s�]w�u����BN
�49��/�VR���v�?�
����,v�ro-e����]��������^������s��^������o)u3o~�[�1�1�����Z�7~�b�����V�?`�_���������
e��xo���6��������bgx+��.�gG'}���,�*[��xk���"e\�)��������=���H��^�����������������T�����~���R�����-f�Jo-���*�W^y�^z�%o-y^x�]~����I�^�z�I��y���m��f�_�
:4��j�*k����}��iz\6lp=0���k���?���5j��-ZX����D�������_~��L�q(OQ�O�)?��c���|	*>Ki�NM��a��M��o�B���������������=��B�`��V�bE[�x����_�V�l��s��-[����M89{��qo"�7@Z�����!���rG��H��*�	��3�f�M|_?u�������I����J�3�}�<B��'�}�����Z��H�E����.�k#�qmd���k#=������Dx��.$�}iY�!kP������!���oo��m����j�V�Xac���C��t%9s��u!��\�%����7nlo����B��O?��~����N�M��wwa�~�-���B��������J�����W_Mx�*X���o�U�V��C�>�)������T�R�������;�=8�4�������
>�/_ns��qi������Hk��zK�[�9�c����8���S���yh��[9�^�edB�b��T�+���U6��� 1e�n�%iS��O<a
��������dX�`�5j���.
�"�����]E�BQU�)�P0���G���������Q���c�T'�T����>�~7�+W�q�����k]S�\��5���^s!j� ��_~�^x�m��
zO���Y������������PX_�\ll��y��������Q���{�v],g���)�����������JU���o�����=���7�T�Z�U."k�rOp lp]'��������|f�>��
����_�MB��n���z�3L����1i���K�s��.��������<z������[CR
��n��F����+4R����Pi����O]Y�\���)TU8�U�M�4�u�U�TU�U�V�UE�]y��.pu�nPH���_������K;��s�����V�Z.'S�W{*�
��@N]$UN����,Yb����{�j�3=�`�W�^���,��g�_�n��m7�|��<c�������)~*h�������~�������8�, )��D\@�R�6��Ym�&a'�w�����������Exk�����zkY��=q6���6ou�k+�P���Ok�0�4
a�-[��AFZ�.~Fy��K:?�2U��B��yI���:t�`�[���y������IUn��I
���B��n���~��o��?�n���q�4h�_R*Tp��]�2�1}r��d��.���t����;�9^|�E��8p����(t;|�p+W��Ko��)��8���\fQ���������c��sm�S�m[������{��l����-���U���6���a�D�kS�m�/G���1��5��uw���m|&�T���3����'�1�T��n�
r�]�D�.|Qe��K�R+@��w�}���;���R/8u�LL�W��Owa�e�]��{��w�;����8f�y�.�O�I���:+�.�:�����������m~~���������'_�\����bN7h2�^�LSAYJ4����UF&G�K`���A�
��������H�"n[R
��������WJ��NUfM�2�W�}t_��DX]~�F��"�U7��S��ifU [�����>i1��w�7�%��n��v���e������`�����P.�����uG�5 <iX�@����O���[ou��j*p�*���Q����u��
��I����&|]�v�G}4�	
2��7o�p?=&{�X`��a��r�����:��
<='mS����}�y��i&���S�����c�����#���k�����S?S��hrA����<x�+K����w�q�����
���9��&G��f��I
��2���������xp��j���8�KRU��5������!��@�P�[����Zp{^��-�<bB�;��2���Gm�������o	?���1�������?�+��EjbU�)�
���emC��7#�bk��	n]���i�}U���I
�4v�|�&����i*�QqSr�L��jF��{��Y
��<���.Rp�x�b��x;v���}����3��?��37��~�9U�i�������W<U�i����lB�9���]s�5��[�4U���P�^��>��s���w��F��z*�R��t�i�+��p�����.)����!��4�k�S)�T��`xIeJ ��F��@���\�n )��D\@���6��
��Q;�%~��p�tch�o��������5��[�lq2�I4�V 4�U�@�����W��B1u�TH�s���_�O?��U����+.$��
�4��fU0��������m[�}T�n���j�=~�a�dS;Mh��H���0U��)�����+@a�YMHi2U�i�uoU����������^��PP
���Pa��5pz�7_������n���Aa��yuuM.��k��TTM��9B����h��P*�$���/Z���L��5�yT�����t�"vc�3�%����T�s_�!�~&��)*0���KK��\u�U.TRLR�<��EDD��i�1�6:����v�WR�L �+n����65*VRu�B.�0z�x{���{����E]tB��M�[���LU���n�l2M��j5Q]���*��%�j��v���� .1�&w�q����^U���/�]71���h�����Cc�)<T(��C��
;�*|����\���C�r*z�t����q��'�N����@5=��P�B��U5�4��"S*���?6B���7 U
h����&	H<��*�T��
�f���m�CT5� ��w��v��%tM
����Xm��Kn���
��V�\b�"�l��R����RWJ�:��@WMu�U���/0�ERN��+���B�0N����4���������~���*�������2���L�����+U0�|�a��.�U��az��:urU�
&��
����R�+����]Be��US�7s��W���<�L�_@FPU�*���3iS��n�<�@� E�f#G�t�U
n��B����v��&G��%M ��s�~(�u�4���N�AUc�%�4u�U�M�q����@��)�L���`3����q��s�V�M2#�u�UW^�K/O���,�N?[`*
��o��*U5�p2��R��N�a�V���y�C _��J5���8�0���~��+�S���Z/�R���7����8i9%@FR��		*%m�B��
��C���}^~��v�]w��#M<��
��M&��3XWXQ�^�:u\����B�-��z��i�f�r�c�PV]���U�Zr��u��{���\U��(�~�{�/_�������7M����*��� �g�n�:w\�������O!���d�*�L�L����4��fGm�����9����P�����)�'�QE�
��]U=@�����9Q�`��������J0P!������'z]�#hu'������-^������-����o���#��f;t����jb�9�@U���/����/K%����r�-.�S'����@a�2u]����]����wj�5?�(��A��k���v��7�����J+u�T���/M��G`\�%K��@�Sr3��$��U���)9��T&�T3�B3�^w�un������I&D�y$�Oy�����w��M�6	�����1����v55�|��M����Z�t��)��8�`�H^��'��������c`�`��PaN�BU�i&��S������=��Xn��TUy�����qIi�Uu
�O>�$�`M9���~��*M���Uy���_W%��-?Q����}�=
�����;jr\+W�t�z�I#����/M��U?30qE���d�4i��+AWb�g�v!�hf^�������������)���K<��W�F�7R�_��^4��N�T�I�G
��g�����pj���o��n��`��(tSN�4S��f��dO>���Na����_�s�=g��Ms-T�T��W�5j��������*p��b�pM��&3x��g�s��HM�p�������k����X��^~�e���/U�5m��-kPu
�����k�^�.
���W���M/�l
�4f����-[�vU��Q�E��y���UD�8
���Kc
*P����J�\S7�P�
�TZY�\97^�g�}�f�M��j8U�%�T~�7�����d�Q;NUU
�T=��.5M\��{�Y�-������S�S�B*)�Q���7Q���S��Y:�4i��?�[�j����+[��]}���Pi�3�SU`
6t?OC�i�XMJ��N�((L<.��0U�)�����;^����#F�M7������k^�@���/� P�U�^�.
${���0kz�w����]�cW0��@�����9���x���=��:N�2l�07��&����8�S2�a�T���C�����s}f������J�Z3�jV��/��M��\��6f�W���H��j��UY)�R�KUU�p)q7H=�M����0)$2d��5�j����!:_�~���>H��d��t��C�������v�Y��o�
�SHu��w��'�������H�����j6��z=�U��*wR5�*�?�d���k����?�g�V�
B�\��L`z���4���\��rG�yV�����T���%�c��u����t*UB�j��_<!d
�*�T�5p�@W���i���={��C�L� IR�J.U`}��G	3���[��O9���Tm�s�c<��	3w��M�&��&x�����tNe7������?�����lL�u���cW��SJ�+�W��^O=�w����������H��>�DL�3��N�
����`�Ri�G�RM���E����,o����PI����v�k�rN@�rt�F;0�#������{'��<�����-�Y��;
�W�vS?f��)��v�~������C���-r�kr	# �:���7�e;2�g�;�� �q��-���m���,z�4o+��4r���Q��
���
����>���;����o���SQ�s�yK+g&� �8�� {;�~��<������E�NEy��d�/��[��/�`yk?�%p�KS kK�,q3^hjXuK�W�^���eK�����
��4v\�b6��-�T�#O��o��
�~,cZ��-��y?
�����[�=�����g�}�M
��V������pj����[��,W����+�� ������[2d�[�R��u�������b�����L��SK�3������:t�U�����^x��9s������z��[�6m�@��Y���+�Sw�U�V���{����7��4M�P�P!+X��� T����H7�����m����V���EDDX��
m���nf���o�P���Z�fM����
4�^~�e��q����z{�$h �c��_��������'O����m����~�i+Q��������7�G��]�&u�6A������c��
�m:������\��9]�V�h�t7�G�����l��}6b����3l�0����EEEy[���+�����	&������/���/^�L��1)r
�T��R���Z�����Y�l��E����������cg�y�ke���i�������`���o�M�6Y��-22�;+�R
��U�^����B�������>j�V |�:�\�2e��~���8��}���W�5-k[Jm��=���oZ��%������9s�t������+U+\���=�5-��27 ���@�Dr@&"�2���|r��m��zk���>|����g�_~���?��
 T���{����i�J��b��y[��W �;wn�������+�+X��5n��uW�8q����x{��W gu���>}�X����~����+���i�l��A���s-::�;�|rQQQ��Y3{���m���.�������]�j������������_�9��+�+Z��M�<�u]��t�wT��(���fZ��e���=;a���G�����]u��9���m��i���.�s�=�������>lO?��u���v����@�������c}����k�z[�q��![�~�������G����o��5k���O>i.�x��*|�W��w��g�aO=��U�X��}�]��@��������u��Qv�WX�|����r��i5j��g�}����k'Nt�X�p�+�S��`�+_���w�}�7o^oO�*U�d��Ust����W �*��[�Z�R��D�)P��EFF� O����W ����s����h�R8N��}�p�+%��?�]|��6�|�7o��5�?�������@���EDDX��5�r�~�\(���Z�dI���^{��/�|�#�]��5k��~��'���������]�v�����[����A����m�Z�z��{��w ���
����m�����#���M�q���2n���.�����UO�fZ(R��
2����c�����\�r����K��>hS�N���G�Yg�����@N4kj��U]��t�R7����5k�����:u�X��y����@.66����\�rjt��;l��E�m���@NA\��M]�rjt�&}���������
��4wY
��={���������fI�W��kM�4�y�������`�A�n����>�"""���+�@N�2�p�
�����YS�O�n;w�tM���R[�l���U�]dd�wV |��e�Z�j���_���/��*U���emK���5��,Yb7�|�w6 �������*U�d�_��
*����-�V�F
�]@<_�:.\��������+���3������������}��y[�
�bcc���������G����8�1c�]u�Un"����[�V�l���n?�4r�=z�1��L�b�v��/_nO<����U���k�G���m���m��6 ������cC�qUpE�M������m���V�^=[�x�������aCWE�����c�p�+�S5���]�����j}���
���c�4ib�^z��/_��}�Y+V��M�6�:����W ������w�Uk��a9r�p�7n�h�-��e�Z����69������.�U�V������@���iUU�EFF����e�����_|��,Y��z��9sZ�\��5�9l�s����h�Dc���;�-_q�V�`A�,��ow��*����p�+���?����?����n��@ W�V���8U�M�0�U��+k��: \�
�"""�����c���O?m?��M�>�j��m�_~���u�������&u�_�>]W�c|rR�fM����7��_�)S�X����{��.|�L����gC�u�?��3ni�4��O>i����
4��
f�f�rA������/n����������k��q��w '���R�J�[j��m�T�R�s]S�{�9{����b���#Go�4r~���Z\\����4rQQQ6{�l�1cF�6~�x7���>h;w���yjZ�f�u���.��W��>}���u��#�������Rjm����z�@V�;��,�/�������k��Z�jm��~��iu��m��OMCO3�jL=Mv!�������[��O����{K8U��f��i�{���{�Z�"E�F��VM!����H��e�Z�^��L�g�q������8=?p�;w��7������z���`��
�=Bs�����:Un��=���nO;�4w�>_�����m���.�{���]������.�%K���_�~��W��o�����y���U�vJ�������>s]w[�l���b���}�0`��>}�t����~�U�P�u-Z�h�MA��� {��i��������[o�����kv��W���*����oO<��u����t�����~���c�}��7iw�}�{��i]��_���w����n��M�v�Z+^���u�Y�Vdw�9����.��J�(�m5�������nEq��r��&O�|J����LA���.��"o���]�u����-[l����M� ��=�\r�<�L�X���K����&����z�����dS[�B����+X��.\��k�v����.n*�\�`��h��uQ��7n�������c�}�
�N?�t+S��N
hBu�\�z�q�[��9-W�\�u�V7���F�K��09C����s���
�V�c�n����1c��P�&L�n��:v����@��+���/��+W�u��d���n�B'U��.qP�1������9�F!�^K��'��t��P���A�\�������C]W��8r�����Z;t�����N��I����Q?+�}��z?$���I�����������5����.R�u~-3�����6�~���c?������\�q>wS��f���O?��*�~�a7V�B#Ul�ke��]������s����c�C�����Ud������sn���[V`��&���9r����{v�}�y{����O=��-Y���b5k������L�k�6m\���q����.���N���E��5������ks�xk);��!{��o-��C�Y�����fs��v��R��Y��	V�`o-e;��f��=���k������u��������\�������t���n���6��a�B�Z"WNkW�����o��vE��������p�>��k����<o-e{�/k[��������q]����.�k#�F�����q]�
y����w��fX0`����2e�M�:��o��z�����o�c.��i�;�����������N.u����\X�4��9rX�
�v��.�����=��|W�����>��SWn��}{7V�o��f=z���������_�~v�m���T���������+�B�_�*�z������g%�7��#czk)�����z���Qm���K��������o�,v���o-e9K��r^�����GwzK��w�'����6f�Gy+��{�Y�V��������y�{k)+Y��V������a�ZW�GjGX������y?����<� "*W�|����\!��;�y]�F<�����!�����BNUo
�(%G�j���x�	���W^i����Lc���K�s�jP��S(ll��������%K���A�i�u��~����'h ��I�]n��mn�&q�;w�k�	���
�Nq��S�9�����jFT�~��={�XTT�;�P�B���)d��{���K������ k�)���u�z3�j��^�z���p��8/��B�?����_���i��9s�X���xz�PW��y��=���������_���	����[��6l���!1U��S�U�������~oO<�kT�Z��,X�-�F]��/o�g�v-)u�}��w��o�u;T���F�E�@N� /��R7����*xj�����7�5-��W/���e�������v��7[�*Ul����rp��Mn�n�t���k���o�����46_�6m�6�&�O�ah�=}�?���"��j�w����o_�;z��G�2 	�i�7i
���]����O��&lP����SCjc�T�t@c������;���]7V�l�>|��^x�+S��w������:u�dm��u�}�f��@���������<y���#\ ��#�.��69q�D�4i����K��gO�MM������v�mnL�SU��5m����cG��nU��@����s��(R��
4���w�uW��s:�~������{��@��j��q����o�;w����[�R�\��SO=RS�LUx��T���/���K��������{���/_>W��cu���b������l��5	����Sq���Wy�"U���o@F����M�n�P�d 2�����LD d"9 ���@�Di�bbbl����Z���w���C�Q�F��eK���-66���w gs���j��Y�N�����n{TT��k����oo'N�7�x����g/�����!�[�|��m�����g;v��������O�����)b;vt-O�<6x�`���_�1@����:N�o.�Gy�F�eg�q��~��w���`�W_}�6m�d_}��=z�����@N�S�,Ybe���6m�X����������,22�uS��+�����j������>���s���w �~�z����D��V��������o�*U���?��jV�@�����q��c|�!������n���K�����h��������J�,i�W��
6�m
��]U*W���	���?\���^h�������W w����5�\c+V���C��`��?�	&X����>�����s����>������N;�4�g���6j��n��V=z��|k����|�A�eu��=v���Z��U���~����-����o��s�9��b-[��"E�X�����W^��{�r��mV�hQ7��SO=eo����u�Y������I4���Q�l���f�{�����S��'�|�6m�d���w��xi
�RS�L&q���@...�6o�l��M�����#l��}v��a[�x�EGG{G�4r
�~��W7YC�b��v����cG7��B��G��q����N7#+�x�9�q}����S����+��|����w��7���kb�m��y{���;����������#G��K/�d�w������*W��an���#GZ��
m���n?��������[�d�����:u�d���t����C���tc�:t���/_���={l���V�J7~\�9�=�SW�J�*���k�����V |�
�bbbl���V�P���q�����5�/66��
�/_�\���]T�r������ct������W W�@+[����3��N����F�4����}t_ ��
�r��e����b��Y��}�������ho�?�M�>��w����n��Fw_ ��
��Z�j�������5kf+V���;��u�\<x���A!��������Y��7�|r��'���C�Z�"El��e��[o��%K\S��W_}�*�z��m�=������h��v���n��1��CY��u]���{l���x�bW�/_>�^���}��.�S(7e����k�[���%KZ�9�#H�9��+���o����#�e��������;������������:7q��g��jk�����p�;��5k��h�����{o�P�
�:d���]��U�-]��v��iG�u�s������h���Y���+�����Z����/o��u�r��Y���-g�t
E��4%i�J��s�=�[*_��&q���Km����}�vo+�P�
�"""��{��]�v��	,&&�� ���V�T�
d����=���6{�l��m����#h������X�@�J�r�
���>��y����k���g��iFV�r@�����5�Z�ha�������@���C������k]��������b�<y�-Z�;�|r����U�VY���g��v�WX�|���R��1��=�\76|r���v�������m����V���EDD�w�a�v�rc�EGG{{��w��j��Y�����W^�����	���o��cG�e�������+�S���A7����;m���n�d��nL�`M�+��]�&u�6���E��.�qqq�������
9 ��(h �YQ5C�YRo���e�4�S���Q���x���,�@<���(h �xF��,���
�r@&��i��-[���p:�����n��M��;_��fJ]�~�k���c����C�y[���b w���7o���1��9s���]�\�r`{�6j�(����,w���3'�c�S�<y���E��V�Z��r�-.`S�r`{���{w��w�U�^�
,��_���)xk�����[��lE�qM���Rk���
>�{�1��+�wF |���u�Y6r�H�2e��7�*W�����-���W_�#�<b������7_���������e��
�
(`m��qM����H9 ���@�Dr@&"�2��@.66����\�rb)��W ���i���i9����4���c��q���];����������{{�E�@.g��m�������.��+^��M�2�6o�l3f� �|
�.\������a�M�4��v�j�\s���p�B���;]H�7o^�Z��u�����[g111.�p���S�������o/���}��WV�^=�R�����[��[7���m���n}��%6m�4+Q��]u�U��3�����m���L��kR��B�
Y�F��O�>�������;m���.�+R�����z�~��A���E&z� f�Ro	�Y�w�����Q���
����B�j��;��t[�reWI��n�������[���]����d
�n������l��!6�|��w��7u
��;�<w�/�1��2*G���Q��
�T�v�����q����������?�|7��&ox���m����+������\wn��$h ����?��8`�������k��I7F�&o�����]U�g�y�5n������fY��{7�8�Hu`�|��Y�J��}�������1�j�����6l�=��Cv�Yg������j��/��.������m����h��S>�[�f�)/����#�����&L��:/2]�R����p�����U3��m����cK�.�
6�YV��/�B��N;�U��i���t�rJ��:k�,�_��
4��-[����G�V�n]�?-2�����)�KN��y�D�J�����n��]���?��������T���3���L�Wl������[����W/X��Q����W ��J�,���Kn�g��*��(P�m;�( ����l�����eK�+V����������������Pd�y����i����G����R�w���c�}��7�����?��'���]�g���&�EF��g�f�>���N�u$/�k��xS�x�����.��h����p�B�P��]t�E���i���8��:/���
oxK'��Q�������%'�\:hV�M�6Y����P�B���,X�U�X������:/��I�,�j����@ �[�nu�E�������f�=���������mj2��@���
���@<T���n�9�4�'�d�����cGk���[��/����:���#����������\F�7�m�������5�f]T�}�[o-u]jm���z�����}w7��Re�5���?�B?��R�����x=W��-�����xK����.o)uQ���]��s��#1���C�Z�:�y�l��V���R�����h������+�X������mkp��?�.R�u~2����x\Y3R�u>��/�-Wr�������������:oR
�4h��2Z�V�\���
d"*����o���u�Z�f�l��a���GTT��?q�D�9s�]w�u���2����Q!���s��-[��r�w�^o�������3W�P!ok�2������C�����/�����_��m=����m��9V�bE+]���5eu^�����h��V�NW����o�����=��>n�8�\�jU+X��[NMF��>�t��#��|��V�J=z�����6m�����K�.n{������ow�h��6m��m��z@z����INM�������k�-�(W���5��I�u���F�i�[����[�|�����r^dmT��5k��3fX��]P&�����M�:5��YF��*��LD�����LD d"9 ���@�Dr@1{�l��#G�����-Z��.��R{����-@��Z�6m�}���t?�?���������?n�\r�{e��������O�n��������;�~���%}���z����){�������v�����_�hQ����l�����������P��W^i��-���=m���n���S�����@�o�b4f��?��%�t��C���%K�-@��@M�c����1116p�@�Q�����k	_���]k���p�
��cGw����~���|�MoK�V�Xa��~��m��f����������g
4p�����H�����+Wz[�NK�7���?���29 ��\��m����6i�$��B�
���?'{���Y:d]�t�-Z���P��s�=�����N�_|������m��7w�<��3'�W��t����O?Y�*U��?������O>qKy���A��pA��}���w����K����j����G�z�B8+\���;����}X7�x�;n��Q'�W������Y�)p��a��%4{���>}����S�n��6o�<w
9r�U����u���\H�7��������$�~��.��BwLf����|�F�yR���[2d�o
���YDDD�����EFF��9s���&{���Y����7o�Gy�}��Q�3�8���|�"E��
���W��t����b����Z���LUp�o�����'�pa��������>{����&Lpa$��	z��%}�k[����q��~�	��
(��gU�������[��]���W_�������0��+�������/������'�k'3�r4��FR��~��W�s|vdmr2�������)U�4k��5j�������m���V�Z5W�4D����J�*��9sVTI]�fM�w���.������.�+���ka-0������g��.�������S��.
n�A������5��h�$}���%�k�vx�_��U]�u��yG�� ���eu��k����gp�_~��U������%J�u #�=�XcM��z�k���f�����]u�U�>��n����\_�����u������$%K��B�
y[��7o^���)0�����'��l�������O?��]��7�Nt����5�k����w�
t�����6�r�-���_��I�r����CFtU���������3��)S��	}���	�t����z�k��j����dy��������fW�b���K�z[��u���f�����kU�T����_���q��a�M7���}�J�.7c�������{/����y�������q}��u�Y8��ukw�E��MJ��������[���k���a��5k�xG�c��I����}�n������7�c�o�W�^��I���K����+���$��=���#G��
2$.22������������v����E�d��������q������{7�qz|z��5e��3k���q�Fo+����������J��;��g!}N���4i�s���k�d�
d*��lN�9�P����e_|��8p�U
��N����`��?����	PE�&S�����e���X�'p?�f�5��*xD�m:w�����f�;���������BPh���:��d�m���SO=�0��Y��@�z�/_���6mj'N�'�|2�=.�6m��_~�M���5�������?�h��Ww3���A�U=�J
]��C��o��f���s��C����>s���+N
���Ecn������h�FM��k$1M���R6lh���������E�D����7�t-���{n]��x]3�v�B�W����Z�j��i��s�=�-i������II��W��,]Ozoz�B��K/�����{�97 � ��9�����o'���.D�W���W�^��������z}��\����Z��e��Gu��>��u���u):|���Y���@_�4�fa�@���Q�uk@x��l��z�4�^��4��m��f��s��XAt_b={�����?�8�MA���j��6m������Y��j"�[���g�}���x"���@�����wCH(l��$z_jB�;���u�^�j��~����?u�k����Y
u������3�&�x�������s3���+ {!��1����i����{��7a����J��e��o�I�D_��!S��+|H:�W���m��I��W_���_�m�]3g�t���)_��[N��s��&M��eU��2B����f�\�h��XH�N�:��������H��S���?}�����=@����������B4�N�Y%"��T��:��?�t��w#0�����k&@���1c\@�1�2�*�T-�1�T��YVU��Uv�L���o����.H@�C dc����?�Ls�
x-��w�U�P�U,l���m�`������e
0���?��%�n�}.P����U+V�U����%T�����x����qcW���II�deU]��1�]�zl�Z�����	�
�Dn�*.�7BA�����n�S��^�jzo���{�nwLF��p?�P��um>��C���{G�e��Tz�� ��K/u���Jn@�B dc
�eI4�]�{D��Y��
C��k����?�����r�����;u�S��B�o.��#u����/FI��@����]�=�q�kC��5j����F]E�?�|������
(2�G�U<
��EJ�)_�p��ZfN��P%��u���[��h��_|��1��g�~�����*0{���e��jz��
�`P��t�*�K<$�Gv�L��m�A��]�vu�d����_���r�J7@�����@q�M7��>�
����h�}�Q��/U���
)�U��&~8�s��8p�=�����o��!����BY��4y�����\�;u�S8'�������Ca]f�����[�5��|���� se�g*U�j;�W?#i`��oUx�iY���Y���i��@6���nn�5�	�����(_���v�
I_�4��*��D]�tm�[���J�ZH���U������f���. S�q��EH�\����KU��O]�4���#���tS��xOi�Ud&wM$n����.z��{��w\��x�b7[��#������A�|��K\���g*@f#��1�o��_������0T
)4��Q�c������u��T�#�t��*����:�u1������{��g�]w������RWV
t���kr�>���8�j��@��O?��M��/������D�����-�B�e�zS]TW�)��XV
�����Ko8���
�V��f�
F�V�^m�*Ur����.���7B���6�]�X��kZ���Bu���O�@6�zt^]"4vN�p@3qi`�;��#a�bU�C��i������7>p���d-g�q�|^<I�K��7u���?�/Q���������;]{I�����U�C
2J�.�?�~�nF@F���+���T5����Im���
�5��(���p��A��&w�]�Uw*��l��P���pU���H�))���~�iLH�+�����J74d ������ku���$S�NM�&�/*
��M��<�jH4KX`�zu��<y�q���'�����`Z�~}�AU>H.X� ���K]K(h,8n���K�4���~���]����+Z���w�5��1��O�nO>�������a��)P��*rt]�zY�|y��A0�$
���sg�Eo��A��H��%K�� �}���ZL��kD�J��-��/�p��*�DA���U�����^��~����]K��u]��TIjU����|�����8q��P%p=�iY����l]��������T�n�z/�oQJ!�{�bIDAT7�t�~Y�?��Ogq+V�[�t���x����5i����w���w�x�������9r��G�!C�w��}��Ao�?�k���;����V e��7�?����D�f�W�~��5q�{�w���|���93�\�r��GM�tLbk����Y�f�1:��?���M^ll������Z�:Aj�o�W�^��/�w]���}��=h�v�����#��}����d�4��q�-X� �t��	�T�T)n�������3��
L�37��1@jt=�=��C�Ir2�3Uttt\�.]�;��^��������H�s# k�B8h��w�}�u=RUP`�;U�xU�����&l�O���?�������s��:u�tB�����[�^���e���t�@�����)S\u���}!J�x�k���U5���n����ss���YPuM���J�*��W�'Q�����h�,��d6����LU��L�������o��_mW]u���n��
r�������������q�U�X�U�f,Vw���w����BO]5�p�+�hY��/P��Wf~�R����6m�$�m����:��-�R9o@�B�Dr@�1��`p�tR�IEND�B`�
Apple_M2_ultra.pngimage/png; name=Apple_M2_ultra.pngDownload
json_bench.sh.txttext/plain; charset=US-ASCII; name=json_bench.sh.txtDownload
#13David Rowley
dgrowleyml@gmail.com
In reply to: David Rowley (#12)
1 attachment(s)
Re: Speed up JSON escape processing with SIMD plus other optimisations

On Sun, 4 Aug 2024 at 02:11, David Rowley <dgrowleyml@gmail.com> wrote:

I did some more testing on this on a few different machines; apple M2
Ultra, AMD 7945HX and with a Raspberry Pi 4.

I did some more testing on this patch today as I wanted to see what
Intel CPUs thought about it. The only modern Intel CPU I have is a
13th-generation laptop CPU. It's an i7-1370P. It's in a laptop with
solid-state cooling. At least, I've never heard a fan running on it.
Watching the clock speed during the test had it jumping around wildly,
so I assume it was thermally throttling.

I've attached the results here anyway. They're very noisy.

I also did a test where I removed all the escaping logic and had the
code copy the source string to the destination without checking for
chars to escape. I wanted to see how much was left performance-wise.
There was only a further 10% increase.

I tidied up the patch a bit more and pushed it.

Thanks for the reviews.

David

Attachments:

intel_i7-1370P.pngimage/png; name=intel_i7-1370P.pngDownload
#14John Naylor
johncnaylorls@gmail.com
In reply to: David Rowley (#1)
1 attachment(s)
Re: Speed up JSON escape processing with SIMD plus other optimisations

On Thu, May 23, 2024 at 8:24 AM David Rowley <dgrowleyml@gmail.com> wrote:

Other things I considered were if doing 16 bytes at a time is too much
as it puts quite a bit of work into byte-at-a-time processing if just
1 special char exists in a 16-byte chunk. I considered doing SWAR [1]
processing to do the job of vector8_has_le() and vector8_has() byte
maybe with just uint32s. It might be worth doing that. However, I've
not done it yet as it raises the bar for this patch quite a bit. SWAR
vector processing is pretty much write-only code. Imagine trying to
write comments for the code in [2] so that the average person could
understand what's going on!?

Sorry to resurrect this thread, but I recently saw something that made
me think of this commit (as well as the similar one 0a8de93a48c):

https://lemire.me/blog/2025/04/13/detect-control-characters-quotes-and-backslashes-efficiently-using-swar/

I don't find this use of SWAR that bad for readability, and there's
only one obtuse clever part that merits a comment. Plus, it seems json
escapes are pretty much set in stone? I gave this a spin with

/messages/by-id/attachment/163406/json_bench.sh.txt

master:

Test 1
tps = 321.522667 (without initial connection time)
tps = 315.070985 (without initial connection time)
tps = 331.070054 (without initial connection time)
Test 2
tps = 35.107257 (without initial connection time)
tps = 34.977670 (without initial connection time)
tps = 35.898471 (without initial connection time)
Test 3
tps = 33.575570 (without initial connection time)
tps = 32.383352 (without initial connection time)
tps = 31.876192 (without initial connection time)
Test 4
tps = 810.676116 (without initial connection time)
tps = 745.948518 (without initial connection time)
tps = 747.651923 (without initial connection time)

swar patch:

Test 1
tps = 291.919004 (without initial connection time)
tps = 294.446640 (without initial connection time)
tps = 307.670464 (without initial connection time)
Test 2
tps = 30.984440 (without initial connection time)
tps = 31.660630 (without initial connection time)
tps = 32.538174 (without initial connection time)
Test 3
tps = 29.828546 (without initial connection time)
tps = 30.332913 (without initial connection time)
tps = 28.873059 (without initial connection time)
Test 4
tps = 748.676688 (without initial connection time)
tps = 768.798734 (without initial connection time)
tps = 766.924632 (without initial connection time)

While noisy, this test seems a bit faster with SWAR, and it's more
portable to boot. I'm not sure where I'd put the new function so both
call sites can see it, but that's a small detail...

--
John Naylor
Amazon Web Services

Attachments:

v1-swar-json.patchtext/x-patch; charset=US-ASCII; name=v1-swar-json.patchDownload
diff --git a/src/backend/utils/adt/json.c b/src/backend/utils/adt/json.c
index 51452755f58..8f832dacd40 100644
--- a/src/backend/utils/adt/json.c
+++ b/src/backend/utils/adt/json.c
@@ -19,7 +19,6 @@
 #include "funcapi.h"
 #include "libpq/pqformat.h"
 #include "miscadmin.h"
-#include "port/simd.h"
 #include "utils/array.h"
 #include "utils/builtins.h"
 #include "utils/date.h"
@@ -1621,6 +1620,22 @@ escape_json(StringInfo buf, const char *str)
  */
 #define ESCAPE_JSON_FLUSH_AFTER 512
 
+static inline bool
+has_json_escapable_byte(const char *str)
+{
+	uint64		x;
+
+	memcpy(&x, str, sizeof(uint64));
+
+	uint64		is_ascii = 0x8080808080808080ULL & ~x;
+	uint64		xor2 = x ^ 0x0202020202020202ULL;
+	uint64		lt32_or_eq34 = xor2 - 0x2121212121212121ULL;
+	uint64		sub92 = x ^ 0x5C5C5C5C5C5C5C5CULL;
+	uint64		eq92 = (sub92 - 0x0101010101010101ULL);
+
+	return ((lt32_or_eq34 | eq92) & is_ascii) != 0;
+}
+
 /*
  * escape_json_with_len
  *		Produce a JSON string literal, properly escaping the possibly not
@@ -1645,7 +1660,7 @@ escape_json_with_len(StringInfo buf, const char *str, int len)
 	 * Figure out how many bytes to process using SIMD.  Round 'len' down to
 	 * the previous multiple of sizeof(Vector8), assuming that's a power-of-2.
 	 */
-	vlen = len & (int) (~(sizeof(Vector8) - 1));
+	vlen = len & (int) (~(sizeof(uint64) - 1));
 
 	appendStringInfoCharMacro(buf, '"');
 
@@ -1661,19 +1676,13 @@ escape_json_with_len(StringInfo buf, const char *str, int len)
 		 * string byte-by-byte.  This optimization assumes that most chunks of
 		 * sizeof(Vector8) bytes won't contain any special characters.
 		 */
-		for (; i < vlen; i += sizeof(Vector8))
+		for (; i < vlen; i += sizeof(uint64))
 		{
-			Vector8		chunk;
-
-			vector8_load(&chunk, (const uint8 *) &str[i]);
-
 			/*
 			 * Break on anything less than ' ' or if we find a '"' or '\\'.
 			 * Those need special handling.  That's done in the per-byte loop.
 			 */
-			if (vector8_has_le(chunk, (unsigned char) 0x1F) ||
-				vector8_has(chunk, (unsigned char) '"') ||
-				vector8_has(chunk, (unsigned char) '\\'))
+			if (has_json_escapable_byte(&str[i]))
 				break;
 
 #ifdef ESCAPE_JSON_FLUSH_AFTER
@@ -1706,7 +1715,7 @@ escape_json_with_len(StringInfo buf, const char *str, int len)
 		 * Per-byte loop for Vector8s containing special chars and for
 		 * processing the tail of the string.
 		 */
-		for (int b = 0; b < sizeof(Vector8); b++)
+		for (int b = 0; b < sizeof(uint64); b++)
 		{
 			/* check if we've finished */
 			if (i == len)
diff --git a/src/common/jsonapi.c b/src/common/jsonapi.c
index 7dad4da65f6..6803ccbbc29 100644
--- a/src/common/jsonapi.c
+++ b/src/common/jsonapi.c
@@ -19,7 +19,6 @@
 
 #include "common/jsonapi.h"
 #include "mb/pg_wchar.h"
-#include "port/pg_lfind.h"
 
 #ifdef JSONAPI_USE_PQEXPBUFFER
 #include "pqexpbuffer.h"
@@ -1949,6 +1948,23 @@ json_lex(JsonLexContext *lex)
 		return JSON_SUCCESS;
 }
 
+static inline
+bool
+has_json_escapable_byte(const char *str)
+{
+	uint64		x;
+
+	memcpy(&x, str, sizeof(uint64));
+
+	uint64		is_ascii = 0x8080808080808080ULL & ~x;
+	uint64		xor2 = x ^ 0x0202020202020202ULL;
+	uint64		lt32_or_eq34 = xor2 - 0x2121212121212121ULL;
+	uint64		sub92 = x ^ 0x5C5C5C5C5C5C5C5CULL;
+	uint64		eq92 = (sub92 - 0x0101010101010101ULL);
+
+	return ((lt32_or_eq34 | eq92) & is_ascii) != 0;
+}
+
 /*
  * The next token in the input stream is known to be a string; lex it.
  *
@@ -2166,11 +2182,9 @@ json_lex_string(JsonLexContext *lex)
 			 * Skip to the first byte that requires special handling, so we
 			 * can batch calls to jsonapi_appendBinaryStringInfo.
 			 */
-			while (p < end - sizeof(Vector8) &&
-				   !pg_lfind8('\\', (uint8 *) p, sizeof(Vector8)) &&
-				   !pg_lfind8('"', (uint8 *) p, sizeof(Vector8)) &&
-				   !pg_lfind8_le(31, (uint8 *) p, sizeof(Vector8)))
-				p += sizeof(Vector8);
+			while (p < end - sizeof(uint64) &&
+				   !has_json_escapable_byte(p))
+				p += sizeof(uint64);
 
 			for (; p < end; p++)
 			{
#15David Rowley
dgrowleyml@gmail.com
In reply to: John Naylor (#14)
Re: Speed up JSON escape processing with SIMD plus other optimisations

On Wed, 28 May 2025 at 11:24, John Naylor <johncnaylorls@gmail.com> wrote:

https://lemire.me/blog/2025/04/13/detect-control-characters-quotes-and-backslashes-efficiently-using-swar/

I don't find this use of SWAR that bad for readability, and there's
only one obtuse clever part that merits a comment. Plus, it seems json
escapes are pretty much set in stone?

I think we'll end up needing some SWAR code. There are plenty of
places where 16 bytes is too much to do at once. e.g. looking for the
delimiter character in a COPY FROM, 16 is likely too many when you're
important a bunch of smallish ints. A 4 or 8 byte SWAR search is
likely better for that. With 16 you're probably going to find a
delimiter every time you look and do byte-at-a-time processing to find
that delimiter.

I gave this a spin with
/messages/by-id/attachment/163406/json_bench.sh.txt

master:

Test 1
tps = 321.522667 (without initial connection time)
tps = 315.070985 (without initial connection time)
tps = 331.070054 (without initial connection time)
Test 2
tps = 35.107257 (without initial connection time)
tps = 34.977670 (without initial connection time)
tps = 35.898471 (without initial connection time)
Test 3
tps = 33.575570 (without initial connection time)
tps = 32.383352 (without initial connection time)
tps = 31.876192 (without initial connection time)
Test 4
tps = 810.676116 (without initial connection time)
tps = 745.948518 (without initial connection time)
tps = 747.651923 (without initial connection time)

swar patch:

Test 1
tps = 291.919004 (without initial connection time)
tps = 294.446640 (without initial connection time)
tps = 307.670464 (without initial connection time)
Test 2
tps = 30.984440 (without initial connection time)
tps = 31.660630 (without initial connection time)
tps = 32.538174 (without initial connection time)
Test 3
tps = 29.828546 (without initial connection time)
tps = 30.332913 (without initial connection time)
tps = 28.873059 (without initial connection time)
Test 4
tps = 748.676688 (without initial connection time)
tps = 768.798734 (without initial connection time)
tps = 766.924632 (without initial connection time)

While noisy, this test seems a bit faster with SWAR, and it's more
portable to boot. I'm not sure where I'd put the new function so both
call sites can see it, but that's a small detail...

Isn't that mostly a performance regression? How does it do with ANSI
chars where the high bit is set?

I had in mind we'd have a swar.h header and have a bunch of inline
functions for this in there. I've not yet studied how well compilers
would inline multiple such SWAR functions to de-duplicate the common
parts.

David

#16John Naylor
johncnaylorls@gmail.com
In reply to: David Rowley (#15)
Re: Speed up JSON escape processing with SIMD plus other optimisations

On Wed, May 28, 2025 at 10:18 AM David Rowley <dgrowleyml@gmail.com> wrote:

I think we'll end up needing some SWAR code. There are plenty of
places where 16 bytes is too much to do at once. e.g. looking for the
delimiter character in a COPY FROM, 16 is likely too many when you're
important a bunch of smallish ints. A 4 or 8 byte SWAR search is
likely better for that. With 16 you're probably going to find a
delimiter every time you look and do byte-at-a-time processing to find
that delimiter.

I believe I saw an implementation or paper where the delimiter
locations for an input segment are turned into a bitmap, and in that
case the stride wouldn't matter so much. I've seen a use of SWAR in a
hash table that intentionally allowed bytes to overflow into the next
higher byte, which doesn't happen in SIMD lanes, so it can be useful
on all platforms.

Isn't that mostly a performance regression?

D'oh! My brain was imagining time, not TPS.

How does it do with ANSI chars where the high bit is set?

It would always fail in that case.

I had in mind we'd have a swar.h header and have a bunch of inline
functions for this in there. I've not yet studied how well compilers
would inline multiple such SWAR functions to de-duplicate the common
parts.

That would be a good step when we have a use case, and with that we
might also be able to clean up some odd-looking code in simd.h.

--
John Naylor
Amazon Web Services