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

Question

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.

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();

Maybe it would be advisable to share your code of your alternative, because I don’t see this statement to be true `…but that would have a significant performance impact.` — Rand Random, Nov 12 '22 at 01:50
@RandRandom the stack would contain an additional comparison for every single item in the array, every single time that the items are compared... which is multiple times in a sort depending on the sort algorithm. So I feel like there's a pretty good case to assume a performance impact. — Joe_DM, Nov 12 '22 at 01:54
I'm wondering if there is some way to emit IL directly into the top of the stack for the running thread as to make it throw an exception and unwind the stack on its own. If I find something I'll let you know but it seems like a fun challenge. — Joe_DM, Nov 12 '22 at 01:55
If you are already using a `Comparison` then you can simply make it throw if you need to cancel, as Theodor suggested. If you are not using a `Comparison` then your sorting is trivial, and no matter how many items you are sorting there is only so many items you can fit in memory, therefore your sorting should already be so fast that the user should not have enough time to even see the "please wait" dialog, let alone move the mouse over the [Cancel] button and click it. So, something is fishy here. — Mike Nakis, Nov 20 '22 at 14:41
I am pretty sure you are not just sorting bytes. So, precisely what is it that you are sorting, if I may ask? — Mike Nakis, Nov 20 '22 at 14:41

score 1 · Answer 1 · answered Nov 13 '22 at 12:02

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}

shingo · Answer 2 · 2022-11-12T07:43:18.533

-1

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();

edited Nov 12 '22 at 07:43

answered Nov 12 '22 at 03:57

shingo

18,436
5
23
42

The OP has asked for observing a `CancellationToken`. The `public bool cancel;` field is not even [`volatile`](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/volatile). Btw public fields in C# are capitalized in PascalCase, and in general they should be avoided (they should be properties instead of fields). – Theodor Zoulias Nov 12 '22 at 07:25
I have made this `cancel` to private and added a `Cancel` method. I don't think the OP asked is in particular to `CancellationToken`, the question is _"How to properly cancel an in-place sort without sacrificing much performance in newer dotnet versions?"_, so performance is more important. And the sort method is just executed in a single thread so the `volatile` keyword is not help. – shingo Nov 12 '22 at 07:46
The `Sort` method is executed on a single thread, but the `_cancel` is turned to `true` from another thread. How confident are you that the change will be observed [in a timely manner](https://learn.microsoft.com/en-us/archive/msdn-magazine/2012/december/csharp-the-csharp-memory-model-in-theory-and-practice) by the thread that does the sorting, on all CPU architectures supported by .NET? Quote: *"[...] the compiler might replace repeated reads of a field with a single read."* – Theodor Zoulias Nov 12 '22 at 08:15
I'm afraid I can't gotcha. I've learnt from the article that volatile preserves read-write order in a thread, but there is only one variable in my code, I don't understand why I need worry about the order. Could you please clarify on this? What problem I will face if I don't mark it as volatile? – shingo Nov 12 '22 at 09:36
Shingo I am not an expert in lock-free multithreading. The `CancellationTokenSource` stores its state in a `volatile` field ([source code](https://github.com/dotnet/runtime/blob/52eed7dc3912594631dfecca56da3057bec52ba6/src/libraries/System.Private.CoreLib/src/System/Threading/CancellationTokenSource.cs#L38)) and your `ByteComparer` doesn't. So I don't trust your code. Eric Lippert would probably [not trust](https://stackoverflow.com/questions/2528969/lock-free-multi-threading-is-for-real-threading-experts/2529773#2529773) it either. – Theodor Zoulias Nov 12 '22 at 10:24

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

2 Answers2