5 ms·

This analogy is not a new idea, see "The transactional memory / garbage collection analogy" by Dan Grossman at OOPSLA 2007: https://dl.acm.org/doi/abs/10.1145/1

This analogy is not a new idea, see "The transactional memory / garbage collection analogy" by Dan Grossman at OOPSLA 2007: https://dl.acm.org/doi/abs/10.1145/1297027.1297080 https://dl.acm.org/doi/abs/10.1145/1297027.1297080 PDF available here: https://homes.cs.washington.edu/~djg/papers/analogy_oopsla07.pdf https://homes.cs.washington.edu/~djg/papers/analogy_oopsla07...

amelius 5y ago
> Transactional memory is currently one of the hottest topics in computer-science research, having attracted the focus of researchers in programming languages, computer architecture, and parallel programming, as well as the attention of development groups at major software and hardware companies. The fundamental source of the excitement is the belief that by replacing locks and condition variables with transactions we can make it easier to write correct and efficient shared-memory parallel programs. Has this research come to fruition? What languages/environments use such an approach today?
- twoodfin 5y ago
  It’s widely regarded as a dead end. Conceptually, it’s quite appealing so who knows, it might find new life someday. Garbage collection was a niche technology for decades, as was JIT compilation. Joe Duffy’s write-up on how STM failed at Microsoft with .NET is illustrative: http://joeduffyblog.com/2010/01/03/a-brief-retrospective-on-transactional-memory/ http://joeduffyblog.com/2010/01/03/a-brief-retrospective-on-...
  - PaulHoule 5y ago
    right... it's not hard to invent some scheme that scales to a 2 core computer but it is not crazy to have 64 or more cores these days and even if you have 2% serial overhead from communications you are not going to scale past 50. The problems of making a system really scale as opposed to just scale are bad enough that the best we know how to do is give people simpler primitives that work -- each layer you add to the system is another opportunity to add another limitation to it. Modern garbage collectors are fairly scalable (e.g. don't break outright as the heap size increases) and any manual memory management would also have the risk of scaling problems, to the point where you might say that garbage collection is more "scalable" when the thing being scaled is the kind of arbitrary complexity that appears in business applications. What people complain about with garbage collection are: (1) a fixed constant overhead they think is too high and will probably always think to high, (2) long pauses that are manageable in practice unless you are timing events with millisecond precision with a microcontroller. Thus one of these things is mainstream and other isn't.
    - twoodfin 5y ago
      Yeah. As is pointed out down-thread of the linked post, even when it was confined to a niche, garbage collection did what it claimed it would (eliminate the need for error-prone manual memory management) at an acceptable cost for many systems & applications. JITs were similar. So far, STM and HTM have followed a path more like VLIW instruction sets: Conceptually appealing for their promise of simplification, but in practice only demonstrating success in specialized uses, with the tradeoffs proving unattractive seemingly everywhere else they've been tried.
      - sitkack 5y ago
        I think it is a false equivalence to say that STM and HTM are like VLIW (which has been been a resounding success for DSP workloads). I am not defending VLIW. Transactions are extremely powerful conceptually, to be composable and not cause flapping requires a higher level of coordination.
    - tomp 5y ago
      > What people complain about with garbage collection are: (1) a fixed constant overhead they think is too high and will probably always think to high, (2) long pauses that are manageable in practice unless you are timing events with millisecond precision with a microcontroller. I keep hearing this about "modern" GC and it keeps being very much not true in practice. I'm running IntelliJ IDEA (Java) on a laptop with 8GB of RAM, and it keeps freezing every so often. I'm suspecting GC causing paging. This is something that is obviously avoided with reference counting or manual memory management.
      - jhgb 5y ago
        > This is something that is obviously avoided with reference counting You'd prefer your data being larger in memory due to refcount fields and slower to access due to atomic operations on those fields?
        tomp 5y ago
        It's not like tracing GC is without memory overhead... Slower is a question of priorities. I'd definitely trade off slower overall performance (I don't really need my IDE to be that performant... it's not like it's using 100% CPU, or even 10%!) but a huge improvement in latency (i.e. no catastrophic slowdowns / freezes).
- jasonwatkinspdx 5y ago
  Well, I'd say it's a bit muddled. Pure STM systems have seen limited success, mostly on the jvm, particularly clojure. But as a technology it's not spread widely in the industry, despite the fundamental advantage of composability. I personally would attribute this to a sort of gulf created by two common approaches: 1. It's become very common to structure software as a stateless service cluster backed by a stateful database technology. Most of the databases used in this approach would not be described as STM, but the net effect to the application is similar, even if involving more layers and complexity. 2. People have gotten pretty comfortable with simple mutex patterns connected by queues of various sorts. This is a sort of worse is better situation, where the simplicity and high performance of a mutex protected whatever in a toy test or microbenchmark is far more efficient than STM. However, a system composed of many of these mutex protected islands proves a whole different beast indeed. STM has largely been criticized from the perspective of the former, vs the latter. There are many people who have made the observation that transactional concurrency control, state of the art garbage collection, and even file systems have been converging on similar features. This is being driven by the common constrains on both sides of what hardware and humans expect. In particular with persistent memory, I think you'll see all three of these unify into a single design, because systems that attempt to solve these problems separately will have very inferior match to the hardware.
  - barrkel 5y ago
    I think trying to scale out compute + mutable state across multiple CPUs on a single box has somewhat fallen by the wayside outside of specialized applications like databases and distributed query engines, as a local maximum avoided in favour of scalability via more boxes. There's several forces behind this. Applications are more likely to be web-based or services - i.e. inherently distributed - and less likely to be desktop or traditional client/server, where almost all compute happened on a single server. As distributed services, maximizing statelessness and avoiding mutable shared memory is key to solving a lot of problems: scaling out (no shared memory), redundancy (keep a second copy of the application logic running somewhere, no sync required), recovery and idempotence (if something fails, try again until it succeeds - repeated attempts are safe). Reliable persistent queues are part of that. They let you bring services up and down and switch over without down time, or restart after a failure and resume where they left off. The problems of shared mutable state are best kept in specialized applications: databases, queuing systems, distributed caches, consistent key-value stores. Keeping state consistent in a distributed system is a genuinely hard problem, and STM isn't much help, except perhaps as an implementation detail in some of those specialized applications.
- The_rationalist 5y ago
  Tsx is disabled on rhel :/ https://www.phoronix.com/scan.php?page=news_item&px=Red-Hat-RHEL-8.3 https://www.phoronix.com/scan.php?page=news_item&px=Red-Hat-...
- cma 5y ago
  Hardware support is only very recent, Intel added support at various times and then had to remove it due to security and correctness issues, but I think it is now finally available: > Intel's Transactional Synchronization Extensions (TSX) is available in some of the Skylake processors. It was earlier implemented in Haswell and Broadwell processors as well, but the implementations turned out both times to be defective and support for TSX was disabled. The TSX specification describes the transactional memory API for use by software developers, but withholds details on technical implementation.[11] ARM architecture has a similar extension.[12] https://en.wikipedia.org/wiki/Transactional_memory https://en.wikipedia.org/wiki/Transactional_memory I believe even with it available, OSes turn it off because of all the other Intel vulnerabilities and it making them even more expensive to workaround.
- whateveracct 5y ago
  Haskell has wonderful STM in the stdlib and a pretty good collection of community libraries on top of that.
- pjlegato 5y ago
  Clojure famously makes extensive use of a software transactional memory (STM) to provide painless multithreading: * https://clojure.org/reference/refs https://clojure.org/reference/refs * https://sw1nn.com/blog/2012/04/11/clojure-stm-what-why-how/ https://sw1nn.com/blog/2012/04/11/clojure-stm-what-why-how/
  - fulafel 5y ago
    It kind of came and went in Clojure, not much code uses it today. In your second link, the linked followup post is also interesting as it captures some misunderstandings one might have when starting out with STM code.

amelius 5y ago

> Transactional memory is currently one of the hottest topics in computer-science research, having attracted the focus of researchers in programming languages, computer architecture, and parallel programming, as well as the attention of development groups at major software and hardware companies. The fundamental source of the excitement is the belief that by replacing locks and condition variables with transactions we can make it easier to write correct and efficient shared-memory parallel programs. Has this research come to fruition? What languages/environments use such an approach today?

twoodfin 5y ago
It’s widely regarded as a dead end. Conceptually, it’s quite appealing so who knows, it might find new life someday. Garbage collection was a niche technology for decades, as was JIT compilation. Joe Duffy’s write-up on how STM failed at Microsoft with .NET is illustrative: http://joeduffyblog.com/2010/01/03/a-brief-retrospective-on-transactional-memory/ http://joeduffyblog.com/2010/01/03/a-brief-retrospective-on-...
- PaulHoule 5y ago
  right... it's not hard to invent some scheme that scales to a 2 core computer but it is not crazy to have 64 or more cores these days and even if you have 2% serial overhead from communications you are not going to scale past 50. The problems of making a system really scale as opposed to just scale are bad enough that the best we know how to do is give people simpler primitives that work -- each layer you add to the system is another opportunity to add another limitation to it. Modern garbage collectors are fairly scalable (e.g. don't break outright as the heap size increases) and any manual memory management would also have the risk of scaling problems, to the point where you might say that garbage collection is more "scalable" when the thing being scaled is the kind of arbitrary complexity that appears in business applications. What people complain about with garbage collection are: (1) a fixed constant overhead they think is too high and will probably always think to high, (2) long pauses that are manageable in practice unless you are timing events with millisecond precision with a microcontroller. Thus one of these things is mainstream and other isn't.
  - twoodfin 5y ago
    Yeah. As is pointed out down-thread of the linked post, even when it was confined to a niche, garbage collection did what it claimed it would (eliminate the need for error-prone manual memory management) at an acceptable cost for many systems & applications. JITs were similar. So far, STM and HTM have followed a path more like VLIW instruction sets: Conceptually appealing for their promise of simplification, but in practice only demonstrating success in specialized uses, with the tradeoffs proving unattractive seemingly everywhere else they've been tried.
    - sitkack 5y ago
      I think it is a false equivalence to say that STM and HTM are like VLIW (which has been been a resounding success for DSP workloads). I am not defending VLIW. Transactions are extremely powerful conceptually, to be composable and not cause flapping requires a higher level of coordination.
  - tomp 5y ago
    > What people complain about with garbage collection are: (1) a fixed constant overhead they think is too high and will probably always think to high, (2) long pauses that are manageable in practice unless you are timing events with millisecond precision with a microcontroller. I keep hearing this about "modern" GC and it keeps being very much not true in practice. I'm running IntelliJ IDEA (Java) on a laptop with 8GB of RAM, and it keeps freezing every so often. I'm suspecting GC causing paging. This is something that is obviously avoided with reference counting or manual memory management.
    - jhgb 5y ago
      > This is something that is obviously avoided with reference counting You'd prefer your data being larger in memory due to refcount fields and slower to access due to atomic operations on those fields?
      - tomp 5y ago
        It's not like tracing GC is without memory overhead... Slower is a question of priorities. I'd definitely trade off slower overall performance (I don't really need my IDE to be that performant... it's not like it's using 100% CPU, or even 10%!) but a huge improvement in latency (i.e. no catastrophic slowdowns / freezes).
jasonwatkinspdx 5y ago
Well, I'd say it's a bit muddled. Pure STM systems have seen limited success, mostly on the jvm, particularly clojure. But as a technology it's not spread widely in the industry, despite the fundamental advantage of composability. I personally would attribute this to a sort of gulf created by two common approaches: 1. It's become very common to structure software as a stateless service cluster backed by a stateful database technology. Most of the databases used in this approach would not be described as STM, but the net effect to the application is similar, even if involving more layers and complexity. 2. People have gotten pretty comfortable with simple mutex patterns connected by queues of various sorts. This is a sort of worse is better situation, where the simplicity and high performance of a mutex protected whatever in a toy test or microbenchmark is far more efficient than STM. However, a system composed of many of these mutex protected islands proves a whole different beast indeed. STM has largely been criticized from the perspective of the former, vs the latter. There are many people who have made the observation that transactional concurrency control, state of the art garbage collection, and even file systems have been converging on similar features. This is being driven by the common constrains on both sides of what hardware and humans expect. In particular with persistent memory, I think you'll see all three of these unify into a single design, because systems that attempt to solve these problems separately will have very inferior match to the hardware.
- barrkel 5y ago
  I think trying to scale out compute + mutable state across multiple CPUs on a single box has somewhat fallen by the wayside outside of specialized applications like databases and distributed query engines, as a local maximum avoided in favour of scalability via more boxes. There's several forces behind this. Applications are more likely to be web-based or services - i.e. inherently distributed - and less likely to be desktop or traditional client/server, where almost all compute happened on a single server. As distributed services, maximizing statelessness and avoiding mutable shared memory is key to solving a lot of problems: scaling out (no shared memory), redundancy (keep a second copy of the application logic running somewhere, no sync required), recovery and idempotence (if something fails, try again until it succeeds - repeated attempts are safe). Reliable persistent queues are part of that. They let you bring services up and down and switch over without down time, or restart after a failure and resume where they left off. The problems of shared mutable state are best kept in specialized applications: databases, queuing systems, distributed caches, consistent key-value stores. Keeping state consistent in a distributed system is a genuinely hard problem, and STM isn't much help, except perhaps as an implementation detail in some of those specialized applications.
The_rationalist 5y ago
Tsx is disabled on rhel :/ https://www.phoronix.com/scan.php?page=news_item&px=Red-Hat-RHEL-8.3 https://www.phoronix.com/scan.php?page=news_item&px=Red-Hat-...
cma 5y ago
Hardware support is only very recent, Intel added support at various times and then had to remove it due to security and correctness issues, but I think it is now finally available: > Intel's Transactional Synchronization Extensions (TSX) is available in some of the Skylake processors. It was earlier implemented in Haswell and Broadwell processors as well, but the implementations turned out both times to be defective and support for TSX was disabled. The TSX specification describes the transactional memory API for use by software developers, but withholds details on technical implementation.[11] ARM architecture has a similar extension.[12] https://en.wikipedia.org/wiki/Transactional_memory https://en.wikipedia.org/wiki/Transactional_memory I believe even with it available, OSes turn it off because of all the other Intel vulnerabilities and it making them even more expensive to workaround.
whateveracct 5y ago
Haskell has wonderful STM in the stdlib and a pretty good collection of community libraries on top of that.
pjlegato 5y ago
Clojure famously makes extensive use of a software transactional memory (STM) to provide painless multithreading: * https://clojure.org/reference/refs https://clojure.org/reference/refs * https://sw1nn.com/blog/2012/04/11/clojure-stm-what-why-how/ https://sw1nn.com/blog/2012/04/11/clojure-stm-what-why-how/
- fulafel 5y ago
  It kind of came and went in Clojure, not much code uses it today. In your second link, the linked followup post is also interesting as it captures some misunderstandings one might have when starting out with STM code.