How to properly cancel an in-place sort without sacrificing much performance in newer dotnet version-CodePudding

In the past I used to start a new thread for sorting, and abort it when the user clicked 'Cancel', and it worked flawlessly on virtually all .NET Framework versions. But since the introduction of .NET Core and .NET 5 , a call to Thread.Abort() throws PlatformNotSupportedException.

So it is time now to find a better way to do that. The main problem is that Array.Sort() and List.Sort() methods do not acccept a CancellationToken. I could go by sending my own Comparison delegate and call cancellationToken.ThrowIfCancellationRequested(); inside but that would have a significant performance impact.

How to properly cancel an in-place sort without sacrificing much performance in newer dotnet versions?

Attached a snippet that used to work on .NET Framework:

byte[] arr = new byte[1024 * 1024 * 1024];

Thread thread = new Thread(() => Array.Sort(arr));
thread.IsBackground = true;
thread.Start();

if (!thread.Join(1000))
    thread.Abort();

CodePudding user response：

You could use the Comparison<T> below, that checks the CancellationToken once every 10,000 comparisons. This ratio amounts to checking more than once per millisecond in my machine. So the delay should not be noticeable.

public static Comparison<T> CreateCancelableComparison<T>(
    CancellationToken cancellationToken)
{
    int counter = 0;
    return (T x, T y) =>
    {
        if (counter   > 10_000) // Check the token every X comparisons
        {
            counter = 0;
            cancellationToken.ThrowIfCancellationRequested();
        }
        return Comparer<T>.Default.Compare(x, y);
    };
}

Usage example:

Array.Sort(arr, CreateCancelableComparison<byte>(token));

According to my measurements¹, passing a Comparison<T> argument to the Array.Sort method makes the sorting at least 2 times slower. For example this: Array.Sort(arr, (x, y) => x - y); takes almost double the time than Array.Sort(arr);. Passing an IComparer<T> is even worse. Sorting with the CreateCancelableComparison is about 2,5 slower. I don't know of any solution to this problem, other than reimplementing the Array.Sort functionality from scratch.

¹ _{Console application, .NET 7, Release mode}

CodePudding user response：

I think if you just test a boolean value before comparison, JIT could optimize the situation with a single instruction.

class ByteComparer : IComparer<byte>
{
    private bool _cancel;

    public int Compare(byte x, byte y)
    {
        if (!_cancel) return x - y;
        throw new TaskCanceledException();
    }
    
    public void Cancel() => _cancel = true;
}

var arr = new byte[1024 * 1024 * 100];
var comparer = new ByteComparer();
Task.Run(() => Array.Sort(arr, comparer));
...
comparer.Cancel();