Re: Swift Threads
Re: Swift Threads
- Subject: Re: Swift Threads
- From: "Gerriet M. Denkmann" <email@hidden>
- Date: Sun, 24 Aug 2014 12:44:19 +0700
On 24 Aug 2014, at 01:23, Jens Alfke <email@hidden> wrote:
>
>> On Aug 23, 2014, at 12:46 AM, Gerriet M. Denkmann <email@hidden> 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 (email@hidden)
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:
This email sent to email@hidden
| References: | |
| | >Swift Threads (From: "Gerriet M. Denkmann" <email@hidden>) |