I would like to share this interesting video

http://video.google.com/videoplay?docid=2139967204534450862

Mr. Soerensen, thanks - a really nice video.

Knud Soerensen wrote

> I would like to share this interesting video
> 
> http://video.google.com/videoplay?docid=2139967204534450862

The author admits, that he has some problems when resizing.
He solved them by "stalling".
With 64MB hashes the stall time is short though.

http://blogs.azulsystems.com/cliff/

But I wonder, how much "stalling" will be done on resizing to some milliards of hash positions.

-manfred

Good stuff.  BTW, does anyone know when is D going to start using lock free algorithms with their built-in/templated containers?

-Craig

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

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

Brad Roberts wrote:
> [...]
> 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.
> [...]

Well, the point is that even if nobody rewrites any containers to use lock-free algorithms, you can get correct lock-free behavior at whatever level of granularity you feel is appropriate by writing the relevant code in an STM atomic {} block.  Granted, there are cases where a lock-free container makes sense and may provide, for instance, better concurrency in the high-contention case.  But much of the attraction of STM is that for the simple case, no code actually has to be rewritten, which is great for people who need to build big data structures but don't want to become experts in designing lock-free algorithms.

Dave

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...

Will this require the user to expose a .clone() method for classes involved in transactions?

Sean Kelly wrote:
> 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...
> 
> Will this require the user to expose a .clone() method for classes involved in transactions?

I don't want to overpromise and underdeliver, so I will start out with the disclaimer that nothing I say about D features is guaranteed to be implemented. ;)  That being said, word-based STM is the most generic form, and requires no special work on the part of any user whatsoever. The first form of STM provided may or may not be word-based. ;) However, Walter and his "STM advisors" are aware of the other forms of STM, including object-based, and there is a possibility of having user-specifiable STM implementations.  I think everyone realizes that concurrency is the hot new buzzword, and you can rest assured that D will take it very, very seriously.

Dave

Knud Soerensen wrote:
> I would like to share this interesting video 
> 
> http://video.google.com/videoplay?docid=2139967204534450862

Very interesting, thanks for that. Maybe now we can convince Walter to include the patch I made about a year ago to make D's AA power-of-2/AND instead of prime/MOD?

I'm wondering if this would be useful for D. What about memory allocations? If one thread is allocating a key/value, will that allocation block other threads? Any difference between Phobos/Tango?

L.