June 14, 2006
Bruno Medeiros wrote:
>
> Makes me think, how does one keep up with this? I mean, one who isn't (nor wishes to be) a hardware expert, but wants to keep up with the general developments in this area, thus maintaining an overview of it.

comp.programming.threads is worth keeping an eye on, though the jargon can get a bit thick there at times.  The C++ committee is also working on a new memory model for C++, so any discussion there may be useful. The easiest way to keep an eye on this is follow the links from Hans Boehm's website  (http://www.hpl.hp.com/personal/Hans_Boehm/) though you could keep an eye on comp.std.c++ as well if you're having trouble staying awake at night.  Finally, any paper with Maurice Herlihy's name on it is a useful resource if you want a deeper understanding of some of these ideas and don't mind some research.  He's got a website with links to many of his papers, though IIRC some of them are hard to track down without an ACM membership.


Sean
June 14, 2006
Interesting indeed!

I'm currently reading Boehm's article "Threads Cannot be Implemented as a Library". I wonder if this means that threads should become primitives of some sort [in D] ?

L.


June 14, 2006
Lionello Lunesu wrote:
> Interesting indeed!
> 
> I'm currently reading Boehm's article "Threads Cannot be Implemented as a Library". I wonder if this means that threads should become primitives of some sort [in D] ?

It's been a while since I read that article, but I think D already has enough in-language recognition of threading issues to escape most/all of the problems Boehm mentions: Thread is a standard library component rather than a third-party component, synchronized is available for mutual exclusion, and volatile (plus perhaps inline asm code) is enough to manage lock-free work.  A more robust multithread-aware memory model would be good to have, but it's a sticky enough issue that I think Walter is right for waiting on that for now.


Sean
June 15, 2006
Sean Kelly wrote:
> Lionello Lunesu wrote:
>> Interesting indeed!
>>
>> I'm currently reading Boehm's article "Threads Cannot be Implemented as a Library". I wonder if this means that threads should become primitives of some sort [in D] ?
> 
> It's been a while since I read that article, but I think D already has enough in-language recognition of threading issues to escape most/all of the problems Boehm mentions: Thread is a standard library component rather than a third-party component, synchronized is available for mutual exclusion, and volatile (plus perhaps inline asm code) is enough to manage lock-free work.  A more robust multithread-aware memory model would be good to have, but it's a sticky enough issue that I think Walter is right for waiting on that for now.

...that leaves only atomic operations? Or would "volatile" or "synchronized" take care of memory fencing and such?

Would be nice if there were an built-in type with overloaded ++x, x++, x=y, all atomic. (I've seen some C++ templates that do this.)

L.
June 15, 2006
Lionello Lunesu wrote:
> Sean Kelly wrote:
>> Lionello Lunesu wrote:
>>> Interesting indeed!
>>>
>>> I'm currently reading Boehm's article "Threads Cannot be Implemented as a Library". I wonder if this means that threads should become primitives of some sort [in D] ?
>>
>> It's been a while since I read that article, but I think D already has enough in-language recognition of threading issues to escape most/all of the problems Boehm mentions: Thread is a standard library component rather than a third-party component, synchronized is available for mutual exclusion, and volatile (plus perhaps inline asm code) is enough to manage lock-free work.  A more robust multithread-aware memory model would be good to have, but it's a sticky enough issue that I think Walter is right for waiting on that for now.
> 
> ...that leaves only atomic operations? Or would "volatile" or "synchronized" take care of memory fencing and such?

"volatile" is actually intended to address compiler optimizations in a similar way to how memory barriers address CPU optimizations.  It is a necessary part of any lock-free operation in D.  "synchronized" is used for mutual exclusion and typically involves a mutex, so while it should have the proper effect, it's not lock-free.

> Would be nice if there were an built-in type with overloaded ++x, x++, x=y, all atomic. (I've seen some C++ templates that do this.)

It would be nice, but I've yet to see a proposal that I like.  The problem is that in addition to pure atomic operations (which is how the x86 typically works by default) lock-free programmers typically want to make an assertion about instruction ordering as well, and built-in semantics don't expose this very cleanly.  One could simply have volatile types similar to Java where no optimization is allowed on them at all, but this may be too heavy-handed to satisfy some folks.  For now, I think a library solution is a reasonable alternative.  Ares has had one for quite a while and it's almost standalone so it could be used with Phobos with very little effort.  The documentation is here (DDoc seems to want to generate docs for private template functions, so I apologize for the clutter):

http://svn.dsource.org/projects/ares/trunk/doc/ares/std/atomic.html

And the code itself is here:

http://svn.dsource.org/projects/ares/trunk/src/ares/std/atomic.d

It currently only works on the x86 and is really intended for API developers, but it does the trick and I'll expand it as needed.  For typical use, msync.acq (acquire), msync.rel (release), and msync.none are the flags you're likely to care about.  The other more fine-grained flags just alias acq/rel on x86 anyway.  In case the docs are confusing, the API calls supported are:

load
store
storeIf (ie. CAS)
increment
decrement


Sean
June 16, 2006
Sean Kelly wrote:
> Lionello Lunesu wrote:
>> ...that leaves only atomic operations? Or would "volatile" or "synchronized" take care of memory fencing and such?
> 
> "volatile" is actually intended to address compiler optimizations in a similar way to how memory barriers address CPU optimizations.  It is a necessary part of any lock-free operation in D.  "synchronized" is used for mutual exclusion and typically involves a mutex, so while it should have the proper effect, it's not lock-free.

So I suppose "volatile" could be extended to include memory locking as well!

// instructions inside this block are 'lock'ed
volatile(atomic) {
	++a;
	a = x;
}

(or perhaps even "synchronized(memory) {...}", but I think extending volatile makes more sense).

Come to think of it, doesn't "synchronized" also imply "volatile"?

Or, another possibility would be to add the volatile declaration as in C, but then actually locking all access to the variable:

volatile int i;
i++;// atomic

Seems to me it should be possibly to extend D with a built-in and portable construct for these atomic operations.

> It would be nice, but I've yet to see a proposal that I like.  The problem is that in addition to pure atomic operations (which is how the x86 typically works by default) lock-free programmers typically want to make an assertion about instruction ordering as well, and built-in semantics don't expose this very cleanly.  One could simply have volatile types similar to Java where no optimization is allowed on them at all, but this may be too heavy-handed to satisfy some folks.  For now, I think a library solution is a reasonable alternative.  Ares has had one for quite a while and it's almost standalone so it could be used with Phobos with very little effort.  The documentation is here (DDoc seems to want to generate docs for private template functions, so I apologize for the clutter):
> 
> http://svn.dsource.org/projects/ares/trunk/doc/ares/std/atomic.html
> 
> And the code itself is here:
> 
> http://svn.dsource.org/projects/ares/trunk/src/ares/std/atomic.d


Thanks, I'll have a look at them.

L.
June 16, 2006
Sean Kelly wrote:
> Lionello Lunesu wrote:
>> Sean Kelly wrote:
>>> Lionello Lunesu wrote:
>>>> Interesting indeed!
>>>>
>>>> I'm currently reading Boehm's article "Threads Cannot be Implemented as a Library". I wonder if this means that threads should become primitives of some sort [in D] ?
>>>
>>> It's been a while since I read that article, but I think D already has enough in-language recognition of threading issues to escape most/all of the problems Boehm mentions: Thread is a standard library component rather than a third-party component, synchronized is available for mutual exclusion, and volatile (plus perhaps inline asm code) is enough to manage lock-free work.  A more robust multithread-aware memory model would be good to have, but it's a sticky enough issue that I think Walter is right for waiting on that for now.
>>
>> ...that leaves only atomic operations? Or would "volatile" or "synchronized" take care of memory fencing and such?
> 
> "volatile" is actually intended to address compiler optimizations in a similar way to how memory barriers address CPU optimizations.  It is a necessary part of any lock-free operation in D.  "synchronized" is used for mutual exclusion and typically involves a mutex, so while it should have the proper effect, it's not lock-free.
> 
>> Would be nice if there were an built-in type with overloaded ++x, x++, x=y, all atomic. (I've seen some C++ templates that do this.)
> 
> It would be nice, but I've yet to see a proposal that I like.  The problem is that in addition to pure atomic operations (which is how the x86 typically works by default) lock-free programmers typically want to make an assertion about instruction ordering as well, and built-in semantics don't expose this very cleanly.  One could simply have volatile types similar to Java where no optimization is allowed on them at all, but this may be too heavy-handed to satisfy some folks.  For now, I think a library solution is a reasonable alternative.  Ares has had one for quite a while and it's almost standalone so it could be used with Phobos with very little effort. 

I'd really like to see this included in the standard distribution.
Has anyone made a general-purpose lock-free linked list? Just a low-level list of void * pointers would be fantastic.

 The documentation is here (DDoc
> seems to want to generate docs for private template functions, so I apologize for the clutter):
> 
> http://svn.dsource.org/projects/ares/trunk/doc/ares/std/atomic.html
> 
> And the code itself is here:
> 
> http://svn.dsource.org/projects/ares/trunk/src/ares/std/atomic.d
> 
> It currently only works on the x86 and is really intended for API developers, but it does the trick and I'll expand it as needed.  For typical use, msync.acq (acquire), msync.rel (release), and msync.none are the flags you're likely to care about.  The other more fine-grained flags just alias acq/rel on x86 anyway.  In case the docs are confusing, the API calls supported are:
> 
> load
> store
> storeIf (ie. CAS)
> increment
> decrement
> 
> 
> Sean
June 16, 2006
Lionello Lunesu wrote:
> Sean Kelly wrote:
>> Lionello Lunesu wrote:
>>> ...that leaves only atomic operations? Or would "volatile" or "synchronized" take care of memory fencing and such?
>>
>> "volatile" is actually intended to address compiler optimizations in a similar way to how memory barriers address CPU optimizations.  It is a necessary part of any lock-free operation in D.  "synchronized" is used for mutual exclusion and typically involves a mutex, so while it should have the proper effect, it's not lock-free.
> 
> So I suppose "volatile" could be extended to include memory locking as well!

Yes it could, though for now I prefer it the way it is as it offers more control over exactly what's going on.  It helps tremendously that D has such good inline asm support.

> // instructions inside this block are 'lock'ed
> volatile(atomic) {
>     ++a;
>     a = x;
> }
> 
> (or perhaps even "synchronized(memory) {...}", but I think extending volatile makes more sense).
> 
> Come to think of it, doesn't "synchronized" also imply "volatile"?

Yes.  Synchronization mechanisms rely on memory barriers to work properly.  In fact, it's been suggested in the past on c.p.t that an empty mutex block:

    synchronzed {}

could be used as a high-level sort of bidirectional memory barrier, except for the risk of the compiler optimizing the call away entirely.

> Or, another possibility would be to add the volatile declaration as in C, but then actually locking all access to the variable:
> 
> volatile int i;
> i++;// atomic

This is sort of how Java implements volatile and it wouldn't surprise me if C++ did something similar.  Right now, the "volatile" qualifier offers basically no language guarantees for concurrent programming, as it was actually intended for accessing interrupt data IIRC.

> Seems to me it should be possibly to extend D with a built-in and portable construct for these atomic operations.

Definately.  The trouble is coming up with a good design :-)  I think the C++ team is definately qualified to do so, but they may have to make some sacrifices in the interest of time.


Sean
June 16, 2006
Don Clugston wrote:
> 
> I'd really like to see this included in the standard distribution.
> Has anyone made a general-purpose lock-free linked list? Just a low-level list of void * pointers would be fantastic.

Mango contains some of Doug Lea's containers and there may be one there.  If not, it shouldn't be tremendously difficult to implement or port one.  I'm not sure I have the time right now, but if someone wants to the the atomic package in Ares they're more than welcome to.


Sean
June 17, 2006
Sean Kelly wrote:
> Bruno Medeiros wrote:
>>
>> Makes me think, how does one keep up with this? I mean, one who isn't (nor wishes to be) a hardware expert, but wants to keep up with the general developments in this area, thus maintaining an overview of it.
> 
> comp.programming.threads is worth keeping an eye on, though the jargon can get a bit thick there at times.  The C++ committee is also working on a new memory model for C++, so any discussion there may be useful. The easiest way to keep an eye on this is follow the links from Hans Boehm's website  (http://www.hpl.hp.com/personal/Hans_Boehm/) though you could keep an eye on comp.std.c++ as well if you're having trouble staying awake at night.  Finally, any paper with Maurice Herlihy's name on it is a useful resource if you want a deeper understanding of some of these ideas and don't mind some research.  He's got a website with links to many of his papers, though IIRC some of them are hard to track down without an ACM membership.
> 
> 
> Sean

Well, that's the thing, I just want to have some general knowledge about this area of hardware and concurrency/distributed-systems, not become an expert on it. My time to learn new things is limited (and I definitely have no trouble going to sleep :( ), so my priority goes for learning things that I have immediate need to use/become-involved. If I ever have the need to learn more in-depth I will.
You see, concurrency is very important for people interested in server-side programming. But for multimedia programming, it's not that important. For now that is, as it seems that with the coming of multicore CPUs, concurrency is becoming more and more of a general software development topic, relevant even for non-intrinsically concurrent apps.

-- 
Bruno Medeiros - CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D