Subjects.cs

using System.Buffers;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;

namespace SimdProof;

/// <summary>
/// Поиск, подсчёт и сравнение строк руками против методов BCL, плюс две ручные векторные реализации (AVX2 и AVX-512)
///
/// Ключевое: RyuJIT не векторизует произвольный цикл (issue #12466, с 2019).
/// Ручной for по строке компилируется в скаляр. Вся SIMD-скорость строковых
/// операций живёт внутри BCL, где вектора написаны руками.
///
/// Пруфы:
///   Автовекторизация RyuJIT - issue #12466
///       https://github.com/dotnet/runtime/issues/12466
///   SearchValues (.NET 8) - https://learn.microsoft.com/dotnet/api/system.buffers.searchvalues
///   AVX-512 медленнее AVX2 из-за latency масок EVEX - LLVM #91302
///       https://github.com/llvm/llvm-project/issues/91302
///   AVX-512 не быстрее на инференсе, местами медленнее - OpenVINO #11710
///       https://github.com/openvinotoolkit/openvino/issues/11710
///
/// NoInlining на методах - только чтобы каждый печатался в листинге
/// отдельно и под своим именем. На сам цикл и проверку инлайн не влияет.
/// </summary>
public static class Subjects
{
    // ------------------------------------------------------------------
    // Поиск одного символа: цикл против BCL.
    // ------------------------------------------------------------------
    [MethodImpl(MethodImplOptions.NoInlining)]
    public static int IndexOfCharManual(string s, char c)
    {
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == c)
            {
                return i;
            }
        }

        return -1;
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static int IndexOfCharBcl(string s, char c)
    {
        return s.IndexOf(c);
    }

    // ------------------------------------------------------------------
    // Ручная векторизация AVX2 (ymm, 16 символов за шаг).
    // ------------------------------------------------------------------

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static unsafe int IndexOfCharVector256(string s, char c)
    {
        int length = s.Length;
        fixed (char* pStart = s)
        {
            char* p = pStart;
            int i = 0;

            if (Avx2.IsSupported && length >= Vector256<ushort>.Count)
            {
                Vector256<ushort> target = Vector256.Create((ushort)c);
                int step = Vector256<ushort>.Count;

                for (; i <= length - step; i += step)
                {
                    Vector256<ushort> block = Avx.LoadVector256((ushort*)(p + i));
                    Vector256<ushort> eq = Avx2.CompareEqual(block, target);

                    int mask = Avx2.MoveMask(eq.AsByte());
                    if (mask != 0)
                    {
                        return i + (BitOperations.TrailingZeroCount(mask) / 2);
                    }
                }
            }

            for (; i < length; i++)
            {
                if (p[i] == c)
                {
                    return i;
                }
            }
        }

        return -1;
    }

    // ------------------------------------------------------------------
    // Ручная векторизация AVX-512 (zmm, 32 символа за шаг).
    // По пруфу LLVM #91302 маски EVEX имеют бОльшую latency,
    // так что "шире" может выйти МЕДЛЕННЕЕ.
    // ------------------------------------------------------------------

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static unsafe int IndexOfCharVector512(string s, char c)
    {
        int length = s.Length;
        fixed (char* pStart = s)
        {
            char* p = pStart;
            int i = 0;

            if (Avx512BW.IsSupported && length >= Vector512<ushort>.Count)
            {
                Vector512<ushort> target = Vector512.Create((ushort)c);
                int step = Vector512<ushort>.Count;

                for (; i <= length - step; i += step)
                {
                    Vector512<ushort> block = Avx512F.LoadVector512((ushort*)(p + i));

                    ulong mask = Avx512BW.CompareEqual(block, target).ExtractMostSignificantBits();
                    if (mask != 0)
                    {
                        return i + BitOperations.TrailingZeroCount(mask);
                    }
                }
            }

            for (; i < length; i++)
            {
                if (p[i] == c)
                {
                    return i;
                }
            }
        }

        return -1;
    }

    // ------------------------------------------------------------------
    // Подсчёт символа: цикл против span.Count (BCL, векторный).
    // ------------------------------------------------------------------

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static int CountCharManual(string s, char c)
    {
        int count = 0;
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == c)
            {
                count++;
            }
        }

        return count;
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static int CountCharBcl(string s, char c)
    {
        return s.AsSpan().Count(c);
    }

    // ------------------------------------------------------------------
    // Сравнение строк: цикл против SequenceEqual (BCL, векторный).
    // Строки равны и разные по ссылке - полный проход, без фаст-пасов.
    // ------------------------------------------------------------------

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static bool EqualsManual(string a, string b)
    {
        if (a.Length != b.Length)
        {
            return false;
        }

        for (int i = 0; i < a.Length; i++)
        {
            if (a[i] != b[i])
            {
                return false;
            }
        }

        return true;
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static bool EqualsBcl(string a, string b)
    {
        return a.AsSpan().SequenceEqual(b);
    }

    // ------------------------------------------------------------------
    // Поиск любого из набора
    // ------------------------------------------------------------------

    private static readonly SearchValues<char> Vowels = SearchValues.Create("aeiou");

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static int IndexOfVowelManual(string s)
    {
        for (int i = 0; i < s.Length; i++)
        {
            char c = s[i];
            if (c is 'a' or 'e' or 'i' or 'o' or 'u')
            {
                return i;
            }
        }

        return -1;
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static int IndexOfVowelAny(string s) => s.AsSpan().IndexOfAny("aeiou");

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static int IndexOfVowelSearchValues(string s) => s.AsSpan().IndexOfAny(Vowels);

    // ------------------------------------------------------------------
    // Регистронезависимый поиск через ToLower против BCL.
    // ------------------------------------------------------------------

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static int IndexOfIgnoreCaseManual(string s, char c)
    {
        char lower = char.ToLowerInvariant(c);
        for (int i = 0; i < s.Length; i++)
        {
            if (char.ToLowerInvariant(s[i]) == lower)
            {
                return i;
            }
        }

        return -1;
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static int IndexOfIgnoreCaseBcl(string s, string needle)
    {
        return s.IndexOf(needle, StringComparison.OrdinalIgnoreCase);
    }
}