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

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.