1

(Sorry if this is the wrong forum.)

I have implemented a generic form of

https://raw.githubusercontent.com/raywenderlich/swift-algorithm-club/master/Radix%20Sort/radixSort.swift as follows:

https://gist.github.com/sbromberger/cfb0081263e1fe6e4f7b5ba4efc83a31

I then decided it might be nice if this were an extended method on Array itself, so I rewrote it like this:

https://gist.github.com/sbromberger/9d98948b50b6733b08dd0e19b1f31e60

I was surprised at the timing:

var arr1 = (1...5000).map{_ in arc4random()}
var arr2 = arr1
radixSort(arr1) function time 76.472963 ms
arr1 == arr2 = false
arr2.radixSort() method time 180.216068 ms
arr1 == arr2 = true

Could someone help me figure out why the performance is so poor when the code is a method as opposed to a function?

(Also, as an aside, radix sort beats Array.sort() on arrays of integers larger than about 3k elements or so.)

2

Compiled with -O and timing using Foundation.Date, I see both versions taking about 2ms, plus or minus 0.3ms. Without -O they both take about 65ms on my machine. So I think whatever you're seeing is just a coincidence.

3

Thanks. It's repeatable through a whole slew of random arrays of varying size, though. It's probably an optimization thing. I really should remember to -O when I do timing tests.

Nope: even optimized on my machine, I'm getting

radixSort(arr1) function time 3.137651 ms
arr2.radixSort() method time 7.412426 ms

Also, I'm using DispatchTime.now(). Is that the wrong way to do it?

4

I think you'll have to attach your whole testing setup, self-contained, to see what's different between your version and mine. (In particular, the second gist you have above had a number of minor bugs, at least yesterday.)

5

Thanks. I fixed the bugs (comes from trying to avoid another copy/paste). As far as showing the setup, I don't know how to do that, but my profiling today is giving me completely different results from yesterday's tests (that showed that radixSort(&arr1) was faster than arr2.sort(). I can't explain this change.