Swift: How to interrupt a sort routine

Question

I want to give users the ability to stop a sorting routine if it takes too long.

I tried to use DispatchWorkItem.cancel. However, this does not actually stop processes that have already started.

let myArray = [String]() // potentially 230M elements!
...
workItem = DispatchWorkItem {
    let result = myArray.sorted()
    DispatchQueue.main.async {
    print ("done")
    }
}

// if process is too long, user clicks "Cancel" => workItem.cancel() // does not stop sort

How can I kill the workItem's thread?

I don't have access to the sorted routine, therefore I cannot insert tests to check if current thread is in "cancelled" status...

Answer 1

As you have deduced, one simply cannot kill a work item without periodically checking isCancelled and manually performing an early exit if it is set.

There are two options:

1. You can used sorted(by:), test for isCancelled there, throwing an error if it is canceled. That achieves the desired early exit.

   That might look like:

   func cancellableSort() -> DispatchWorkItem {
       var item: DispatchWorkItem!
       item = DispatchWorkItem() {
           let unsortedArray = (0..<10_000_000).shuffled()
           let sortedArray = try? unsortedArray.sorted { (obj1, obj2) -> Bool in
               if item.isCancelled {
                   throw SortError.cancelled
               }
               return obj1 < obj2
           }
           // do something with your sorted array
           item = nil
       }
       DispatchQueue.global().async(execute: item)
       return item
   }
   

   Where

   enum SortError: Error {
       case cancelled
   }
   

   Be forewarned that even in release builds, this can have a dramatic impact on performance. So you might want to benchmark this.

2. You could just write your own sort routine, inserting your own test of isCancelled inside the algorithm. This gives you more control over where precisely you perform the test (i.e., you might not want to do it for every comparison, but rather at some higher level loop within the algorithm, thereby minimizing the performance impact). And given the number of records, this gives you a chance to pick an algorithm best suited for your data set.

Obviously, when benchmarking these alternatives, make sure you test optimized/release builds so that your results are not skewed by your build settings.

As an aside, you might considering using Operation, too, as its handling of cancelation is more elegant, IMHO. Plus you can have a dedicated object for the sort operation, which is cleaner.