Transactional memory similarity to garbage collection
realworldtech.com
realworldtech.com
PDF available here: https://homes.cs.washington.edu/~djg/papers/analogy_oopsla07...
Has this research come to fruition? What languages/environments use such an approach today?
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-...
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.
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.
Transactions are extremely powerful conceptually, to be composable and not cause flapping requires a higher level of coordination.
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.
You'd prefer your data being larger in memory due to refcount fields and slower to access due to atomic operations on those fields?
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).
Also, most of the flaws of Java's memory management seem to be concentrated in the part of the language that says that almost everything has to be an object with a header and on the heap. Remove that and your graph of objects to trace shrinks very substantially.
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.
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.
Web applications aren't special in this regard. We've just normalized being incredibly wasteful of computing resources when designing them, spinning up huge clusters to serve a workload that could be easily satisfied with a single machine (or a few machines for availability).
Premature scale-out, because we've forgotten how to scale-up, is the root of much evil.
I am not free to name the product, but I worked on a product that has done billions of dollars in revenue that designed a bunch of state management checkpointing using a custom STM implementation for C (yes, C). It made so, so many things straightforward in terms of corner cases; we also extended transactionality to sync over the wire in some cases.
I also think STM-adjacent designs are gaining some traction - for example, FoundationDB looks an awful lot like an STM system from the point of view of applications, much more than it looks like a traditional database.
Basically, poor STM performance in .Net is too much mutation and mutation-induced logging. This is why clojure's STM is much more widely used.
I have particularly deep experience in various Haskell projects and I must insist that no relatively (1) big Haskell project (2) with a hint of concurrency and (3) developed by several people can go without use of STM.
I can use MVars myself for problem space discovery. When there are at least two of use, I will use TVar and insist others should too.
> 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
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.
* https://clojure.org/reference/refs * https://sw1nn.com/blog/2012/04/11/clojure-stm-what-why-how/
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.
The promise of transactional memory was that it composes and you only have to think about your data access and not have to worry about running into deadlocks.
There’s a lot of static analysis in the JVM that reduces locking, speeds up garbage collection, and removes the need to declare the type of a generic variable.
I expect over time we will see inference in borrow checkers reduce the brain cycles you need to spend thinking about these things, and borrow semantics will be “good enough” for a long time.
Or who knows, maybe STM systems will be able to infer borrow semantics and benefit from aggressive lock elision.
All of this structure doesn't exist in the memory. So you need transactions at the page level which is too crude, or the byte level which is too granular.
Hardware is simply the wrong level to solve this problem at. Unless the hardware starts understanding how we use memory way, way, way, way better than it does right now.