Personal tools

HaskellImplementorsWorkshop/2012/Newton

From HaskellWiki

< HaskellImplementorsWorkshop | 2012
Revision as of 09:00, 18 July 2012 by GregoryCollins (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Bringing Atomic Memory Operations to a Lazy Language

Ryan Newton

The GHC Haskell compiler recently gained the capability to generate atomic compare-and-swap (CAS) assembly instructions. This opens up a new world of data-structure implementation possibilities, but also raises a number of problems due to the fact that pointer equality is not, in general, a meaningful concept in Haskell.

This talk describes existing CAS support for IORefs and Arrays and provide a recipe for others to add additional operations (e.g. test-and-set, fetch-and-add). We present performance results for our implementations of data structures such as Michael-Scott queues and Chase-Lev work-stealing deques. Finally, we give guidelines for how to write code that is robust to Haskell program transformations that will cause spurious failures of operations like CAS; this includes a discussion of GHC-specific guarantees (NOINLINE, etc) that enable safe use of atomic pointer operations.