4 ms·

One thing you could do to optimize further (on CPUs with the BMI2 instruction set) is to use the PEXT instruction to perform the bit extract operation (after a

One thing you could do to optimize further (on CPUs with the BMI2 instruction set) is to use the PEXT instruction to perform the bit extract operation (after a BSWAP of course). The whole operation could be something like (untested): ; Parameters: RDI - pointer to input character ; Return value: RAX - Unicode codepoint, or -1 for error lea r8, [encoding_table] ; Load pointer to table base using rip-relative addressing mov edx, [rdi] ; unaligned (over)read of 32-bit utf8 codepoint mov ebx, edx ; Copy to EBX to construct our table index and ebx, 0xf8 ; Mask off the (potential) data bits ; Now we want to convert the top 5 bits into an index into a table of three * 32-bit entries ; Currently EBX = index * 8, we need index * 12, so we'll divide by two and then multiply by 3 shr ebx, 1 lea ebx, [ebx + ebx * 2] bswap edx ; Get the codepoint into big-endian representation pext ecx, edx, [ebx + 4] ; extract padding bits using mask pext eax, edx, [ebx] ; extract data bits cmp ecx, [ebx + 8] ; check padding bits cmovnz eax, -1 retq encoding_table: ; 00000xxx - 01111xxx times 16 dd 0x7F, 0x80, 0x00 ; 10000xxx - 10111xxx (invalid) times 8 dd 0, 0xFFFFFFFF, 0 ; The padding will never match here, forcing an error return ; 11000xxx - 11011xxx (two bytes) - padding value 11010 times 4 dd 0x1F3F, 0xE0C0, 0x1A ; 11100xxx - 11101xxx (three bytes) - padding value 1110 1010 times 2 dd 0x0F3F3F, 0xF0C0C0, 0xEA ; 11110xxx (four bytes) - padding value 111 1010 1010 dd 0x073F3F3F, 0xF8C0C0C0, 0x7AAAA

goldenkey 9y ago
Pretty cool, a recent development, only in Haswell and later architectures (2013 and later.) https://en.m.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets https://en.m.wikipedia.org/wiki/Bit_Manipulation_Instruction...
- userbinator 9y ago
  ...and on the Haswell PEXT runs in one uop with a latency of 3! That is nothing short of amazing for an operation which, from its description, would seem to require a microcode loop or at least a few more cycles to collect an arbitrary number of bits with arbitrary gaps between them: http://www.felixcloutier.com/x86/PEXT.html http://www.felixcloutier.com/x86/PEXT.html The only unfortunate thing is that it was introduced quite recently in terms of x86 history (instead of being present early on but just microcoded), so earlier software can't take advantage of it nor any subsequent improvements, and uses a pretty complex encoding (VEX) only usable in protected mode. But if anything, this is another datapoint in the argument in favour of CISC --- try doing this on a MIPS, RISC-V or even ARM! With less powerful ISAs, even something as simple as the "shl ax, 4" (shift the lower 16 bits only) turns into a multi-instruction sequence of masking and combining.
  - ant6n 9y ago
    ARMV8 has bit field extract/insert, which are fairly powerful, and I'd say more generic than "shl ax,N", which is really only there for legacy reasons (it's an instruction with 16-bit operator prefix). RISC generally tries to keep instructions as generic/useful as possible to keep silicon small.
  - to3m 9y ago
    I was thinking about this today. Imagine treating it N bits at a time. N=4, perhaps. 16 cases, so it won't take up much space, and you can just write out each case independently. Perhaps it's easy to have a table? - then you might do 8 bits at a time, maybe. This suboperation does an N-bit version of the total operation: takes N bits of the mask, the corresponding N bits of the input, and produces an S-bit result, R. (S is the population count of that part of the mask.) Suppose N=4. Then for a 64-bit value, you can do 16 of these in parallel, and you've got 16 intermediate results, R0...Rf, and 16 result sizes, S0...Sf. Then combine them. Overall result = R0 | R1<<S0 | R2<<S0+S1 | R3<<S0+S1+S2 | ... | Rf<<S0+S1+S2+...+Se. I've no idea whether this is actually easy to implement this way, but at least it requires no loop ;) ---- 12-bit example where N=4. Mask is %000101011000, and value is %lkjihgfedcba. (I've labelled each bit of the value by its position, since that's the key part.) Intermediate results: R0=%000d, S0=1. R1=%00ge, S1=2. R2=%000i, S2=1. R0's contribution to the overall result = R0 = %d. R1's = R1<<S0 = R1<<1 = %ge0. R2's = R2<<S0+S1 = R<<3 = %i000. So the overall result is %000d|%ge0|%i000 = %iged.
bdonlan 9y ago
As a followup, I went and implemented this for fun: https://github.com/bdonlan/branchless-utf8/blob/master/test/decode.s https://github.com/bdonlan/branchless-utf8/blob/master/test/... Performance seems to be quite good compared to the implementations from the article (577.333 MB/s vs the author's implementation's 410 MB/s on my hardware)

goldenkey 9y ago

Pretty cool, a recent development, only in Haswell and later architectures (2013 and later.) https://en.m.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets https://en.m.wikipedia.org/wiki/Bit_Manipulation_Instruction...

userbinator 9y ago
...and on the Haswell PEXT runs in one uop with a latency of 3! That is nothing short of amazing for an operation which, from its description, would seem to require a microcode loop or at least a few more cycles to collect an arbitrary number of bits with arbitrary gaps between them: http://www.felixcloutier.com/x86/PEXT.html http://www.felixcloutier.com/x86/PEXT.html The only unfortunate thing is that it was introduced quite recently in terms of x86 history (instead of being present early on but just microcoded), so earlier software can't take advantage of it nor any subsequent improvements, and uses a pretty complex encoding (VEX) only usable in protected mode. But if anything, this is another datapoint in the argument in favour of CISC --- try doing this on a MIPS, RISC-V or even ARM! With less powerful ISAs, even something as simple as the "shl ax, 4" (shift the lower 16 bits only) turns into a multi-instruction sequence of masking and combining.
- ant6n 9y ago
  ARMV8 has bit field extract/insert, which are fairly powerful, and I'd say more generic than "shl ax,N", which is really only there for legacy reasons (it's an instruction with 16-bit operator prefix). RISC generally tries to keep instructions as generic/useful as possible to keep silicon small.
- to3m 9y ago
  I was thinking about this today. Imagine treating it N bits at a time. N=4, perhaps. 16 cases, so it won't take up much space, and you can just write out each case independently. Perhaps it's easy to have a table? - then you might do 8 bits at a time, maybe. This suboperation does an N-bit version of the total operation: takes N bits of the mask, the corresponding N bits of the input, and produces an S-bit result, R. (S is the population count of that part of the mask.) Suppose N=4. Then for a 64-bit value, you can do 16 of these in parallel, and you've got 16 intermediate results, R0...Rf, and 16 result sizes, S0...Sf. Then combine them. Overall result = R0 | R1<<S0 | R2<<S0+S1 | R3<<S0+S1+S2 | ... | Rf<<S0+S1+S2+...+Se. I've no idea whether this is actually easy to implement this way, but at least it requires no loop ;) ---- 12-bit example where N=4. Mask is %000101011000, and value is %lkjihgfedcba. (I've labelled each bit of the value by its position, since that's the key part.) Intermediate results: R0=%000d, S0=1. R1=%00ge, S1=2. R2=%000i, S2=1. R0's contribution to the overall result = R0 = %d. R1's = R1<<S0 = R1<<1 = %ge0. R2's = R2<<S0+S1 = R<<3 = %i000. So the overall result is %000d|%ge0|%i000 = %iged.

bdonlan 9y ago

As a followup, I went and implemented this for fun: https://github.com/bdonlan/branchless-utf8/blob/master/test/decode.s https://github.com/bdonlan/branchless-utf8/blob/master/test/... Performance seems to be quite good compared to the implementations from the article (577.333 MB/s vs the author's implementation's 410 MB/s on my hardware)