TransactionDataStructureExample - Revision history

JaroslavTulach at 09:40, 7 June 2025

JaroslavTulach — Sat, 07 Jun 2025 09:40:07 GMT

←Older revision		Revision as of 09:40, 7 June 2025
Line 43:		Line 43:

	if (data.compareAndSet(current, new Data(v1, v2, v3))) {		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;		return;
	}		}
		+	// otherwise try again
	}		}
	}		}

JaroslavTulach at 09:38, 7 June 2025

JaroslavTulach — Sat, 07 Jun 2025 09:38:29 GMT

←Older revision		Revision as of 09:38, 7 June 2025
Line 4:		Line 4:
	* Use ''compare and swap'' operation to ''transactionally'' (hence the similarity with [[TransactionalMemory]]) update the state of the object		* 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		* repeat everything again if there was a clash
-	* and the ~~```~~current~~```~~ value was modified by some other thread meanwhile	+	* and the '''current''' value was modified by some other thread meanwhile

JaroslavTulach at 09:37, 7 June 2025

JaroslavTulach — Sat, 07 Jun 2025 09:37:59 GMT

←Older revision		Revision as of 09:37, 7 June 2025
Line 1:		Line 1:
	Let's keep the internal data in a dedicated immutable structure called '''Data'''. When performing an update:		Let's keep the internal data in a dedicated immutable structure called '''Data'''. When performing an update:
-	* Read ~~its~~ current state.	+	* Read the '''current''' state.
-	* Compute an update.	+	* 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		* 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		* repeat everything again if there was a clash

JaroslavTulach at 09:37, 7 June 2025

JaroslavTulach — Sat, 07 Jun 2025 09:37:29 GMT

←Older revision		Revision as of 09:37, 7 June 2025
Line 1:		Line 1:
-	Let's keep the internal data in a dedicated immutable ~~object~~ called '''Data'''. Read its current state. Compute an update. ~~Let's use~~ ''compare and swap'' operation to ''transactionally'' (hence the similarity with [[TransactionalMemory]]) update the state of the object or repeat everything again if there was a clash ~~with~~ some other thread:	+	Let's keep the internal data in a dedicated immutable structure called '''Data'''. When performing an update:
		+	* Read its current state.
		+	* Compute an update.
		+	* 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

JaroslavTulach at 09:34, 7 June 2025

JaroslavTulach — Sat, 07 Jun 2025 09:34:41 GMT

←Older revision		Revision as of 09:34, 7 June 2025
Line 22:		Line 22:
	}		}

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

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

JaroslavTulach at 07:10, 7 June 2025

JaroslavTulach — Sat, 07 Jun 2025 07:10:50 GMT

←Older revision		Revision as of 07:10, 7 June 2025
Line 31:		Line 31:
	current = data.get();		current = data.get();

-	int r1 = combine(current.value1, current.value2);	+	// the following three operations must be performed in a "transaction" ...
-	int r2 = combine(current.value2, current.value3);	+	int v1 = combine(current.value1, current.value2);
-	int r3 = combine(current.value3, current.value1);	+	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(r1, r2, r3))) {	+	if (data.compareAndSet(current, new Data(v1, v2, v3))) {
	return;		return;
	}		}

JaroslavTulach at 16:49, 6 June 2025

JaroslavTulach — Fri, 06 Jun 2025 16:49:07 GMT

←Older revision		Revision as of 16:49, 6 June 2025
Line 43:		Line 43:
	</source>		</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 ~~this~~ pattern [[TransactionalDataStructure]].	+	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]].

JaroslavTulach at 16:47, 6 June 2025

JaroslavTulach — Fri, 06 Jun 2025 16:47:38 GMT

←Older revision		Revision as of 16:47, 6 June 2025
Line 43:		Line 43:
	</source>		</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 [[~~wikipedia::Lock free algorithm~~]]. Let's call such this pattern [[TransactionalDataStructure]].	+	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 this pattern [[TransactionalDataStructure]].

JaroslavTulach at 16:28, 6 June 2025

JaroslavTulach — Fri, 06 Jun 2025 16:28:08 GMT

←Older revision		Revision as of 16:28, 6 June 2025
Line 43:		Line 43:
	</source>		</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. Let's call such this pattern [[TransactionalDataStructure]].	+	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 [[wikipedia::Lock free algorithm]]. Let's call such this pattern [[TransactionalDataStructure]].

JaroslavTulach at 16:24, 6 June 2025

JaroslavTulach — Fri, 06 Jun 2025 16:24:52 GMT

←Older revision		Revision as of 16:24, 6 June 2025
Line 1:		Line 1:
-	Let's keep the internal data a ~~special~~ immutable object. Let's use ''compare and swap'' operation to ''transactionally ~~update~~'' the state of the object or ~~recompute~~ everything again:	+	Let's keep the internal data in a dedicated immutable object called '''Data'''. Read its current state. Compute an update. Let's use ''compare and swap'' operation to ''transactionally'' (hence the similarity with [[TransactionalMemory]]) update the state of the object or repeat everything again if there was a clash with some other thread: