A Lock-Free Hash Table (google video)

[Brad Roberts]

David B. Held wrote:
> Craig Black wrote:
>> Good stuff.  BTW, does anyone know when is D going to start using lock 
>> free
>> algorithms with their built-in/templated containers?
> 
> When STM is implemented. ;)  And I hope I'm not giving away too much by 
> saying that some reasonably smart folks are working on it even as we 
> speak...
> 
> Dave

STM (software transactional memory) isn't required for lock-free simple 
data structures (not all structures can be done lock free and I'm not an 
expert in that area).  It can be used, but it's overkill.

A better answer, however, is that thread safety isn't something that you 
apply to every single layer of data structures.  You need to really 
consider the appropriate level of granularity.  Even lock free routines 
have a cost that you don't necessarily want to pay all the time.  Given 
that, the lowest level is generally _not_ the right place to be applying 
synchronization logic (be it with atomic operations or locks).

And to be clear, I've asked this before and been convinced of the above. 
  You could ask the same thing of the stl for c++, and the same answer 
would apply.

NOW, and even better answer might be to have the safety be a pluggable 
policy decision and then people would be able to make the choice for 
themselves.  That'd allow the best of all worlds.  The problem is that 
writing code that flexibly is quite a bit of work and someone would need 
to volunteer to do it since I'm just about 100% sure that the code in 
question here isn't going to change otherwise.

Your question is a good one, and the answer is a lot more complex than 
it seems at first blush.

Later,
Brad