Use shift based DFA for utf8 validation

[Keno]

There's a post going around on Twitter for how to write a super fast DFA, e.g. for UTF8 validation: https://twitter.com/_rsc/status/1413843059972923394?s=19. We have a UTF8 validation function, so we should try this technique. Should be reasonably simple to do.

[Keno]

I guess there's also this: https://lemire.me/blog/2020/10/20/ridiculously-fast-unicode-utf-8-validation/, which may be implemented elsewhere in the ecosystem.

[StefanKarpinski]

I read through the Lemire paper for inspiration on vectorized string length that handles our way of counting invalid data as characters correctly. Can't find the issue now.

[RohitRathore1]

Can't find the issue now.

So, it means it has been resolved now?

[jakobnissen]

It's this: #33988 .

[StefanKarpinski]

No, it literally means I was not able to find the issue on GitHub. Thanks for the link, @jakobnissen.

[StefanKarpinski]

For what it's worth, UTF-8 validation is rarely a bottleneck in Julia since we don't do it unless the user explicitly asks for validation.

[Seelengrab]

Our UTF-8 validation function is ultimately a forward to this C code. This function is called in ios.c and flisp/string.c, so it would probably have to remain a C version to make the change more localized.

[oscardssmith]

In general, we like to replace C code with Julia where practical.

[Seelengrab]

I'm not familiar with how flisp is used in julia (I think it's for the parser?), so I'm not sure if decoupling the julia & parser versions is good here 🤷 Just wanted to point it out, since this is labeled as good-first-issue.

[StefanKarpinski]

It's fine to leave the flisp UTF-8 validation alone and use it for validating Julia source and have a separate pure Julia implementation for validating Julia strings. Validating source code is definitely not a bottleneck, so making that faster doesn't matter. So all someone has to do is replace this stuff with whatever fast vectorized implementation they want.