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.

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

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

On Sep 15, 2017, at 21:18 , Gerriet M. Denkmann <g@...> 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.

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

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

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.

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.