Performance
Unlike the locking techniques used in most modern multithreaded applications, STM is very optimistic: a 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. Advocates of STM believe this penalty is justified by the conceptual benefits of STM.
Theoretically, the worst case space and time complexity of n concurrent transactions is 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.
Read more about this topic: Software Transactional Memory
Famous quotes containing the word performance:
“True balance requires assigning realistic performance expectations to each of our roles. True balance requires us to acknowledge that our performance in some areas is more important than in others. True balance demands that we determine what accomplishments give us honest satisfaction as well as what failures cause us intolerable grief.”
—Melinda M. Marshall (20th century)
“Nobody can misunderstand a boy like his own mother.... Mothers at present can bring children into the world, but this performance is apt to mark the end of their capacities. They can’t even attend to the elementary animal requirements of their offspring. It is quite surprising how many children survive in spite of their mothers.”
—Norman Douglas (1868–1952)
“The child to be concerned about is the one who is actively unhappy, [in school].... In the long run, a child’s emotional development has a far greater impact on his life than his school performance or the curriculum’s richness, so it is wise to do everything possible to change a situation in which a child is suffering excessively.”
—Dorothy H. Cohen (20th century)