4 ms·

Interesting to compare the SWAR approach with 64-bit register, a similar approach with 128-bit register (SSE-2), and string search instructions (SSE-4.2). This

Interesting to compare the SWAR approach with 64-bit register, a similar approach with 128-bit register (SSE-2), and string search instructions (SSE-4.2). This implementation in ClickHouse can be used as a reference: https://github.com/ClickHouse/ClickHouse/blob/a04b38db907b8e01760a45ab8cf7aa0acab45d5c/base/base/find_symbols.h#L14 https://github.com/ClickHouse/ClickHouse/blob/a04b38db907b8e... Obviously, SWAR should be slower (due to register size), but how slower?

hummus_bae 4y ago
All modern CPU architectures have builtin fast string compare instructions. Here is a table from the Intel manual (bolded are the relevant compare instructions): https://msdk.intel.com/en-us/library/cc286809.aspx https://msdk.intel.com/en-us/library/cc286809.aspx > SSE-4.2: Compare strings using dqa (32-bit mode), dqq (64-bit mode), dqu, dsx > SSE-3: Compare strings using cmpsdx, cmpsd, scansigndx, scansignd > SSE-2: Compare strings using pmaxsw, pand, pmin, pmins > SSE-1: Compare strings using pandn, pavg, pandnpand, pandnpandn, pandn, pandnpandndivr, ...
- deleted 4y ago
  [deleted]
- anonymoushn 4y ago
  If you want to write a fast parser you mostly don't end up using these. You use pshufb, as detailed in a sibling comment by stabbles.
- amelius 4y ago
  But this is not strictly speaking a string compare operation, I suppose.
stabbles 4y ago
Sometimes you can do this in two instructions per 16 / 32 / 64 chars (sse / avx / avx-512 resp): shuffle & compare. The gist of it is lookup[hash(char)] == char where 'lookup[hash(char)]' corresponds to _mm_shuffle_epi8 with a carefully crafted constant and input data, and '==' corresponds to _mm_cmpeq_epi8. The intrinsic c = _mm_shuffle_epi8(a, b) pretty much computes c[i] = b[a[i] & 0x0F], so if there are no collisions in a[i] & 0x0F, you can construct a special b so that b[hash('@')] = '@' b[hash('/')] = '/' b[hash('?')] = '?' b[hash('\\')] = '\\' b[x] = 0x00 # otherwise Unfortunately in this case, it doesn't work, since `/` and `?` have a collision, they both map to `0x0F`. If you would just search for say @, / and \, it would be possible, and shuffle + cmp is sufficient.
- Sesse__ 4y ago
  Shift them to the right one bit :-)
  - anonymoushn 4y ago
    Unfortunately there's no 8-bit srli, and if you use the 16-bit srli, you could end up shifting a 1 into the high bit of the low 8 bits of your 16-bit word. pshufb treats a 1 in the high bit as a signal to map the input to 0 instead of using the lower 4 bits as a lookup table. So the full thing ends up being (for AVX-2): _mm256_srli_epi16 // by 1 _mm256_and_si256 // to mask off the high bit _mm256_shuffle_epi8 // b[a[i] & 0x0F] _mm256_cmpeq_epi8 // a[i] == This is still pretty good! If you end up needing more instructions to get map your chosen bytes to 16 unique low nibbles though, some other technique may pull ahead. See here for some techniques: http://0x80.pl/articles/simd-byte-lookup.html http://0x80.pl/articles/simd-byte-lookup.html Note that the above article is a bit too conservative about the applicability of some of these techniques and does not end up telling you to do cmpeq(input, pshufb(constant, input)) even though this is what you want if all the bytes of interest are <128 (i.e. they are ascii characters) which is often true.

hummus_bae 4y ago

All modern CPU architectures have builtin fast string compare instructions. Here is a table from the Intel manual (bolded are the relevant compare instructions): https://msdk.intel.com/en-us/library/cc286809.aspx https://msdk.intel.com/en-us/library/cc286809.aspx > SSE-4.2: Compare strings using dqa (32-bit mode), dqq (64-bit mode), dqu, dsx > SSE-3: Compare strings using cmpsdx, cmpsd, scansigndx, scansignd > SSE-2: Compare strings using pmaxsw, pand, pmin, pmins > SSE-1: Compare strings using pandn, pavg, pandnpand, pandnpandn, pandn, pandnpandndivr, ...

deleted 4y ago
[deleted]
anonymoushn 4y ago
If you want to write a fast parser you mostly don't end up using these. You use pshufb, as detailed in a sibling comment by stabbles.
amelius 4y ago
But this is not strictly speaking a string compare operation, I suppose.

stabbles 4y ago

Sometimes you can do this in two instructions per 16 / 32 / 64 chars (sse / avx / avx-512 resp): shuffle & compare. The gist of it is lookup[hash(char)] == char where 'lookup[hash(char)]' corresponds to _mm_shuffle_epi8 with a carefully crafted constant and input data, and '==' corresponds to _mm_cmpeq_epi8. The intrinsic c = _mm_shuffle_epi8(a, b) pretty much computes c[i] = b[a[i] & 0x0F], so if there are no collisions in a[i] & 0x0F, you can construct a special b so that b[hash('@')] = '@' b[hash('/')] = '/' b[hash('?')] = '?' b[hash('\\')] = '\\' b[x] = 0x00 # otherwise Unfortunately in this case, it doesn't work, since `/` and `?` have a collision, they both map to `0x0F`. If you would just search for say @, / and \, it would be possible, and shuffle + cmp is sufficient.

Sesse__ 4y ago
Shift them to the right one bit :-)
- anonymoushn 4y ago
  Unfortunately there's no 8-bit srli, and if you use the 16-bit srli, you could end up shifting a 1 into the high bit of the low 8 bits of your 16-bit word. pshufb treats a 1 in the high bit as a signal to map the input to 0 instead of using the lower 4 bits as a lookup table. So the full thing ends up being (for AVX-2): _mm256_srli_epi16 // by 1 _mm256_and_si256 // to mask off the high bit _mm256_shuffle_epi8 // b[a[i] & 0x0F] _mm256_cmpeq_epi8 // a[i] == This is still pretty good! If you end up needing more instructions to get map your chosen bytes to 16 unique low nibbles though, some other technique may pull ahead. See here for some techniques: http://0x80.pl/articles/simd-byte-lookup.html http://0x80.pl/articles/simd-byte-lookup.html Note that the above article is a bit too conservative about the applicability of some of these techniques and does not end up telling you to do cmpeq(input, pshufb(constant, input)) even though this is what you want if all the bytes of interest are <128 (i.e. they are ascii characters) which is often true.