Repository: go
Issue: unicode/utf8: optimize utf8.Valid with AVX2 instructions on AMD64
Labels: Performance,NeedsInvestigation

UTF-8 validation is employed in many applications using text formats such as JSON.

An implementation of [Ridiculously fast unicode (UTF-8) validation](https://lemire.me/blog/2020/10/20/ridiculously-fast-unicode-utf-8-validation/) has been available in https://github.com/segmentio/asm/tree/main/utf8 since early 2022; authored by @pelletier and myself, it was published under MIT license.

The algorithm described in the research paper yields up to 10x throughput on UTF-8 validation of medium to large strings, as shown in this preliminary comparison:

```
goos: linux
goarch: amd64
pkg: unicode/utf8
cpu: Intel(R) Xeon(R) CPU @ 2.60GHz
                            │     base      │                avx2                 │
                            │    sec/op     │   sec/op     vs base                │
ValidTenASCIIChars              5.038n ± 0%   4.156n ± 0%  -17.51% (p=0.000 n=10)
Valid100KASCIIChars            10.736µ ± 1%   3.684µ ± 0%  -65.68% (p=0.000 n=10)
ValidTenJapaneseChars           30.05n ± 0%   30.00n ± 0%   -0.17% (p=0.000 n=10)
ValidLongMostlyASCII           88.697µ ± 0%   3.174µ ± 0%  -96.42% (p=0.000 n=10)
ValidLongJapanese             126.734µ ± 0%   7.712µ ± 0%  -93.91% (p=0.000 n=10)
ValidStringTenASCIIChars        5.044n ± 0%   4.748n ± 0%   -5.88% (p=0.000 n=10)
ValidString100KASCIIChars      10.667µ ± 0%   3.683µ ± 0%  -65.47% (p=0.000 n=10)
ValidStringTenJapaneseChars     30.25n ± 1%   29.59n ± 0%   -2.21% (p=0.000 n=10)
ValidStringLongMostlyASCII     89.232µ ± 1%   3.173µ ± 0%  -96.44% (p=0.000 n=10)
ValidStringLongJapanese       126.678µ ± 0%   7.717µ ± 1%  -93.91% (p=0.000 n=10)
Valid/1kValid                  907.70n ± 0%   83.38n ± 0%  -90.81% (p=0.000 n=10)
Valid/1MValid                  933.39µ ± 1%   80.94µ ± 1%  -91.33% (p=0.000 n=10)
Valid/10ASCII                   4.750n ± 0%   4.152n ± 0%  -12.59% (p=0.000 n=10)
Valid/10Japan                   32.44n ± 0%   32.00n ± 0%   -1.37% (p=0.000 n=10)
Valid/small4096                3710.0n ± 0%   323.3n ± 0%  -91.28% (p=0.000 n=10)
Valid/small32768               29.623µ ± 1%   2.528µ ± 0%  -91.47% (p=0.000 n=10)
Valid/small65536               59.227µ ± 0%   5.052µ ± 0%  -91.47% (p=0.000 n=10)
Valid/small262144              236.84µ ± 0%   20.19µ ± 0%  -91.47% (p=0.000 n=10)
Valid/small4194304             3794.1µ ± 1%   324.6µ ± 0%  -91.44% (p=0.000 n=10)
Valid/small33554432            30.454m ± 0%   2.829m ± 1%  -90.71% (p=0.000 n=10)
Valid/small134217728           121.93m ± 0%   13.81m ± 1%  -88.68% (p=0.000 n=10)
Valid/small268435456           243.73m ± 0%   27.76m ± 1%  -88.61% (p=0.000 n=10)
Valid/tail300                  269.60n ± 0%   30.41n ± 0%  -88.72% (p=0.000 n=10)
Valid/tail316                  283.85n ± 0%   29.59n ± 0%  -89.58% (p=0.000 n=10)
geomean                         11.27µ        1.871µ       -83.41%

                     │     base     │                  avx2                   │
                     │     B/s      │      B/s       vs base                  │
Valid/1kValid          1.051Gi ± 0%   11.437Gi ± 0%   +988.55% (p=0.000 n=10)
Valid/1MValid          1.046Gi ± 1%   12.065Gi ± 1%  +1053.11% (p=0.000 n=10)
Valid/10ASCII          1.961Gi ± 0%    2.243Gi ± 0%    +14.40% (p=0.000 n=10)
Valid/10Japan          881.9Mi ± 0%    894.2Mi ± 0%     +1.40% (p=0.000 n=10)
Valid/small4096        1.028Gi ± 0%   11.798Gi ± 0%  +1047.49% (p=0.000 n=10)
Valid/small32768       1.030Gi ± 1%   12.071Gi ± 0%  +1071.69% (p=0.000 n=10)
Valid/small65536       1.031Gi ± 0%   12.082Gi ± 0%  +1072.40% (p=0.000 n=10)
Valid/small262144      1.031Gi ± 0%   12.090Gi ± 0%  +1072.86% (p=0.000 n=10)
Valid/small4194304     1.030Gi ± 1%   12.034Gi ± 0%  +1068.81% (p=0.000 n=10)
Valid/small33554432    1.026Gi ± 0%   11.044Gi ± 1%   +976.30% (p=0.000 n=10)
Valid/small134217728   1.025Gi ± 0%    9.054Gi ± 1%   +783.14% (p=0.000 n=10)
Valid/small268435456   1.026Gi ± 0%    9.006Gi ± 1%   +777.99% (p=0.000 n=10)
Valid/tail300          1.037Gi ± 0%    9.189Gi ± 0%   +786.53% (p=0.000 n=10)
Valid/tail316          1.037Gi ± 0%    9.948Gi ± 0%   +859.39% (p=0.000 n=10)
geomean                1.067Gi         8.136Gi        +662.20%
```

The algorithm also scales much better than the current implementation of `utf8.Valid` as the size of input grows, as shown by this graph plotting the compute time for the two versions for input sizes of 0 to 400 bytes: 
![image](https://github.com/golang/go/assets/865510/424a7047-03e5-49a8-80cc-fe0414723b9b)

The main trade-off here is complexity; while the code has been fuzz-tested against the current version of `utf8.Valid`, as well as successfully used on production workloads, a bug will always be possible in this implementation or on other platforms that would be added later on.

I looked for prior discussions on improving the performance of `unicode/utf8`, but could not find much content on the topic. This proposal will likely set a precedent for porting the algorithm to other architectures, if accepted.

Part of the requirements to integrate it with the standard library could be to expand test coverage in the `unicode/utf8` package to ensure the correctness of this implementation and hypothetical future additions for other architectures.