* Officially described at [[wikipedia::Lock free algorithm]].
* Use [[TransactionalDataStructure]] to implement such algorithms easily

== Typical Example ==

{{:TransactionDataStructureExample}}

Let's keep the internal data in a dedicated immutable structure called '''Data'''. When performing an update:
* Read the '''current''' state.
* Compute an update based on the '''current''' state
* Use ''compare and swap'' operation to ''transactionally'' (hence the similarity with [[TransactionalMemory]]) update the state of the object
* repeat everything again if there was a clash
* and the '''current''' value was modified by some other thread meanwhile


<source lang="java">


import java.util.concurrent.atomic.AtomicReference;

public abstract class Helper {

private static final class Data {

final int value1;
final int value2;
final int value3;

Data(int value1, int value2, int value3) {
this.value1 = value1;
this.value2 = value2;
this.value3 = value3;
}
}

private final AtomicReference<Data> data = new AtomicReference<>(new Data(0, 0, 0));

protected abstract int combine(int x, int y);

public final void update() {
Data current;
while (true) {
current = data.get();

// the following three operations must be performed in a "transaction" ...
int v1 = combine(current.value1, current.value2);
int v2 = combine(current.value2, current.value3);
int v3 = combine(current.value3, current.value1);
// either we want to apply them all or none at all!

if (data.compareAndSet(current, new Data(v1, v2, v3))) {
// CAS checks the value in data is still == to current
// if so it changes it to new Data and we can return
return;
}
// otherwise try again
}
}
}
</source>

Neat usage of immutability. The data that are supposed to be consistent are '''final''' in a ''Data'' class. The mutability is handled all at once with {{JDK|java/util/concurrent/atomic|AtomicReference}} ''compareAndSet'' method. Either it fails and the computation runs again or it succeeds and atomically changes the data to newly created and consistent value. No locks involved, hence the reference to [[LockFreeAlgorithm]]s. Let's call such a pattern [[TransactionalDataStructure]].

[[TransactionalDataStructure]] is a realization of [[LockFreeAlgorithm]]. The primary goal may be different than to (just) ''avoid locks'' however. The [[TransactionalDataStructure]] pattern can be used to build a reliable data structure that ''keeps consistency'' even under multi threaded access and can be easily reason about. To do so the data structure uses two important concepts:

* immutability (helps to reason about consistency)
* compare and swap (aka [[wikipedia::Compare-and-swap|CAS]]) operation (always selects just a single thread to perform an update)

Let's start with a code sample!

=== [[TransactionDataStructureExample|Example]] ===

{{:TransactionDataStructureExample}}

=== Trade CPU for no Locks! ===

[[LockFreeAlgorithm]]s avoid synchronization and rather prefer multiple threads to do (and potentially throw away) their work. This kind of ''trade CPU for no locks'' is exactly what [[TransactionalMemory]] tried to promise.
The mantra of ''"let the computation run and on commit verify"'' whether all inputs are still the same and only then write down the changed values, is exactly the [[TransactionalMemory|transactional]] approach.

Why the [[TransactionalMemory]] approaches failed so far? It is easy to do the [[wikipedia::Compare-and-swap|compare&swap]] with a single value, it is harder, but possible to do it with two values. With more values, it becomes almost impossible. Software [[TransactionalMemory]] doesn't restrict the amount of [[wikipedia::Compare-and-swap|CAS]] operations, so it is easy to get to the impractical scale of the problem.

I had to implement this kind [[wikipedia::Compare-and-swap|CAS]]-like check few times in [[NetBeans]]. For example here: https://github.com/apache/netbeans/blob/c22dbacda230435cec1c5067bf8ae6c359e15d55/platform/openide.util.lookup/src/org/openide/util/lookup/ProxyLookup.java#L434 however my problem wasn't performance (btw. the code still uses '''synchronized'''), but two other reasons:

===== [[deadlock|Never call 3rd party code with a lock]] =====

The [[deadlock|Never call 3rd party code with a lock]] mantra for framework designers (essential for designing [[deadlock]]-free [[API]]s) - to do that you have to read state ahead of doing any computation; if there is a need to perform a callback (to unknown code): make sure no lock is held when the callback returns enter the [[wikipedia::Compare-and-swap|CAS phase]] - e.g. check preconditions and update if they hold, just like [[TransactionalMemory]] would do

===== Re-entrancy =====

The [[Lookup]], {{NB|org-openide-util-lookup|org/openide/util/lookup|ProxyLookup}} code was so central in [[NetBeans]], that the critical section could appear multiple times on stack and the nested invocations could invalidate the read in input values! '''Locking doesn't help with re-entrant data structures at all''' - the only way is to use this transactional memory approach - read values in, do the computation, and [[wikipedia::Compare-and-swap|CAS]] or try again. Plus one has to ''"hope"'' that the data structure somehow '''stabilizes''' and nested calls don't invalidate the outer calls indefinitely (which was working well in the case of [[NetBeans]] [[Lookup]] library which gradually converged to more and more computed state).

== It's Cool to be Transactional! ==

The term [[TransactionalMemory]] isn't massively known these days. The software [[TransactionalMemory]] hype is over for years. No surprise [[Java]] (EE) developers know nothing about it. However majority of developers understands '''DB transactions'''. Thus explaining [[wikipedia::Compare-and-swap|CAS]] as a "transaction commit" may be natural to them. Moreover [[LockFreeAlgorithm]]s are still [[Good_Technology#Coolness|cool and in]]! Don't be afraid to use [[TransactionalDataStructure]]s! They make every code (not just an [[API]]) easier to reason about and robust for '''multithreaded access'''.

==== Used in Enso ====

* [[I]]'ve just created a pull request to turn [https://github.com/enso-org/enso/pull/13315/files#r2155192765 bindings map to fully transactional] data structure

[[Category:APIDesignPatterns]]

Finally, after all those years I had a reason to release new version of [[Bck2Brwsr]] with support for [[Html4Java|HTML/Java API]] version 1.8.1. It is [https://repo1.maven.org/maven2/org/apidesign/bck2brwsr/vm4brwsr/0.81/ out] as of July 1st, 2025.