Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Thomas Koenig <tkoenig@netcologne.de>
Newsgroups: comp.arch
Subject: Re: Byte Addressability And Beyond
Date: Thu, 30 May 2024 11:59:53 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 51
Message-ID: <v39pno$1m7mr$1@dont-email.me>
References: <v0s17o$2okf4$2@dont-email.me> <v31c4r$3u28v$1@dont-email.me>
 <v327n3$1use$1@gal.iecc.com> <BM25O.40665$HBac.4762@fx15.iad>
 <v32lpv$1u25$1@gal.iecc.com> <v33bqg$9cst$11@dont-email.me>
 <v34v62$ln01$1@dont-email.me> <v36bva$10k3v$2@dont-email.me>
 <2024May29.090435@mips.complang.tuwien.ac.at>
 <v39dpj$1k4hm$1@dont-email.me> <v39lc7$1lfii$1@dont-email.me>
Injection-Date: Thu, 30 May 2024 13:59:53 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="944cb8743c41371018806bf99f5e6551";
	logging-data="1777371"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19rDe7DXBtnZGo5c4XwmQdMPlsIN0SU+Bs="
User-Agent: slrn/1.0.3 (Linux)
Cancel-Lock: sha1:nE9zlzIx78bm0NhULp6Wpl94YEg=
Bytes: 3579

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
> 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?

Sounds quite reasonable (and would be like what Mitch describes for his
My 66000 decoders).  Apart from filling the buffers, it would also need
to return the number of bytes consumed and the number of UTF-32
characters generated, plus a possible error indication.

Looking at what IBM did, the CU14 instruction is memory-to-memory
and they use both the length and the address of both the source
and destination data in register pairs.  The number of characters
to process are then decremented according to what has been processed
(and there might be a CPU-defined limit).  They also appear to have
optional error checking only.

Complicated...