Evan Martin (evan) wrote in evan_tech,
Evan Martin
evan
evan_tech

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.
Subscribe
  • Post a new comment

    Error

    switch
    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.
    Help
  • 1 comment