Content-Type: text/plain;
	charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3864.600.51.1.1\))
Subject: Re: Optimize UUID parse using SIMD
From: Chao Li <li.evan.chao@gmail.com>
In-Reply-To: 
 <CAD21AoDAviFUHJA-wJ11X-yQAb3aVbrOyY3BBn_vfXk2q6arBA@mail.gmail.com>
Date: Fri, 7 Aug 2026 11:07:17 +0800
Cc: Haibo Yan <tristan.yim@gmail.com>,
 PostgreSQL-development <pgsql-hackers@postgresql.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <5A6326C9-25EC-4D07-99C2-DA490A7BC7ED@gmail.com>
References: 
 <CAD21AoCqeR4UQU77Q_yOMNNzJ7AVeiO5QZT+4HnzPm4Wm-e02Q@mail.gmail.com>
 <CABXr29GAXiSsD+Y2-kbCxOnmvfA=xp8yfW5HLEVmpDN42BMBwQ@mail.gmail.com>
 <CAD21AoAGKT8kj2tdYNq0xBnzicQkz5s=ctG2yx5xAKx-69C5YA@mail.gmail.com>
 <CABXr29GkTK9RUqBuV9iK_mYKjjUu1sWg7j7ZB_wtQNv93Z0WYA@mail.gmail.com>
 <CAD21AoC-M3HFaQ-DCXSKRgMceH=mDPXWdCSz22SG6HM=po-w5Q@mail.gmail.com>
 <CABXr29Go2OGuFOoV57XeABbRDq9EdV4T9rL7PCrq84R2hoORAg@mail.gmail.com>
 <CAD21AoB+gJALda3UPGvZMXAeFjF_4qrNoHVfwvF-uj8L19hnPA@mail.gmail.com>
 <CABXr29Ej7f80skZWXmSJsJDehOxc5Wj1D7bapBYe5y2e+zif-A@mail.gmail.com>
 <CAD21AoBVZTkg_E+Bam7Df6KgCur+rhBL9+hWZqR+YMsAoVgbxw@mail.gmail.com>
 <93F6B685-C5DC-444D-A92D-0927A528C1B8@gmail.com>
 <CAD21AoDAviFUHJA-wJ11X-yQAb3aVbrOyY3BBn_vfXk2q6arBA@mail.gmail.com>
To: Masahiko Sawada <sawada.mshk@gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/5A6326C9-25EC-4D07-99C2-DA490A7BC7ED%40gmail.com>
Precedence: bulk


> On Aug 7, 2026, at 00:09, Masahiko Sawada <sawada.mshk@gmail.com> =
wrote:
>=20
> On Wed, Aug 5, 2026 at 8:40=E2=80=AFPM Chao Li =
<li.evan.chao@gmail.com> wrote:
>>=20
>>=20
>>=20
>>> On Aug 6, 2026, at 08:19, Masahiko Sawada <sawada.mshk@gmail.com> =
wrote:
>>>=20
>>> On Tue, Jun 30, 2026 at 11:03=E2=80=AFAM Haibo Yan =
<tristan.yim@gmail.com> wrote:
>>>>=20
>>>> On Tue, Jun 30, 2026 at 10:53=E2=80=AFAM Masahiko Sawada =
<sawada.mshk@gmail.com> wrote:
>>>>>=20
>>>>> On Mon, Jun 29, 2026 at 5:53=E2=80=AFPM Haibo Yan =
<tristan.yim@gmail.com> wrote:
>>>>>>=20
>>>>>> On Mon, Jun 29, 2026 at 2:55=E2=80=AFPM Masahiko Sawada =
<sawada.mshk@gmail.com> wrote:
>>>>>>>=20
>>>>>>> On Sun, Jun 28, 2026 at 7:20=E2=80=AFPM Haibo Yan =
<tristan.yim@gmail.com> wrote:
>>>>>>>>=20
>>>>>>>> On Thu, Jun 25, 2026 at 3:16=E2=80=AFPM Masahiko Sawada =
<sawada.mshk@gmail.com> wrote:
>>>>>>>>>=20
>>>>>>>>> On Thu, Jun 25, 2026 at 2:31=E2=80=AFPM Haibo Yan =
<tristan.yim@gmail.com> wrote:
>>>>>>>>>>=20
>>>>>>>>>>=20
>>>>>>>>>>=20
>>>>>>>>>> On Thu, Jun 25, 2026 at 11:28=E2=80=AFAM Masahiko Sawada =
<sawada.mshk@gmail.com> wrote:
>>>>>>>>>>>=20
>>>>>>>>>>> Hi all,
>>>>>>>>>>>=20
>>>>>>>>>>> I'd like to propose the $subject.
>>>>>>>>>>>=20
>>>>>>>>>>> Since commit ec8719ccbfcd made hex_decode_safe() SIMD-aware, =
decoding
>>>>>>>>>>> a run of hex digits is now fast. The attached patch reuses
>>>>>>>>>>> hex_decode_safe() in the UUID input function to speed up =
parsing.
>>>>>>>>>>>=20
>>>>>>>>>>> We accept several textual forms of a UUID[1]. The fast path =
handles
>>>>>>>>>>> the common ones: 32 hex digits, the canonical =
8x-4x-4x-4x-12x form
>>>>>>>>>>> (where "nx" means n hex digits), and either of those wrapped =
in
>>>>>>>>>>> braces. Otherwise, it falls back to the ordinary scalar UUID =
parse.
>>>>>>>>>>>=20
>>>>>>>>>>> I've benchmarked the parse speed using the following query:
>>>>>>>>>>>=20
>>>>>>>>>>> CREATE TEMP TABLE u AS SELECT gen_random_uuid()::text AS t =
FROM
>>>>>>>>>>> generate_series(1, 1000000);
>>>>>>>>>>> EXPLAIN (ANALYZE, TIMING OFF) SELECT t::uuid FROM u;
>>>>>>>>>>>=20
>>>>>>>>>>> I compared the execution time of the second query, which =
measures
>>>>>>>>>>> uuid_in() alone, with/without SIMD optimization. Here are =
results (the
>>>>>>>>>>> median of 5 runs):
>>>>>>>>>>>=20
>>>>>>>>>>> HEAD: 208.879 ms
>>>>>>>>>>> Patched: 40.983 ms
>>>>>>>>>>>=20
>>>>>>>>>>> The improvements look promising to me. But in a realistic =
pipeline the
>>>>>>>>>>> parse is a small fraction of the work, so end-to-end gains =
could be
>>>>>>>>>>> much smaller.
>>>>>>>>>>>=20
>>>>>>>>>>> Feedback is very welcome.
>>>>>>>>>>>=20
>>>>>>>>>> I may be missing something, but I wonder whether the fast =
path is relying on
>>>>>>>>>> slightly different input semantics from the existing UUID =
parser.
>>>>>>>>>>=20
>>>>>>>>>> In particular, hex_decode_safe() is not a strict =E2=80=9C32 =
hex characters only=E2=80=9D
>>>>>>>>>> decoder.  It skips whitespace, which is fine for its existing =
callers, but I
>>>>>>>>>> don=E2=80=99t think UUID input should treat whitespace inside =
the UUID body as
>>>>>>>>>> ignorable.
>>>>>>>>>=20
>>>>>>>>> Good catch! hex_decode_safe() skips whitespaces so the patch =
accepts
>>>>>>>>> the following UUID value, which is bad:
>>>>>>>>>=20
>>>>>>>>> select '019f00b5-7f8a-722f-b707-59f0ed25cd  '::uuid;
>>>>>>>>>                uuid
>>>>>>>>> --------------------------------------
>>>>>>>>> 019f00b5-7f8a-722f-b707-59f0ed25cd00
>>>>>>>>> (1 row)
>>>>>>>>>=20
>>>>>>>>>> Also, since hex_decode_safe() returns void, the UUID fast =
path
>>>>>>>>>> cannot verify that exactly UUID_LEN bytes were produced.
>>>>>>>>>=20
>>>>>>>>> IIUC hex_decode_safe() does return the output length in bytes. =
So I
>>>>>>>>> think we can fallback to the scalar UUID parser if
>>>>>>>>> esctx.error_occurred is true or if the returned value is not =
16.
>>>>>>>>>=20
>>>>>>>>=20
>>>>>>>> You=E2=80=99re right, I misread that part.  Checking both =
esctx.error_occurred and
>>>>>>>> the returned length sounds good to me.
>>>>>>>>=20
>>>>>>>>>>=20
>>>>>>>>>> So I think it would be safer either to pre-validate that the =
32 source
>>>>>>>>>> characters are all hex digits before calling =
hex_decode_safe(), or to use a
>>>>>>>>>> UUID-specific strict hex decoder for this path.  After that, =
a comment
>>>>>>>>>> explaining why hex_decode_safe() is safe here would make the =
invariant much
>>>>>>>>>> clearer.
>>>>>>>>>=20
>>>>>>>>> IIUC hex_decode_simd_helper() accepts only hex digits so we =
could
>>>>>>>>> re-use it for UUID parsing. Let me check if the above idea of =
using
>>>>>>>>> the return value works for us first.
>>>>>>>>>=20
>>>>>>>>=20
>>>>>>>> That sounds reasonable.  My main concern was to keep the fast =
path=E2=80=99s accepted
>>>>>>>> input set identical to the scalar UUID parser.  Falling back =
when the decoded
>>>>>>>> length is not UUID_LEN, together with regression tests for =
whitespace cases,
>>>>>>>> should address that.
>>>>>>>>=20
>>>>>>>>>>=20
>>>>>>>>>> Could you also add a few regression tests for invalid inputs =
that contain
>>>>>>>>>> whitespace inside otherwise fast-path-looking UUID strings?  =
For example:
>>>>>>>>>>=20
>>>>>>>>>> =
---------------------------------------------------------------
>>>>>>>>>>=20
>>>>>>>>>> SELECT 'a0eebc99 9c0b4ef8bb6d6bb9bd380a11'::uuid;
>>>>>>>>>> SELECT 'a0eebc999c0b4ef8bb6d6bb9bd380a1 '::uuid;
>>>>>>>>>> SELECT '{a0eebc999c0b4ef8bb6d6bb9bd380a1 }'::uuid;
>>>>>>>>>> SELECT 'a0eebc99-9c0b-4ef8-bb6d-6bb9bd380a1 '::uuid;
>>>>>>>>>> =
---------------------------------------------------------------
>>>>>>>>>>=20
>>>>>>>>>> These should continue to be rejected in the same way as the =
scalar parser.
>>>>>>>>>> Regards,
>>>>>>>>>=20
>>>>>>>>> Agreed.
>>>>>>>>>=20
>>>>>>>=20
>>>>>>> I've attached the updated patch.
>>>>>>>=20
>>>>>>> Regards,
>>>>>>>=20
>>>>>>> --
>>>>>>> Masahiko Sawada
>>>>>>> Amazon Web Services: https://aws.amazon.com
>>>>>>=20
>>>>>> I noticed a few typos in the comments:
>>>>>>=20
>>>>>> src/backend/utils/adt/uuid.c
>>>>>> line 56: =E2=80=9Cscalar implmentation=E2=80=9D -> =E2=80=9Cscalar =
implementation=E2=80=9D
>>>>>> line 109: =E2=80=9Cswalled=E2=80=9D -> =E2=80=9Cswallowed=E2=80=9D
>>>>>> line 110: =E2=80=9Ckepping=E2=80=9D -> =E2=80=9Ckeeping=E2=80=9D
>>>>>> line 118: =E2=80=9Cgrammer=E2=80=9D -> =E2=80=9Cgrammar=E2=80=9D
>>>>>> line 119: =E2=80=9Cwhitespaces=E2=80=9D -> =E2=80=9Cwhitespace=E2=80=
=9D
>>>>>>=20
>>>>>> Could you fix them ?
>>>>>=20
>>>>> Oops, I fixed them and rechecked other places.
>>>>>=20
>>>>> I've attached the updated patch.
>>>>>=20
>>>>> Regards,
>>>>>=20
>>>>> --
>>>>> Masahiko Sawada
>>>>> Amazon Web Services: https://aws.amazon.com
>>>>=20
>>>> The code looks good to me now.  I only noticed one small typo in =
the
>>>> commit trailer: Reviwed-by should be Reviewed-by.
>>>>=20
>>>> Otherwise, it looks good.  Thank you for fixing these issues.
>>>>=20
>>>=20
>>> After spending more time on this patch, I find out two things:
>>>=20
>>> 1. USE_NO_SIMD doesn't work in uuid.c without including port/simd.h.
>>> But including port/simd.h seems wrong as it doesn't use any SIMD
>>> support functions.
>>>=20
>>> 2. hex_decode_safe() is faster than the current UUID parse
>>> (isxdigit()+strtoul() approach) even without SIMD. I've created a
>>> small benchmark test tool (attached as 0002 patch, not intended to =
be
>>> pushed into the core), and measures UUID parsing performance of =
three
>>> approaches: 'scalar' is the current string_to_uuid() that uses
>>> isxdigit()+strtoul()), 'simd' uses hex_decode_safe() with SIMD, and
>>> 'nosimd' uses hex_decode_safe() without SIMD, with different shapes =
of
>>> UUIDs. Here are results:
>>>=20
>>> =3D# select path, shape, n_inputs, best_ms::numeric(10,3) from
>>> uuid_parse_bench(100000, 5);
>>> path  |      shape       | n_inputs | best_ms
>>> --------+------------------+----------+---------
>>> scalar | canonical        |   100000 |  22.661
>>> simd   | canonical        |   100000 |   1.400
>>> nosimd | canonical        |   100000 |   1.652
>>> scalar | bare32           |   100000 |  15.932
>>> simd   | bare32           |   100000 |   0.471
>>> nosimd | bare32           |   100000 |   1.110
>>> scalar | braced_canonical |   100000 |  17.330
>>> simd   | braced_canonical |   100000 |   1.088
>>> nosimd | braced_canonical |   100000 |   1.314
>>> scalar | braced_bare32    |   100000 |  15.942
>>> simd   | braced_bare32    |   100000 |   0.488
>>> nosimd | braced_bare32    |   100000 |   1.141
>>> scalar | dashed4          |   100000 |  16.185
>>> simd   | dashed4          |   100000 |  16.493
>>> nosimd | dashed4          |   100000 |  16.403
>>> scalar | invalid_hex      |   100000 |   0.199
>>> simd   | invalid_hex      |   100000 |   1.150
>>> nosimd | invalid_hex      |   100000 |   0.385
>>> (18 rows)
>>>=20
>>> Each of shape means:
>>> - 'canonical': 8x-4x-4x-4x-12x, what uuid_out() emits
>>> - 'bare32': 32 contiguous hex digits
>>> - 'braced_canonical': {8x-4x-4x-4x-12x}
>>> - 'braced_bare32': {32 hex digits}
>>> - 'dashed4': dash after every group of 4
>>> - 'invalid_hdx': canonical but with a invalid digit
>>>=20
>>> 'nosimd' is 10x~ faster than 'scalar' in most cases. All paths are
>>> mostly the same in 'dashed4' and 'invalid_hex' cases because 'simd'
>>> and 'nosimd' fall back to the 'scalar' case. According to these
>>> results, my conclusion is that we can use hex_decode_safe() for
>>> canonical forms and 32 contiguous hex forms anyway, and let
>>> hex_decode_safe() choose whether to use SIMD. We would win in either
>>> case. We still use the current scalar approach for uncommon UUID =
forms
>>> and error reporting purposes.
>>>=20
>>> Regards,
>>>=20
>>> --
>>> Masahiko Sawada
>>> Amazon Web Services: https://aws.amazon.com
>>> =
<v4-0001-Optimize-UUID-parse-using-SIMD.patch><v4-0002-uuid_parse_bench-mo=
dule.patch>
>>=20
>> A few comments on v4.
>>=20
>> 1 - 0001
>> ```
>> +static void
>> +string_to_uuid(const char *source, pg_uuid_t *uuid, Node *escontext)
>> +{
>> +       const char *body =3D source;
>> +       size_t          len =3D strlen(source);
>> ```
>>=20
>> I think it would be better to avoid strlen(). The old code processes =
at most UUID_LEN (16) byte pairs, so it does not need to scan =
arbitrarily far on malformed input. So, maybe we could use something =
like strnlen(source, 39) instead.
>=20
> While strnlen(source, 39) works there, 39 is a magic number and it's
> tied to the current format check logic. What is the benefit of using
> strnlen(source, 39) instead? I'm not sure it warrants having the magic
> number.

It doesn't have to be exactly 39; 1024 (long enough) would also work, or =
perhaps something based on UUID_LEN, such as UUID_LEN * 3. I think the =
main point is to avoid unbounded scanning on malformed input.

The old code did not have this issue because it only examined as much =
input as needed based on UUID_LEN. The new fast path starts to use =
strlen(), so this would be a new risk introduced by the optimization.

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/