lock-free, con't -- tim harris: evan_tech

lock-free, con't -- tim harris

I saw a talk by Tim Harris on his research concerning lock-free programming. Similarly to the talk I wrote about before, he provided an "atomic" keyword and block, but his approach was different. The gist is that he stored memory changes in an atomic section in a sort of log, and through some tricky sequences of CAS he could commit this log without locks. It requires language support because memory accesses need to check the log (but the common case is an O(1) memory access) and he included some promising-looking numbers on performance, even when compared to Java's lock-free data structures, especially when the number of processors got huge (like more than 10 -- they have some fancy hardware!).

Apparently his work has made it into GHC (the main Haskell compiler) as well, though he didn't elaborate on it. But at the beginning of his talk he said there were two versions of the talk: one in Haskell, and one in a more Java-like language, and so he chose the latter. I was sad.

I really ought to study concurrency in Haskell because it ought to be interesting. With functions without effects you never need a write lock; but at the same time, the reason you'd want to lock something is only when you mutate it, which means you do need some sort of locking, even in effect-free functions.

In any case, there are a number of interesting-looking papers on his site. In particular, "A Practical Multi-Word Compare-and-Swap Operation" at a glance looks like the seed of the implementation of the effect-log technique I described above.

lock-free, con't -- tim harris

blog moved

dremel

treemaps

Error