Thread-safe collections

Hello all,

I just looked around for thread-safe collections, and found nothing that looks like a shared dictionary.  The squeak-dev archives contain the obligatory newbie posts (wanting all collections to be thread safe) and the expected replies, some of which are overly dismissive of the idea.  Something that protects things like #at:ifAbsentPut: and friends is _really_ useful.  Am I missing an existing implementation?

Bill


_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

2009/10/23 Schwab,Wilhelm K <[hidden email]>:
> Hello all,
>
> I just looked around for thread-safe collections, and found nothing that looks like a shared dictionary.  The squeak-dev archives contain the obligatory newbie posts (wanting all collections to be thread safe) and the expected replies, some of which are overly dismissive of the idea.  Something that protects things like #at:ifAbsentPut: and friends is _really_ useful.  Am I missing an existing implementation?
>

Imo, there's only one shared collection which is useful - shared queue. :)
If you need more kinds of thread-safe collections, it probably
indicating that the concurrent code (or model) which you designed is
in pretty bad shape.

Just compare two following snippets:

1 to: 100 do: [:i |  collection threadSafeAt: i put: something].

and:

semaphore critical: [ 1 to: 100 do: [:i |  collection at: i put: something] ].

What you think, which one is better?


> Bill
>
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>



--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

The Symbol table is another very useful collection that should be
thread-safe.  From my experience in VW, getting that to be both fast and
thread-safe can be a bit tricky.  For example, the debugger should not
create symbols while debugging because you could be debugging the
critical section of the symbol table internment...

Igor Stasenko wrote:
_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

A thread-safe collection package could have non-blocking implementations of most methods. Writing an object reference into an array should be an atomic operation and I assume most collections use Arrays for their implementation.

Gulik.

--
http://gulik.pbwiki.com/

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Sig,

One can always construct examples in which protecting the entire loop is the better option.  That's not the scenario of interest.  Just as shared queues are useful, shared sets and dictionaries have value for sporadic access scenarios.  Doing it your way, everyone writes their own incompletely protected (read buggy/dangerous) ad-hoc implementations of these common collections.

I favor having solid implementations that are complete and as correct as we can get them, leaving people to optimize as you suggest when it makes sense to do so.

Bill


-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Igor Stasenko
Sent: Thursday, October 22, 2009 5:23 PM
To: [hidden email]
Subject: Re: [Pharo-project] Thread-safe collections

2009/10/23 Schwab,Wilhelm K <[hidden email]>:
> Hello all,
>
> I just looked around for thread-safe collections, and found nothing that looks like a shared dictionary.  The squeak-dev archives contain the obligatory newbie posts (wanting all collections to be thread safe) and the expected replies, some of which are overly dismissive of the idea.  Something that protects things like #at:ifAbsentPut: and friends is _really_ useful.  Am I missing an existing implementation?
>

Imo, there's only one shared collection which is useful - shared queue. :) If you need more kinds of thread-safe collections, it probably indicating that the concurrent code (or model) which you designed is in pretty bad shape.

Just compare two following snippets:

1 to: 100 do: [:i |  collection threadSafeAt: i put: something].

and:

semaphore critical: [ 1 to: 100 do: [:i |  collection at: i put: something] ].

What you think, which one is better?


> Bill
>
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>



--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

2009/10/23 Michael van der Gulik <[hidden email]>: well, #basicAt:put: using a primitive, so its already atomic
operation, given than VM doesn't running the code in
multiple native threads.

So, there is no point in changing something for Arrays, and therefore
no point to invent a non-blocking.. its already meets our demands.

Lets take a look at collections which doing something more
sophisticated at #at:put:, like OrderedCollection or Dictionary.
What kind of non-blocking we can introduce here?
Dictionary may need to rehash the array due to growth..
OrderedCollection may also need to grow its storage (if you using
#add: ) and such operations is far from being atomic. So, what kind of
non-blocking you can invent here?
The only choice is to use blocking, and hence we are getting back to
example above.. what is more efficient:

1 to: 100 do: [:i |  collection threadSafeAt: i put: something].

or:

semaphore critical: [ 1 to: 100 do: [:i |  collection at: i put: something] ].



--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

2009/10/23 Schwab,Wilhelm K <[hidden email]>:
> Sig,
>
> One can always construct examples in which protecting the entire loop is the better option.  That's not the scenario of interest.  Just as shared queues are useful, shared sets and dictionaries have value for sporadic access scenarios.  Doing it your way, everyone writes their own incompletely protected (read buggy/dangerous) ad-hoc implementations of these common collections.
>
> I favor having solid implementations that are complete and as correct as we can get them, leaving people to optimize as you suggest when it makes sense to do so.
>
> Bill
>
>
Here is what you need. And you have a thread-safe collections for
free.. and not only collections, you can use it for anything you want
:)


'From Squeak3.10.2 of ''5 June 2008'' [latest update: #7179] on 23
October 2009 at 3:41:44 am'!
Object subclass: #SharedResource
        instanceVariableNames: 'resource lock'
        classVariableNames: ''
        poolDictionaries: ''
        category: 'CorruptVM-tests'!

!SharedResource methodsFor: 'as yet unclassified' stamp: 'sig 10/23/2009 03:36'!
doesNotUnderstand: aMessage
        | result |
        lock critical: [
                result := aMessage sentTo: resource
        ].

        ^ result! !

!SharedResource methodsFor: 'as yet unclassified' stamp: 'sig 10/23/2009 03:36'!
initialize
        lock := Semaphore forMutualExclusion ! !

!SharedResource methodsFor: 'as yet unclassified' stamp: 'sig 10/23/2009 03:35'!
resource: anObject
        resource := anObject! !

"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!

SharedResource class
        instanceVariableNames: ''!

!SharedResource class methodsFor: 'as yet unclassified' stamp: 'sig
10/23/2009 03:37'!
on: anObject
        ^ self new resource: anObject! !


------------

i know its a brain-dead way.. but do you really think that you can get
something better with implementing collections
without ending up with fact, that almost every method will require a
semaphore to protect from race condition? :)

--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Checkmate; I can't think of any way of implementing a thread-safe growing/shrinking collection using only available atomic operations.

There might be a way. I'll sleep on it.

Gulik.

--
http://gulik.pbwiki.com/

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Michael van der Gulik wrote:
> A thread-safe collection package could have non-blocking implementations
> of most methods. Writing an object reference into an array should be an
> atomic operation and I assume most collections use Arrays for their
> implementation.

Write to an array is atomic, but the sequence of

   1. Look in array to see if entry is used, and if unused

   2. Store into array

is not atomic, and hashed collections like Set, Dictionary, etc. require
this sequence, usually with additional non-atomic operations on write,
and sometimes on read.

It's difficult to make a collection that is non-blocking and thread-safe
for writing, except for collections that are inherently safe, like Array.

A few months ago I did implement a hashed collection (essentially a
variant of IdentityDictionary) that requires semaphore access for write,
but not for read. This increases the code complexity somewhat, and the
code fragility quite a bit. One code change by someone who does not
understand all of the invariants that must be observed, and it's no
longer thread-safe. The collection is believed to be thread-safe, but
testing all of the code branches is very difficult, so it has not been
thoroughly tested. (Actually, I know of one design bug that I need to
fix, but I believe I know how to fix it.) This collection is rather
special-purpose; we had a particular requirement for being able to read
it even when debugging the process that was writing to it, otherwise I
would not have bothered.

It's probably possible to write a hashed collection that is thread-safe
and semaphore-free for both read and write, but unless there's a very
specific requirement for that it's probably simpler, faster, and more
reliable to just use a semaphore.

Regards,

-Martin

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

2009/10/23 Martin McClure <[hidden email]>:
>
> It's probably possible to write a hashed collection that is thread-safe
> and semaphore-free for both read and write, but unless there's a very
> specific requirement for that it's probably simpler, faster, and more
> reliable to just use a semaphore.
>
+1.
If you traveling into the field of concurrency, you have to change the mindset.
You should pick different abstractions for that. And collections is
one which you should leave to grow in single-threaded woods.
Or.. of course.. you can attempt to make them thread-safe.. But it
will be clumpsy , rigid and very error prone.

> Regards,
>
> -Martin
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>



--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Sig,

You appear to be assuming that all such access is in (big) loops.  That's not always the case; sometimes, a little #at:ifAbsentPut: here or there can conflict in ugly ways, and something that gets the blocking right is non-trivial and very useful.

Bill



-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Igor Stasenko
Sent: Thursday, October 22, 2009 7:38 PM
To: [hidden email]
Subject: Re: [Pharo-project] Thread-safe collections

2009/10/23 Michael van der Gulik <[hidden email]>: well, #basicAt:put: using a primitive, so its already atomic operation, given than VM doesn't running the code in multiple native threads.

So, there is no point in changing something for Arrays, and therefore no point to invent a non-blocking.. its already meets our demands.

Lets take a look at collections which doing something more sophisticated at #at:put:, like OrderedCollection or Dictionary.
What kind of non-blocking we can introduce here?
Dictionary may need to rehash the array due to growth..
OrderedCollection may also need to grow its storage (if you using
#add: ) and such operations is far from being atomic. So, what kind of non-blocking you can invent here?
The only choice is to use blocking, and hence we are getting back to example above.. what is more efficient:

1 to: 100 do: [:i |  collection threadSafeAt: i put: something].

or:

semaphore critical: [ 1 to: 100 do: [:i |  collection at: i put: something] ].



--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

 
Sig,

What about things like managing connections to remote hosts?  Do I have a socket going over there?  No??  Let's make one.  Sounds like a great job for a shared dictionary.

Bill



-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Igor Stasenko
Sent: Thursday, October 22, 2009 8:34 PM
To: [hidden email]
Subject: Re: [Pharo-project] Thread-safe collections

2009/10/23 Martin McClure <[hidden email]>:
>
> It's probably possible to write a hashed collection that is
> thread-safe and semaphore-free for both read and write, but unless
> there's a very specific requirement for that it's probably simpler,
> faster, and more reliable to just use a semaphore.
>
+1.
If you traveling into the field of concurrency, you have to change the mindset.
You should pick different abstractions for that. And collections is one which you should leave to grow in single-threaded woods.
Or.. of course.. you can attempt to make them thread-safe.. But it will be clumpsy , rigid and very error prone.

> Regards,
>
> -Martin
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>



--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

2009/10/23 Schwab,Wilhelm K <[hidden email]>:
>
> Sig,
>
> What about things like managing connections to remote hosts?  Do I have a socket going over there?  No??  Let's make one.  Sounds like a great job for a shared dictionary.
>

it depends on your model, what you need to manage and how.
If your goal is to communicate with remote hosts, where are sockets
come from is not really relevant to you.
Mainly you just getting a reference to object, which provides some
facilities to you.
How that object manages a collection of sockets, or does it manages
them at all is not your concern..
And i wouldn't say that having a thread-safe collections is a big win
for managing connections comparing to other possible implementations
which not require any thread-safety for collections.



--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Sig,

It appears we are not going to agree.

Bill


-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Igor Stasenko
Sent: Thursday, October 22, 2009 10:38 PM
To: [hidden email]
Subject: Re: [Pharo-project] Thread-safe collections

2009/10/23 Schwab,Wilhelm K <[hidden email]>:
>
> Sig,
>
> What about things like managing connections to remote hosts?  Do I have a socket going over there?  No??  Let's make one.  Sounds like a great job for a shared dictionary.
>

it depends on your model, what you need to manage and how.
If your goal is to communicate with remote hosts, where are sockets come from is not really relevant to you.
Mainly you just getting a reference to object, which provides some facilities to you.
How that object manages a collection of sockets, or does it manages them at all is not your concern..
And i wouldn't say that having a thread-safe collections is a big win for managing connections comparing to other possible implementations which not require any thread-safety for collections.



--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

2009/10/23 Schwab,Wilhelm K <[hidden email]>:
> Sig,
>
> It appears we are not going to agree.
>
It appears not.

Thread-safe collections is too good to be true solutions for
concurrency. Its too simplistic approach and in a long run , fairly
ineffective.
In any real-world application the basic building blocks is not generic
collections, but different objects which composing your domain model.
Some of your domain objects could use collections, some of them not.
But you can't predict how do they using them , and in what way to
state that putting thread-safe collection in use will make the whole
model thread safe.
And that's why i think thread-safety should be introduced at higher
levels of abstractions.

> Bill
>

--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Sig,

That's fine as far as it goes, but the building blocks are useful both as concrete components and as examples of how to protect something.

Bill



-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Igor Stasenko
Sent: Thursday, October 22, 2009 11:01 PM
To: [hidden email]
Subject: Re: [Pharo-project] Thread-safe collections

2009/10/23 Schwab,Wilhelm K <[hidden email]>:
> Sig,
>
> It appears we are not going to agree.
>
It appears not.

Thread-safe collections is too good to be true solutions for concurrency. Its too simplistic approach and in a long run , fairly ineffective.
In any real-world application the basic building blocks is not generic collections, but different objects which composing your domain model.
Some of your domain objects could use collections, some of them not.
But you can't predict how do they using them , and in what way to state that putting thread-safe collection in use will make the whole model thread safe.
And that's why i think thread-safety should be introduced at higher levels of abstractions.

> Bill
>

--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

2009/10/23 Schwab,Wilhelm K <[hidden email]>:
> Sig,
>
> That's fine as far as it goes, but the building blocks are useful both as concrete components and as examples of how to protect something.
>
yeah, and given these examples one could easily write a thread-unsafe
application.
But then, when it doesn't working as expected, he scratching his head
and saying: hey, what's going on! I'm using a thread-safe library, why
the heck my application not thread-safe?!?!

And instead of start writing a concurrent, thread-safe code, he
chooses to write another library, which will be 100% thread-safe and
then he can be 'assured' that his thread-unsafe code will magically
become thread-safe because he using a 'right' tool :)



--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Like I said, we're pretty clearly not going to agree.  I see no advantage to witholding a good example that is itself useful only because a newbie might extrapolate too far; I see lost opporunity and buggy ad hoc implementations resulting from not providing the solid example.





-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Igor Stasenko
Sent: Thursday, October 22, 2009 11:35 PM
To: [hidden email]
Subject: Re: [Pharo-project] Thread-safe collections

2009/10/23 Schwab,Wilhelm K <[hidden email]>:
> Sig,
>
> That's fine as far as it goes, but the building blocks are useful both as concrete components and as examples of how to protect something.
>
yeah, and given these examples one could easily write a thread-unsafe application.
But then, when it doesn't working as expected, he scratching his head and saying: hey, what's going on! I'm using a thread-safe library, why the heck my application not thread-safe?!?!

And instead of start writing a concurrent, thread-safe code, he chooses to write another library, which will be 100% thread-safe and then he can be 'assured' that his thread-unsafe code will magically become thread-safe because he using a 'right' tool :)



--
Best regards,
Igor Stasenko AKA sig.

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

I would really like to see some packages getting implementing around  
the idea of a couple of robust and
well tested thread safe collections.

Stef

On Oct 23, 2009, at 2:16 AM, Schwab,Wilhelm K wrote:


_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Stef,

With no disrespect to Sig's opinions, I'm glad to hear that.  I very quickly cobbled together a class called SharedLookupTable, and have no problems making it (suitably debugged) available.

Now it's time for me to kick your ass a little, to coin a phrase :)  Monticello is pretty good at what it does, but I sense the things it does not do interfering with good decision making.  The class ended up in my Dolphin compatibility package, in part because it belongs there, though it really should be separate so I can easily release it and people would be able to get it w/o having to accept other ideas they might not want.  But it went in the compatiblity package so I would not have to mess around with another package.  Saving them is a pain; loading them into a new image is a pain.

Saving: the interface works well once understood, and the features it offers should never go away.  However, either by script or by multiple selection, it would be nice to provide a comment to be applied to everything to be saved "now" vs. having to be prompted for it, then have the list scroll, then have to click away another window.  Do that 30 times and it starts to get old.

Loading: I spent a chunk of yesterday trying to build an RC1 image.  Doing so revealed that my script-loader for script-loader does not validate package names.  I had one build attempt come to a halt over case-sensitivity; I do not mind that.  What I mind is that the particular case mix in question was more or less forced on me by a typo of mine.  If MC were better about offering choices when they apply, I might not have typed it that way.

I realize that Gofer is coming, and it might fix a lot of this.  The ideas above are probably not new, but I list them just in case.

Bill



-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Stéphane Ducasse
Sent: Friday, October 23, 2009 2:46 AM
To: [hidden email]
Subject: Re: [Pharo-project] Thread-safe collections

I would really like to see some packages getting implementing around the idea of a couple of robust and well tested thread safe collections.

Stef

On Oct 23, 2009, at 2:16 AM, Schwab,Wilhelm K wrote:


_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project