On 24 Aug 2014, at 01:23, Jens Alfke <j...@mooseyard.com> wrote:
>
>> On Aug 23, 2014, at 12:46 AM, Gerriet M. Denkmann <gerr...@mdenkmann.de>
>> wrote:
>
>> Works fine and is twice as fast.
>
> That approach is a bit naive, as it's going to spawn a huge number of
> [dispatched blocks] (something like O(n) of them, I think.) Also, once the
> array sizes start getting smaller than a cache line the CPU cores are going
> to be fighting over access to memory. That's probably why you got only a 2x
> speedup instead of 4x or 8x (depending on your CPU).
My computer has 8 Cpus (4 of which are called "logical", so the other 4 clearly
are "illogical", but they work quite fine nevertheless).
The actual implementation looks like:
quicksort( array, depth)
{
partition( array )
if ( depth < kLimit )
{
dispatch_apply(2...
{
quicksort( left or right side, depth + 1)
}
}
else
{
quicksort( left side, depth + 1)
quicksort( right side, depth + 1)
}
}
Depth starts with 0, so there are no more than 2^ kLimit dispatched blocks.
Messing around with kLimit shows:
It gets faster up to kLimit = 3 or 4. I.e. 8 or 16 dispatched blocks.
The improvements by increasing kLimit are getting smaller.
Increasing kLimit even further than 4 makes it not faster.
Even tried kLimit = 1000
Actual depths for an array of size 10 000 000 are about 54 ... 63; log2(10 mio)
= 23.2, but the partition is not as good as theoretically possible - instead of
halving the array, it partitions it into about 1/4 + 3/4 on average.
>
>> But how to do this in Swift?
>
> The same way as in Objective-C.
>
>> Just doing the same as in Obj-C does not work (nor is it expected, as there
>> is no documented thread-safeness of Swift arrays).
>
> Well, Swift arrays are passed by value, not by reference. What does your
> Swift implementation look like?
Using the "passed by value" thing in Swift, quicksort() would sort the array,
but the caller wouldn't notice; it's array would remain unchanged, which is not
really useful.
So I use:
func quicksortArray( inout array: [UInt32], lowerIndex: UInt, upperIndex: UInt,
depth: UInt )
1. problem:
Even with kLimit = 0 this gets really slow
Reason: the compiler notices that dispatch_apply is kind of dangerous and
always copies the arrays to be used.
And copies them back into the containing array afterwards.
So I changed it to:
quicksort( array, depth)
{
partition( array )
if ( depth < kLimit )
{
dispatch_apply(2...
{
quicksort( left or right side, depth + 1)
}
}
else
{
quicksortWithoutDispatch( left side, depth + 1) // same as
quicksort, but without any mention of dispatch_apply
quicksortWithoutDispatch( right side, depth + 1)
}
}
2. problem:
Sometimes (not always) one of the two arrays sorted inside of dispatch_apply is
not copied back.
3. problem
Sometimes (not always) random crashes
Which kind of proves that dispatch_apply with Swift is not a very good idea.
Or (more likely): my way of doing it is not very clever.
Kind regards,
Gerriet.
_______________________________________________
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
