[[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)

==== 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]]

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'''.

[[Category:APIDesignPatterns]]

[[Category:APIDesignPatterns]]

[[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)

===== 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! ==

===== 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! ==

===== [[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 =====

[[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)

[[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!

* 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)

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

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