| 1 |
This document contains notes about various ideas that for one reason or another |
| 2 |
are not being actively pursued. |
| 3 |
|
| 4 |
## Next byte is non-ASCII after ASCII optimization |
| 5 |
|
| 6 |
The current plan for a SIMD-accelerated inner loop for handling ASCII bytes |
| 7 |
makes no use of the bit of information that if the buffers didn't end but the |
| 8 |
ASCII loop exited, the next byte will not be an ASCII byte. |
| 9 |
|
| 10 |
## Handling ASCII with table lookups when decoding single-byte to UTF-16 |
| 11 |
|
| 12 |
Both uconv and ICU outperform encoding_rs when decoding single-byte to UTF-16. |
| 13 |
unconv doesn't even do anything fancy to manually unroll the loop (see below). |
| 14 |
Both handle even the ASCII range using table lookup. That is, there's no branch |
| 15 |
for checking if we're in the lower or upper half of the encoding. |
| 16 |
|
| 17 |
However, adding SIMD acceleration for the ASCII half will likely be a bigger |
| 18 |
win than eliminating the branch to decide ASCII vs. non-ASCII. |
| 19 |
|
| 20 |
## Manual loop unrolling for single-byte encodings |
| 21 |
|
| 22 |
ICU currently outperforms encoding_rs (by over x2!) when decoding a single-byte |
| 23 |
encoding to UTF-16. This appears to be thanks to manually unrolling the |
| 24 |
conversion loop by 16. See [ucnv_MBCSSingleToBMPWithOffsets][1]. |
| 25 |
|
| 26 |
[1]: https://ssl.icu-project.org/repos/icu/icu/tags/release-55-1/source/common/ucnvmbcs.cpp |
| 27 |
|
| 28 |
Notably, none of the single-byte encodings have bytes that'd decode to the |
| 29 |
upper half of BMP. Therefore, if the unmappable marker has the highest bit set |
| 30 |
instead of being zero, the check for unmappables within a 16-character stride |
| 31 |
can be done either by ORing the BMP characters in the stride together and |
| 32 |
checking the high bit or by loading the upper halves of the BMP charaters |
| 33 |
in a `u8x8` register and checking the high bits using the `_mm_movemask_epi8` |
| 34 |
/ `pmovmskb` SSE2 instruction. |
| 35 |
|
| 36 |
## After non-ASCII, handle ASCII punctuation without SIMD |
| 37 |
|
| 38 |
Since the failure mode of SIMD ASCII acceleration involves wasted aligment |
| 39 |
checks and a wasted SIMD read when the next code unit is non-ASCII and non-Latin |
| 40 |
scripts have runs of non-ASCII even if ASCII spaces and punctuation is used, |
| 41 |
consider handling the next two or three bytes following non-ASCII as non-SIMD |
| 42 |
before looping back to the SIMD mode. Maybe move back to SIMD ASCII faster if |
| 43 |
there's ASCII that's not space or punctuation. Maybe with the "space or |
| 44 |
punctuation" check in place, this code can be allowed to be in place even for |
| 45 |
UTF-8 and Latin single-byte (i.e. not having different code for Latin and |
| 46 |
non-Latin single-byte). |
| 47 |
|
| 48 |
## Prefer maintaining aligment |
| 49 |
|
| 50 |
Instead of returning to acceleration directly after non-ASCII, consider |
| 51 |
continuing to the alignment boundary without acceleration. |
| 52 |
|
| 53 |
## Read from SIMD lanes instead of RAM (cache) when ASCII check fails |
| 54 |
|
| 55 |
When the SIMD ASCII check fails, the data has already been read from memory. |
| 56 |
Test whether it's faster to read the data by lane from the SIMD register than |
| 57 |
to read it again from RAM (cache). |
| 58 |
|
| 59 |
## Use Level 2 Hanzi and Level 2 Kanji ordering |
| 60 |
|
| 61 |
These two are ordered by radical and then by stroke count, so in principle, |
| 62 |
they should be mostly Unicode-ordered, although at least Level 2 Hanzi isn't |
| 63 |
fully Unicode-ordered. Is "mostly" good enough for encode accelelation? |
| 64 |
|
| 65 |
## Create a `divmod_94()` function |
| 66 |
|
| 67 |
Experiment with a function that computes `(i / 94, i % 94)` more efficiently |
| 68 |
than generic code. |
| 69 |
|
| 70 |
## Align writes on Aarch64 |
| 71 |
|
| 72 |
On [Cortex-A57](https://stackoverflow.com/questions/45714535/performance-of-unaligned-simd-load-store-on-aarch64/45938112#45938112 |
| 73 |
), it might be a good idea to move the destination into 16-byte alignment. |
| 74 |
|
| 75 |
## Unalign UTF-8 validation on Aarch64 |
| 76 |
|
| 77 |
Currently, Aarch64 runs the generic ALU UTF-8 validation code that aligns |
| 78 |
reads. That's probably unnecessary on Aarch64. (SIMD was slower than ALU!) |
| 79 |
|
| 80 |
## Table-driven UTF-8 validation |
| 81 |
|
| 82 |
When there are at least four bytes left, read all four. With each byte |
| 83 |
index into tables corresponding to magic values indexable by byte in |
| 84 |
each position. |
| 85 |
|
| 86 |
In the value read from the table indexed by lead byte, encode the |
| 87 |
following in 16 bits: advance 2 bits (2, 3 or 4 bytes), 9 positional |
| 88 |
bits one of which is set to indicate the type of lead byte (8 valid |
| 89 |
types, in the 8 lowest bits, and invalid, ASCII would be tenth type), |
| 90 |
and the mask for extracting the payload bits from the lead byte |
| 91 |
(for conversion to UTF-16 or UTF-32). |
| 92 |
|
| 93 |
In the tables indexable by the trail bytes, in each positions |
| 94 |
corresponding byte the lead byte type, store 1 if the trail is |
| 95 |
invalid given the lead and 0 if valid given the lead. |
| 96 |
|
| 97 |
Use the low 8 bits of the of the 16 bits read from the first |
| 98 |
table to mask (bitwise AND) one positional bit from each of the |
| 99 |
three other values. Bitwise OR the results together with the |
| 100 |
bit that is 1 if the lead is invalid. If the result is zero, |
| 101 |
the sequence is valid. Otherwise it's invalid. |
| 102 |
|
| 103 |
Use the advance to advance. In the conversion to UTF-16 or |
| 104 |
UTF-32 case, use the mast for extracting the meaningful |
| 105 |
bits from the lead byte to mask them from the lead. Shift |
| 106 |
left by 6 as many times as the advance indicates, etc. |