Here’s the video from my recent talk to the Northwest C++ Users Group (NWCPP) about how to translate the data-race free type system into a system of user-defined annotations in C++. I start with the definition of a data race and discuss various ways to eliminate them. Then I describe the ownership system and give a few examples of annotated programs.
Here are the slides from the presentation. They include extensive notes.
By the way, we are looking for speakers at the NWCPP, not necessarily related to C++. We are thinking of changing the charter to include all programming languages. If you are near Seattle on Oct 21 09 (or any third Wednesday of the month), and you are ready to give a 60 min presentation, please contact me.
September 22, 2009 at 11:48 pm
Great Talk!
I have a few quick questions:
1) Is there some benefit to an multi-level ownership tree as opposed to single-level tree? (i.e. all owned objects contain a direct link to their monitors)
2) It appears that the runtime portion of owner annotations could be implemented in D2 with a free function + some minor runtime changes. Is this correct, or are there other issues? (Besides, efficiency/good defaults)
3) It appears lent’s main goal is alias control and possibly efficiency/DRY. Is there a safety reason for lent? (i.e. assuming all shared objects, including owned children, are wrapped in synchronized blocks, would there be something more than a performance issue?
September 23, 2009 at 10:55 am
1) Multi-level trees are a practical necessity. When you define a class, you can only specify “this” as the owner of its members. The actual top owner is not know until runtime, and it’s usually different for different instantiations. We’re talking reusability of classes.
2) I just don’t see a runtime regime to be very practical. And it would be an even harder sell than the type-system one.
3) Imagine someone changing the implementation of strlen to store the alias of the last tested string. This implementation would first compare the argument of strlen to this cached alias. But the comparison would be done without locking the alias, and you have a data race with other concurrent uses of the squirreled string. Marking the strlen argument “lent” would prevent such squirreling.
September 23, 2009 at 11:48 am
Thanks.
1) I’m not sure I see the practical reasons. On a theoretical level it makes local type-checking easier, but in your talk you mentioned type systems that have instance types (I can recall if that’s the right term) which might(?) be able to handle the complexity. From the runtime perspective, each object has to walk an ownership tree to reach it’s lock/do validation/etc. I didn’t see a use case for needing the tree structure inside a region. So wouldn’t it be easier and more efficient for each object in a region to only hold a reference to the top owner?
2) Well, on one hand, wasn’t the talk essentially about a convention based runtime regime? On the other, my question was really regarding ease of implementation of the runtime-half of one part of a full ownership-type system. The idea was a free function such as shared(T) owner(T,U…)(Object owner, U params) could be used to create ownership regions/trees.
3) Well, I can definitely see the usage of lent w.r.t. naked data. However, assuming string was a shared object, then wouldn’t the alias still be okay? In order to access the squirreled string, strlen would use synchronized methods and therefore there would be no data races (at least at the hardware level).
September 23, 2009 at 12:47 pm
Maybe I haven’t stressed it enough–all the checking (and walking up the tree) can be done at compile time, there’s no need for a runtime component. In the annotation-based system it’s the programmer who does the checking. However, as I argued, the checking can be done locally, which makes it practical.
As for the string example, you are probably thinking of a string implemented as a monitor. I’m talking about a regular string or, in the case of strlen, just a pointer to char. strlen has no idea who the owner of this string is, so it cannot take the correct lock.
Notice that this is not a problem with the current argument of strlen–this one is correctly locked for the duration of the call. It’s the stashed one that is no longer locked and whose owner is unknown.
The slides from my presentation will soon be published on the NWCPP web site. I’ll add the link here as soon as they are up. Each slide is accompanied by a more comprehensive commentary.
October 12, 2009 at 1:58 pm
Many people from the D community, myself included, have followed, your blog with considerable interest, and valued the ideas you have been educating us with.
It has been reported in the D.newsgroup [subject: Revamped concurrency API ] that you ‘no longer want to be involved’.
Myself and others, have received this news with disbelief. One can only assume it is a difference of opinion. Would you like to confirm or deny this, perhaps with an explanation for the D community.
respectfully
Nick B.
October 13, 2009 at 1:58 pm
I had no idea there was a discussion about me in the D language newsgroup (I stopped following it because of the large volume). I’ll try to respond there.
August 6, 2013 at 2:29 pm
The slides are down and are not in Internet Archive, would you like to repost them? Or have they been obsoleted? Thanks
August 7, 2013 at 10:20 am
There’s been several reorganizations of the NWCPP web site since I posted the slides. Currently they are at http://nwcpp.org/talks/2009/Ownership_Systems_against_Data_Races.pdf .