TransactionalDataStructure - Revision history

JaroslavTulach at 19:19, 3 April 2026

2026-04-03T19:19:27Z

←Older revision		Revision as of 19:19, 3 April 2026
Line 1:		Line 1:
-	[[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:	+	[[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 reasoned about. To do so the data structure uses two important concepts:

	* immutability (helps to reason about consistency)		* immutability (helps to reason about consistency)

JaroslavTulach: /* Used in Enso */

2025-06-18T18:05:32Z

Used in Enso

←Older revision		Revision as of 18:05, 18 June 2025
Line 33:		Line 33:
	==== Used in Enso ====		==== Used in Enso ====

-	* [[I]]'ve just ~~create~~ a pull request to turn [https://github.com/enso-org/enso/pull/13315/files#r2155192765 bindings map to fully transactional] data structure	+	* [[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]]		[[Category:APIDesignPatterns]]

JaroslavTulach: /* It's Cool to be Transactional! */

2025-06-18T18:05:23Z

It's Cool to be Transactional!

←Older revision		Revision as of 18:05, 18 June 2025
Line 31:		Line 31:
	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'''.		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 create a pull request to turn [https://github.com/enso-org/enso/pull/13315/files#r2155192765 bindings map to fully transactional] data structure

	[[Category:APIDesignPatterns]]		[[Category:APIDesignPatterns]]

JaroslavTulach at 06:55, 7 June 2025

2025-06-07T06:55:25Z

←Older revision		Revision as of 06:55, 7 June 2025
Line 1:		Line 1:
-	[[TransactionalDataStructure]] is a realization of [[LockFreeAlgorithm]]. The primary goal may 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:	+	[[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)		* immutability (helps to reason about consistency)

JaroslavTulach: /* Re-entrancy */

2025-06-06T17:42:51Z

Re-entrancy

←Older revision		Revision as of 17:42, 6 June 2025
Line 25:		Line 25:
	===== Re-entrancy =====		===== 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 in [[NetBeans]] [[Lookup]] library which gradually converged to computed state).	+	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! ==		== It's Cool to be Transactional! ==

JaroslavTulach: /* Re-entrancy */

2025-06-06T17:42:15Z

Re-entrancy

←Older revision		Revision as of 17:42, 6 June 2025
Line 25:		Line 25:
	===== Re-entrancy =====		===== 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 the case in [[NetBeans]] [[Lookup]] library).	+	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 in [[NetBeans]] [[Lookup]] library which gradually converged to computed state).

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

JaroslavTulach: /* Never call 3rd party code with a lock */

2025-06-06T17:40:45Z

Never call 3rd party code with a lock

←Older revision		Revision as of 17:40, 6 June 2025
Line 21:		Line 21:
	===== [[deadlock\|Never call 3rd party code with a lock]] =====		===== [[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 ~~in critical section under a lock~~; if there is a need to perform a callback (to unknown code): ~~leave the~~ lock ~~and~~ when the callback returns enter the ~~critical section again,~~ check preconditions and update if they hold, just like ~~in the~~ [[TransactionalMemory]] ~~case.~~	+	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 =====		===== Re-entrancy =====

JaroslavTulach at 17:36, 6 June 2025

2025-06-06T17:36:04Z

←Older revision		Revision as of 17:36, 6 June 2025
Line 1:		Line 1:
-	[[TransactionalDataStructure]] is a realization of [[LockFreeAlgorithm]]. The primary goal may different ~~that~~ to ''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:	+	[[TransactionalDataStructure]] is a realization of [[LockFreeAlgorithm]]. The primary goal may 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)		* immutability (helps to reason about consistency)

JaroslavTulach at 17:30, 6 June 2025

2025-06-06T17:30:35Z

←Older revision		Revision as of 17:30, 6 June 2025
Line 1:		Line 1:
-	[[TransactionalDataStructure]] is a realization of [[LockFreeAlgorithm]]. The primary goal is ''~~not to~~ avoid locks''~~, but~~ 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:	+	[[TransactionalDataStructure]] is a realization of [[LockFreeAlgorithm]]. The primary goal may different that to ''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)		* immutability (helps to reason about consistency)
-	* compare and swap (aka [[wikipedia::Compare-and-swap\|CAS]]) operation (selects a single thread to perform an update)	+	* 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!		Let's start with a code sample!

JaroslavTulach at 17:10, 6 June 2025

2025-06-06T17:10:20Z

←Older revision		Revision as of 17:10, 6 June 2025
Line 3:		Line 3:
	* immutability (helps to reason about consistency)		* immutability (helps to reason about consistency)
	* compare and swap (aka [[wikipedia::Compare-and-swap\|CAS]]) operation (selects a single thread to perform an update)		* compare and swap (aka [[wikipedia::Compare-and-swap\|CAS]]) operation (selects a single thread to perform an update)
		+
		+	Let's start with a code sample!

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