.NET-Community-Toolkit/CommunityToolkit.HighPerformance/Helpers/Internals/SpanHelper.Count.cs

// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

using System;
using System.Numerics;
using System.Runtime.CompilerServices;

namespace CommunityToolkit.HighPerformance.Helpers.Internals;

/// <summary>
/// Helpers to process sequences of values by reference.
/// </summary>
internal static partial class SpanHelper
{
    /// <summary>
    /// Counts the number of occurrences of a given value into a target search space.
    /// </summary>
    /// <param name="r0">A <typeparamref name="T"/> reference to the start of the search space.</param>
    /// <param name="length">The number of items in the search space.</param>
    /// <param name="value">The <typeparamref name="T"/> value to look for.</param>
    /// <typeparam name="T">The type of value to look for.</typeparam>
    /// <returns>The number of occurrences of <paramref name="value"/> in the search space</returns>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static nint Count<T>(ref T r0, nint length, T value)
        where T : IEquatable<T>
    {
        if (!Vector.IsHardwareAccelerated)
        {
            return CountSequential(ref r0, length, value);
        }

        // Special vectorized version when using a supported type
        if (typeof(T) == typeof(byte) ||
            typeof(T) == typeof(sbyte) ||
            typeof(T) == typeof(bool))
        {
            ref sbyte r1 = ref Unsafe.As<T, sbyte>(ref r0);
            sbyte target = Unsafe.As<T, sbyte>(ref value);

            return CountSimd(ref r1, length, target);
        }

        if (typeof(T) == typeof(char) ||
            typeof(T) == typeof(ushort) ||
            typeof(T) == typeof(short))
        {
            ref short r1 = ref Unsafe.As<T, short>(ref r0);
            short target = Unsafe.As<T, short>(ref value);

            return CountSimd(ref r1, length, target);
        }

        if (typeof(T) == typeof(int) ||
            typeof(T) == typeof(uint))
        {
            ref int r1 = ref Unsafe.As<T, int>(ref r0);
            int target = Unsafe.As<T, int>(ref value);

            return CountSimd(ref r1, length, target);
        }

        if (typeof(T) == typeof(long) ||
            typeof(T) == typeof(ulong))
        {
            ref long r1 = ref Unsafe.As<T, long>(ref r0);
            long target = Unsafe.As<T, long>(ref value);

            return CountSimd(ref r1, length, target);
        }

#if NET6_0_OR_GREATER
        if (typeof(T) == typeof(nint) ||
            typeof(T) == typeof(nuint))
        {
            ref nint r1 = ref Unsafe.As<T, nint>(ref r0);
            nint target = Unsafe.As<T, nint>(ref value);

            return CountSimd(ref r1, length, target);
        }
#endif

        return CountSequential(ref r0, length, value);
    }

    /// <summary>
    /// Implements <see cref="Count{T}"/> with a sequential search.
    /// </summary>
    private static nint CountSequential<T>(ref T r0, nint length, T value)
        where T : IEquatable<T>
    {
        nint result = 0;
        nint offset = 0;

        // Main loop with 8 unrolled iterations
        while (length >= 8)
        {
            result += Unsafe.Add(ref r0, offset + 0).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 1).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 2).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 3).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 4).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 5).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 6).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 7).Equals(value).ToByte();

            length -= 8;
            offset += 8;
        }

        if (length >= 4)
        {
            result += Unsafe.Add(ref r0, offset + 0).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 1).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 2).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 3).Equals(value).ToByte();

            length -= 4;
            offset += 4;
        }

        // Iterate over the remaining values and count those that match
        while (length > 0)
        {
            result += Unsafe.Add(ref r0, offset).Equals(value).ToByte();

            length -= 1;
            offset += 1;
        }

        return result;
    }

    /// <summary>
    /// Implements <see cref="Count{T}"/> with a vectorized search.
    /// </summary>
    private static nint CountSimd<T>(ref T r0, nint length, T value)
        where T : unmanaged, IEquatable<T>
    {
        nint result = 0;
        nint offset = 0;

        // Skip the initialization overhead if there are not enough items
        if (length >= Vector<T>.Count)
        {
            Vector<T> vc = new(value);

            do
            {
                // Calculate the maximum sequential area that can be processed in
                // one pass without the risk of numeric overflow in the dot product
                // to sum the partial results. We also backup the current offset to
                // be able to track how many items have been processed, which lets
                // us avoid updating a third counter (length) in the loop body.
                nint max = GetUpperBound<T>();
                nint chunkLength = length <= max ? length : max;
                nint initialOffset = offset;

                Vector<T> partials = Vector<T>.Zero;

                // Unrolled vectorized loop, with 8 unrolled iterations. We only run this when the
                // current type T is at least 2 bytes in size, otherwise the average chunk length
                // would always be too small to be able to trigger the unrolled loop, and the overall
                // performance would just be slightly worse due to the additional conditional branches.
                if (typeof(T) != typeof(sbyte))
                {
                    while (chunkLength >= Vector<T>.Count * 8)
                    {
                        ref T ri0 = ref Unsafe.Add(ref r0, offset + (Vector<T>.Count * 0));
                        Vector<T> vi0 = Unsafe.As<T, Vector<T>>(ref ri0);
                        Vector<T> ve0 = Vector.Equals(vi0, vc);

                        partials -= ve0;

                        ref T ri1 = ref Unsafe.Add(ref r0, offset + (Vector<T>.Count * 1));
                        Vector<T> vi1 = Unsafe.As<T, Vector<T>>(ref ri1);
                        Vector<T> ve1 = Vector.Equals(vi1, vc);

                        partials -= ve1;

                        ref T ri2 = ref Unsafe.Add(ref r0, offset + (Vector<T>.Count * 2));
                        Vector<T> vi2 = Unsafe.As<T, Vector<T>>(ref ri2);
                        Vector<T> ve2 = Vector.Equals(vi2, vc);

                        partials -= ve2;

                        ref T ri3 = ref Unsafe.Add(ref r0, offset + (Vector<T>.Count * 3));
                        Vector<T> vi3 = Unsafe.As<T, Vector<T>>(ref ri3);
                        Vector<T> ve3 = Vector.Equals(vi3, vc);

                        partials -= ve3;

                        ref T ri4 = ref Unsafe.Add(ref r0, offset + (Vector<T>.Count * 4));
                        Vector<T> vi4 = Unsafe.As<T, Vector<T>>(ref ri4);
                        Vector<T> ve4 = Vector.Equals(vi4, vc);

                        partials -= ve4;

                        ref T ri5 = ref Unsafe.Add(ref r0, offset + (Vector<T>.Count * 5));
                        Vector<T> vi5 = Unsafe.As<T, Vector<T>>(ref ri5);
                        Vector<T> ve5 = Vector.Equals(vi5, vc);

                        partials -= ve5;

                        ref T ri6 = ref Unsafe.Add(ref r0, offset + (Vector<T>.Count * 6));
                        Vector<T> vi6 = Unsafe.As<T, Vector<T>>(ref ri6);
                        Vector<T> ve6 = Vector.Equals(vi6, vc);

                        partials -= ve6;

                        ref T ri7 = ref Unsafe.Add(ref r0, offset + (Vector<T>.Count * 7));
                        Vector<T> vi7 = Unsafe.As<T, Vector<T>>(ref ri7);
                        Vector<T> ve7 = Vector.Equals(vi7, vc);

                        partials -= ve7;

                        chunkLength -= Vector<T>.Count * 8;
                        offset += Vector<T>.Count * 8;
                    }
                }

                while (chunkLength >= Vector<T>.Count)
                {
                    ref T ri = ref Unsafe.Add(ref r0, offset);

                    // Load the current Vector<T> register, and then use
                    // Vector.Equals to check for matches. This API sets the
                    // values corresponding to matching pairs to all 1s.
                    // Since the input type is guaranteed to always be signed,
                    // this means that a value with all 1s represents -1, as
                    // signed numbers are represented in two's complement.
                    // So we can just subtract this intermediate value to the
                    // partial results, which effectively sums 1 for each match.
                    Vector<T> vi = Unsafe.As<T, Vector<T>>(ref ri);
                    Vector<T> ve = Vector.Equals(vi, vc);

                    partials -= ve;

                    chunkLength -= Vector<T>.Count;
                    offset += Vector<T>.Count;
                }

#if NET6_0_OR_GREATER
                result += CastToNativeInt(Vector.Sum(partials));
#else
                result += CastToNativeInt(Vector.Dot(partials, Vector<T>.One));
#endif
                length -= offset - initialOffset;
            }
            while (length >= Vector<T>.Count);
        }

        // Optional 8 unrolled iterations. This is only done when a single SIMD
        // register can contain over 8 values of the current type, as otherwise
        // there could never be enough items left after the vectorized path
        if (Vector<T>.Count > 8 &&
            length >= 8)
        {
            result += Unsafe.Add(ref r0, offset + 0).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 1).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 2).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 3).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 4).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 5).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 6).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 7).Equals(value).ToByte();

            length -= 8;
            offset += 8;
        }

        // Optional 4 unrolled iterations
        if (Vector<T>.Count > 4 &&
            length >= 4)
        {
            result += Unsafe.Add(ref r0, offset + 0).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 1).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 2).Equals(value).ToByte();
            result += Unsafe.Add(ref r0, offset + 3).Equals(value).ToByte();

            length -= 4;
            offset += 4;
        }

        // Iterate over the remaining values and count those that match
        while (length > 0)
        {
            result += Unsafe.Add(ref r0, offset).Equals(value).ToByte();

            length -= 1;
            offset += 1;
        }

        return result;
    }

    /// <summary>
    /// Gets the upper bound for partial sums with a given <typeparamref name="T"/> parameter.
    /// </summary>
    /// <typeparam name="T">The type argument currently in use.</typeparam>
    /// <returns>The native <see cref="int"/> value representing the upper bound.</returns>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static unsafe nint GetUpperBound<T>()
        where T : unmanaged
    {
        if (typeof(T) == typeof(sbyte))
        {
            return sbyte.MaxValue;
        }

        if (typeof(T) == typeof(short))
        {
            return short.MaxValue;
        }

        if (typeof(T) == typeof(int))
        {
            return int.MaxValue;
        }

        if (typeof(T) == typeof(long))
        {
            if (sizeof(nint) == sizeof(int))
            {
                return int.MaxValue;
            }

            // If we are on a 64 bit architecture and we are counting with a SIMD vector of 64
            // bit values, we can use long.MaxValue as the upper bound, as a native integer will
            // be able to contain such a value with no overflows. This will allow the count tight
            // loop to process all the items in the target area in a single pass (except the mod).
            // The (void*) cast is necessary to ensure the right constant is produced on runtimes
            // before .NET 5 that don't natively support C# 9. For instance, removing that (void*)
            // cast results in the value 0xFFFFFFFFFFFFFFFF (-1) instead of 0x7FFFFFFFFFFFFFFFF.
            return (nint)(void*)long.MaxValue;
        }

#if NET6_0_OR_GREATER
        if (typeof(T) == typeof(nint))
        {
            return nint.MaxValue;
        }
#endif

        throw null!;
    }

    /// <summary>
    /// Casts a value of a given type to a native <see cref="int"/>.
    /// </summary>
    /// <typeparam name="T">The input type to cast.</typeparam>
    /// <param name="value">The input <typeparamref name="T"/> value to cast to native <see cref="int"/>.</param>
    /// <returns>The native <see cref="int"/> cast of <paramref name="value"/>.</returns>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static nint CastToNativeInt<T>(T value)
        where T : unmanaged
    {
        if (typeof(T) == typeof(sbyte))
        {
            return (byte)(sbyte)(object)value;
        }

        if (typeof(T) == typeof(short))
        {
            return (ushort)(short)(object)value;
        }

        if (typeof(T) == typeof(int))
        {
            return (nint)(uint)(int)(object)value;
        }

        if (typeof(T) == typeof(long))
        {
            return (nint)(ulong)(long)(object)value;
        }

#if NET6_0_OR_GREATER
        if (typeof(T) == typeof(nint))
        {
            return (nint)(object)value;
        }
#endif

        throw null!;
    }
}