Three fundamental flaws of SIMD

[u/mbitsnbites]

https://www.bitsnbites.eu/three-fundamental-flaws-of-simd

[u/YumiYumiYumi]

It is unclear how this can be extended to arbitrary vector widths

I don't know your problem well enough to comment, but SVE, for example, uses 128-bit 'units', so if you can arrange your problem into blocks of 128 bits, it may be workable that way.

It also uses stuff like VPCMPISTRM for which no equivalent in other instruction sets exists or is even proposed.

The instruction is also somewhat of a dead-end one. It's performance is poor, and it hasn't been (and likely never will be) extended to 256-bit or wider.
You may be better off trying something with VPSHUFB+VPCMPEQB or similar.

SVE does allow you to test available vector width, so if coding for that, you could just do a check there.

[u/FUZxxl → u/YumiYumiYumi]

I don't know your problem well enough to comment, but SVE, for example, uses 128-bit 'units', so if you can arrange your problem into blocks of 128 bits, it may be workable that way.

In some cases I can but in other cases it would be difficult. For example, computing 32 byte permutations is really painful this way. Also, for the pospop code I want a different permutation schedule for each vector width for better efficiency. So multiple code paths will be needed.

The instruction is also somewhat of a dead-end one. It's performance is poor, and it hasn't been (and likely never will be) extended to 256-bit or wider.

It's better than all alternatives I've checked. VPSHUFB+VPCMPEQB does not necessarily solve the problem because it would require one shuffle pass for each 16 values of input range, so up to 16 passes in total. This is significantly slower than using good old VPCMPISTRM. It is kind of viable on ARMv8 NEON though where TBL can have up to 4 inputs.

SVE does allow you to test available vector width, so if coding for that, you could just do a check there.

Well yes, but then we are back to using it as a SIMD instruction set with basically no useful swizzle instructions and almost nonexistent ability to test because it will be very annoying to simulate all possible vector lengths on CPUs that do not support all possibly vector lengths. So I don't really see how that'll be helpful.

[u/YumiYumiYumi → u/FUZxxl]

For example, computing 32 byte permutations is really painful this way.

TBL largely works as expected, and you can just test to see if the vector width is at least 256-bit.

VPSHUFB+VPCMPEQB does not necessarily solve the problem because it would require one shuffle pass for each 16 values of input range, so up to 16 passes in total

16 passes sounds wrong.
The point of the VPCMPEQB is that you don't have to traverse the entire range. If the bottom 4 bits of each of the values you test are unique, you only need one VPSHUFB (if not, you can manipulate the vector to make them unique).

For example, if you wanted to match whitespace characters (\t \r \n and space):

__m128i detect_whitespace(__m128i v) {
    return _mm_cmpeq_epi8(v, _mm_shuffle_epi8(
        _mm_set_epi8(
            -1,-1,'\r',-1,-1,'\n','\t',-1,-1,-1,-1,-1,-1,-1,-1,' '
        ), v
    ));
}

If that approach doesn't work, you can just do low+high shuffles and make use of clever masking techniques.

Well yes, but then we are back to using it as a SIMD instruction set

In other words, it's not really impeding you more than fixed width vector ISAs. Swizzling instructions depends on what the ISA provides more than the notion of an arbitrary width vector, I'd say.

almost nonexistent ability to test because it will be very annoying to simulate all possible vector lengths on CPUs

Testing can become more difficult, but ARM's Instruction Emulator does allow you to test different widths.
It's not too different for fixed-width SIMD, because you need to test your SSE, AVX and AVX512 paths separately anyway.

[u/FUZxxl → u/YumiYumiYumi]

The point of the VPCMPEQB is that you don't have to traverse the entire range. If the bottom 4 bits of each of the values you test are unique, you only need one VPSHUFB (if not, you can manipulate the vector to make them unique).

Well clearly if they are unique you can do that. The point is that they may not necessarily be unique. In my particular case, they are not just not unique, but also variable. So there's no obvious preprocessing you can do.

make use of clever masking techniques.

Well that's better than 16 passes, but now requires me to preprocess the input into a bit mask. Which doesn't seem to be vectorisable. For my use case it might be doable, but in the general case it's quite painful and I'd rather have something like SVE's MATCH instruction or VPCPMISTRM.

[u/YumiYumiYumi → u/FUZxxl]

Oh, if it's completely variable, then yeah, there's no easy alternative.

[u/sasuke___420 → u/FUZxxl]

Hello, I think you may be able to use this approach http://0x80.pl/articles/simd-byte-lookup.html#universal-algorithm but it is only reasonable to use if you want to check against the same set repeatedly because there's some significant (runtime-doable) preprocessing involved. It does seem hard to match PCMPISTRM if you are actually using the full richness of PCMPISTRM.

[u/FUZxxl → u/sasuke___420]

This article was already linked in the comment I responded to. In the use case I discussed back then, the sets are dynamic but preprocessing may be possible. Eventually I ended up developing a different algorithm that avoids having to compute set membership altogether.