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

Question

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

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

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

1. Vector<T>在每个插槽中创建一个仅包含目标元素的对象。
2. Vector.Equals()在输入集向量和上一步中的向量之间使用，以获取在单个匹配槽中包含 1 的掩码（如果没有匹配，则仅包含 0）。
3. 使用包含基于 1 的索引 (1, 2, 3, 4, ...) 的预初始化向量，Vector.Dot()在该向量和上一步中的掩码之间进行调用。每个索引都将乘以 0，除了潜在匹配索引，它将乘以 1。我们得到的是这些乘法的总和，它要么是 0，要么是匹配元素的从 1 开始的索引。

4. 如果结果为 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

您希望编译器生成的 x86 asm 是比较等于 ( pcmpeqb)pmovmskb或movmskps（具有 1 字节或 4 字节元素的位掩码的向量），然后如果掩码非零，则对第一个设置位进行位扫描（bsf或者tzcnt）。

这将比整数点积更有效！

您已经有了比较相等的功能，而且我想我已经看到了其他带有向量->位图内在的 C# 问答。如果有人想编辑此答案或使用将 / JIT 编译到此 asm 的 C# 发布自己的答案，请这样做。我不懂 C#，我只是为了 x86 SIMD 而来。