Re: Swift and Threads

[Gerriet M. Denkmann]

> On 13 Sep 2016, at 15:20, Quincey Morris 
>  wrote:
> 
>> On Sep 13, 2016, at 00:57 , Gerriet M. Denkmann  wrote:
>> 
>> I was struggling to find a solution which is thread safe.
> 
> Your problem didn’t really need thread safety, though. There appeared to be 
> no data dependencies between the bitfield elements — each was written 
> independently and never read — so all you needed was atomicity to make sure 
> the underlying code didn’t trip over itself. Further, as you discovered, your 
> task was easily partitionable into *independent* data sections, so you didn’t 
> really need atomicity either, if your data storage was structured carefully.
> 
> But I’m assuming none of this is true for your real goal, unless your real 
> goal is solely to initialize a big array using multiple CPUs.

My real problem is a pet project: a sieve of Eratosthenes (Ἐρατοσθένης) to find 
all primes up to a certain number.
I use this to learn Swift, and to compare the performance of Swift to 
Objective-C.

So I have this huge bitfield (which different subclasses implement differently) 
and I have to mark certain items in a certain range as non-prime (= true or 1).

As the range to be marked changes as the algorithm proceeds, it makes no sense 
to have 8 sub-bitfields and give one each to a marking thread; at a later stage 
only the last sub-bitfield will need markings, and the algorithm would be again 
single threaded.

I indeed need no atomicity: all threads have their own data section, which do 
not overlap.

Everything works fine (in Swift as in Objective-C) with dispatch_apply, as long 
as the bitfield is malloced.
In case of bitfield: [Bool] the solution suggested by Stephen J. Butler will 
probably also work (I am just implementing it).


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

Re: Swift and Threads

[Gerriet M. Denkmann]

> On 13 Sep 2016, at 14:14, Stephen J. Butler  wrote:
> 
> This site suggests a version using withUnsafeMutableBufferPointer:
> 
> http://blog.human-friendly.com/swift-arrays-are-not-threadsafe
> 
> let nbrOfThreads = 8
> let step = 2
> let itemsPerThread = number * step
> let bitLimit = nbrOfThreads * itemsPerThread
> var bitfield = [Bool](count: bitLimit, repeatedValue: false)
> 
> let queue = dispatch_get_global_queue( DISPATCH_QUEUE_PRIORITY_HIGH, 0 );
> 
> bitfield.withUnsafeMutableBufferPointer { (inout bitfieldBuffer : 
> UnsafeMutableBufferPointer) -> () in
> dispatch_apply( Int(nbrOfThreads), queue ) { ( idx: size_t) -> Void in
> let startIndex = itemsPerThread * Int(idx)
> let endIndex = min( startIndex + itemsPerThread, bitLimit )
> if talk { print("Thread[\(idx)] does \(startIndex) ..< \(endIndex)") }
> 
> var currIndex = startIndex
> while( currIndex < endIndex )
> {
> bitfieldBuffer[currIndex] = true
> currIndex += step
> }
> }
> }

This is excellent: slightly faster than my original code, uses no additional 
memory and does not crash.
Exactly what I was looking for.

Thank your very, very much indeed!

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

Re: Swift and Threads

[Quincey Morris]

On Sep 12, 2016, at 23:52 , Gerriet M. Denkmann  wrote:
> 
> I tried a variation of my function. This does not crash (not even in Debug 
> builds), but takes twice the memory and is about four times slower:

I no longer understand what we’re doing here. Based on the code you’ve posted, 
it looks like you’re approaching a multithreaded optimization problem by 
microbenchmarking fake code, using implementation-dependent data structures 
whose characteristics are not governed by an API contract, and ignoring thread 
safety. How can that possibly lead to a design for your real code? What kind of 
advice (if any) are you seeking?

___

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

Re: Swift and Threads

[Alastair Houghton]

On 13 Sep 2016, at 05:29, Jens Alfke  wrote:
> 
> The Bool type is one byte in size.
> 
> C++ has a specialization for std::vector that makes it a true bit 
> array, but I’m not sure if Swift’s generic system is powerful enough to be 
> able to entirely switch out the implementation based on the parameter type.

Before anyone thinks it’s a good idea to copy that idea straight into Swift’s 
standard library, std::vector doesn’t behave quite the same as the other 
std::vector<> implementations, and the specialisation is widely regarded as a 
mistake.  It’d be a *really* good idea to avoid making similar mistakes in 
Swift.

(Also, there’s a strong argument for having a separate bit vector type, with 
set-like operations, support for sparse bit vectors and the like.)

Kind regards,

Alastair.

--
http://alastairs-place.net


___

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

Re: Swift and Threads

[Stephen J. Butler]

This site suggests a version using withUnsafeMutableBufferPointer:

http://blog.human-friendly.com/swift-arrays-are-not-threadsafe

let nbrOfThreads = 8
let step = 2
let itemsPerThread = number * step
let bitLimit = nbrOfThreads * itemsPerThread
var bitfield = [Bool](count: bitLimit, repeatedValue: false)

let queue = dispatch_get_global_queue( DISPATCH_QUEUE_PRIORITY_HIGH, 0 );

bitfield.withUnsafeMutableBufferPointer { (inout bitfieldBuffer :
UnsafeMutableBufferPointer) -> () in
dispatch_apply( Int(nbrOfThreads), queue ) { ( idx: size_t) -> Void in
let startIndex = itemsPerThread * Int(idx)
let endIndex = min( startIndex + itemsPerThread, bitLimit )
if talk { print("Thread[\(idx)] does \(startIndex) ..<
\(endIndex)") }

var currIndex = startIndex
while( currIndex < endIndex )
{
bitfieldBuffer[currIndex] = true
currIndex += step
}
}
}


On Tue, Sep 13, 2016 at 1:52 AM, Gerriet M. Denkmann 
wrote:

>
> > On 12 Sep 2016, at 22:49, Jens Alfke  wrote:
> >
> >
> >> On Sep 12, 2016, at 6:42 AM, Gerriet M. Denkmann 
> wrote:
> >>
> >> So: is the code ok and the compiler broken in Debug mode?
> >> Or is the code fundamentally wrong and that it works in Release is just
> a fluke?
>
> I tried a variation of my function. This does not crash (not even in Debug
> builds), but takes twice the memory and is about four times slower:
>
> func markAndTell_2( talk: Bool, number: Int) -> [Bool]
> {
> [...]
> let bitLimit = nbrOfThreads * itemsPerThread
> var bitfield = [Bool](count: bitLimit, repeatedValue: false)
>
> var outputSlice0: ArraySlice = []
> [...]
> var outputSlice7: ArraySlice = []
>
> let queue = dispatch_get_global_queue(
> DISPATCH_QUEUE_PRIORITY_HIGH, 0 );
> dispatch_apply( Int(nbrOfThreads), queue,
> { ( idx: size_t) -> Void in
>
> let startIndex = itemsPerThread * Int(idx)
> let endIndex = min( startIndex + itemsPerThread,
> bitLimit )
>
> var tempSlice: ArraySlice = bitfield[
> startIndex ..< endIndex ]
>
> var currIndex = startIndex
> while( currIndex < endIndex )
> {
> tempSlice[currIndex] = true
> currIndex += step
> }
>
> switch(idx)
> {
> case 0: outputSlice0 = tempSlice
> [...]
> case 7: outputSlice7 = tempSlice
> default: print("Thread[\(idx)] does not
> know where to put its slice")
> }
> }
> )
>
> bitfield = []
> bitfield += outputSlice0
> [...]
> bitfield += outputSlice7
>
> return bitfield
> }
>
> 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/
> stephen.butler%40gmail.com
>
> This email sent to stephen.but...@gmail.com
>
___

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

Re: Swift and Threads

[Gerriet M. Denkmann]

> On 12 Sep 2016, at 22:49, Jens Alfke  wrote:
> 
> 
>> On Sep 12, 2016, at 6:42 AM, Gerriet M. Denkmann  
>> wrote:
>> 
>> So: is the code ok and the compiler broken in Debug mode?
>> Or is the code fundamentally wrong and that it works in Release is just a 
>> fluke?

I tried a variation of my function. This does not crash (not even in Debug 
builds), but takes twice the memory and is about four times slower:

func markAndTell_2( talk: Bool, number: Int) -> [Bool]
{
[...]
let bitLimit = nbrOfThreads * itemsPerThread
var bitfield = [Bool](count: bitLimit, repeatedValue: false)

var outputSlice0: ArraySlice = []
[...]
var outputSlice7: ArraySlice = []

let queue = dispatch_get_global_queue( DISPATCH_QUEUE_PRIORITY_HIGH, 0 
);
dispatch_apply( Int(nbrOfThreads), queue,
{ ( idx: size_t) -> Void in

let startIndex = itemsPerThread * Int(idx)
let endIndex = min( startIndex + itemsPerThread, 
bitLimit )

var tempSlice: ArraySlice = bitfield[ startIndex 
..< endIndex ]

var currIndex = startIndex
while( currIndex < endIndex )
{
tempSlice[currIndex] = true  
currIndex += step
}

switch(idx)
{
case 0: outputSlice0 = tempSlice
[...]
case 7: outputSlice7 = tempSlice
default: print("Thread[\(idx)] does not know 
where to put its slice")
}   
}
)

bitfield = []
bitfield += outputSlice0
[...]
bitfield += outputSlice7

return bitfield
}

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