12:30 pm, 19 Nov 04
lock-free
Hot on the heels of my previous post: a talk from Andrei Alexandrescu on issues with threads in C++. One interesting takeaway is that because threading behavior is underspecified in C++, certain ought-to-be-legal compiler optimizations must be turned off, and that reportedly Java 1.5 can actually perform better optimizations because its memory model is more rigorously defined.
Apparently a paper by Herlihy [but which one? probably the one with 390 citations?] sorta revolutionized the field in 1995, proving that you can implement data structures (including hash tables) in a threadsafe manner without locks when you have a compare-and-swap primitive. Unfortunately this work was after pthreads so the spec doesn't provide a portable cas(), even though hardware manufactures quickly caught on and most today provide a primitive (with some exceptions on 64-bit architectures that I didn't quite follow?). I will hopefully read this paper over the weekend and be able to provide a more fair representation of it later.
Apparently a paper by Herlihy [but which one? probably the one with 390 citations?] sorta revolutionized the field in 1995, proving that you can implement data structures (including hash tables) in a threadsafe manner without locks when you have a compare-and-swap primitive. Unfortunately this work was after pthreads so the spec doesn't provide a portable cas(), even though hardware manufactures quickly caught on and most today provide a primitive (with some exceptions on 64-bit architectures that I didn't quite follow?). I will hopefully read this paper over the weekend and be able to provide a more fair representation of it later.
You can do simple singly linked lists with a single pointer, but to do a more complex data-structure you may need to exchange two contiguous pointers (a head and a tail for example).
I actually use lockless singly linked lists in ULE for appending a thread to a foreign CPUs queue of additions.
Also, the java vs C++ debate mirrors the old fortran vs c debate. Fortran was always much more optimizable because it did not have pointers, which means the compiler could be certain about aliasing and so on. Pointers really are a pain in the ass from an optimization point of view.