Reducing the cost of autodecoding

[Stefam Koch via Digitalmars-d]

On Tuesday, 25 October 2016 at 19:16:07 UTC, Steven Schveighoffer 
wrote:
> On 10/25/16 12:57 PM, Dmitry Olshansky wrote:
>> On 10/12/16 3:53 PM, Andrei Alexandrescu wrote:
>>> So we've had a good run with making popFront smaller. In ASCII
>>> microbenchmarks with ldc, the speed is indistinguishable from 
>>> s = s[1 ..
>>> $]. Smaller functions make sure that the impact on 
>>> instruction cache in
>>> larger applications is not high.
>> [snip]
>>> Your mission, should you choose to accept it, is to define a 
>>> combination
>>> front/popFront that reduces the gap.
>>>
>>
>> I'm sooo late to the party. Still a neat trick with UTF lookup 
>> table is
>> to cram it into a single word with bit packing. Since we only 
>> ever
>> consider top 5 bits of leading byte of which the top one can 
>> be safely
>> discarded with a quick < 0x80 check. This leaves us at 4bits 
>> -> 16 entry
>> table, fits nicely in a 64-bit word with 4bits per entry.
>
> Half of the entries in your table are 0 (every char that starts 
> with 10). In addition, you only need 2 bits to store the length 
> (max byte sequence is 4, subtract 1 from sequence to get 2 
> bits).
>
> So I think you can fit this into a 16-bit word (8 entries of 2 
> bits each). You just need to pre-check for the invalid 
> sequences (you no longer have to check for 0 result):
>
> if(c < 0x80) s = s[1 .. $];
> else if(c < 0xc0 || c > 0xf7) throw new Exception("blah");
> else s = s[1 + myStride(c) .. $];
>
> Should behave better on 32-bit system.
>
> You could also store 3-bits to avoid extra addition.
>
> -Steve

The whole point of a LUT to begin with is to reduce instructions.