Making a C# snippet faster

Question

I have a code in hand that I want to optimize further if it's possible.

I have searched and could not found any further methods to optimize it.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace EditorPlayer
{
    internal static class Program
    {
        [MethodImpl(MethodImplOptions.AggressiveOptimization)]
        public unsafe static void UnsafeQuickSort(int[] data)
        {
            fixed(int* pData = data)
            {
                UnsafeQuickSortRecursive(pData, 0, data.Length - 1);
            }

        }
        [MethodImpl(MethodImplOptions.AggressiveOptimization | MethodImplOptions.AggressiveInlining)]
        private unsafe static void UnsafeQuickSortRecursive(int* data, int left, int right)
        {
            int i = left - 1;
            int j = right;

            while (true)
            {
                int d = data[left];
                do i++; while (data[i] < d);
                do j--; while (data[j] > d);

                if (i < j)
                {
                    int tmp = data[i];
                    data[i] = data[j];
                    data[j] = tmp;
                }
                else
                {
                    if (left < j) UnsafeQuickSortRecursive(data, left, j);
                    if (++j < right) UnsafeQuickSortRecursive(data, j, right);
                    return;
                }
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveOptimization)]
        internal static void Main(string[] args)
        {
            int[] array = new int[10000000];
            Random rnd = new Random();
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = rnd.Next(100000);
            }

            Stopwatch stopwatch = new Stopwatch();

            stopwatch.Start();
            UnsafeQuickSort(array);
            stopwatch.Stop();

            Console.WriteLine($"Time took: {stopwatch.Elapsed.TotalMilliseconds}");
            stopwatch.Restart();

            Console.ReadLine();
        }
    }
}

The code above has also a identical twin written in c++ but c++ gives much better results. I would usually expect the difference would be around %5-%20 but it's way more than that. It's nearly %240.

In my machine C++ takes 230 ms while C# takes 550. I am looking for further tips to reduce the C# execution time.

Can you give any headsup ?

Note: This is tested on .NET 7

For one thing, you're only calling the method once - which means you're including the JIT side of things. I would recommend using [BenchmarkDotNet](https://github.com/dotnet/BenchmarkDotNet) to run better benchmarks to start with. — Jon Skeet, May 02 '23 at 09:25
I wouldn't be surprised if `unsafe` prevents the runtime doing some optimisations — Alan Birtles, May 02 '23 at 09:37
More about performance: [True Unsafe Code Performance](https://stackoverflow.com/questions/5374815/true-unsafe-code-performance) — Luuk, May 02 '23 at 09:41
We can't see your C++ version. A standard mistake is that RAND_MAX is rather low in C++, the Random class has a range that is over 3 orders of magnitude larger. Sorting duplicates is always faster. — Hans Passant, May 02 '23 at 09:59

Guru Stron · Accepted Answer · 2023-05-04T15:30:31.513

Not an answer but few notes which may help:

Use proper benchmarking tools like BenchmarkDotNet. .NET runtime can have few quirks like multiple JITing which can affect measurements.
If target is a "one time" console application (i.e. some CLI tool and not a long-running process like web server) - consider deploying code using Native AOT (note that it has some limitation). For such use-cases it has huge performance benefits compared to using runtime-depended apps. For example my simple measurements on the topic.
As far as I know C# compiler (still) does not support tail recursive calls optimization so possibly it would be beneficial to switch to "looping" approach.
.NET 7 has some looping performance irregularities. Try explicitly setting DOTNET_TC_QuickJitForLoops to 0.

score 0 · Answer 2 · answered May 02 '23 at 20:00

That implementation of quicksort has a (at least one) bug, causing it to not sort the array. It almost sorts the array, but that's not good enough. The problem appears to be that int j = right; should have been int j = right + 1; (the +1 cancelling out the initial decrement that is done unconditionally in the do/while loop), but I do not guarantee that that completely fixes the code.

There is one very common optimization of quick sort that you have not included in the code, and I think you should have found it since it is so common: sorting small (sub)arrays using a specialized algorithm that is good for small arrays. Insertion sort is often mentioned, but another option is an Optimal Sorting Network for example.

These days it is becoming more and more popular to also use SIMD for quicksort, even in C#.

For the purpose of improving performance of some special cases that you did not test here, you could look into different pivot selection, and into detecting overly deep recursion and falling back to a different algorithm in that case.

Naturally, all of these techniques apply just as much to the C++ implementation, possibly more since C# does not have direct access to AVX-512 yet.

The code above has also a identical twin written in c++ but c++ gives much better results.

This is typical when running a .NET method only once.

Making a C# snippet faster

2 Answers2