Re: Byte Addressability And Beyond

Terje Mathisen wrote:

Anton Ertl wrote:

This approach can also be SIMDified, converting regbits/32 code points
in one representation to the same number of code points in the other
representation plus a length of the UTF-8 representation.
>
The disadvantage of this approach exists particularly for
UTF-8->UTF-32: this is a very sequential approach full of dependences:
each use of the conversion instruction is followed by a dependent load
of the next input fragment, and the next use of the conversion
instruction depends on that load.

 Rather the opposite:
 UTF8->UTF32 looks a _lot_ like an easier example of a byte-oriented variable length (x86?) instruction decoder, but with the big simplification that the first byte directly tells you how long the sequence is.
 Doing a SIMD version corresponds to a superscalar x86 in that the decoder needs to grab a variable number of bytes for each instruction, starting the next immediately after.

Even better (compared to a superscalar x86 instruction decoder), _every_ byte uses the top two bits to tell you if this is 7-bit ascii, the start of a UTF-8 encoded code point, or a follow-on byte inside a UTF-8 code point.
This means that each decoder can work alone, without having to wait for the length decoding of the previous code point ("instruction") before deciding to discard or pass on the results it got from starting where it did.
It seems like it would be very feasible to have (say) 8 parallel decoders starting at every corresponding byte offset, and return a SIMD register with 2-8 32-bit decoded code points, right?
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"