1. Start Here
   1. Welcome
   2. Introduction
   3. Quick Start
   4. Cheat Sheet
   5. Waiting
   6. Maps + Sets
   7. Exceptions
   8. F.A.Q.
2. Getting it
   1. Releases
   2. Snapshots
   3. Source
   4. License
3. Examples
   1. Quick Start
   2. Indexed Map
   3. Philosophers
4. Reference
   1. ScalaDoc API
   2. Benchmarking
   3. Expert Group
   4. Semantics
   5. Mailing List
   6.  
   7. Sponsors
   8. 

Map + Set Snapshots

A feature of the TMap and TSet collections provided with ScalaSTM is fast (O (1)) snapshots. We use these snapshots to provide consistent iteration of TMap.View and TSet.View, even when the iteration is performed outside a transaction.

Consistent iteration

TMap.View extends mutable.MapLike, so it provides all of the rich-trait functionality of a Map. It is pretty clear that functions like get and put should be atomic even when they are called outside an atomic block, but what about iterator? An iterator can be held for a long time, so what should it produce when the underlying collection continues to be changed by concurrent threads?

We have chosen to make TMap.View.iterator and TSet.View.iterator return an iterator over an atomic snapshot of the collection. The iterator method acts as if it has made a copy of the entire collection and returned an iterator over the copy. Concurrent updates can proceed uninhibited.

Much of the rich-trait functionality provided by Map and Set is implemented in terms of iterator, so the snapshot isolation provided by these methods avoids surprises. For example, the following code might print zero or two matches if m.iterator wasn’t consistent

val m = TMap("one" -> 1).single

(new Thread { override def run {
  atomic { implicit txn =>
    m -= "one"
    m += ("ONE" -> 1)
  }
} }).start

for ((k, v) <- m; if v == 1) println(k)

Manual snapshots

You can directly access the snapshot functionality via the functions snapshot and clone. TMap and TMap.View return an immutable.Map from snapshot; TSet and TSet.View return an immutable.Set ¹. The TMap or TSet returned from clone is a fully-functional transactional (and concurrent) collection.

How does it work?

Underneath, TMap and TSet use mutable hash tries constructed from Ref-s, with generation numbers that control copy-on-write. The algorithm is a novel hybrid of Nathan Bronson’s SnapTree ² and Transactional Predication ³, described in Chapter 4 of his thesis ⁴. As with transactional predication, no atomic block is required for accessing the collection outside a transaction, which substantially reduces overheads when no composition of operations is required.