Fastest way to move unique array elements to the front and slice the array

Question

I have a function that gets a pointer to a array with size 4 (always) and must slice only the unique elements and return them. This function gets called 100k times a second thats why it needs to be fast and souldn't pressure the GC very much (thats why buffer variable is a pointer - stackalloc).

private const int BufferLength = 4;
private static unsafe ReadOnlySpan<int> SliceUnique(int* buffer)
{
   // TODO: move the unique elements to the front
   // and get the last unique index

   return new ReadOnlySpan<int>(buffer, lastUniqueIndex + 1);
}

// Example: 
// input: [1, 3, 2, 1]                      | [1, 4, 4, 4]
// output: [1, 3, 2] (order doesn't matter) | [1, 4]

Answer 1

Here is what I came up with (back when the question was about array of ints, but I'm sure it can be modified to handle ReadOnlySpan<int> (whatever that is...)).
Tested on my computer, average execution time is 195 milliseconds for 1,000,000 arrays (including the creation of the arrays):

int[] RemoveDuplicates(int[] array)
{
    bool remove1 = array[1] == array[0];
    bool remove2 = array[2] == array[1] || array[2] == array[0];
    bool remove3 = array[3] == array[2] || array[3] == array[1] || array[3] == array[0];

    if (remove1 && remove2 && remove3)
        return new int[] { array[0] };
    if (remove1 && remove2)
        return new int[] { array[0], array[3] };
    if (remove1 && remove3)
        return new int[] { array[0], array[2] };
    if (remove2 && remove3)
        return new int[] { array[0], array[1] };
    if (remove1)
        return new int[] { array[0], array[2], array[3] };
    if (remove2)
        return new int[] { array[0], array[1], array[3] };
    if (remove3)
        return new int[] { array[0], array[1], array[2] };
    return new int[] { array[0], array[1], array[2], array[3] };
}

testing code:

static void Main(string[] args)
{
    long sum = 0;
    var stopwatch = new System.Diagnostics.Stopwatch();
    var numberOfTimes = 1000 * 1000;
    for (int i = 0; i < 100; i++)
    {
        stopwatch.Restart();
        for (int j = 0; j < numberOfTimes; j++)
        {
            var a = new int[] { j % 2, j % 3, j % 4, j % 5 };
            var r = RemoveDuplicates(a);
        }
        stopwatch.Stop();
        sum += stopwatch.ElapsedMilliseconds;
        // Console.WriteLine(string.Format("{0} => {1}", string.Join(",", a), string.Join(",", r)));
    }
    double avg = sum / 100;
    Console.WriteLine("Average execution time (100 executions) is {0}", avg);
    Console.ReadKey();
}

Answer 2

For an array [a,b,c,d]:

if (a==b)
    if (b==c)
        if (c==d)
            return (a,1)
        else
            return (a,d,2)
    else
        if (c==d)
            return (a,c,2)
        else
            if (a==d)
                return (a,c,2)
            else
                return (a,c,d,3)
else
    if (b==c)
        if (c==d)
            return (a,b,2)
        else
            if (a==d)
                return (a,b,2)
            else   
                return (a,b,d,3)
    else
        if (c==d)
            if (a==c)
                return (a,b,2)
            else
                return (a,b,c,3)
        else
            if (a==c)
                if (b==d)
                    return (a,b,2)
                else
                    return (a,b,d,3)
            else
                if (b==d)
                    return (a,b,c,3)
                else
                    if (a==d)
                        return (a,b,c,3)
                    else
                        return (a,b,c,d,4)

... you get the idea... just written off the top of my head, so better have unit test with all possible inputs :-)

Answer 3

@ZoharPeled answer - optimized with ReadOnlySpan

    private static unsafe ReadOnlySpan<int> SliceUniqueZoharPeledOptimized(int* buffer)
    {
        bool remove1 = buffer[1] == buffer[0];
        bool remove2 = buffer[2] == buffer[1] || buffer[2] == buffer[0];
        bool remove3 = buffer[3] == buffer[2] || buffer[3] == buffer[1] || buffer[3] == buffer[0];

        if (remove1 && remove2 && remove3)
        {
            return new ReadOnlySpan<int>(buffer, 1);
        }

        if (remove1 && remove2)
        {
            buffer[1] = buffer[3];
            return new ReadOnlySpan<int>(buffer, 2);
        }

        if (remove1 && remove3)
        {
            buffer[1] = buffer[2];
            return new ReadOnlySpan<int>(buffer, 2);
        }

        if (remove2 && remove3)
        {
            return new ReadOnlySpan<int>(buffer, 2);
        }

        if (remove1)
        {
            buffer[1] = buffer[3];
            return new ReadOnlySpan<int>(buffer, 3);
        }

        if (remove2)
        {
            buffer[2] = buffer[3];
            return new ReadOnlySpan<int>(buffer, 3);
        }

        if (remove3)
        {
            return new ReadOnlySpan<int>(buffer, 3);
        }

        return new ReadOnlySpan<int>(buffer, 4);
    }