Talk:Software transactional memory

I've received some negative feedback about this article from friends. I'm currently researching the area and will improve it in the future. Deco 21:50, 3 February 2006 (UTC)

What exactly is wrong? countryhacker 20:55, 4 February 2006 (UTC)

Sorry for not answering, didn't see this. In short it was missing a lot of information, and the English was also a bit messy. I've rewritten it. I hope the original author is not offended - there's plenty of room for additional expansion still. Deco 23:47, 8 February 2006 (UTC)

KVD, February 2006: The article first mentions that STM has a performance disadvantage on a small number of processors, and then it goes on to say "in addition to its performance benefits, ...". This is a contradiction, or at least confusing. Is the net effect of STM a performance gain or performance loss? Or is there a minimal degree of concurrency (e.g. a minimal number of processors) beyond which STM becomes interesting?

As far as I remember, WORST case (when all but one transactions fail) is O(n) where n is number of concurrent processes. This is definitely not "twice". Maybe it does happen rarely in real world, but is worth mentioning anyway. countryhacker 09:24, 24 February 2006 (UTC)

It's a loss on small numbers of processors, but a gain on larger numbers. Sorry if the wording was unclear. You're right that the theoretical worst-case is considerably worse than the typical overhead observed in experiments. Deco 22:52, 19 June 2006 (UTC)

The link to DSTM2 seems to be a dead end, and I was unable to google it, either. Is this project dead? 82.130.103.206 (talk) 15:34, 11 August 2011 (UTC)

Implementation issues

Quoted from the article:

atomic { if (x != y) while (true) { } } Transaction A

atomic { x++; y++; } Transaction B

Provided x=y initially, neither transaction above alters this invariant, but it's possible transaction A will read x after transaction B updates it but read y before transaction B updates it, causing it to enter an infinite loop.

Hmmm - isn't it the point of transactions that the intermediate state "x == y+1" is NOT visible anywhere outside of transaction B? "Commit" is an atomic operation, isn't it??? --84.137.86.147 22:25, 4 March 2006 (UTC)

Sorry for the fuss. Now I understand that the situation can occur if the thread of transaction A first reads x, then is suspended (for any reason), then transaction B is run completely and finally A resumes and reads the value of y... --84.137.86.147 22:34, 4 March 2006 (UTC)

Right. The transaction A has read inconsistent state committed by transaction B, which prevents transaction A from committing successfully, but that doesn't mean it'll terminate. Deco 22:52, 19 June 2006 (UTC)

This isn't true for implementations that guarantee isolation (the I in ACID). E.g. if you use optimistic evaluation and store a transaction log, upon committing this log you would A) Ensure that no read variables have been updated by other transactions B) Ensure that none of the written to variables have been read by any ongoing transaction. This ensures that each transactions acts completely in isolation (conceptually). So if A reads x, then B runs completely, B would fail to commit because x has been read by the ongoing transaction A.

That's true. Whether or not this leads to nontermination depends on the specific implementation of STM. Deco 00:47, 9 January 2007 (UTC)

Since we are talking about TRANSACTIONAL memory, I guess a correct implementation must implement at least ACI (that is, ACID without the D) semantic. In an ACI context, the consistence problem documented in the page is not an issue. Somebody should edit that section out. Jcea 11:58, 9 January 2007 (UTC)

To what section are you referring? There is no consistence problem with any implementation of STM, including the one I originally described - if the transaction has read inconsistent state it will abort if it completes. The issue is nontermination, which necessitates a timeout. Deco 18:52, 9 January 2007 (UTC)

I'm talking about the section showing partial transactions (partial update states) visible to other processes. That section talks about seeing "impossible" states because of that. Since we are talking about "transactional" memory, a correct implementation would be ACI (ACID without the D) and so other concurrent threads should not see partially updated states. A "real" transactional memory implementation should detect the inconsistence when reading "stale" data, at that time, long time before the commit. Jcea 15:31, 10 January 2007 (UTC)

I find this entire section wrong: We are talking about transactional memory. By transaction definition, we have Atomicity and Independency, so the risk of reading "stale" data is not an issue. I delete the entire section Jcea 19:30, 26 January 2007 (UTC)

I have restored the section. The paper on which it is based specifically describes this scenario in very similar terms, and claims to implement a software transactional memory. If you contest this claim, then you need to take that up with the original authors. I've emphasized many times that the reading of stale data is possible only because reading is optimistic in this implementation, and no transaction having read such data ever commits. Not all STM implementations guarantee that stale data is never read, only that transactions reading it cannot succeed, which preserves the ACI properties. Deco 19:40, 26 January 2007 (UTC)

I added a small comment about "conflict" exceptions raising when reading/writing stale data. With this small change, I'm satisfied :-) Jcea 18:16, 2 April 2007 (UTC)

I'm afraid I had to delete this comment because it's not accurate - it seems that you're still missing the point. To check every access up front to see whether it's violating serializability would be prohibitively costly. The whole point of an optimistic approach is to delay this cost until commit time. Again, it does not matter if a transaction reads stale data, as long as that transaction is from then on unable to commit. This is not a small issue, it is fundamental to how optimistic reading works. Dcoetzee 18:00, 6 April 2007 (UTC)

I think that a better example would have Transaction B cause Transaction A to perform an illegal operation. The difficulty in such a situation is how to "roll back" A's incomplete transaction after the program has already executed an illegal instruction. For example:

atomic { z = x/y; } Transaction A

atomic { y = 0; x = 4; y = x - 2; } Transaction B

In this case, it is possible that executing B's transaction will not only force a concurrently-executing A transaction to be rolled back - but B could also cause A to perform an illegal (and usually fatal) divide-by-zero operation as well. Note that this divide-by-zero operation does not occur in any successful A transaction. —Preceding unsigned comment added by 69.181.119.118 (talk) 23:35, 12 December 2007 (UTC)

Implementations

What exactly qualifies an STM implementation as being "large-scale product-quality"? I know a number of people who are using Haskell/STM in a non-research (at least, not research on STM) context. In other news, Audrey-tan has incorporated STM into Perl 6. (Is this product-quality yet? Or large-scale enough?) Liyang 21:40, 19 June 2006 (UTC)

Honestly, I wasn't familiar with those implementations. The current claim might be misleading; feel free to edit it, but I personally wouldn't tell anyone that STM is ready for major software projects. Deco 22:52, 19 June 2006 (UTC)

Why is this the only place where I find Tom Knight as a pioneer? I read part of the paper and I agree but in several academic papers (even in Herlihy and Moss paper) and in the book Transactional Memory by Tim Harris, no one mentions him (it could be for my lack of search though). In the same book but on another matter, they point that in 77 Lomet describes transactional memories without an implementation, is this enough to include a reference? —Preceding unsigned comment added by 193.136.19.96 (talk) 13:42, 14 October 2010 (UTC)

How are commitments made atomic?

I don't have a comment, I just have a question, that might be answered here... well, I guess I better ask it here than on the main page... When a transaction commits, how does it make its "commitment" atomic to other threads, NOT currently in a transaction? Or should all accesses to objects possibly in a transaction check (that is, perform some kind of read-barrier - performance penalty)? Tom Primožič 19:10, 13 February 2007 (UTC)

Good question, and worth adding to the article. This varies by implementation, but usually involves some kind of "quick swap" of the object reference to point to the new version of the object. If multiple objects are involved, it may (again in some implemenations) be possible for a transaction to read incompatible state partway through the commit, but any transaction that does so will itself be doomed to abort, and so its behaviour is irrelevant. For this reason a read barrier is not needed. Deco 21:40, 13 February 2007 (UTC)

But the question is, what if there are some accesses (reading of fields of objects) that aren't enclosed in a transaction? I read that (some/most?) implementations impose no overhead on code outside of transactions. So, basically other code simply reads state, regardless of any transactions in progress/commitment. Besides, what if there are multiple references to the same object (as in ML, probably also Java)? This would require some kind of redirection/forwarding mechanism, which would again require a read barrier (everytime an object is accessed, you must check, whether your a few moments ago still valid reference was redirected by a commited transaction to a new version of that object.

You see, I'm not arguing here... I'm just wondering how do existing implementations deal with that. Furthermore, what about adding into the article that some implementations don't write and keep a log, but rather write to a copy of the object? It's not conceptually different, just implementation-wise... Tom Primožič, 21:59, 13 February 2007 (UTC)

I think I got the answer... I guess that transactions are only atomic to other transactions. However, the reads outside transactions are either not to be considered atomic (as they are out of transaction - but sometimes, it doesn't really matter: if (i > 5) { print "foobar\n"; } -> since i is only read once, it doesn't matter whether it's atomic or not) or are simply - wrong ( x++ is wrong, it should be atomic { x++ }} ) Tom Primožič, 8:21, 15 February 2007 (UTC)

Expansion coming

I've just gotten access to a more comprehensive and up-to-date reference regarding software transactional memory and I intend to expand the article based on it. Stay tuned. Dcoetzee 17:54, 6 April 2007 (UTC)

Transactional Locking

I added a section on transactional locking, which overcomes the problem mentioned in "implementation issues". I think this work by Dice, Shalev, Shavit defines the state of the art in STM.

Bartosz 20:20, 18 August 2007 (UTC)

Detecting failure to terminate

The article says "One way to deal with these issues is to detect transactions that ... fail to terminate and abort them cleanly"

I don't think that's possible with a Turing-complete computer language. http://en.wikipedia.org/wiki/Halting_problem.

The text should have more explanation, or be removed as a possible solution. Like, should atomic operations have a time limit, like a timeout of a select() call? —Preceding unsigned comment added by 62.163.31.210 (talk) 11:48, 1 October 2007 (UTC)

Quoting specific Patents undesirable

In section "Transactional locking" the author not only mentions (pending?) patents on STM but quotes from a specific patent, viz:

(Zhang et al. 2006[6]) is a US patent entitled "Software transaction commit order and conflict management" (which references CO US patent 5701480). Its abstract part is the following: <snip>

I would prefer that Wikipedia articles not quote patents directly unless it is the primary source on the matter. Patent law is strange: just by having seen some of the patent text on Wikipedia, if I write/use a STM, the patent holder may claim that I have 'knowingly infringed'. Don't know if there is a wiki policy on this but perhaps there should be...

The article also make many quite unsupported/unreferenced assertions, eg "Tens of STM articles and patents utilizing "commit order" have already been published."

Please excuse my lack of wiki markup language skills. — Preceding unsigned comment added by 121.214.116.38 (talk) 18:06, 31 August 2011 (UTC)

Commitment ordering

The neutrality of part of this page is disputed, as part of a wider discussion. See Talk:Commitment ordering and Wikipedia talk:WikiProject Computer science#User:Comps / Commitment ordering. —Ruud 14:34, 23 December 2011 (UTC)

No progress since 2011? 71.19.161.130 (talk) 20:16, 5 February 2015 (UTC)

External links modified

Hello fellow Wikipedians,

I have just added archive links to one external link on Software transactional memory. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

• Added archive https://web.archive.org/20080601163025/http://www.hackshack.de:80/tarifa/ to http://www.hackshack.de/tarifa/

When you have finished reviewing my changes, please set the checked parameter below to true to let others know.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 19:23, 12 February 2016 (UTC)

Transactional Locking II Paper Link

It's dead and not archived as far as I can tell, so I have marked it as such. I found a copy at https://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/Transactional_Locking.pdf, BUT I don't know if that's a legal (re copyright and friends) publication of it or if that matters. 86.145.226.161 (talk) 12:13, 25 September 2019 (UTC)