Subj : Re: Implementing lock-free data structures To : comp.programming.threads From : Joe Seigh Date : Thu Mar 10 2005 06:43 am On Thu, 10 Mar 2005 03:13:22 GMT, David Hopwood wrote: > Joe Seigh wrote: >> I was going to do a write up of general instructions on how to >> implement lock-free data structures using RCU, atomic_ptr, >> hazard pointers, Boehm GC, etc... since it doesn't appear that >> anyone else has, except for COW objects and linked lists, and >> it's clear that lock-free won't take off until there's better >> documentation. > > Why do you expect it to, or think that it should "take off"? In my view > lock/wait-free techniques are best suited to being used *by language > and operating system implementations* to provide carefully chosen sets > of higher-level concurrency abstractions (message queues, pipes, promises, > M-structures, etc.) > > Lock-free stuff is (and always will be) too complicated, error-prone, > and platform-specific to use directly in applications. And applications > shouldn't care whether the abstractions they use are implemented using > lock-free techniques or otherwise. > Take off in a relative sense. Complicated is a relative term also. There are a lot of people out there who think multithreading in general is too complicated and if they had any say in the matter that it should be banned. I talked to someone recently whose product is hitting Moore's Wall rather hard. They're using a data structure with a really efficient big O property but it's still getting hit hard enough that contention is a problem. The lock-free implementation of that data structure doesn't exist yet and I don't think a lock-free linked list with O(n/2) lookups is going to hack it. I don't feel like publishing the general rules at this point because it would basically be a guide for patenting all the lock-free implementations no one has gotten around to yet. Because the US patent office *will* issue patents for them. Sun already has a patent on lock-free ilnked list used with one form of GC. And lastly, there are some semantic differences between lock-free and conventional locked data structures. You can't always transparently swap implementations. -- Joe Seigh .