Editing Software transactional memory (section)

== Performance ==
Unlike the [[Lock (computer science)|locking]] techniques used in most modern multithreaded applications, STM is often very [[Optimistic concurrency control|optimistic]]: a [[Thread (computing)|thread]] completes modifications to shared memory without regard for what other threads might be doing, recording every read and write that it is performing in a log. Instead of placing the onus on the writer to make sure it does not adversely affect other operations in progress, it is placed on the reader, who after completing an entire transaction verifies that other threads have not concurrently made changes to memory that it accessed in the past. This final operation, in which the changes of a transaction are validated and, if validation is successful, made permanent, is called a ''commit''. A transaction may also ''abort'' at any time, causing all of its prior changes to be rolled back or undone. If a transaction cannot be committed due to conflicting changes, it is typically aborted and re-executed from the beginning until it succeeds.

The benefit of this optimistic approach is increased concurrency: no thread needs to wait for access to a resource, and different threads can safely and simultaneously modify disjoint parts of a data structure that would normally be protected under the same lock.

However, in practice, STM systems also suffer a performance hit compared to fine-grained lock-based systems on small numbers of processors (1 to 4 depending on the application). This is due primarily to the overhead associated with maintaining the log and the time spent committing transactions. Even in this case performance is typically no worse than twice as slow.<ref>{{cite web |url=http://channel9.msdn.com/ShowPost.aspx?PostID=231495 |title=Programming in the Age of Concurrency: Software Transactional Memory |last=Peyton Jones |first=Simon |author-link=Simon Peyton Jones |website=Microsoft Developers Network: Channel 9 |access-date=2007-06-09}}</ref> Advocates of STM believe this penalty is justified by the conceptual benefits of STM.{{citation needed|date=December 2012}}

Theoretically, the [[worst case]] space and time complexity of ''n'' concurrent transactions is ''[[Big O notation|O]]''(''n''). Actual needs depend on implementation details (one can make transactions fail early enough to avoid overhead), but there will also be cases, albeit rare, where lock-based algorithms have better time complexity than software transactional memory.