Subj : Re: Lock-free binary trees
To   : comp.programming.threads
From : Joe Seigh
Date : Mon Sep 19 2005 08:18 pm

gottlobfrege@gmail.com wrote:
> Joe Seigh wrote:
> 
>>No locks required for readers, just writers.
> 
> 
> I was hoping for something more explicit: reading while writing?  But
> just one writer at a time?  That's what I'd assume, but just wanted to
> be sure.
> 
Yes, the kind of stuff you can do with RCU, SMR, pre JSR-166 GC, or
atomically thread-safe reference counting (proxy or plain).  You
could make it writer lock-free also by employing COW (copy on write)
but if you go that route you might as well use a sorted array.  I
could do a writer lock-free tree but not a balanced one.  Tree
balancing code is quite complex.

> 
>> Skip lists are essentially linked lists and doing lock-free
>>linked lists has been around for ages and is fairly well understood.
> 
> 
> Exactly why I thought lock-free skip-lists would be doable (and useful
> - possibly the only reader and writer lock free associative containers
> so far?).  Yet they seem to have only be tackled in the last 2 or 3
> years, with improvements still being made.  They do look a bit tricky,
> so that may be why it wasn't done sooner.
> 

Lock-free has become popular recently, especially as thesis topics.
Grad students don't seem to have much imagination though, they all
seem to tackle the same problems.


-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.