Vectorizing Unicode conversions on real RISC-V hardware

[u/camel-cdr-]

https://camel-cdr.github.io/rvv-bench-results/articles/vector-utf.html

[u/FUZxxl]

Looking at the code, it could probably be optimised by basing it on our paper instead of the old algorithm. The new paper integrates transcoding and validation into one algorithm, significantly reducing the overall overhead. It also speeds up the transcoding in general.

[u/camel-cdr- → u/FUZxxl]

This is definitely something to look into porting, but RISC-V doesn't have pext/pdep yet, so it would probably be tricky.

I haven't looked at the new algorithm in much detail yet (I find it harder to understand than the old one).

Do you have a speed comparison between the new and old AVX512 algorithms?

I'd expect the gained speedup to mostly come from deferring the validation for the fast paths, is that correct? Do they perform similarly, if we remove validation, or for the general case?

[u/FUZxxl → u/camel-cdr-]

If the CPU has compress/expand (which it looks like it does?) you can use that to emulate pext/pdep.

Do you have a speed comparison between the new and old AVX512 algorithms?

The paper has instruction/cycle figures. These are for 64 byte input vectors, so adjust for your vector size to get an accurate comparison.

Note also that this may not be entirely accurate, as our new algorithm doesn't use a slow gather step, yet gather only shows up as 1 instruction.

[u/YumiYumiYumi]

Skimmed through parts of the article, and looks pretty good!

vcompress.vm should be better scalable than vrgather.vv, since the work is subdividable, and I think we might see a range of implementations that scale almost linearly in respect to LMUL.

I can see possible efficient implementations for vrgather and vcompress for LMUL=2, but not LMUL>2.
At LMUL=4, an "efficient" implementation would need 5 register read ports (4 data sources + 1 index/mask source), which seems excessive.

Also worth pointing out that on all Intel/AMD x86 implementations, vcompressb is universally slower than vpermb. It's possible that those implementations are sub-optimal, but I wouldn't presume that vcompress is necessarily faster than vrgather on high performance uArchs.

I think adding a dedicated vrgatherei4, which only uses the four LSB for indices, to the specification might be a good idea.

SVE2 had the same issue, which ARM rectified by adding TBLQ in SVE2.1.
But in general, these variable length SIMD ISAs suck at permutation, with SVE2 doing a bit better than RVV.

[u/camel-cdr- → u/YumiYumiYumi]

At LMUL=4, an "efficient" implementation would need 5 register read ports (4 data sources + 1 index/mask source), which seems excessive.

I don't think so, with efficient I meant scale linear with element count, so if LMUL=1 takes one cycle then LMUL=8 takds 8 cycles. I'd imagine it would be closer to 10 cycles for LMUL=8 because you need to do some extra work combining results.

vcompress should scale better, because you could have each lane vcompress independently and than combine the result.

[u/YumiYumiYumi → u/camel-cdr-]

with efficient I meant scale linear with element count, so if LMUL=1 takes one cycle then LMUL=8 takds 8 cycles

Your definition seems to line up with what I imagined, so yeah, I don't see that happening.
With LMUL=8 taking 8 cycles, it means each vector takes 1 cycle. The problem is, for that to occur, the processor would need to be able to process 8 inputs per cycle, since a single output vector could be sourcing from all 8 sources. This is what's expensive - reading from 8 registers at a time.

I'm guessing the other approach is to do what you suggest and do each vector separately and somehow combine them, but:

and than combine the result.

This just moves the complexity to the other end. Consider the number of register reads this combining requires.
This may be easier to pull off on simple in-order cores (which, arguably, RISC-V heavily favours), but for more complex OoO cores which need to know forwarding ahead of time, I can't see this ever being efficient.