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

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

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

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

== 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|free, cool and in]]! Don't be afraid to use [[TransactionalDataStructure]]s! They make every code (not just [[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 [[API]]) easier to reason about and robust for '''multithreaded access'''.

[[Category:APIDesignPatterns]]

[[Category:APIDesignPatterns]]

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:

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

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