Guid comparer using x86 SIMD instructions

[MarkPflug]

I wrote a Guid comparer that uses x86 SIMD instructions to implement a branchless comparer.

sealed class GuidComparer : IComparer<Guid>
{
	public int Compare(Guid x, Guid y)
	{
		if (Ssse3.IsSupported)
		{
			return CompareSimd(x, y);
		}
		else
		{
			return x.CompareTo(y);
		}
	}

	// shuffle the bytes such that they result in LE comparison order after MoveMask.
	// I think we can ignore BE, since x86 should always be LE?
	static readonly Vector128<sbyte> Shuffle = 
	// Guid compare shuffle
	     Vector128.Create((sbyte)15, 14, 13, 12, 11, 10, 9, 8, 6, 7, 4, 5, 0, 1, 2, 3);
	// SqlGuid compare shuffle
	//  Vector128.Create((sbyte)3, 2, 1, 0, 5, 4, 7, 6, 9, 8, 15, 14, 13, 12, 11, 10);

	// the compare operations only work on sbyte, not byte. This is used to rotate the values
	// such that they compare as unsigned bytes
	static readonly Vector128<sbyte> Shift = Vector128.Create(unchecked((sbyte)128));
		
	public static unsafe int CompareSimd(Guid x, Guid y)
	{
		Vector128<sbyte> xv = Sse2.LoadVector128((sbyte*)&x);
		Vector128<sbyte> yv = Sse2.LoadVector128((sbyte*)&y);

		xv = Ssse3.Shuffle(xv, Shuffle);
		yv = Ssse3.Shuffle(yv, Shuffle);

		xv = Sse2.Add(xv, Shift);
		yv = Sse2.Add(yv, Shift);

		var lv = Sse2.CompareLessThan(xv, yv);
		var gv = Sse2.CompareGreaterThan(xv, yv);

		var lm = Sse2.MoveMask(lv);
		var gm = Sse2.MoveMask(gv);

		var r = gm - lm;
		return r;
	}
}

The existing guid comparison (Guid.CompareTo) is fast enough, as it usually only has to inspect a single value to make a determination. However, in some benchmarking, it seems like it might suffer from branch misprediction. In a fully-random guid the first compared value will be random, so the branch is going to be unpredictable. In my benchmarking, I found the SIMD approach to be ~2x faster (half the time) as the current comparer implementation, when comparing random guids.

The more interesting case is when doing comparisons of "sequential guids", such as those produced by UuidCreateSequential on Windows. Using the standard guid comparer, the fastest changing byte in a sequential guid is also the first byte compared by the standard guid comparer. Comparing pairs of sequentially allocated guids, the standard comparer is marginally faster than the SIMD implementation, since the first branch becomes very predictable. The SIMD compare was 21% slower.

However, when using SqlGuid to do the comparison, the fastest changing byte is the last byte compared. SqlGuid uses a comparer which will match the order produced by SqlServer order by. This means that if you were trying to sort sequential guids in .NET using the SqlGuid comparer, it is going to be a bit slower than sorting random guids, as most of the guid bytes will compare equal. In this scenario I found the SIMD approach to be ~5x faster than the SqlGuid comparer. Given the changes might be coming in #72549, this might not be as dramatic, but I think it would still be significant.

The only thing that needs to change between the Guid and SqlGuid comparison implementations is the Shuffle vector, see commented out line.

It is entirely possible there is a flaw in my logic, but it agreed with the existing comparer in all the testing I did. Maybe someone can see some improvements, as I'm definitely not an expert in SIMD operations.

[EgorBo]

You don't need to save constant vectors to static fields - moreover, it makes code only slower now.

From my understand CompareTo operation only makes sense for sequential guids so if SIMD doesn't work well there then it's probably to keep the existing logic.

[MarkPflug]

Thanks for the feedback, @EgorBo. Inlining the statics as locals dropped the delta from 21% to 10% for sequential guids.

I think this implementation is best suited for SqlGuid comparison, which is more likely to be used with sequential guids than the standard Guid.

[Xyncgas]

What an awesome display of your intellectual integrity, I hope the bits treat you well, maybe the sound of shuffling bytes leads you the way, to the miracle of that the 128bits create, friend, SIMD is one the most powerful weapon on this planet a human can have inside .NET, aside from source generation custom Json serializer a working encryption implementation IAsyncEnumerable helper object mappers, it will pays you off down the road