c# - 使用 C# Vector<T> SIMD 查找匹配元素的索引

Question

使用 C# 的 Vector<T> ，我们如何才能最有效地向量化查找集合中特定元素的索引的操作？

作为约束，该集合将始终是 Span<T>一个整数基元，它最多包含 1 个匹配元素。

我想出了一个看起来不错的解决方案，但我很好奇我们是否可以做得更好。这是方法:

创建一个 Vector<T>在每个插槽中仅由目标元素组成。

使用 Vector.Equals()在输入集向量和上一步的向量之间，得到一个在单个匹配槽中包含 1 的掩码(如果没有匹配，则只包含 0)。

使用包含基于 1 的索引 (1, 2, 3, 4, ...) 的预初始化向量，调用 Vector.Dot()在该向量和上一步的掩码之间。每个索引都将乘以 0，除了潜在的匹配索引，它将乘以 1。我们得到的是这些乘法的总和，它要么是 0，要么是匹配元素的从 1 开始的索引。

如果结果为 0，则返回 -1 表示不匹配。否则，从结果中减去 1 使其从 0 开始，然后返回该结果。

    // One-time initialized vector containing { 1, 2, 3, 4, ... }
    Vector<ushort> indexes = MemoryMarshal.Cast<ushort, Vector<ushort>>(Enumerable.Range(1, Vector<ushort>.Count).Select(index => (ushort)index).ToArray())[0];

    // The input set and the element to search for
    Span<ushort> set = stackalloc ushort[]{ 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 };
    ushort element = 22;

    // Interpret input set as a sequence of vectors (set is assumed to have length power of two for brevity)
    var setVectors = MemoryMarshal.Cast<ushort, Vector<ushort>>(set);

    // Create a vector that contains the target element in each slot
    var elementVector = new Vector<ushort>(element);

    // Loop per vector rather than per element
    foreach (var vector in setVectors)
    {
        // Get a mask that has a 1 in the single matching slot, or only 0s
        var mask = Vector.Equals(vector, elementVector);

        // Get the dot product of the mask and the indexes
        // This will multiple each index by 0, or by 1 if it is the matching one, and return their sum, i.e. the matching index or 0
        // Note that the indexes are deliberately 1-based, to distinguished from 0 (no match)
        var index = Vector.Dot(indexes, mask);

        // Either return 0 for no match, or reduce the index by 1 to get the 0-based index
        return index == 0 ? -1 : index - 1;
    }

Answer 1

正如我所看到的简单 Span<char>.IndexOf 已经在使用 Intrinsics 来搜索一个简单的值。你甚至不需要转换为 char 来使用它，因为 MemoryExtensions.IndexOf只关心尺寸和Unsafe.SizeOf<ushort>() == sizeof(char) !

也在 JsonReaderHelper.IndexOfOrLessThan 您会发现一个更复杂的矢量化示例进行搜索。它使用字节搜索，但我相信如果 Span<ushort>.IndexOf，您可以根据自己的需要进行调整。不合适。