Thread: [POC] verifying UTF-8 using SIMD instructions

On 01/02/2021 19:32, John Naylor wrote:
> It makes sense to start with the ascii subset of UTF-8 for a couple 
> reasons. First, ascii is very widespread in database content, 
> particularly in bulk loads. Second, ascii can be validated using the 
> simple SSE2 intrinsics that come with (I believe) any x64-64 chip, and 
> I'm guessing we can detect that at compile time and not mess with 
> runtime checks. The examples above using SSE for the general case are 
> much more complicated and involve SSE 4.2 or AVX.

I wonder how using SSE compares with dealing with 64 or 32-bit words at 
a time, using regular instructions? That would be more portable.

> Here are some numbers on my laptop (MacOS/clang 10 -- if the concept is 
> okay, I'll do Linux/gcc and add more inputs). The test is the same as 
> Heikki shared in [3], but I added a case with >95% Chinese characters 
> just to show how that compares to the mixed ascii/multibyte case.
> 
> master:
> 
>   chinese | mixed | ascii
> ---------+-------+-------
>      1081 |   761 |   366
> 
> patch:
> 
>   chinese | mixed | ascii
> ---------+-------+-------
>      1103 |   498 |    51
> 
> The speedup in the pure ascii case is nice.

Yep.

> In the attached POC, I just have a pro forma portability stub, and left 
> full portability detection for later. The fast path is inlined inside 
> pg_utf8_verifystr(). I imagine the ascii fast path could be abstracted 
> into a separate function to which is passed a function pointer for full 
> encoding validation. That would allow other encodings with strict ascii 
> subsets to use this as well, but coding that abstraction might be a 
> little messy, and b80e10638e3 already gives a performance boost over PG13.

All supported encodings are ASCII subsets. Might be best to putt the 
ASCII-check into a static inline function and use it in all the verify 
functions. I presume it's only a few instructions, and these functions 
can be pretty performance sensitive.

> I also gave a shot at doing full UTF-8 recognition using a DFA, but so 
> far that has made performance worse. If I ever have more success with 
> that, I'll add that in the mix.

That's disappointing. Perhaps the SIMD algorithms have higher startup 
costs, so that you need longer inputs to benefit? In that case, it might 
make sense to check the length of the input and only use the SIMD 
algorithm if the input is long enough.

- Heikki

On 07/02/2021 22:24, John Naylor wrote:
> Here is a more polished version of the function pointer approach, now 
> adapted to all multibyte encodings. Using the not-yet-committed tests 
> from [1], I found a thinko bug that resulted in the test for nul bytes 
> to not only be wrong, but probably also elided by the compiler. Doing it 
> correctly is noticeably slower on pure ascii, but still several times 
> faster than before, so the conclusions haven't changed any. I'll run 
> full measurements later this week, but I'll share the patch now for review.

As a quick test, I hacked up pg_utf8_verifystr() to use Lemire's 
algorithm from the simdjson library [1], see attached patch. I 
microbenchmarked it using the the same test I used before [2].

These results are with "gcc -O2" using "gcc (Debian 10.2.1-6) 10.2.1 
20210110"

unpatched master:

postgres=# \i mbverifystr-speed.sql
CREATE FUNCTION
  mixed | ascii
-------+-------
    728 |   393
(1 row)

v1-0001-Add-an-ASCII-fast-path-to-multibyte-encoding-veri.patch:

  mixed | ascii
-------+-------
    759 |    98
(1 row)

simdjson-utf8-hack.patch:

  mixed | ascii
-------+-------
     53 |    31
(1 row)

So clearly that algorithm is fast. Not sure if it has a high startup 
cost, or large code size, or other tradeoffs that we don't want. At 
least it depends on SIMD instructions, so it requires more code for the 
architecture-specific implementations and autoconf logic and all that. 
Nevertheless I think it deserves a closer look, I'm a bit reluctant to 
put in half-way measures, when there's a clearly superior algorithm out 
there.

I also tested the fallback implementation from the simdjson library 
(included in the patch, if you uncomment it in simdjson-glue.c):

  mixed | ascii
-------+-------
    447 |    46
(1 row)

I think we should at least try to adopt that. At a high level, it looks 
pretty similar your patch: you load the data 8 bytes at a time, check if 
there are all ASCII. If there are any non-ASCII chars, you check the 
bytes one by one, otherwise you load the next 8 bytes. Your patch should 
be able to achieve the same performance, if done right. I don't think 
the simdjson code forbids \0 bytes, so that will add a few cycles, but 
still.

[1] https://github.com/simdjson/simdjson
[2] 
https://www.postgresql.org/message-id/06d45421-61b8-86dd-e765-f1ce527a5a2f@iki.fi

- Heikki

PS. Your patch as it stands isn't safe on systems with strict alignment, 
the string passed to the verify function isn't guaranteed to be 8 bytes 
aligned. Use memcpy to fetch the next 8-byte chunk to fix.

On 09/02/2021 22:08, John Naylor wrote:
> Maybe there's a smarter way to check for zeros in C. Or maybe be more 
> careful about cache -- running memchr() on the whole input first might 
> not be the best thing to do.

The usual trick is the haszero() macro here: 
https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord. That's 
how memchr() is typically implemented, too.

- Heikki

On 13/02/2021 03:31, John Naylor wrote:
> On Mon, Feb 8, 2021 at 6:17 AM Heikki Linnakangas <hlinnaka@iki.fi 
> <mailto:hlinnaka@iki.fi>> wrote:
>  >
>  > I also tested the fallback implementation from the simdjson library
>  > (included in the patch, if you uncomment it in simdjson-glue.c):
>  >
>  >   mixed | ascii
>  > -------+-------
>  >     447 |    46
>  > (1 row)
>  >
>  > I think we should at least try to adopt that. At a high level, it looks
>  > pretty similar your patch: you load the data 8 bytes at a time, check if
>  > there are all ASCII. If there are any non-ASCII chars, you check the
>  > bytes one by one, otherwise you load the next 8 bytes. Your patch should
>  > be able to achieve the same performance, if done right. I don't think
>  > the simdjson code forbids \0 bytes, so that will add a few cycles, but
>  > still.
> 
> Attached is a patch that does roughly what simdjson fallback did, except 
> I use straight tests on the bytes and only calculate code points in 
> assertion builds. In the course of doing this, I found that my earlier 
> concerns about putting the ascii check in a static inline function were 
> due to my suboptimal loop implementation. I had assumed that if the 
> chunked ascii check failed, it had to check all those bytes one at a 
> time. As it turns out, that's a waste of the branch predictor. In the v2 
> patch, we do the chunked ascii check every time we loop. With that, I 
> can also confirm the claim in the Lemire paper that it's better to do 
> the check on 16-byte chunks:
> 
> (MacOS, Clang 10)
> 
> master:
> 
>   chinese | mixed | ascii
> ---------+-------+-------
>      1081 |   761 |   366
> 
> v2 patch, with 16-byte stride:
> 
>   chinese | mixed | ascii
> ---------+-------+-------
>       806 |   474 |    83
> 
> patch but with 8-byte stride:
> 
>   chinese | mixed | ascii
> ---------+-------+-------
>       792 |   490 |   105
> 
> I also included the fast path in all other multibyte encodings, and that 
> is also pretty good performance-wise.

Cool.

> It regresses from master on pure 
> multibyte input, but that case is still faster than PG13, which I 
> simulated by reverting 6c5576075b0f9 and b80e10638e3:

I thought the "chinese" numbers above are pure multibyte input, and it 
seems to do well on that. Where does it regress? In multibyte encodings 
other than UTF-8? How bad is the regression?

I tested this on my first generation Raspberry Pi (chipmunk). I had to 
tweak it a bit to make it compile, since the SSE autodetection code was 
not finished yet. And I used generate_series(1, 1000) instead of 
generate_series(1, 10000) in the test script (mbverifystr-speed.sql) 
because this system is so slow.

master:

  mixed | ascii
-------+-------
   1310 |  1041
(1 row)

v2-add-portability-stub-and-new-fallback.patch:

  mixed | ascii
-------+-------
   2979 |   910
(1 row)

I'm guessing that's because the unaligned access in check_ascii() is 
expensive on this platform.

- Heikki

On 02/06/2021 19:26, John Naylor wrote:
> For v10, I've split the patch up into two parts. 0001 uses pure C 
> everywhere. This is much smaller and easier to review, and gets us the 
> most bang for the buck.
> 
> One concern Heikki raised upthread is that platforms with poor 
> unaligned-memory access will see a regression. We could easily add an 
> #ifdef to take care of that, but I haven't done so here.
> 
> To recap: On ascii-only input with storage taken out of the picture, 
> profiles of COPY FROM show a reduction from nealy 10% down to just over 
> 1%. In microbenchmarks found earlier in this thread, this works out to 
> about 7 times faster. On multibyte/mixed input, 0001 is a bit faster, 
> but not really enough to make a difference in copy performance.

Nice!

This kind of bit-twiddling is fun, so I couldn't resist tinkering with 
it, to see if we can shave some more instructions from it:

> +/* from https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord */
> +#define HAS_ZERO(chunk) ( \
> +    ((chunk) - UINT64CONST(0x0101010101010101)) & \
> +     ~(chunk) & \
> +     UINT64CONST(0x8080808080808080))
> +
> +/* Verify a chunk of bytes for valid ASCII including a zero-byte check. */
> +static inline int
> +check_ascii(const unsigned char *s, int len)
> +{
> +    uint64        half1,
> +                half2,
> +                highbits_set;
> +
> +    if (len >= 2 * sizeof(uint64))
> +    {
> +        memcpy(&half1, s, sizeof(uint64));
> +        memcpy(&half2, s + sizeof(uint64), sizeof(uint64));
> +
> +        /* If there are zero bytes, bail and let the slow path handle it. */
> +        if (HAS_ZERO(half1) || HAS_ZERO(half2))
> +            return 0;
> +
> +        /* Check if any bytes in this chunk have the high bit set. */
> +        highbits_set = ((half1 | half2) & UINT64CONST(0x8080808080808080));
> +
> +        if (!highbits_set)
> +            return 2 * sizeof(uint64);
> +        else
> +            return 0;
> +    }
> +    else
> +        return 0;
> +}

Some ideas:

1. Better to check if any high bits are set first. We care more about 
the speed of that than of detecting zero bytes, because input with high 
bits is valid but zeros are an error.

2. Since we check that there are no high bits, we can do the zero-checks 
with fewer instructions like this:

/* NB: this is only correct if 'chunk' doesn't have any high bits set */
#define HAS_ZERO(chunk) ( \
   ((chunk) + \
    UINT64CONST(0x7f7f7f7f7f7f7f7f)) & \
   UINT64CONST(0x8080808080808080) == UINT64CONST(0x8080808080808080))

3. It's probably cheaper perform the HAS_ZERO check just once on (half1 
| half2). We have to compute (half1 | half2) anyway.


Putting all that together:

/* Verify a chunk of bytes for valid ASCII including a zero-byte check. */
static inline int
check_ascii(const unsigned char *s, int len)
{
    uint64        half1,
                half2,
                highbits_set;
    uint64        x;

    if (len >= 2 * sizeof(uint64))
    {
        memcpy(&half1, s, sizeof(uint64));
        memcpy(&half2, s + sizeof(uint64), sizeof(uint64));

        /* Check if any bytes in this chunk have the high bit set. */
        highbits_set = ((half1 | half2) & UINT64CONST(0x8080808080808080));
        if (highbits_set)
            return 0;

        /*
         * Check if there are any zero bytes in this chunk. This is only correct
         * if there are no high bits set, but we checked that already.
         */
        x = (half1 | half2) + UINT64CONST(0x7f7f7f7f7f7f7f7f);
        x &= UINT64CONST(0x8080808080808080);
        if (x != UINT64CONST(0x8080808080808080))
            return 0;

        return 2 * sizeof(uint64);
    }
    else
        return 0;
}

In quick testing, that indeed compiles into fewer instructions. With 
GCC, there's no measurable difference in performance. But with clang, 
this version is much faster than the original, because the original 
version is much slower than when compiled with GCC. In other words, this 
version seems to avoid some clang misoptimization. I tested only with 
ASCII input, I haven't tried other cases.

What test set have you been using for performance testing this? I'd like 
to know how this version compares, and I could also try running it on my 
old raspberry pi, which is more strict about alignmnt.

> 0002 adds the SSE4 implementation on x86-64, and is equally fast on all 
> input, at the cost of greater complexity.

Didn't look closely, but seems reasonable at a quick glance.

- Heikki

> 3. It's probably cheaper perform the HAS_ZERO check just once on (half1
| half2). We have to compute (half1 | half2) anyway.

Wouldn't you have to check (half1 & half2) ?

I haven't looked at the surrounding code. Are we processing all the
COPY data in one long stream or processing each field individually? If
we're processing much more than 128 bits and happy to detect NUL
errors only at the end after wasting some work then you could hoist
that has_zero check entirely out of the loop (removing the branch
though it's probably a correctly predicted branch anyways).

Do something like:

zero_accumulator = zero_accumulator & next_chunk

in the loop and then only at the very end check for zeros in that.

On 03/06/2021 17:33, Greg Stark wrote:
>> 3. It's probably cheaper perform the HAS_ZERO check just once on (half1
> | half2). We have to compute (half1 | half2) anyway.
> 
> Wouldn't you have to check (half1 & half2) ?

Ah, you're right of course. But & is not quite right either, it will 
give false positives. That's ok from a correctness point of view here, 
because we then fall back to checking byte by byte, but I don't think 
it's a good tradeoff.

I think this works, however:

/* Verify a chunk of bytes for valid ASCII including a zero-byte check. */
static inline int
check_ascii(const unsigned char *s, int len)
{
    uint64        half1,
                half2,
                highbits_set;
    uint64        x1,
                x2;
    uint64        x;

    if (len >= 2 * sizeof(uint64))
    {
        memcpy(&half1, s, sizeof(uint64));
        memcpy(&half2, s + sizeof(uint64), sizeof(uint64));

        /* Check if any bytes in this chunk have the high bit set. */
        highbits_set = ((half1 | half2) & UINT64CONST(0x8080808080808080));
        if (highbits_set)
            return 0;

        /*
         * Check if there are any zero bytes in this chunk.
         *
         * First, add 0x7f to each byte. This sets the high bit in each byte,
         * unless it was a zero. We already checked that none of the bytes had
         * the high bit set previously, so the max value each byte can have
         * after the addition is 0x7f + 0x7f = 0xfe, and we don't need to
         * worry about carrying over to the next byte.
         */
        x1 = half1 + UINT64CONST(0x7f7f7f7f7f7f7f7f);
        x2 = half2 + UINT64CONST(0x7f7f7f7f7f7f7f7f);

        /* then check that the high bit is set in each byte. */
        x = (x1 | x2);
        x &= UINT64CONST(0x8080808080808080);
        if (x != UINT64CONST(0x8080808080808080))
            return 0;

        return 2 * sizeof(uint64);
    }
    else
        return 0;
}

- Heikki

On 03/06/2021 22:10, John Naylor wrote:
> On Thu, Jun 3, 2021 at 3:08 PM Heikki Linnakangas <hlinnaka@iki.fi 
> <mailto:hlinnaka@iki.fi>> wrote:
>  >                 x1 = half1 + UINT64CONST(0x7f7f7f7f7f7f7f7f);
>  >                 x2 = half2 + UINT64CONST(0x7f7f7f7f7f7f7f7f);
>  >
>  >                 /* then check that the high bit is set in each byte. */
>  >                 x = (x1 | x2);
>  >                 x &= UINT64CONST(0x8080808080808080);
>  >                 if (x != UINT64CONST(0x8080808080808080))
>  >                         return 0;
> 
> That seems right, I'll try that and update the patch. (Forgot to attach 
> earlier anyway)

Ugh, actually that has the same issue as before. If one of the bytes is 
in one half is zero, but not in the other half, this fail to detect it. 
Sorry for the noise..

- Heikki

On 03/06/2021 22:16, Heikki Linnakangas wrote:
> On 03/06/2021 22:10, John Naylor wrote:
>> On Thu, Jun 3, 2021 at 3:08 PM Heikki Linnakangas <hlinnaka@iki.fi
>> <mailto:hlinnaka@iki.fi>> wrote:
>>   >                 x1 = half1 + UINT64CONST(0x7f7f7f7f7f7f7f7f);
>>   >                 x2 = half2 + UINT64CONST(0x7f7f7f7f7f7f7f7f);
>>   >
>>   >                 /* then check that the high bit is set in each byte. */
>>   >                 x = (x1 | x2);
>>   >                 x &= UINT64CONST(0x8080808080808080);
>>   >                 if (x != UINT64CONST(0x8080808080808080))
>>   >                         return 0;
>>
>> That seems right, I'll try that and update the patch. (Forgot to attach
>> earlier anyway)
> 
> Ugh, actually that has the same issue as before. If one of the bytes is
> in one half is zero, but not in the other half, this fail to detect it.
> Sorry for the noise..

If you replace (x1 | x2) with (x1 & x2) above, I think it's correct.

- Heikki

On 03/06/2021 21:58, John Naylor wrote:
> 
>  > What test set have you been using for performance testing this? I'd like
> 
> The microbenchmark is the same one you attached to [1], which I extended 
> with a 95% multibyte case.

Could you share the exact test you're using? I'd like to test this on my 
old raspberry pi, out of curiosity.

- Heikki

On 07/06/2021 15:39, John Naylor wrote:
> On Mon, Jun 7, 2021 at 8:24 AM Heikki Linnakangas <hlinnaka@iki.fi 
> <mailto:hlinnaka@iki.fi>> wrote:
>  >
>  > On 03/06/2021 21:58, John Naylor wrote:
>  > > The microbenchmark is the same one you attached to [1], which I 
> extended
>  > > with a 95% multibyte case.
>  >
>  > Could you share the exact test you're using? I'd like to test this on my
>  > old raspberry pi, out of curiosity.
> 
> Sure, attached.
> 
> --
> John Naylor
> EDB: http://www.enterprisedb.com <http://www.enterprisedb.com>
> 
Results from chipmunk, my first generation Raspberry Pi:

Master:

  chinese | mixed | ascii
---------+-------+-------
    25392 | 16287 | 10295
(1 row)

v11-0001-Rewrite-pg_utf8_verifystr-for-speed.patch:

  chinese | mixed | ascii
---------+-------+-------
    17739 | 10854 |  4121
(1 row)

So that's good.

What is the worst case scenario for this algorithm? Something where the 
new fast ASCII check never helps, but is as fast as possible with the 
old code. For that, I added a repeating pattern of '123456789012345ä' to 
the test set (these results are from my Intel laptop, not the raspberry pi):

Master:

  chinese | mixed | ascii | mixed2
---------+-------+-------+--------
     1333 |   757 |   410 |    573
(1 row)

v11-0001-Rewrite-pg_utf8_verifystr-for-speed.patch:

  chinese | mixed | ascii | mixed2
---------+-------+-------+--------
      942 |   470 |    66 |   1249
(1 row)

So there's a regression with that input. Maybe that's acceptable, this 
is the worst case, after all. Or you could tweak check_ascii for a 
different performance tradeoff, by checking the two 64-bit words 
separately and returning "8" if the failure happens in the second word. 
And I haven't tried the SSE patch yet, maybe that compensates for this.

- Heikki

On 29/06/2021 14:20, John Naylor wrote:
> I still wasn't quite happy with the churn in the regression tests, so 
> for v13 I gave up on using both the existing utf8 table and my new one 
> for the "padded input" tests, and instead just copied the NUL byte test 
> into the new table. Also added a primary key to make sure the padded 
> test won't give weird results if a new entry has a duplicate description.
> 
> I came up with "highbit_carry" as a more descriptive variable name than 
> "x", but that doesn't matter a whole lot.
> 
> It also occurred to me that if we're going to check one 8-byte chunk at 
> a time (like v12 does), maybe it's only worth it to load 8 bytes at a 
> time. An earlier version did this, but without the recent tweaks. The 
> worst-case scenario now might be different from the one with 16-bytes, 
> but for now just tested the previous worst case (mixed2).

I tested the new worst case scenario on my laptop:

gcc master:

  chinese | mixed | ascii | mixed16 | mixed8
---------+-------+-------+---------+--------
     1311 |   758 |   405 |     583 |    725


gcc v13:

  chinese | mixed | ascii | mixed16 | mixed8
---------+-------+-------+---------+--------
      956 |   472 |   160 |     572 |    939


mixed16 is the same as "mixed2" in the previous rounds, with 
'123456789012345ä' as the repeating string, and mixed8 uses '1234567ä', 
which I believe is the worst case for patch v13. So v13 is somewhat 
slower than master in the worst case.

Hmm, there's one more simple trick we can do: We can have a separate 
fast-path version of the loop when there are at least 8 bytes of input 
left, skipping all the length checks. With that:

gcc v14:
  chinese | mixed | ascii | mixed16 | mixed8
---------+-------+-------+---------+--------
      737 |   412 |    94 |     476 |    725


All the above numbers were with gcc 10.2.1. For completeness, with clang 
11.0.1-2 I got:

clang master:
  chinese | mixed | ascii | mixed16 | mixed8
---------+-------+-------+---------+--------
     1044 |   724 |   403 |     930 |    603
(1 row)

clang v13:
  chinese | mixed | ascii | mixed16 | mixed8
---------+-------+-------+---------+--------
      596 |   445 |    79 |     417 |    715
(1 row)


clang v14:
  chinese | mixed | ascii | mixed16 | mixed8
---------+-------+-------+---------+--------
      600 |   337 |    93 |     318 |    511

Attached is patch v14 with that optimization. It needs some cleanup, I 
just hacked it up quickly for performance testing.

- Heikki

On Tue, 13 Jul 2021 at 01:15, John Naylor <john.naylor@enterprisedb.com> wrote:
> > It seems like it would be easy to have pg_utf8_verify_one in my proposed pg_utf8.h header and replace the body of
pg_utf8_verifycharwith it. 
>
> 0001: I went ahead and tried this for v15, and also attempted some clean-up:
>
> - Rename pg_utf8_verify_one to pg_utf8_verifychar_internal.
> - Have pg_utf8_verifychar_internal return -1 for invalid input to match other functions in the file. We could also do
thisfor check_ascii, but it's not quite the same thing, because the string could still have valid bytes in it, just not
enoughto advance the pointer by the stride length. 
> - Remove hard-coded numbers (not wedded to this).
>
> - Use a call to pg_utf8_verifychar in the slow path.
> - Reduce pg_utf8_verifychar to thin wrapper around pg_utf8_verifychar_internal.

- check_ascii() seems to be used only for 64-bit chunks. So why not
remove the len argument and the len <= sizeof(int64) checks inside the
function. We can rename it to check_ascii64() for clarity.

- I was thinking, why not have a pg_utf8_verify64() that processes
64-bit chunks (or a 32-bit version). In check_ascii(), we anyway
extract a 64-bit chunk from the string. We can use the same chunk to
extract the required bits from a two byte char or a 4 byte char. This
way we can avoid extraction of separate bytes like b1 = *s; b2 = s[1]
etc. More importantly, we can avoid the separate continuation-char
checks for each individual byte. Additionally, we can try to simplify
the subsequent overlong or surrogate char checks. Something like this
:

int pg_utf8_verifychar_32(uint32 chunk)
{
    int        len, l;

    for (len = sizeof(chunk); len > 0; (len -= l), (chunk = chunk << l))
    {
        /* Is 2-byte lead */
        if ((chunk & 0xF0000000) == 0xC0000000)
        {
            l = 2;
            /* .......  .......  */
        }
        /* Is 3-byte lead */
        else if ((chunk & 0xF0000000) == 0xE0000000)
        {
            l = 3;
            if (len < l)
                break;

            /* b2 and b3 should be continuation bytes */
            if ((chunk & 0x00C0C000) != 0x00808000)
                return sizeof(chunk) - len;

            switch (chunk & 0xFF200000)
            {
                /* check 3-byte overlong: 1110.0000 1001.xxxx 10xx.xxxx
                 * i.e. (b1 == 0xE0 && b2 < 0xA0). We already know b2
is of the form
                 * 10xx since it's a continuation char. Additionally
condition b2 <=
                 * 0x9F means it is of the form 100x.xxxx.  i.e.
either 1000.xxxx
                 * or 1001.xxxx. So just verify that it is xx0x.xxxx
                 */
                case 0xE0000000:
                    return sizeof(chunk) - len;

                /* check surrogate: 1110.1101 101x.xxxx 10xx.xxxx
                 * i.e. (b1 == 0xED && b2 > 0x9F): Here, > 0x9F means either
                 * 1010.xxxx, 1011.xxxx, 1100.xxxx, or 1110.xxxx. Last
two are not
                 * possible because b2 is a continuation char. So it has to be
                 * first two. So just verify that it is xx1x.xxxx
                 */
                case 0xED200000:
                    return sizeof(chunk) - len;
                default:
                    ;
            }

        }
        /* Is 4-byte lead */
        else if ((chunk & 0xF0000000) == 0xF0000000)
        {
            /* .........  */
            l = 4;
        }
        else
            return sizeof(chunk) - len;
    }
    return sizeof(chunk) - len;
}

On Sat, 17 Jul 2021 at 04:48, John Naylor <john.naylor@enterprisedb.com> wrote:
> v17-0001 is the same as v14. 0002 is a stripped-down implementation of Amit's
> chunk idea for multibyte, and it's pretty good on x86. On Power8, not so
> much. 0003 and 0004 are shot-in-the-dark guesses to improve it on Power8,
> with some success, but end up making x86 weirdly slow, so I'm afraid that
> could happen on other platforms as well.

Thanks for trying the chunk approach. I tested your v17 versions on
Arm64. For the chinese characters, v17-0002 gave some improvement over
v14. But for all the other character sets, there was around 10%
degradation w.r.t. v14. I thought maybe the hhton64 call and memcpy()
for each mb character might be the culprit, so I tried iterating over
all the characters in the chunk within the same pg_utf8_verify_one()
function by left-shifting the bits. But that worsened the figures. So
I gave up that idea.

Here are the numbers on Arm64 :

HEAD:
 chinese | mixed | ascii | mixed16 | mixed8
---------+-------+-------+---------+--------
    1781 |  1095 |   628 |     944 |   1151

v14:
 chinese | mixed | ascii | mixed16 | mixed8
---------+-------+-------+---------+--------
     852 |   484 |   144 |     584 |    971


v17-0001+2:
 chinese | mixed | ascii | mixed16 | mixed8
---------+-------+-------+---------+--------
     731 |   520 |   152 |     645 |   1118


Haven't looked at your v18 patch set yet.

On Sat, Mar 13, 2021 at 4:37 AM John Naylor
<john.naylor@enterprisedb.com> wrote:
> On Fri, Mar 12, 2021 at 9:14 AM Amit Khandekar <amitdkhan.pg@gmail.com> wrote:
> > I was not thinking about auto-vectorizing the code in
> > pg_validate_utf8_sse42(). Rather, I was considering auto-vectorization
> > inside the individual helper functions that you wrote, such as
> > _mm_setr_epi8(), shift_right(), bitwise_and(), prev1(), splat(),
>
> If the PhD holders who came up with this algorithm thought it possible to do it that way, I'm sure they would have.
Inreality, simdjson has different files for SSE4, AVX, AVX512, NEON, and Altivec. We can incorporate any of those as
needed.That's a PG15 project, though, and I'm not volunteering. 

Just for fun/experimentation, here's a quick (and probably too naive)
translation of those helper functions to NEON, on top of the v15
patch.

On Thu, Jul 22, 2021 at 6:16 AM John Naylor
<john.naylor@enterprisedb.com> wrote:
> Neat! It's good to make it more architecture-agnostic, and I'm sure we can use quite a bit of this.

One question is whether this "one size fits all" approach will be
extensible to wider SIMD.

>  to_bool(const pg_u8x16_t v)
>  {
> +#if defined(USE_NEON)
> + return vmaxvq_u32((uint32x4_t) v) != 0;
>
> --> return vmaxvq_u8(*this) != 0;

I chose that lane width because I saw an unsubstantiated claim
somewhere that it might be faster, but I have no idea if it matters.
The u8 code looks more natural anyway.  Changed.

>  vzero()
>  {
> +#if defined(USE_NEON)
> + return vmovq_n_u8(0);
>
> --> return vdupq_n_u8(0); // or equivalently, splat(0)

I guess it doesn't make a difference which builtin you use here, but I
was influenced by the ARM manual which says the vdupq form is
generated for immediate values.

> is_highbit_set(const pg_u8x16_t v)
>  {
> +#if defined(USE_NEON)
> + return to_bool(bitwise_and(v, vmovq_n_u8(0x80)));
>
> --> return vmaxq_u8(v) > 0x7F

Ah, of course.  Much nicer!

> +#if defined(USE_NEON)
> +static pg_attribute_always_inline pg_u8x16_t
> +vset(uint8 v0, uint8 v1, uint8 v2, uint8 v3,
> + uint8 v4, uint8 v5, uint8 v6, uint8 v7,
> + uint8 v8, uint8 v9, uint8 v10, uint8 v11,
> + uint8 v12, uint8 v13, uint8 v14, uint8 v15)
> +{
> + uint8 pg_attribute_aligned(16) values[16] = {
> + v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15
> + };
> + return vld1q_u8(values);
> +}
>
> --> They have this strange beast instead:
>
>   // Doing a load like so end ups generating worse code.
>   // uint8_t array[16] = {x1, x2, x3, x4, x5, x6, x7, x8,
>   //                     x9, x10,x11,x12,x13,x14,x15,x16};
>   // return vld1q_u8(array);
>   uint8x16_t x{};
>   // incredibly, Visual Studio does not allow x[0] = x1
>   x = vsetq_lane_u8(x1, x, 0);
>   x = vsetq_lane_u8(x2, x, 1);
>   x = vsetq_lane_u8(x3, x, 2);
> ...
>   x = vsetq_lane_u8(x15, x, 14);
>   x = vsetq_lane_u8(x16, x, 15);
>   return x;
>
> Since you aligned the array, that might not have the problem alluded to above, and it looks nicer.

Strange indeed.  We should probably poke around in the assember and
see... it might be that MSVC doesn't like it, and I was just
cargo-culting the alignment.  I don't expect the generated code to
really "load" anything of course, it should ideally be some kind of
immediate mov...

FWIW here are some performance results from my humble RPI4:

master:

 chinese | mixed | ascii
---------+-------+-------
    4172 |  2763 |  1823
(1 row)

Your v15 patch:

 chinese | mixed | ascii
---------+-------+-------
    2267 |  1248 |   399
(1 row)

Your v15 patch set + the NEON patch, configured with USE_UTF8_SIMD=1:

 chinese | mixed | ascii
---------+-------+-------
     909 |   620 |   318
(1 row)

It's so good I wonder if it's producing incorrect results :-)

I also tried to do a quick and dirty AltiVec patch to see if it could
fit into the same code "shape", with less immediate success: it works
out slower than the fallback code on the POWER7 machine I scrounged an
account on.  I'm not sure what's wrong there, but maybe it's a uesful
start (I'm probably confused about endianness, or the encoding of
boolean vectors which may be different (is true 0x01or 0xff, does it
matter?), or something else, and it's falling back on errors all the
time?).

It occurred to me that the DFA + ascii quick check approach could also
be adapted to speed up some cases where we currently walk a string
counting characters, like this snippet in
text_position_get_match_pos():

/* Convert the byte position to char position. */
while (state->refpoint < state->last_match)
{
    state->refpoint += pg_mblen(state->refpoint);
    state->refpos++;
}

This coding changed in 9556aa01c69 (Use single-byte
Boyer-Moore-Horspool search even with multibyte encodings), in which I
found the majority of cases were faster, but some were slower. It
would be nice to regain the speed lost and do even better.

In the case of UTF-8, we could just run it through the DFA,
incrementing a count of the states found. The number of END states
should be the number of characters. The ascii quick check would still
be applicable as well. I think all that is needed is to export some
symbols and add the counting function. That wouldn't materially affect
the current patch for input verification, and would be separate, but
it would be nice to get the symbol visibility right up front. I've set
this to waiting on author while I experiment with that.

--
John Naylor
EDB: http://www.enterprisedb.com

On 20/10/2021 00:42, John Naylor wrote:
> I've decided I'm not quite comfortable with the additional complexity in 
> the build system introduced by the SIMD portion of the previous patches. 
> It would make more sense if the pure C portion were unchanged, but with 
> the shift-based DFA plus the bitwise ASCII check, we have a portable 
> implementation that's still a substantial improvement over the current 
> validator. In v24, I've included only that much, and the diff is only 
> about 1/3 as many lines. If future improvements to COPY FROM put 
> additional pressure on this path, we can always add SIMD support later.

+1.

I had another look at this now. Looks good, just a few minor comments below:

> +/*
> + * Verify a chunk of bytes for valid ASCII, including a zero-byte check.
> + */
> +static inline bool
> +is_valid_ascii(const unsigned char *s, int len)
> +{
> +    uint64        chunk,
> +                highbit_cum = UINT64CONST(0),
> +                zero_cum = UINT64CONST(0x8080808080808080);
> +
> +    Assert(len % sizeof(chunk) == 0);
> +
> +    while (len >= sizeof(chunk))
> +    {
> +        memcpy(&chunk, s, sizeof(chunk));
> +
> +        /*
> +         * Capture any zero bytes in this chunk.
> +         *
> +         * First, add 0x7f to each byte. This sets the high bit in each byte,
> +         * unless it was a zero. We will check later that none of the bytes in
> +         * the chunk had the high bit set, in which case the max value each
> +         * byte can have after the addition is 0x7f + 0x7f = 0xfe, and we
> +         * don't need to worry about carrying over to the next byte.
> +         *
> +         * If any resulting high bits are zero, the corresponding high bits in
> +         * the zero accumulator will be cleared.
> +         */
> +        zero_cum &= (chunk + UINT64CONST(0x7f7f7f7f7f7f7f7f));
> +
> +        /* Capture any set bits in this chunk. */
> +        highbit_cum |= chunk;
> +
> +        s += sizeof(chunk);
> +        len -= sizeof(chunk);
> +    }

This function assumes that the input len is a multiple of 8. There's an 
assertion for that, but it would be good to also mention it in the 
function comment. I took me a moment to realize that.

Given that assumption, I wonder if "while (len >= 0)" would marginally 
faster. Or compute "s_end = s + len" first, and check for "while (s < 
s_end)", so that you don't need to update 'len' in the loop.

Also would be good to mention what exactly the return value means. I.e 
"returns false if the input contains any bytes with the high-bit set, or 
zeros".

> +    /*
> +     * Check if any high bits in the zero accumulator got cleared.
> +     *
> +     * XXX: As noted above, the zero check is only valid if the chunk had no
> +     * high bits set. However, the compiler may perform these two checks in
> +     * any order. That's okay because if any high bits were set, we would
> +     * return false regardless, so invalid results from the zero check don't
> +     * matter.
> +     */
> +    if (zero_cum != UINT64CONST(0x8080808080808080))
> +        return false;

I don't understand the "the compiler may perform these checks in any 
order" comment. We trust the compiler to do the right thing, and only 
reorder things when it's safe to do so. What is special here, why is it 
worth mentioning here?

> @@ -1721,7 +1777,7 @@ pg_gb18030_verifystr(const unsigned char *s, int len)
>      return s - start;
>  }
>  
> -static int
> +static pg_noinline int
>  pg_utf8_verifychar(const unsigned char *s, int len)
>  {
>      int            l;

Why force it to not be inlined?

> + * In a shift-based DFA, the input byte is an index into array of integers
> + * whose bit pattern encodes the state transitions. To compute the current
> + * state, we simply right-shift the integer by the current state and apply a
> + * mask. In this scheme, the address of the transition only depends on the
> + * input byte, so there is better pipelining.

Should be "To compute the *next* state, ...", I think.

The way the state transition table works is pretty inscrutable. That's 
understandable, because the values were found by an SMT solver, so I'm 
not sure if anything can be done about it.

- Heikki

>-----Original Message-----
>From: Heikki Linnakangas <hlinnaka@iki.fi> 
>Sent: Friday, December 10, 2021 12:34 PM
>To: John Naylor <john.naylor@enterprisedb.com>; Vladimir Sitnikov <sitnikov.vladimir@gmail.com>
>Cc: pgsql-hackers <pgsql-hackers@postgresql.org>; Amit Khandekar <amitdkhan.pg@gmail.com>; Thomas Munro
<thomas.munro@gmail.com>;Greg Stark <stark@mit.edu>
 
>Subject: [EXTERNAL] Re: speed up verifying UTF-8
>
>On 20/10/2021 00:42, John Naylor wrote:
>> I've decided I'm not quite comfortable with the additional complexity 
>> in the build system introduced by the SIMD portion of the previous patches.
>> It would make more sense if the pure C portion were unchanged, but 
>> with the shift-based DFA plus the bitwise ASCII check, we have a 
>> portable implementation that's still a substantial improvement over 
>> the current validator. In v24, I've included only that much, and the 
>> diff is only about 1/3 as many lines. If future improvements to COPY 
>> FROM put additional pressure on this path, we can always add SIMD support later.
>
>+1.
>
>I had another look at this now. Looks good, just a few minor comments below:
>
>> +/*
>> + * Verify a chunk of bytes for valid ASCII, including a zero-byte check.
>> + */
>> +static inline bool
>> +is_valid_ascii(const unsigned char *s, int len) {
>> +    uint64        chunk,
>> +                highbit_cum = UINT64CONST(0),
>> +                zero_cum = UINT64CONST(0x8080808080808080);
>> +
>> +    Assert(len % sizeof(chunk) == 0);
>> +
>> +    while (len >= sizeof(chunk))
>> +    {
>> +        memcpy(&chunk, s, sizeof(chunk));
>> +
>> +        /*
>> +         * Capture any zero bytes in this chunk.
>> +         *
>> +         * First, add 0x7f to each byte. This sets the high bit in each byte,
>> +         * unless it was a zero. We will check later that none of the bytes in
>> +         * the chunk had the high bit set, in which case the max value each
>> +         * byte can have after the addition is 0x7f + 0x7f = 0xfe, and we
>> +         * don't need to worry about carrying over to the next byte.
>> +         *
>> +         * If any resulting high bits are zero, the corresponding high bits in
>> +         * the zero accumulator will be cleared.
>> +         */
>> +        zero_cum &= (chunk + UINT64CONST(0x7f7f7f7f7f7f7f7f));
>> +
>> +        /* Capture any set bits in this chunk. */
>> +        highbit_cum |= chunk;
>> +
>> +        s += sizeof(chunk);
>> +        len -= sizeof(chunk);
>> +    }
>
>This function assumes that the input len is a multiple of 8. There's an assertion for that, but it would be good to
alsomention it in the function comment. I took me a moment to realize that.
 
>
>Given that assumption, I wonder if "while (len >= 0)" would marginally faster. Or compute "s_end = s + len" first, and
checkfor "while (s < s_end)", so that you don't need to update 'len' in the loop.
 
>
>Also would be good to mention what exactly the return value means. I.e "returns false if the input contains any bytes
withthe high-bit set, or zeros".
 
>
>> +    /*
>> +     * Check if any high bits in the zero accumulator got cleared.
>> +     *
>> +     * XXX: As noted above, the zero check is only valid if the chunk had no
>> +     * high bits set. However, the compiler may perform these two checks in
>> +     * any order. That's okay because if any high bits were set, we would
>> +     * return false regardless, so invalid results from the zero check don't
>> +     * matter.
>> +     */
>> +    if (zero_cum != UINT64CONST(0x8080808080808080))
>> +        return false;
>
>I don't understand the "the compiler may perform these checks in any order" comment. We trust the compiler to do the
rightthing, and only reorder things when it's safe to do so. What is special here, why is it worth mentioning here?
 
>
>> @@ -1721,7 +1777,7 @@ pg_gb18030_verifystr(const unsigned char *s, int len)
>>      return s - start;
>>  }
>>  
>> -static int
>> +static pg_noinline int
>>  pg_utf8_verifychar(const unsigned char *s, int len)  {
>>      int            l;
>
>Why force it to not be inlined?
>
>> + * In a shift-based DFA, the input byte is an index into array of 
>> + integers
>> + * whose bit pattern encodes the state transitions. To compute the 
>> + current
>> + * state, we simply right-shift the integer by the current state and 
>> + apply a
>> + * mask. In this scheme, the address of the transition only depends 
>> + on the
>> + * input byte, so there is better pipelining.
>
>Should be "To compute the *next* state, ...", I think.
>
>The way the state transition table works is pretty inscrutable. That's understandable, because the values were found
byan SMT solver, so I'm not sure if anything can be done about it.
 
>
>- Heikki
>

If I remember correctly the shift instruction is very fast...

On Fri, Dec 10, 2021 at 2:33 PM Heikki Linnakangas <hlinnaka@iki.fi> wrote:

> I had another look at this now. Looks good, just a few minor comments below:

Thanks for reviewing! I've attached v25 to address your points.

> This function assumes that the input len is a multiple of 8. There's an
> assertion for that, but it would be good to also mention it in the
> function comment. I took me a moment to realize that.

Done.

> Given that assumption, I wonder if "while (len >= 0)" would marginally
> faster. Or compute "s_end = s + len" first, and check for "while (s <
> s_end)", so that you don't need to update 'len' in the loop.

With two chunks, gcc 4.8.5/11.2 and clang 12 will unroll the inner
loop, so it doesn't matter:

L51:
        mov     rdx, QWORD PTR [rdi]
        mov     rsi, QWORD PTR [rdi+8]
        lea     rax, [rdx+rbx]
        lea     rbp, [rsi+rbx]
        and     rax, rbp
        and     rax, r11
        cmp     rax, r11
        jne     .L66
        or      rdx, rsi
        test    rdx, r11
        jne     .L66
        sub     r8d, 16          ; refers to "len" in the caller
pg_utf8_verifystr()
        add     rdi, 16
        cmp     r8d, 15
        jg      .L51

I *think* these are the same instructions as from your version from
some time ago that handled two integers explicitly -- I rewrote it
like this to test different chunk sizes.

(Aside on 32-byte strides: Four chunks was within the noise level of
two chunks on the platform I tested. With 32 bytes, that increases the
chance that a mixed input would have non-ascii and defeat this
optimization, so should be significantly faster to make up for that.
Along those lines, in the future we could consider SSE2 (unrolled 2 x
16 bytes) for this path. Since it's part of the spec for x86-64, we
wouldn't need a runtime check -- just #ifdef it inline. And we could
piggy-back on the CRC SSE4.2 configure test for intrinsic support, so
that would avoid adding a bunch of complexity.)

That said, I think your suggestions are better on code clarity
grounds. I'm on the fence about "while(s < s_end)", so I went with
"while (len > 0)" because it matches the style in wchar.c.

> Also would be good to mention what exactly the return value means. I.e
> "returns false if the input contains any bytes with the high-bit set, or
> zeros".

Done.

> > +     /*
> > +      * Check if any high bits in the zero accumulator got cleared.
> > +      *
> > +      * XXX: As noted above, the zero check is only valid if the chunk had no
> > +      * high bits set. However, the compiler may perform these two checks in
> > +      * any order. That's okay because if any high bits were set, we would
> > +      * return false regardless, so invalid results from the zero check don't
> > +      * matter.
> > +      */
> > +     if (zero_cum != UINT64CONST(0x8080808080808080))
> > +             return false;

> I don't understand the "the compiler may perform these checks in any
> order" comment. We trust the compiler to do the right thing, and only
> reorder things when it's safe to do so. What is special here, why is it
> worth mentioning here?

Ah, that's a good question, and now that you mention it, the comment
is silly. When looking at the assembly output a while back, I was a
bit astonished that it didn't match my mental model of what was
happening, so I made this note. I've removed the whole XXX comment
here and expanded the first comment in the loop to:

/*
 * Capture any zero bytes in this chunk.
 *
 * First, add 0x7f to each byte. This sets the high bit in each byte,
 * unless it was a zero. If any resulting high bits are zero, the
 * corresponding high bits in the zero accumulator will be cleared.
 *
 * If none of the bytes in the chunk had the high bit set, the max
 * value each byte can have after the addition is 0x7f + 0x7f = 0xfe,
 * and we don't need to worry about carrying over to the next byte. If
 * any input bytes did have the high bit set, it doesn't matter
 * because we check for those separately.
 */

> > @@ -1721,7 +1777,7 @@ pg_gb18030_verifystr(const unsigned char *s, int len)
> >       return s - start;
> >  }
> >
> > -static int
> > +static pg_noinline int
> >  pg_utf8_verifychar(const unsigned char *s, int len)
> >  {
> >       int                     l;
>
> Why force it to not be inlined?

Since the only direct caller is now only using it for small inputs, I
thought about saving space, but it's not enough to matter, so I'll go
ahead and leave it out. While at it, I removed the unnecessary
"inline" declaration for utf8_advance(), since the compiler can do
that anyway.

> > + * In a shift-based DFA, the input byte is an index into array of integers
> > + * whose bit pattern encodes the state transitions. To compute the current
> > + * state, we simply right-shift the integer by the current state and apply a
> > + * mask. In this scheme, the address of the transition only depends on the
> > + * input byte, so there is better pipelining.
>
> Should be "To compute the *next* state, ...", I think.

Fixed.

> The way the state transition table works is pretty inscrutable. That's
> understandable, because the values were found by an SMT solver, so I'm
> not sure if anything can be done about it.

Do you mean in general, or just the state values?

Like any state machine, the code is simple, and the complexity is
hidden in the data. Hopefully the first link I included in the comment
is helpful.

The SMT solver was only needed to allow 32-bit (instead of 64-bit)
entries in the transition table, so it's not strictly necessary. A
lookup table that fits in 1kB is nice from a cache perspective,
however.

With 64-bit, the state values are less weird-looking but they're still
just arbitrary numbers. As long as ERR = 0 and the largest is at most
9, it doesn't matter what they are, so I'm not sure it's much less
mysterious. You can see the difference between 32-bit and 64-bit in
[1].

--
In addition to Heikki's. review points, I've made a couple small
additional changes from v24: I rewrote this part, so we don't need
these macros anymore:

-                       if (!IS_HIGHBIT_SET(*s) ||
-                               IS_UTF8_2B_LEAD(*s) ||
-                               IS_UTF8_3B_LEAD(*s) ||
-                               IS_UTF8_4B_LEAD(*s))
+                       if (!IS_HIGHBIT_SET(*s) || pg_utf_mblen(s) > 1)

And I moved is_valid_ascii() to pg_wchar.h so it can be used
elsewhere. I'm not sure there's a better place to put it. I tried
using this for text_position(), for which I'll start a new thread.

[1] https://www.postgresql.org/message-id/attachment/125672/v22-addendum-32-bit-transitions.txt



--
John Naylor
EDB: http://www.enterprisedb.com


--
John Naylor
EDB: http://www.enterprisedb.com

I plan to push v25 early next week, unless there are further comments.

-- 
John Naylor
EDB: http://www.enterprisedb.com

On Fri, Dec 17, 2021 at 9:29 AM John Naylor
<john.naylor@enterprisedb.com> wrote:
>
> I plan to push v25 early next week, unless there are further comments.

Pushed, thanks everyone!

-- 
John Naylor
EDB: http://www.enterprisedb.com