GC, the simple solution

[Don Clugston]

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