4 ms·

Another trick for classifying bytes is to use pshufb. That instruction works like: fn pshufb(a: [i8; 16], b: [i8; 16]) -> [i8; 16] { result = [0; 16]

Another trick for classifying bytes is to use pshufb. That instruction works like: fn pshufb(a: [i8; 16], b: [i8; 16]) -> [i8; 16] { result = [0; 16] for j in 0, 1, …, 15 { if b[j] >= 0 { result[j] = a[b[j] & 15]; } } return result; } So you can often construct values m1, m2, and compute: a = pshufb(m1, input & 0xf) b = pshufb(m2, (unsigned_input) >> 4) x = f(a,b) Where f is something like bit wise AND. Roughly, m1 and m2 assign sets of 8 potential properties based on the high or low order bits of each byte, and then we and together the sets of properties to make sure the upper and lower bits ‘agree’. This technique can sometimes be used to mark a few special characters.

dragontamer 2y ago
Pshufb is an old trick. An oldie but a goodie from SSE2 days. All hail modern improvements!! pdep, pext, vpcompressb, vpexpandb, and especially vpermi2v. Forget about 16 byte lookup table with pshufb. Try a 128-byte lookup with vpermi2v AVX512. -------- I find that pext/pdep for 64-bits and vpcompressb/vpexpandb for 512-bits is also more flexible than pshufb (!!!!) in practice, if a bit slower as it is over multiple instructions. Supercomputer programs are written with a gather-conpute-scatter pattern. Gather your data, compute on the data, and finally place the data where needed. Pext and vpcompressb are gather operations. Pdep and vpexpandb are scatter. Pshufb is only a gather and thus fails to match the supercomputer pattern. GPUs provide a bpermute (backwards-permute) that scatters results back to a table and is really the missing link IMO. Hopefully Intel will provide bpermute of their own eventually....
teo_zero 2y ago
> So you can often construct values m1, m2, and compute: And what would m1 and m2 be for the specific problem¹ described in TFA? ¹ Namely, to find out if the input belongs to [0-9A-Za-z]
- dragontamer 2y ago
  The original poster got lucky and m1 and m2 can in fact be constructed. But your overall post and skepticism is warranted. It's definitely wrong in the general case the original post made. To solve this easily, you truly need the 128-byte table from vpermi2v / AVX512 (note that ASCII is a 7-bit code and thus all functions of ASCII fit inside of a 128-table). The reason the original post got lucky is that the top 2 bits of ASCII determine special vs numbers vs lowercase vs uppercase. The bottom 5 bits determine the specific character. ASCII is a table of tables. 0x30-0x39 are '0' - '9' respectively. So 0x3 in the 'top' table proves you have a number. 0x40 is uppercase and 0x60 is lower case letters. Bottom table is harder to construct but we don't actually need to know the top bits. We just need 0x0-0x9 (valid for numbers) vs 0x1-0xF (valid for 0x4 and 0x6, as 0x40 and 0x60 are invalid letters), and finally 0x0-0x1A (aka p-z, valid for top half of alphabets in ASCII). This harder bottom table is solvable with 3 bits of the 8, meaning we have 5 spare bits for future extensions. So valid for numbers is bit 0x1. Valid for lower-half alphabet is 0x2 and valid for upper-half alphabet is 0x4. Locations like 5 are valid for all three (0x7) while locations like 0 are only valid for numbers and upper half alphabet (aka 0x5). ---------- In the general case, the [0-9a-zA-Z] language is a regular language (even in an arbitrary non-ASCII code in binary), which means it can always be solved with a state transition table and a finite automata. And yes, pshufb can be a very useful tool for making such a table (and a bigger table like vpermi2v is even better). But it's not clear that the pshufb sequence in the original post would always work for an arbitrary jump table. Indeed, for best results you likely need to use pext and other complex bit instructions to efficiently extract the most info out of the bits available. Or you know.... Use the 128-tanle from vpermi2v. ------ Note: FPGAs are composed of 4-LUTs which share many similarities with these 4-bit / 16-byte tables. One can argue that an FPGA is nothing more than a whole bunch of parallel pshufb units. But that doesn't mean that two such tables solves all problems lol. It's often surprising how some problems blow up in your face and suddenly eat up thousands of LUTs.
  - boris-smidt 2y ago
    Interesting i never thought of ASCII to be a table of tables I'll have another look into the ASCII table number sequences to better understand it. This thread is really full of gold nuggets.
boris-smidt 2y ago
I'll try it in the follow up post and probably include some graphics to make it clear what it does. Its indeed the real simd way of comparing multiple characters in 1 iteration instead of 1 character per iteration.
- dragontamer 2y ago
  purplesyringa's post below is ~7 assembly instructions without any need of lookup tables. And the instructions purplesyringa uses are Add, AND, OR, and Compare. Modern CPUs can execute ~4 ADD/AND/OR instructions per clock tick (even if they are SIMD or even AVX512 instructions), so you're looking at under 4ish clock cycles to purplesyringa's solution. Its likely the best solution in the whole thread. The main advantage of pshufb is its extreme flexibility due to the lookup table, so there's advantages in learning that methodology. But in general, sequences of simpler instructions are much faster. --------- The "hard part" of purplesyringa's code is that its branchless. Learning to write branchless (especially using the pcmpeq* line of instructions) is a bit of a hassle and worth practicing for sure. AVX512 added explicit mask registers that do it better but 128-bit SSE / 256-bit AVX is still more widespread today.

dragontamer 2y ago

Pshufb is an old trick. An oldie but a goodie from SSE2 days. All hail modern improvements!! pdep, pext, vpcompressb, vpexpandb, and especially vpermi2v. Forget about 16 byte lookup table with pshufb. Try a 128-byte lookup with vpermi2v AVX512. -------- I find that pext/pdep for 64-bits and vpcompressb/vpexpandb for 512-bits is also more flexible than pshufb (!!!!) in practice, if a bit slower as it is over multiple instructions. Supercomputer programs are written with a gather-conpute-scatter pattern. Gather your data, compute on the data, and finally place the data where needed. Pext and vpcompressb are gather operations. Pdep and vpexpandb are scatter. Pshufb is only a gather and thus fails to match the supercomputer pattern. GPUs provide a bpermute (backwards-permute) that scatters results back to a table and is really the missing link IMO. Hopefully Intel will provide bpermute of their own eventually....

teo_zero 2y ago

> So you can often construct values m1, m2, and compute: And what would m1 and m2 be for the specific problem¹ described in TFA? ¹ Namely, to find out if the input belongs to [0-9A-Za-z]

dragontamer 2y ago
The original poster got lucky and m1 and m2 can in fact be constructed. But your overall post and skepticism is warranted. It's definitely wrong in the general case the original post made. To solve this easily, you truly need the 128-byte table from vpermi2v / AVX512 (note that ASCII is a 7-bit code and thus all functions of ASCII fit inside of a 128-table). The reason the original post got lucky is that the top 2 bits of ASCII determine special vs numbers vs lowercase vs uppercase. The bottom 5 bits determine the specific character. ASCII is a table of tables. 0x30-0x39 are '0' - '9' respectively. So 0x3 in the 'top' table proves you have a number. 0x40 is uppercase and 0x60 is lower case letters. Bottom table is harder to construct but we don't actually need to know the top bits. We just need 0x0-0x9 (valid for numbers) vs 0x1-0xF (valid for 0x4 and 0x6, as 0x40 and 0x60 are invalid letters), and finally 0x0-0x1A (aka p-z, valid for top half of alphabets in ASCII). This harder bottom table is solvable with 3 bits of the 8, meaning we have 5 spare bits for future extensions. So valid for numbers is bit 0x1. Valid for lower-half alphabet is 0x2 and valid for upper-half alphabet is 0x4. Locations like 5 are valid for all three (0x7) while locations like 0 are only valid for numbers and upper half alphabet (aka 0x5). ---------- In the general case, the [0-9a-zA-Z] language is a regular language (even in an arbitrary non-ASCII code in binary), which means it can always be solved with a state transition table and a finite automata. And yes, pshufb can be a very useful tool for making such a table (and a bigger table like vpermi2v is even better). But it's not clear that the pshufb sequence in the original post would always work for an arbitrary jump table. Indeed, for best results you likely need to use pext and other complex bit instructions to efficiently extract the most info out of the bits available. Or you know.... Use the 128-tanle from vpermi2v. ------ Note: FPGAs are composed of 4-LUTs which share many similarities with these 4-bit / 16-byte tables. One can argue that an FPGA is nothing more than a whole bunch of parallel pshufb units. But that doesn't mean that two such tables solves all problems lol. It's often surprising how some problems blow up in your face and suddenly eat up thousands of LUTs.
- boris-smidt 2y ago
  Interesting i never thought of ASCII to be a table of tables I'll have another look into the ASCII table number sequences to better understand it. This thread is really full of gold nuggets.

boris-smidt 2y ago

I'll try it in the follow up post and probably include some graphics to make it clear what it does. Its indeed the real simd way of comparing multiple characters in 1 iteration instead of 1 character per iteration.

dragontamer 2y ago
purplesyringa's post below is ~7 assembly instructions without any need of lookup tables. And the instructions purplesyringa uses are Add, AND, OR, and Compare. Modern CPUs can execute ~4 ADD/AND/OR instructions per clock tick (even if they are SIMD or even AVX512 instructions), so you're looking at under 4ish clock cycles to purplesyringa's solution. Its likely the best solution in the whole thread. The main advantage of pshufb is its extreme flexibility due to the lookup table, so there's advantages in learning that methodology. But in general, sequences of simpler instructions are much faster. --------- The "hard part" of purplesyringa's code is that its branchless. Learning to write branchless (especially using the pcmpeq* line of instructions) is a bit of a hassle and worth practicing for sure. AVX512 added explicit mask registers that do it better but 128-bit SSE / 256-bit AVX is still more widespread today.