Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Software Transactional Memory
Search
Bucharest FP
February 25, 2016
Programming
0
340
Software Transactional Memory
Bucharest FP
February 25, 2016
Tweet
Share
More Decks by Bucharest FP
See All by Bucharest FP
The Curry-Howard-Lambek Correspondence
bucharestfp
3
790
An Applicative Application
bucharestfp
0
9.8k
Composition in FP
bucharestfp
0
330
Formal Design, Implementation and Verification of Blockchain Languages and Virtual Machines
bucharestfp
1
550
PureScript & Halogen
bucharestfp
1
400
A Simple Sudoku Solver in Haskell
bucharestfp
0
1.1k
DeviceGraph — Clustering Devices into People at Adobe with Apache Spark
bucharestfp
0
260
Functional Programming Inception
bucharestfp
0
400
Equational Reasoning in Programming
bucharestfp
0
870
Other Decks in Programming
See All in Programming
What Spring Developers Should Know About Jakarta EE
ivargrimstad
1
610
TypeScript Language Service Plugin で CSS Modules の開発体験を改善する
mizdra
PRO
3
2.4k
複雑なフォームを継続的に開発していくための技術選定・設計・実装 #tskaigi / #tskaigi2025
izumin5210
12
6.4k
AIエージェントによるテストフレームワーク Arbigent
takahirom
0
280
Javaに鉄道指向プログラミング (Railway Oriented Pro gramming) のエッセンスを取り入れる/Bringing the Essence of Railway-Oriented Programming to Java
cocet33000
1
120
コードに語らせよう――自己ドキュメント化が内包する楽しさについて / Let the Code Speak
nrslib
5
1.1k
『Python → TypeScript』オンボーディング奮闘記
takumi_tatsuno
1
140
💎 My RubyKaigi Effect in 2025: Top Ruby Companies 🌐
yasulab
PRO
1
130
Babylon.js 8.0のアプデ情報を 軽率にキャッチアップ / catch-up-babylonjs-8
drumath2237
0
110
型付け力を強化するための Hoogle のすゝめ / Boosting Your Type Mastery with Hoogle
guvalif
1
230
Cursor Meetup Tokyo ゲノミクスとCursor: 進化と制約のあいだ
koido
1
320
イベントストーミングから始めるドメイン駆動設計
jgeem
3
420
Featured
See All Featured
Rebuilding a faster, lazier Slack
samanthasiow
81
9k
Measuring & Analyzing Core Web Vitals
bluesmoon
7
460
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
233
17k
Raft: Consensus for Rubyists
vanstee
137
7k
Learning to Love Humans: Emotional Interface Design
aarron
273
40k
Fantastic passwords and where to find them - at NoRuKo
philnash
51
3.2k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
30
2.4k
Mobile First: as difficult as doing things right
swwweet
223
9.6k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
34
2.3k
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
1
82
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
15
890
Transcript
Software-Transactional Memory in Haskell (an overview of the implementation)
Let's start with WHY
FACT: Many modern applications have increasingly stringent concurrency requirements
FACT: Commodity multicore systems are increasingly affordable and available
FACT: The design and implementation of correct, efficient, and scalable
concurrent software remains a daunting task
Haskell to the rescue! Meet STM
STM protects shared state in concurrent programs
STM provides a more user-friendly and scalable alternative to locks
by promoting the notion of memory transactions as first-class citizens
Transactions, like many of the best ideas in computer science,
originated in the data engineering world
Transactions are one of the foundations of database technology
Full-fledged transactions are defined by the ACID properties Memory transactions
use two of them (A+I)
Transactions provide atomicity and isolation guarantees
Strong atomicity means all-or-nothing
Strong isolation means freedom from interference by other threads
Recall that Haskell is a strictly-typed, lazy, pure functional language
Pure means that functions with side-effects must be marked as
such
The marking is done through the type system at compile
time
STM is just another kind of I/O (with a different
marker: "STM a" instead of "IO a")
Transactional memory needs to be declared explicitly as TVar
The STM library provides an STM-to-IO converter called "atomically"
Transactional memory can only be accessed through dedicated functions like
"modifyTVar", "readTVar", "writeTVar" which can only be called inside STM blocks
Implementation Overview Of GHC's STM
Definition A transaction memory is a set of tuples in
the shape of (Identity,Version,Value) The version number represents the number of times the value has changed.
The Transactional Record Every STM transaction keeps a record of
state changes (similar to the tx log in the DB world)
STM performs all the effects of a transaction locally in
the transactional record
Once the transaction has finished its work locally, a version-based
consistency check determines if the values read for the entire access set are consistent
This version-based consistency check also obtains locks for the write
set and with those locks STM updates the main memory and then releases the locks
Rolling back the effects of a transaction means forgetting the
current transactional record and starting again
Reading: When a readTVar is attempted STM first searches the
tr. record for an existing entry
Reading: If the entry is found, STM will use that
local view of the TVar
Reading: On the first readTVar, a new entry is allocated
and the TVar value is read and stored locally
Reading: The original Tvar does not need to be accessed
again for its value until validation time
Writing: Writing to a Tvar requires that the variable first
be in the tr. record
Writing: If it is not currently in the tr. record,
a readTVar is performed and the value is stored in a new entry
Writing: The version in this entry will be used at
validation time to ensure that no updates were made concurrently to this TVar
Writing: The value is stored locally in the tr. record
until commit time
Validation: Before a transaction can make its effects visible to
other threads it must check that it has seen a consistent view of memory while it was executing
Validation: This is done by checking that TVars hold their
expected values (version comparison)
Validation: During validation, STM fetches the version numbers for all
TVars and checks that they are consistent with its expectations
Validation: STM then acquires locks for the write set in
ascending order of memory address
Validation: STM then reads and checks all version numbers again
Validation: If the version numbers are again consistent with its
expectations, STM allows the commit to happen
Committing: The desired atomicity is guaranteed by: • Validation having
witnessed all TVars with their respective expected values • Locks being held for all of the TVars in the write set
Committing: STM proceeds to increment each locked TVar's num_updates (a.k.a.
version) field
Committing: STM then writes the new values into the respective
current_value fields, and releases the locks
Committing: While these updates happen one-by-one, any attempt to read
from this set will spin while the lock is held
Another useful STM abstraction is the TChan, an unbounded FIFO
channel
Once some messages are transferred into a TChan, they are
ready to be consumed by other threads (broadcasting is possible too)
TChans are useful when threads need to send signals to
each other, as opposed to just accessing shared state
Compile your STM code with: ghc -threaded program.hs When running
the program: ./program +RTS -N
Follow me on GitHub github.com/dserban