Skip to main content

Crate fast_stm

Crate fast_stm 

Source
Expand description

§fast-stm

fast-stm is a performance-focused implementation of Software Transactional Memory for Rust.

This crate is a fork of Marthog’s original stm crate. The fork exists because the original crate has not been updated in years and there is still performance work to do. The original API should not see significant changes.

The crate is designed closely to Haskell’s STM library. Read Simon Marlow’s Parallel and Concurrent Programming in Haskell for more info. Especially the chapter about Performance is also important for using STM in Rust.

§STM

Users who wish to familiarize themselves with the mechanism can skim through the following documents:

With locks, the sequential composition of two threadsafe actions is no longer threadsafe because other threads may interfere between those actions. Applying a third lock to protect both may lead to common sources of errors like deadlocks or race conditions.

Unlike locks, software transactional memory is composable. It is typically implemented by writing all read and write operations in a log. When the action has finished and all the used TVars are consistent, the writes are committed as a single atomic operation. Otherwise the computation repeats. This may lead to starvation, but avoids common sources of bugs.

Panicking within STM does not poison the TVars. STM ensures consistency by never committing on panic.

§Features

This crate exposes features that can tweak implementation behavior:

  • wait-on-retry - enabled by default. If retry is called explicitly in a transaction, the thread waits for one of the variables read in the initial transaction to change before attempting the computation again.
  • early-conflict-detection - when reading a variable that was already read in a transaction, check whether it changed before the commit routine.
  • hash-registers - use HashMap-based internal read and write registers backed by rustc-hash instead of BTreeMap registers.

Only wait-on-retry is enabled by default.

Two additional features are provided for instrumentation:

  • profiling - add event counters to transactions and expose profile_atomically / profile_atomically_with_err.
  • bench - expose manual transaction initialization and commit helpers used by the repository’s benchmarks.

§Usage

You should only use the functions that are safe to use.

Do not have side effects except for the atomic variables from this library. Especially a mutex or other blocking mechanisms inside software transactional memory is dangerous.

You can run the top-level atomic operation by calling atomically.

use fast_stm::atomically;

atomically(|_tx| {
    // some action
    // return value as `Result`, for example
    Ok(42)
});

Calls to atomically should not be nested.

For running an atomic operation inside of another, pass a mutable reference to a Transaction and use ? on the result. You should not handle the error yourself, because it breaks consistency.

use fast_stm::{atomically, TVar};

let var = TVar::new(0);

let x = atomically(|tx| {
    var.write(tx, 42)?;
    var.read(tx)
});

println!("var = {}", x);

§STM safety

[!WARNING] This implementation does not guarantee opacity. Live transactions can observe inconsistent intermediate states. This has to be accounted for when writing transactional code segments. For more details on opacity, see On the Correctness of Transactional Memory.

Software transactional memory is completely safe in the terms that Rust considers safe. Still there are multiple rules that you should obey when dealing with software transactional memory:

  • Do not run code with side effects, especially no IO-code, because STM repeats the computation when it detects inconsistent state. Return a closure if you have to.
  • Do not handle the error types yourself, unless you absolutely know what you are doing. Use Transaction::or to combine alternative paths. Always use ? and never ignore a StmResult.
  • Do not run atomically inside of another. atomically is designed to have side effects and will therefore break STM’s assumptions. Nested calls are detected at runtime and handled with panic. When you use STM in the inner of a function, express it in the public interface by taking &mut Transaction as a parameter and returning StmResult<T>. Callers can safely compose it into larger blocks.
  • Do not mix locks and transactions. Your code will easily deadlock or slow unpredictably.
  • Do not use inner mutability to change the content of a TVar.

§Speed

Generally keep your atomic blocks as small as possible, because the more time you spend, the more likely it is to collide with other threads. For STM, reading TVars is quite slow, because it needs to look them up in the log every time. Every used TVar increases the chance of collisions. Therefore you should keep the amount of accessed variables as low as needed.

§Profiling

The profiling feature can be enabled to add event counters to transaction. Their values can be retrieved by passing a reference to TransactionTallies to the new entry functions: profile_atomically, …

Do not use the profiling feature if you are benchmarking execution times. While regular entry functions (atomically, atomically_with_err) are still available, they internally implement counters without giving public access to their value. This is done to avoid breaking the API when the feature is enabled.

Macros§

try_or_coerce
Convert a TransactionClosureResult<T, E_A> to TransactionClosureResult<T, E_B>.

Structs§

TVar
A variable that can be used in a STM-Block
Transaction
Transaction tracks all the read and written variables.
TransactionTalliesprofiling

Enums§

StmError
Error of a single step of a transaction.
TransactionControl
TransactionError
Error of a single step of a fallible transaction.
TransactionResult
Result of a fallible transaction.

Functions§

abort
Call abort to abort a transaction and pass the error as the return value.
atomically
Run a function atomically by using Software Transactional Memory. It calls to Transaction::with internally, but is more explicit.
atomically_with_err
Run a function atomically by using Software Transactional Memory. It calls to Transaction::with_err internally, but is more explicit.
commit_transactionbench
guard
Retry until cond is true.
init_transactionbench
optionally
Optionally run a transaction f. If f fails with a retry(), it does not cancel the whole transaction, but returns None.
retry
Call retry to abort an operation and run the whole transaction again.
unwrap_or_abort
Unwrap Option or call abort if it is None.
unwrap_or_retry
Unwrap Option or call retry if it is None.

Type Aliases§

StmClosureResult
Return type of a transaction body.
TransactionClosureResult
Return type of a fallible transaction body.