qsort_b in Swift


Gerriet M. Denkmann
 

I have an array:

var sortedArray = [UInt32]()
for _ in 0 ..< limit { sortedArray.append( arc4random() ) }
sortedArray.sort()

This works fine.

I would like to compare the efficiency of “sort” with “qsort_b”, but cannot figure out how to call it in Swift.
Any help would be greatly appreciated.

Gerriet.


Quincey Morris
 

On Sep 15, 2017, at 21:18 , Gerriet M. Denkmann <g@...> wrote:

I would like to compare the efficiency of “sort” with “qsort_b”, but cannot figure out how to call it in Swift.

Yikes, this is masochistic!

This is the prototype:

public func qsort_b(_ __base: UnsafeMutableRawPointer!, _ __nel: Int, _ __width: Int, _ __compar: @escaping (UnsafeRawPointer?, UnsafeRawPointer?) -> Int32)

So I think the code looks like this (syntax-checked in Xcode 9 but not tested):

var sortedArray = [UInt32]()
qsort_b (&sortedArray, sortedArray.count, MemoryLayout<UInt32>.stride) {
(aPtr, bPtr) -> Int32 in
guard let a = aPtr?.load (fromByteOffset: 0, as: UInt32.self) else { return 0 } // or otherwise handle a nil pointer
guard let b = bPtr?.load (fromByteOffset: 0, as: UInt32.self) else { return 0 } // or otherwise handle a nil pointer
return a > b ? 1 : a < b ? -1 : 0
}

The “&sortedArray” relies on the compiler auto-bridging to the UnsafeMutableRawPointer. I don’t know if there’s an easier way to get the UInt32 values from the closure parameters, but perhaps “load” is the right way. Also, I may have the comparison test in the return backwards.


Gerriet M. Denkmann
 

On 16 Sep 2017, at 14:52, Quincey Morris <quinceymorris@rivergatesoftware.com> wrote:

On Sep 15, 2017, at 21:18 , Gerriet M. Denkmann <g@mdenkmann.de> wrote:

So I think the code looks like this (syntax-checked in Xcode 9 but not tested):

var sortedArray = [UInt32]()
qsort_b (&sortedArray, sortedArray.count, MemoryLayout<UInt32>.stride) {
(aPtr, bPtr) -> Int32 in
guard let a = aPtr?.load (fromByteOffset: 0, as: UInt32.self) else { return 0 } // or otherwise handle a nil pointer
guard let b = bPtr?.load (fromByteOffset: 0, as: UInt32.self) else { return 0 } // or otherwise handle a nil pointer
return a > b ? 1 : a < b ? -1 : 0
}
I tried this in Xcode Version 8.3.3 (8E3004b) (Swift 3) and:

1. it works: thank you very much. I never would have figured this out from the documentation alone.

2. qsort_b is about 2.25 times slower than sort (tested with arrays of size 1 mio to 100 mio)..
I also tried a C version with a malloced sortedArray: about the same speed as Swift with qsort_b.

This is the first time I have seen Swift working swifter than Objective-C (and not by a small margin too!).
I am very impressed with the Swift sort.
It would be interesting to know what kind of optimisation magic Swift does here.


Kind regards,

Gerriet.


Quincey Morris
 

On Sep 16, 2017, at 20:40 , Gerriet M. Denkmann <g@...> wrote:

It would be interesting to know what kind of optimisation magic Swift does here.

My guess is that this is not a compiler-related difference, but rather the effect of different algorithms. The performance depends on the initial ordering of the array. My recollection of this subject is hazy, but I think qsort is helped by an array that is already partially ordered, which yours is not. (This is not necessarily an artificial condition. For example, if you add 100 elements to the end of an array of 1000 elements that was already sorted, you will end up with a very non-random array to be re-sorted.)

Qsort is also limited to one algorithm. It’s not impossible that the Swift array sort function does a quick analysis of the array and chooses an algorithm that looks like it will work better than others.

So, yes, it’s very nice to know that Swift’s default sort is something that can be trusted.


Gerriet M. Denkmann
 

On 17 Sep 2017, at 13:05, Quincey Morris <quinceymorris@rivergatesoftware.com> wrote:

On Sep 16, 2017, at 20:40 , Gerriet M. Denkmann <g@mdenkmann.de> wrote:

It would be interesting to know what kind of optimisation magic Swift does here.
My guess is that this is not a compiler-related difference, but rather the effect of different algorithms. The performance depends on the initial ordering of the array. My recollection of this subject is hazy, but I think qsort is helped by an array that is already partially ordered, which yours is not.
From the man page:
The mergesort function is […] intended for sorting data with pre-existing order.
Normally, qsort() is faster than mergesort() which is faster than heapsort().
Memory availability and pre-existing order in the data can make this untrue.


I tried both Swift sort and qsort with different data (10,000,000): random, sorted, and sorted backwards:

Swift sort
random 7.25 n log(n) nsec
back sorted 1.45 n log(n) nsec
sorted 1.35 n log(n) nsec

qsort_b:
random 19 n log(n) nsec
back sorted 5.25 n log(n) nsec
sorted 0.83 n log(n) nsec


So in the dependence on the sortedness of the data the two algorithms differs quite substantially.


Kind regards,

Gerriet.


 



On Sep 16, 2017, at 8:40 PM, Gerriet M. Denkmann <g@...> wrote:

This is the first time I have seen Swift working swifter than Objective-C (and not by a small margin too!).
I am very impressed with the Swift sort.
It would be interesting to know what kind of optimisation magic Swift does here.

The compiler probably inlines the call to the comparison function, as opposed to qsort_b which has (of course) already been compiled so it has to make a regular function call. That makes a big difference when the function is as cheap as comparing two integers.

Similarly, in the Swift code the size of the array elements is a compile-time constant, whereas to qsort_b it's a variable. That results in more efficient code.

—Jens