Bucharest FP

A functional programming group for those living and working in Bucharest

We gather monthly, watch someone talk about something they're passionate about and then continue the discussion in a pub

#019: Software Transactional Memory

This meetup took place at the Eloquentix office, Thursday, 25 February 2016 at 19:00. Find out when our next meetup is.

Software Transactional Memory

Dan Șerban

Biography

Dan is a data engineer who occasionally teaches advanced functional programming, data science (using Spark as the big data framework) and full-stack web development. His passion projects are "Tweλve days of functional programming", the Spark Workshop and WebDev.

Abstract

Ten years ago, our programs used to be faster when we ran them on a next-generation processor, but that time has passed. While that next- generation chip will have more cores, each individual core will be no faster than the previous year’s model. If we want our programs to run faster, we must introduce concurrency into our software designs.

Conceptually, software transactional memory is a concurrency control paradigm analogous to database transactions for controlling access to shared memory in concurrent computing. It provides atomic and isolated execution for regions of code and is an alternative to lock-based synchronization. STM is also the name of a Haskell concurrency library implementing the concept, allowing you to share data between threads without using locks, removing much of the frustration typical of writing threaded code. STM's interface is only slightly more complicated than the interface for doing I/O, because it is built around the same core monad idea.

Compared to locks, software transactional memory is a higher-level access-control mechanism. From a programmer's standpoint, STM allows you to declare what needs to be executed atomically, rather than providing explicit instructions. In order to scale, locks require programmers to reason about details such as complex fine-grained synchronization and deadlock avoidance. Moreover, locks provide only indirect mechanisms towards enforcing atomicity and isolation, placing a greater burden on the programmer to ensure correctness. Software transactional memory promises to automate this process.

The benefits are composability, easier reasoning about concurrency and the absence of deadlocks.

STM is an optimistic access-control construct, as opposed to the pessimism of locks. The general idea of STM is that instead of requiring mutual exclusion from an atomic block of code, as would be the case with locks, the system allows multiple threads to enter the atomic block of code.

With some bookkeeping of state changes as well as some monitoring for the possibility of data races, in the case where a race does not occur, the system will allow the threads to commit. Otherwise, at least one transaction will be aborted and restarted. In the case where data conflicts are rare, this can be a substantial performance gain.

The core abstraction of Haskell's implementation of STM is the TVar, a mutable reference representing general shared state.