Re: speed up verifying UTF-8

Thank you,

It looks like it is important to have shrx for x86 which appears only when
-march=x86-64-v3 is used (see
https://github.com/golang/go/issues/47120#issuecomment-877629712 ).
Just in case: I know x86 wound not use fallback implementation, however,
the sole purpose of shift-based DFA is to fold all the data-dependent ops
into a single instruction.

An alternative idea: should we optimize for validation of **valid** inputs
rather than optimizing the worst case?
In other words, what if the implementation processes all characters always
and uses a slower method in case of validation failure?
I would guess it is more important to be faster with accepting valid input
rather than "faster to reject invalid input".

In shift-DFA approach, it would mean the validation loop would be simpler
with fewer branches (see https://godbolt.org/z/hhMxhT6cf ):

static inline int
pg_is_valid_utf8(const unsigned char *s, const unsigned char *end) {
uint64 class;
uint64 state = BGN;
while (s < end) { // clang unrolls the loop
class = ByteCategory[*s++];
state = class >> (state & DFA_MASK); // <-- note that AND is fused
into the shift operation
}
return (state & DFA_MASK) != ERR;
}

Note: GCC does not seem to unroll "while(s<end)" loop by default, so manual
unroll might be worth trying:

static inline int
pg_is_valid_utf8(const unsigned char *s, const unsigned char *end) {
uint64 class;
uint64 state = BGN;
while(s < end + 4) {
for(int i = 0; i < 4; i++) {
class = ByteCategory[*s++];
state = class >> (state & DFA_MASK);
}
}
while(s < end) {
class = ByteCategory[*s++];
state = class >> (state & DFA_MASK);
}
return (state & DFA_MASK) != ERR;
}

----

static int pg_utf8_verifystr2(const unsigned char *s, int len) {
if (pg_is_valid_utf8(s, s+len)) { // fast path: if string is valid,
then just accept it
return s + len;
}
// slow path: the string is not valid, perform a slower analysis
return s + ....;
}

Vladimir