Could you add some clarity?
The PR is for sse_convert_latin1_to_utf8.
But you're discussing a performance regression with sse_convert_utf16_to_latin1 ?

This PR :
I suspect the branch for 'ASCII fast path' will interfere with unrolling attempts.

The bottleneck is probably: latency from the random lookups and the thruput of the shuffle port.
(I imagine there are 6 shuffles per 16 bytes of input)

The CPU can have 20+ loads "in-flight" at once. The total loads issued per cycle is not that interesting for unrolling (we always have the same number of loads). It is mostly for scheduling instructions at the assembly level, and to ballpark whether we're IO bound (e.g. do we want to replace a lookup with a calculation, are we spilling and reloading register, etc.).

Tables contain results for sse_convert_latin1_to_utf8 only. But somehow 7761599 commit causes sse_convert_latin1_to_utf8 regression.
I just go to the brunch sse_convert_latin1_to_utf8_perf, rebuild all and run the benchmark. Results are placed in the "before the commit" row.
Then I just do git rebase 7761599262953df2a1d9c3427d0d27d1cb044615, rebuild all and run the benchmark again. Results are placed in the "after the commit" row.

@aqrit,

The bottleneck is probably: latency from the random lookups and the thruput of the shuffle port.
(I imagine there are 6 shuffles per 16 bytes of input)

according to uops from Nehalem to Ivy Bridge there are 2 ports for shuffle.
And I use 2 _mm_shuffle_epi8 per _mm_load_si128 to split input into 2 vectors. They are pipelined and should go in 1 cycle both.
And 2 more to pack vectors into utf-8 just after lookup. +1 cycle per shuffle
I don't think shuffle is a candidate for a bottleneck. But LUT surely is. Google says L1 cache hit takes 4 cycles in best case.
There're 2 lookups per load, so at least 8 cycles or many more in case of a cache miss.

But _mm_load_si128 is a bottleneck too. A smaller one. It's latency is 6. My original thought was that it actually might not be pipelined automatically. In this case, 2 sequential calls of it would give 32 bytes instead of 16 for the same latency.

The CPU can have 20+ loads "in-flight" at once.

but x86-64 has only 16 sse registers, how could it be 20+?
Could you provide keywords for googling?

PS: I'm actually new to all these simd stuff so excuse me if I say something stupid)

x86-64 has only 16 sse registers, how could it be 20+?

These are named registers, but we have many more registers.

You can examine the issue experimentally...
https://lemire.me/blog/2022/06/07/memory-level-parallelism-intel-ice-lake-versus-amazon-graviton-3/

A Nehalem would not have a problem with the shuffles. However, a Haswell or Skylake might. On what CPU are you performing the benchmark?

The terms would be register renaming and out-of-order execution, I guess.

uops.info Code Analyzer is probably a good place to start, if we want to micro-optimize this.

@aqrit A fun one is this PR: #318

The westmere kernel (which is currently just scalar code, but subject to autovectorization) is faster than a reasonable hand-coded AVX2 routine. It is still fine because the differences are small... but it is clear that we could micro-optimize better.

I think I get it roughly. But I struggle to draw parallels with actual code in general. But fortunately, for this PR I'm not into tuning this exact implementation but rather introducing the msvc issue and whether it's present in other compilers as well as unrolling effect with different compilers.

I additionally checked clang and icx, both doesn't have this issue at least for this pr. But the results also showed that unrolling is not necessarily consistent between compilers for the same os. clang showed performance degradation for windows and ubuntu, unlike the rest. So, if we use unrolling, we have to choose how to handle such situations.

Tomorrow I'll try to found out whether building separately helps with msvc.
P.S. I got a build error with mingw, should I open an issue?

It doesn't. But I found that clang can actually benefit from unrolling. Just don't use inlined functions in loop body. For some reason they drop performance a lot.

UPD: I replaced inlined functions with macros. Now everything looks much better. Unroll factors are likely not the most optimal, there were some better ones during development. I'm gonna write a script to brute force them.

cache miss

If we're willing to do 4 lookups per 16 bytes of input, then we'd only use 2 cache lines for tables.
https://gist.github.com/aqrit/5c914da98006874d0401983eb687e30e

Note: I haven't actually studied the utf16->utf8 function so I don't what that is doing...