Re: qsort_b in Swift


Gerriet M. Denkmann
 

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.

Join cocoa@apple-dev.groups.io to automatically receive all group messages.