Evan Martin (evan) wrote in evan_tech,
Evan Martin

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.

  • blog moved

    As described elsewhere, I've quit LiveJournal. If you're interested in my continuing posts, you should look at one of these (each contains feed…

  • dremel

    They published a paper on Dremel, my favorite previously-unpublished tool from the Google toolchest. Greg Linden discusses it: "[...] it is capable…

  • treemaps

    I finally wrote up my recent adventures in treemapping, complete with nifty clickable visualizations.

  • Post a new comment


    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment