Используйте 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, если совпадений нет. В противном случае вычтите одно из результата, чтобы сделать его основанным на 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, который вы хотите сгенерировать компилятором, равен для сравнения (pcmpeqb), pmovmskb или movmskps (вектор в битовую маску с 1-байтовыми или 4-байтовыми элементами), а затем, если маска ненулевая, выполняется сканирование для первого установленного бита (bsf или tzcnt).

Это будет более эффективно, чем произведение целочисленных точек !!

У вас уже есть сравнение для равных, и я думаю, что я видел другие C # Q & As с внутренним свойством vector-> bitmap.Если кто-то хочет отредактировать этот ответ или опубликовать свой собственный с помощью C #, который компилирует / JIT для этого ассемблера, сделайте это.Я не знаю C #, я просто здесь для SIMD x86.