News for hackers. Stuff that matters.
Re:What are the lesser known but cool data structures? by tptacek on Saturday May 22, 2010 @09:04PM (#1371445)
You can find blog posts and Stack Overflow articles talking about lock overhead in rb-trees versus skip lists, and just looking at a diagram you can intuitively sense where that idea comes from. But these kinds of analyses are usually flawed by the fact that they assume the most naive possible encoding of tree edges (void* tree* tree*).
Re:What are the lesser known but cool data structures? by jey on Saturday May 22, 2010 @09:07PM (#1371455)
Hm, what are some conncurrency-friendly ways to encode tree edges?
Re:What are the lesser known but cool data structures? by tptacek on Saturday May 22, 2010 @09:12PM (#1371464)
I don't have an answer for you (I'm just making the point that when people argue about how inefficient trees are, they're usually assuming a struct with two edge pointers), but a more direct answer to your question might be:

http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

(That's a lock-free red-black tree impl).