[Question] Is the intrinsics SSE4.2 _mm_cmpistrm instruction exposed somewhere ?

[wolfgarbe]

I am looking for the _mm_cmpistrm instruction, available on SSE4.2 processors.
( PCMPISTRM Packed Compare Implicit Length Strings, Return Mask https://www.felixcloutier.com/x86/pcmpistrm )
Can't find it on the Sse42 object...

[EgorBo]

See #957 (comment) (and follow up comments)
TLDR: Sse2.CompareEquals + Sse2.MoveMask or Sse41.TestZ are enough for string compare and their 256bit versions exist in AVX2

[wolfgarbe]

Thank you for the quick reply.

I'm not doing string comparison, but intersection between two sorted 16-bit arrays using SSE4.1 intrinsics (see code below).
_mm_cmpistrm (vB , vA ,_SIDD_UWORD_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK ) ; would allow to compare any element of vector A to any element of vector B (8*8=64 comparisons).

As far as I know, the proposed Sse2.CompareEquals / _mm256_cmpeq_epi16 allows only a pairwise comparison of the elements of vector A and Vecor B (8 comparisons).

Any suggestion?

int32_t intersect ( uint16_t *A, size_t lengthA ,
uint16_t *B, size_t lengthB ,
uint16_t * out) {
size_t count = 0; // size of intersection
size_t i = 0 , j = 0;
int vectorlength = sizeof ( __m128i ) / sizeof ( uint16_t ) ;
__m128i vA , vB , rv , sm16 ;
while (i < lengthA ) && (j < lengthB ) {
vA = _mm_loadu_si128 (( __m128i *) &A[i]) ;
vB = _mm_loadu_si128 (( __m128i *) &B[j]) ;
rv = _mm_cmpistrm (vB , vA ,
_SIDD_UWORD_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK ) ;
int r = _mm_extract_epi32 (rv , 0) ;
sm16 = _mm_load_si128 ( mask16 + r) ;
__m128i p = _mm_shuffle_epi8 (vA , sm16 ) ;
_mm_storeu_si128 (( __m128i *) ( out + count ) ,p) ;
count += _mm_popcnt_u32 (r) ;
uint16_t a_max = A[i + vectorlength - 1];
uint16_t b_max = B[j + vectorlength - 1];
if ( a_max <= b_max ) i += vectorlength ;
if ( b_max <= a_max ) j += vectorlength ;
}
return count ;
}

Source: Roaring Bitmaps: Implementation of an Optimized Software Library, Daniel Lemire https://arxiv.org/pdf/1709.07821.pdf

[saucecontrol]

That's an interesting use case for pcmpistrX with _SIDD_CMP_EQUAL_ANY. I've only ever seen it used for actual character matching, such as this example in RapidJSON:

runtime/src/native/external/rapidjson/reader.h

Lines 296 to 305 in 0e499ac

	// The rest of string using SIMD
	static const char whitespace[16] = " \n\r\t";
	const __m128i w = _mm_loadu_si128(reinterpret_cast<const __m128i *>(&whitespace[0]));
	for (;; p += 16) {
	const __m128i s = _mm_load_si128(reinterpret_cast<const __m128i *>(p));
	const int r = _mm_cmpistri(w, s, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_LEAST_SIGNIFICANT | _SIDD_NEGATIVE_POLARITY);
	if (r != 16) // some of characters is non-whitespace
	return p + r;
	}

In cases like that (small number of characters to match), similar perf can be achieved when substituting multiple compares with constant vectors that have each character broadcast to all elements -- with even better performance when extended to 256-bit vectors with AVX2.

For a full intersection of 8x8 values, there won't be an approach that can equal what _SIDD_CMP_EQUAL_ANY gives you, until you get access to the new AVX-512 vpintersectX instructions, and even those won't substitute if you want to compare byte or word lengths.

The only real hold-up to getting those missing SSE4.2 instructions into System.Runtime.Intrinsics is finalizing the API shape #957. If you have ideas around that, an API proposal would be welcome, I'm sure. #63331 would be a good template to use.

[wolfgarbe]

Thank you very much for the detailed answer. AVX-512 vpintersectX would indeed work for my use case, but is supported only by a small number of processors and is also not yet available in C#. Probably I have to resort to writing the method in C++ (where _mm_cmpistrm is supported by the Microsoft C++ compiler) and then call it as an external library from C#.
Unfortunately, this looks more like an ugly hack than clean code.

[saucecontrol]

FYI, I've got the ball rolling with #68204. Let's see if we can come up with an API shape that makes sense.