A Lock-Free Hash Table (google video)

[David B. Held]

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