Software Transactional Memory
April 2, 2016
Steve Severance has used Software Transactional Memory (STM) pretty intensively in trading and web crawling applications. He shares things he’s learned, some gotchas, and a comparison of the way STM works in Haskell vs other languages.
- Motivation for STM
- CPUs are getting more cores yet our tools remain fairly primitive
- Locks and lock convoys
- Dealing with deadlocks
- Immutability has helped Haskell some with this
- What is STM? It is in-memory transactional concurrency that gives us two properties
- Atomicity: all results of your transaction will be visible at once
- Isolation of underlying primitives
- Haskell is the best language in the world in which to implement an STM
- It was originally 100 lines of code, and even now it’s only about 600 lines of C!
- It exploits three properties of the language: purity, immutability and laziness
- Learning about STM was when Steve first started to appreciate laziness; up until that point laziness had only hurt, never helped
- Haskell retries an STM transaction as needed. Immutability allows it to do this fearlessly, and laziness avoids fully evaluating the transaction
- STM is harder in other languages. For instance in Clojure you have to manually implement rollback functionality.
- There are some helpful auxiliary packages such as stm-chans
- How about performing unsafe IO in the STM monad? Never! If you’re wanting to do this you’re “doing it wrong.”
- Discussion of the primitives TVar, TMVar, TChan, TQueue, TBQueue, TSem
- How the
retryfunction works by putting our thread to sleep
- Using orElse and the Alternative typeclass
- How often does a transaction block get re-run? Does it get inefficient? Use the stm-stats package to see how well your transactions are performing.
- The asyc package internally uses STM and has great integration with it
- Other languages have STM of varying convenience. Clojure, Scala, C++, C#
- The C# team spent about three years trying to write an STM. They gave up and wrote a retrospective on why it was so hard.
- Side effects make STM hellish in languages other than Haskell.