View mode: basic / threaded / horizontal-split · Log in · Help
June 14, 2006
Re: GC, the simple solution
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
Re: GC, the simple solution
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
Re: GC, the simple solution
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
Re: GC, the simple solution
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
Re: GC, the simple solution
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
Re: GC, the simple solution
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
Re: GC, the simple solution
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
Re: GC, the simple solution
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
Re: GC, the simple solution
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
Re: GC, the simple solution
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
2 3 4 5 6 7
Top | Discussion index | About this forum | D home