用SIMD最快的方法来找出Span<ushort>中是否存在“ushort”？

Question

在C# on .NET Core中，我正在寻找最快的方法来检查给定的ushort值是否存在于Span<ushort>范围内。朴素选项包括枚举span，但我强烈怀疑通过SIMD (即SSE或AVX)存在一个速度更快的单核选项。

这里最快的选择是什么？(不安全代码可以)

Answer 1

一个基本的实现(在应用诸如Peter在注释中描述的优化之前)可以这样工作：

static unsafe bool ContainsUshort(Span<ushort> data, ushort val)
{
    int vecSize = Vector<ushort>.Count;
    var value = new Vector<ushort>(val);
    int i;
    fixed (ushort* ptr = &data[0])
    {
        int limit = data.Length - vecSize;
        for (i = 0; i <= limit; i += vecSize)
        {
            var d = Unsafe.ReadUnaligned<Vector<ushort>>(ptr + i);
            if (Vector.EqualsAny(d, value))
                return true;
        }
    }
    for (; i < data.Length; i++)
    {
        if (data[i] == val)
            return true;
    }
    return false;
}

这就要求System.Runtime.CompilerServices.Unsafe包用于不安全的读取，而不需要从span (或数组)创建向量的效率要低得多。顺便说一句，EqualsAny内部是用(v)ptest而不是(v)pmovmskb实现的，ptest通常要花费更多的(v)ptest操作，所以尽量减少它的影响是比较重要的，但是由于没有直接访问ptest或pmovmskb的权限(可以通过使用更新的平台特定的System.Runtime.Intrinsics.X86 API来避免这种限制)，最后的“向量到条件”AFAIK仍然必须用Vector.EqualsAny (使用填充了0xFFFF的向量)来完成，这有点愚蠢。尽管如此，在我的机器上它还是快了一点(经过测试，返回值将是false，因此非展开版本稍早的退出就没有发挥作用)。

var allSet = new Vector<ushort>(0xFFFF);
int limit = data.Length - vecSize * 2;
for (i = 0; i <= limit; i += vecSize * 2)
{
    var d0 = Unsafe.ReadUnaligned<Vector<ushort>>(ptr + i);
    var d1 = Unsafe.ReadUnaligned<Vector<ushort>>(ptr + i + vecSize);
    var eq = Vector.Equals(d0, value) | Vector.Equals(d1, value);
    if (Vector.EqualsAny(eq, allSet))
        return true;
}