www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Sharing Ref Counted Containers

reply dsimcha <dsimcha yahoo.com> writes:
I noticed that std.container.Array uses completely unsynchronized reference
counting.  Does that mean that it's basically impossible to share it across
threads without introducing race conditions into the reference counting code,
even if you synchronize on other updates?

Are there any plans to make Array and future ref counted containers shareable?
 If not (I'm not saying that making them shareable is necessarily worth
doing), I think there should be a large warning against casting these to
shared.  Usually, when you cast a data structure to shared, you can write
working code as long as you properly synchronize all updates to the data
structure.  However, because updates to the ref count field are happening
under the hood in an invisible fashion, no matter how properly synchronized
updates to the contents of the ref-counted container are, you basically can't
properly synchronize updates to the ref count field.
Aug 04 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 08/04/2010 08:02 PM, dsimcha wrote:
 I noticed that std.container.Array uses completely unsynchronized reference
 counting.  Does that mean that it's basically impossible to share it across
 threads without introducing race conditions into the reference counting code,
 even if you synchronize on other updates?

 Are there any plans to make Array and future ref counted containers shareable?
   If not (I'm not saying that making them shareable is necessarily worth
 doing), I think there should be a large warning against casting these to
 shared.  Usually, when you cast a data structure to shared, you can write
 working code as long as you properly synchronize all updates to the data
 structure.  However, because updates to the ref count field are happening
 under the hood in an invisible fashion, no matter how properly synchronized
 updates to the contents of the ref-counted container are, you basically can't
 properly synchronize updates to the ref count field.

There are no plans to make Array a shared type. A shared container would have a very different interface to begin with. Sharing Array objects is not recommended. Andrei
Aug 04 2010
parent reply Jonathan M Davis <jmdavisprog gmail.com> writes:
On Wednesday 04 August 2010 18:20:36 Andrei Alexandrescu wrote:
 On 08/04/2010 08:02 PM, dsimcha wrote:
 I noticed that std.container.Array uses completely unsynchronized
 reference counting.  Does that mean that it's basically impossible to
 share it across threads without introducing race conditions into the
 reference counting code, even if you synchronize on other updates?
 
 Are there any plans to make Array and future ref counted containers
 shareable?
 
   If not (I'm not saying that making them shareable is necessarily worth
 
 doing), I think there should be a large warning against casting these to
 shared.  Usually, when you cast a data structure to shared, you can write
 working code as long as you properly synchronize all updates to the data
 structure.  However, because updates to the ref count field are happening
 under the hood in an invisible fashion, no matter how properly
 synchronized updates to the contents of the ref-counted container are,
 you basically can't properly synchronize updates to the ref count field.

There are no plans to make Array a shared type. A shared container would have a very different interface to begin with. Sharing Array objects is not recommended. Andrei

I would have thought that sharing pretty much _any_ type more complex than a primitive type without it being synchronized would be a bad idea. And since the standard containers obviously aren't going to be synchronized, I would expect you to have to wrap them in a class or struct which is synchronized. - Jonathan M Davis
Aug 04 2010
next sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Jonathan M Davis (jmdavisprog gmail.com)'s article
 On Wednesday 04 August 2010 18:20:36 Andrei Alexandrescu wrote:
 On 08/04/2010 08:02 PM, dsimcha wrote:
 I noticed that std.container.Array uses completely unsynchronized
 reference counting.  Does that mean that it's basically impossible to
 share it across threads without introducing race conditions into the
 reference counting code, even if you synchronize on other updates?

 Are there any plans to make Array and future ref counted containers
 shareable?

   If not (I'm not saying that making them shareable is necessarily worth

 doing), I think there should be a large warning against casting these to
 shared.  Usually, when you cast a data structure to shared, you can write
 working code as long as you properly synchronize all updates to the data
 structure.  However, because updates to the ref count field are happening
 under the hood in an invisible fashion, no matter how properly
 synchronized updates to the contents of the ref-counted container are,
 you basically can't properly synchronize updates to the ref count field.

There are no plans to make Array a shared type. A shared container would have a very different interface to begin with. Sharing Array objects is not recommended. Andrei

primitive type without it being synchronized would be a bad idea. And since the standard containers obviously aren't going to be synchronized, I would expect you to have to wrap them in a class or struct which is synchronized. - Jonathan M Davis

But the point I was trying to make is that it's basically **impossible** to safely share ref counted containers (except maybe if they're completely encapsulated in a class, **not a struct**, wrapper). No matter how careful you are to synchronize all access, if you pass them around the ref count field will be updated without synchronization. This is not an unreasonable limitation. The purpose of my original post was just to clarify it and suggest that, if it's going to stay that way, there should be a very strong, explicit warning in the documentation.
Aug 04 2010
prev sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2010-08-04 21:55:33 -0400, Jonathan M Davis <jmdavisprog gmail.com> said:

 I would have thought that sharing pretty much _any_ type more complex than a
 primitive type without it being synchronized would be a bad idea. And since the
 standard containers obviously aren't going to be synchronized, I would expect
 you to have to wrap them in a class or struct which is synchronized.

You're exactly right Jonathan. The problem is that 'synchronized' only protects what's directly inside the class and doesn't protect anything beyond an indirection. The container and its reference counter is beyond an indirection, so it is not protected by 'synchronized' and is thus 'shared' according to the type system. So that's what the type system tells you. You can cast your way around that undesired 'shared', and it's the only way to use a container in a synchronized class. I think that's the reason dsimcha wants the documentation to be clearer. Because using a container inside a synchronized class is probably going to be a common thing, what you should and should not do with the container should be documented for when you cast your way around the type system. Personally, I'd say that not being able to use a container inside a synchronized class without subverting the type system looks like a failure of the type system. -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Aug 04 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Michel Fortin wrote:
 On 2010-08-04 21:55:33 -0400, Jonathan M Davis <jmdavisprog gmail.com> 
 said:
 
 I would have thought that sharing pretty much _any_ type more complex 
 than a
 primitive type without it being synchronized would be a bad idea. And 
 since the
 standard containers obviously aren't going to be synchronized, I would 
 expect
 you to have to wrap them in a class or struct which is synchronized.

You're exactly right Jonathan. The problem is that 'synchronized' only protects what's directly inside the class and doesn't protect anything beyond an indirection. The container and its reference counter is beyond an indirection, so it is not protected by 'synchronized' and is thus 'shared' according to the type system. So that's what the type system tells you. You can cast your way around that undesired 'shared', and it's the only way to use a container in a synchronized class. I think that's the reason dsimcha wants the documentation to be clearer. Because using a container inside a synchronized class is probably going to be a common thing, what you should and should not do with the container should be documented for when you cast your way around the type system. Personally, I'd say that not being able to use a container inside a synchronized class without subverting the type system looks like a failure of the type system.

How about an insufficiency of the container library? Andrei
Aug 04 2010
parent Michel Fortin <michel.fortin michelf.com> writes:
On 2010-08-05 00:05:55 -0400, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:

 Personally, I'd say that not being able to use a container inside a 
 synchronized class without subverting the type system looks like a 
 failure of the type system.

How about an insufficiency of the container library?

Well, that depends. If can you manage to make your containers operate with good performance (not using atomic ops) and without requiring casts on the user side when inside a synchronized class, then it's something that needs to be there in std.container. But I'm quite puzzled at how you could achieve this with the current type system. Have any clue? -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Aug 05 2010