10 ms·
Ditch your mutex, you deserve better
- scottmas 11mo agoSo cool! Any languages support STM first class besides Haskell?
- cosmic_quanta 11mo agoI think a decade ago or so, people started trying to integrate STM in Pypy
- vijaysharma12 11mo agoI believe Clojure has first class support for STM.
- CGamesPlay 11mo agoLooks like somebody made a Rust experiment back when Rust was new: https://docs.rs/stm/latest/stm/ https://docs.rs/stm/latest/stm/
- lmm 11mo agoScala has great STM in the same way (monad-based).
- LelouBil 11mo agoNot "first class" but pretty good in Kotlin https://arrow-kt.io/learn/coroutines/stm/ https://arrow-kt.io/learn/coroutines/stm/
- spencerflem 11mo agoThe new Verse lang by Epic Games & a core Haskell contributor has a lot of transaction features. I don’t know if it’s exactly the same as STM though.
- andersa 11mo agoVerse only supports single-threaded transactional memory. Epic hasn't yet demonstrated that their approach can actually scale to be used from multiple threads in a useful manner, though they claim that it will.
- stackghost 11mo agoThere are c++ libraries that offer it.
- hackingonempty 11mo agoScala supports it with for-comprehensions which are equivalent to Haskell's do-notation but STM is not part of the Scala standard library. Zio and Cats Effect are two popular Scala effects systems with STM.
- vinkelhake 11mo agoThis felt like a blast from the past. At a few times reading this article, I had to go back and check that, yes, it's actually a new article from the year 2025 on STM in Haskell and it's even using the old bank account example. I remember 15 or 20 years (has it been that long?) when the Haskell people like dons were banging on about: 1) Moore's law being dead, 2) future CPUs will have tons of cores, and 3) good luck wrangling them in your stone age language! Check out the cool stuff we've got going on over in Haskell!
- VBprogrammer 11mo agoYeah, I wrote an essay on STM in Haskell for a class back in 2005 I think.
- lmm 11mo agoYeah, remember when we used to care about making better programming languages that would perform faster and avoid errors, instead of just slapping blockchains or AI on everything to get VC money. Good times.
- doliveira 11mo agoOnly half-joking: maybe Java was a mistake. I feel like so much was lost in programming language development because of OOP...
- exasperaited 11mo agoJava is most of why we have a proliferation of VM-based languages and a big part of why WASM looks the way it does (though as I understand it, WASM is the shape it is in some measure because it rejects JVM design-for-the-language quirks). I would also not blame Java for the worst of OO, all of that would have happened without it. There were so many OO culture languages pretending to that throne. Java got there first because of the aforementioned VM advantage, but the core concepts are things academia was offering and the industry wanted in non-Ada languages. I would say Java also had a materially strong impact on the desire for server, database and client hardware agnosticism. Some of this is positive reinforcement: Java demonstrates that it's better if you don't have to worry about what brand your server is, and JDBC arguably perfected ODBC. Some of it is negative: a lot of the move to richer client experiences in the browser has to do with trying to remove client-side Java as a dependency, because it failed. It's not the only bridged dependency we removed, of course: Flash is equally important as a negative.
- qprofyeh 11mo ago@OP perhaps there’s a comparison bug in withdraw(): if (a.balance <= amount)
- kubanczyk 11mo agoI've caught unbalanced parens: forkIO (atomically (transfer req.from req.to req.amount)
- DeathArrow 11mo agoWhen working with high throughput concurrent code like consumer producer pipelines, it's better to avoid shared mutable state entirely. Something actor like fits better and C# or Go channels works wonders.
- IshKebab 11mo agoSure, but sometimes shared mutable state is better, especially from a performance point of view. For example blurring an image.
- janetpacker 11mo agoIsn't that a typical case where you don't have to share anything? Divide the image into N chunks, let N threads handle each one, no sharing, just need a single sync point at the end to wait on completion.
- kreetx 11mo agoAccount balance is necessarily a shared mutable state.
- tlb 11mo agoIt's not necessarily shared. You could assign a single thread to own the account balances, reading requests from a message queue. That probably scales better than locking. A single thread can do several million transactions per second, more than the entire global financial system.
- xmcqdpt2 11mo agoAnd in a green threading system like Go or Scala Cats, the balances thread isn’t a thread at all, and it will run in the same thread as the transfer caller when the call isn’t contended, so you don’t even have a context switch.
- kreetx 11mo agoWhat if you want to compose an action on a balance with something else? (That is what the OP is about) Also, with a queue, you've moved the shared state elsewhere, namely, into the queue.
- Nican 11mo agoThis is a nice article, and I appreciate the examples. The next problem to solve is how to persist state on disk across two different accounts after a transfer has been done.
- juliangmp 11mo agoI found that a lot of the problems I had been having with mutexes, stem from the fact that traditionally the mutex and the data it protects are separate. Bolting them together, like Rust's Mutex<T> does, solves a lot these problems. It let's you write normal, synchronous code and leave the locking up to the caller, but without making it a nightmare. You can't even access the data without locking the mutex. This isn't an attack on the (very well written) article though. Just wanted to add my two cents.
- mgaunard 11mo agoI find it better to model that as an Actor than a mutex, but I guess it's inherently the same thing, except the actor also allows asynchronous operations.
- gpderetta 11mo agoYou can go full circle and also make operations on a mutex asynchronous. Hence the realization that message passing and shared memory are truly dual.
- mgaunard 11mo agoThe very idea of a mutex is that it is synchronous. You wait until you can acquire the mutex. If it's asynchronous, it's not a mutex anymore, or it's just used to synchronously setup some other asynchronous mechanism.
- stackghost 11mo ago>Ugh, a correct transfer function should conceptually just be the composition of our well encapsulated withdraw and a deposit functions, but defining it correctly has forced us to remove the locking from both withdraw and deposit, making both of them less safe to use. I know OOP isn't cool any more, but the above is what OOP solves. TFA's transfer() and withdraw() functions aren't compliant with double-entry accounting anyways, so you'd mark them private and only expose Transfer to callers. Let the class handle its own details.
- mrkeen 11mo ago> I know OOP isn't cool any more, but the above is what OOP solves. The article was a lengthy explanation of why the problem occurs in non-STM settings. In OO settings. What do you propose as an OO solution?
- kragen 11mo agoOOP does not provide any help in solving the problem in question, and indeed encapsulation is a major obstacle to solving it. I think you haven't understood what problem is being discussed.
- mgaunard 11mo agotl;dr mutexes are evil because they don't compose, STM is the solution because it does compose, otherwise just avoid shared state, or even state entirely. Not anything that's not already covered in any undergraduate CS course.
- kreetx 11mo agoWhich CS course did you go to?
- mgaunard 11mo agoYou made me check the programme of many university courses. Most parallel programming courses are at Masters level and require specialization, but those are much more advanced (sorting networks, distributed computing on supercomputers and GPU, consensus algorithms, parallelization of linear solvers...) There are undergraduate courses that cover simple things like multithreading patterns in mainstream languages, but it seems they are only available if you go to an education institution with both a practical mindset and a firm grip of the fundamentals, which is unfortunately quite rare, as most institutions tend to specialize in one or the other.
- pessimizer 11mo agoDuring my undergrad this stuff was heavily covered in my Intro to Operating Systems class. But that was 20 years ago, may be different now.
- foota 11mo agoI've found it interesting to think about trying to adopt data structures like CRDT designed for distributed systems to the problem of local consistency between CPU-local data structures spread across cores for parallelism.
- sebstefan 11mo ago>STM is an optimistic concurrency system. This means that threads never block waiting for locks. Instead, each concurrent operation proceeds, possibly in parallel, on their own independent transaction log. Each transaction tracks which pieces of data it has accessed or mutated and if at commit time it is detected that some other transaction has been committed and altered data which this transaction also accessed, then the latter transaction is rolled back and is simply retried. I already foresaw (and it gets mentioned later), the problem that if you have many small, frequent operations, they will prevent a big, long operation from happening because they will always change the state and cause conflicts before the big one can finish. You can easily code yourself an app that will softlock forever. The post doesn't offer a good solution (it talks about one where there's a tradeoff, but you don't need tradeoffs for this) The way this gets fixed it is to make the lock acquisition (or in this case, the priority of the merge?) preemptive (Wound-Wait) All transactions have a global, ever incrementing number attached to them, their ID, which we call "seniority", if you try to get a a lock, and the lock is held by a transaction with a lower seniority (=> a higher ID), you kill the transaction, take the lock, and once you're done the transaction you killed is allowed to retry In the meantime, if a transaction with the lower seniority tries to get the lock, it gets blocked This insures that your program will always finish. In the case of "lots of frequent small transactions" + "one big, long report", the report will get killed a few times, until your report inevitably becomes the most senior transaction to ask for this resource, and is allowed to complete.
- internet_points 11mo agohttps://old.reddit.com/r/haskell/comments/1oujfmi/mutexes_suck_a_love_letter_to_stm/nou6o4h/ https://old.reddit.com/r/haskell/comments/1oujfmi/mutexes_su... apparently "optimistic" glosses over some details
- yencabulator 11mo agoFrom the link: > That ensures a function can't run forever if it's already clear it can't finish without a conflict. That just makes them bail out quicker, it doesn't help them ever succeed.
- 11mo ago
- timeon 11mo ago> If the programmer forgets to lock the mutex the system won't stop them from accessing the data anyways, and even then there's no actual link between the data being locked and the lock itself, we need to trust the programmers to both understand and respect the agreement. A risky prospect on both counts. Not every language is like that. I would not use language (that allows this) for parallel programming. You can use other ways but how can you guarantee everyone who will edit the code-base will not use unenforced mutex?
- philippta 11mo agoThe fundamental problem here is shared memory / shared ownership. If you assign exclusive ownership of all accounting data to a single thread and use CSP to communicate transfers, all of these made up problems go away.
- torginus 11mo agoCSP suffers from backpressure issues (which is not to say its bad, but it's not a panacea either)
- mrkeen 11mo agoYes, multithreaded problems go away on a single thread. Is there any way for an external thread to ask (via CSP) for the state, think about the state, then write back the new state (via CSP)? If so, you're back to race conditions - with the additional constraints of a master thread and CSP.
- philippta 11mo agoThat would be shared ownership again.
- mrkeen 11mo agoSo then I would sell STM to you from the "other end". Everyone else has multiple threads, and should replace their locks with STM for ease and safety. You've got safe single-thread and CSP, you should try STM to gain multithreading and get/set.
- gpderetta 11mo agoThis is equivalent of using a single global lock (and STM is semantically equivalent, just theoretically more scalable). It obviously works, but greatly limits scalability by serializing all operations. Also in practice the CSP node that is providing access control is effectively implementing shared memory (in an extremely inefficient way). The fundamental problem is not shared memory, it is concurrent access control. There's no silver bullet.
- icar 11mo agoI would've enjoyed if the solution was proposed in Go as well.
- WhyNotHugo 11mo agoIndeed, “Software Transactional Memory” sounds like a magic black box. It feels a bit like reading “just use an sql database and transactions”. It’s not really telling me how the problem is solved, just to use someone else’s solution without understating how it’s implemented.
- internet_points 11mo agohttps://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/2005-ppopp-composable.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
- garethrowlands 11mo agoSTM isn't really used in Go like it is in Haskell. Here's the example from a Go STM package that's based on Haskell STM. It has gotchas that you won't encounter in Haskell though, due to the nature of these languages. https://github.com/anacrolix/stm/blob/master/cmd/santa-example/main.go https://github.com/anacrolix/stm/blob/master/cmd/santa-examp... For the equivalent Haskell, check out the link at the top of the file.
- torginus 11mo agoI wonder what happened to hardware transactional memory. Your CPU caches already keep track of which core is keeping which line in its cache and whether they have modified it via the MESI protocol: https://en.wikipedia.org/wiki/MESI_protocol https://en.wikipedia.org/wiki/MESI_protocol So it has most of the hardware to support transactional memory, only it's not exposed to the user. Intel had their own version, but it turned out it was buggy, so they disabled it and never put it in any subsequent CPU so that was that.
- agalunar 11mo ago> A data race occurs any time two threads access the same memory location concurrently and non-deterministically when at least one of the accesses is a write. From what I understand of the C++ memory model (shared by C and Rust), this is not the definition of data race – a data race occurs when two or more threads access memory concurrently where at least one access is a write and the accesses are unsynchronized. However, synchronized accesses may not have a deterministic ordering, in which case a race condition occurs. (Confusing as it may be, I believe this is standard terminology.)
- Surac 11mo agoc# offers a very convinient way to pack data access and locking into one thing. the "lock" instruction. it does hover not let you lock more that one "resource" at a time.
- mrkeen 11mo agoAll of the "my non-Haskell language does this" comments in the thread are the same (with maybe a Rust exception). The "lock" instruction is what the article is telling you to ditch. > If the programmer forgets to lock the mutex the system won't stop them from accessing the data anyways If the programmer forgets to "lock" > and even then there's no actual link between the data being locked and the lock itself lock (thing) { return thing.contents // shared, mutable array given out freely to the world } 'contents' has no notion that it has anything to do with this "lock"ing thing.
- Surac 11mo agoOK, seems my english was not enough to see the point. after reading this clear explantation is have to agree with you 100%
- deleted 11mo ago[deleted]
- nerdralph 11mo agoIt is rather long-winded, and ends with a donation request. I don't like that style of writing.
- gpderetta 11mo agoIn C++ (with a bit of help from boost). bool transfer(boost::synchronized<Account>& sync_from, boost::synchronized<Account>& sync_to, int amount) { auto [from, to] = synchronize(sync_from, sync_to); if (from->withdraw(amount)) { to->deposit(amount) return true; } else { return false } } Hopefully synchronized will make it into the standard library at some point, in the meantime it is not terribly hard to write it yourself if you do not want a boost dependency.
- xmcqdpt2 11mo agoDoes this avoid the dining philosopher deadlock?
- gpderetta 11mo agoyes, 'synchronize' uses a try_lock/backoff algorithm, same as std::scoped_lock. edit: it could theoretically livelock, but I believe most if not all STM implementations also do not guarantee forward progress.
- kragen 11mo agoPurely optimistic STM implementations that abort transactions early and don't permit other transactions to read uncommitted data can guarantee forward progress, and I believe that both Haskell's STM and Fraser and Harris's STM do, though I could easily be mistaken about that.
- gpderetta 11mo agoProbably you are right. I vaguely remembered the "Why Transactional Memory Should Not Be Obstruction-Free" paper, but I might have misunderstood or forgotten what it meant (the implementation can be non obstruction-free, but it doesn't mean it can live-lock).
- 11mo ago
- psychoslave 11mo ago>Moore's law is dying, beefy single cores are no longer keeping up. On the other hand, there are many other things that could be done to avoid wasting all the extra power gained over the years which don't even require any parallelism boost.
- kragen 11mo agoMaybe, but on a 64-core machine, a single-threaded task can't even use 2% of the computer. Even interpreted Python wastes only 97% of the computer.
- kragen 11mo agoI've been excited about STMs since I read "Composable Memory Transactions" back in 02005, shortly before it was published, and I still believe in the glorious transactional future, but it's difficult to adopt an STM piecemeal; it kind of wants to own your entire program, the same way that garbage collection or nonblocking I/O do, and more so than multithreading with locks. You kind of have to commit entirely to an STM. The efforts in C# to adopt an STM ending around 02010 were a disaster as a result. The article says a couple of things about STMs that are not true of STMs in general, just true of the Haskell STM the author is familiar with, like a small Brazilian child confidently telling you that almost everyone speaks Portuguese. One of these is, "STM is an optimistic concurrency system." The possibility of making your concurrency 100% lock-free is one of the most appealing things about STMs, and I think it could be a key to solving the UI latency problem, which just keeps getting worse and worse. Actors and CSP don't normally help here; an Actor is just as "blocking" as a lock. But you can implement an STM with partly pessimistic concurrency, or purely pessimistic, and it might even be a good idea. Another is, "One last benefit of STM which we haven't yet discussed is that it supports intelligent transaction retries based on conditions of the synchronized data itself." This was an innovation introduced by "Composable Memory Transactions", and many STMs do not support it, including Keir Fraser's awesomely fast version. I am even less certain that it is the correct tradeoff for all uses than I am about purely optimistic synchronization. But all of this is why I'm rereading Gray and Reuter's Transaction Processing right now after 25 years. With the benefit of 35 years of hindsight, it's a frustrating mix of inspiring long-range vision and myopic boneheadedness. But it shares a lot of hard-won wisdom about problems like long transactions that pop up in a new guise in STMs.
- isuckatcoding 11mo agoIt kind of threw me off that we went from golang to Haskell so would love to see they bank example actually comeback full circle to golang
- nlitened 11mo agoI think STM looks pretty cool in toy examples, but in practice it's pretty bad. Very difficult for me to make strong logical argument about this, just based on how it feels. In Clojure, there are first-class STM primitives with retriable transactions in the standard lib, but every time I tried to use them, the code was slow, difficult to reason about, full of "colored" functions, and non-composable. Also, unintuitively, the code starts immediately smelling slightly "wrong", as if I tried to put into code my first childish thoughts instead of actually thinking about how the system _should_ work. Like the notorious bank accounts example: yeah, cool, two accounts' balances are TVars — but what if I have 10M accounts? Is the list of accounts also a TVar since sometimes new accounts are created? Are indexes on the list also TVars? How do you persist the lists, how do you synchronize slow persistence and in-memory transactions? How do you synchronize all the deposits with a backup/failover machine? As you continue trying to untangle all this with STM, you start drowning in complexity, and encountering huge contention among transactions touching many parts of your systems, and spewing countless retry logs. It's not only my own experience — I believe it's widely accepted in Clojure community that nobody actually uses STM, and instead uses simple atomic updates or queues.
- blandflakes 11mo agoI have a similar experience, though it's not necessarily related to shortcomings in the STM implementation (which I always felt was quite competent in the space). To expand, I think a few things are true: 1. I've come to feel that actually managing concurrency is a "below the fold" competency for most engineers. I'm not saying it should be, and people need to understand what a data race is. 2. As you pointed out, most state in services that I work on is not in need of coordinated updates, so atoms are where you want to be, or single-writer queues. 100% agreed 3. Structured concurrency approaches, fibers, and other abstracted runtimes seem to be the best way to get concurrent and parallel work, given points 1 and 2 about how coordinated state really isn't that common for most work on my team A lot of times when we're updating state we're more having to think about it in the database, employing either a last-write-wins strategy or when coordination is in need, some form of pessimistic or optimistic locking.
- kragen 11mo agoThanks, this is very valuable! Have you tried other implementations of STM such as Haskell's?
- tonymet 11mo agoA nice trick in go is embedding sync.mutex into any type eg account.Lock() / Unlock()
- bluGill 11mo agoShared data is hard no matter what you do. Parallelism and shared data do not mix. STM makes some things easier, but you still will run into problems if you have a lot of it. You must design your code such that you spend a lot of CPU cycles doing single thread no shared data calculations between every place where you need to share data. If you can't do that you can't do parallelism. When there are only a few places where data needs to be shared a mutexs works since you put your best programmer on maintaining just that code and with only a few places they can figure out it. You can also make a variable atomic, which sometimes works better than a mutex and sometimes worse. You can use STM. However no matter what you use the reality of synchronizing between cores means you can't do any of the above "very often".
- taeric 11mo agoOptimistic locking works great when what is excluded is effectively a calculation. The annoyance, though, is you have basically acknowledged that you can use a compare-and-swap at the end of your calculation to know that things worked. This is not at all always the case, though. Sometimes, what you need to use mutual exclusion for is actively working with something that is, itself, active work. That is, sometimes you have to stop something even starting. Think about how you would model a laundry mat. It isn't enough to say you could use optimistic locks for access to the machines. You can't use the machine until you can use the machine. This is not unheard of in computing, either. Sometimes, you can't process a buffer until you know it has been finished by the code before you.
- mrkeen 11mo ago> Think about how you would model a laundry mat. It isn't enough to say you could use optimistic locks for access to the machines. One machine? Too easy, I want multiple machines! I want to reserve this machine and that machine. And this is happening while someone else wants to grab that machine and this machine. It costs money to grab a machine, so I'll insert a coin into this machine, and then insert a coin into that machine. The other guy grabbed that machine before me, so am I locked out? It turns out he only had one coin, not two: not only did this mean he untook that machine, but the coin he spent flew out of the machine and back into his pocket. While that was going on, I took a nap - instead of busily waiting for that machines - and the laundromat operator woke me up when it was time to try to grab both machines again. myActions :: Wallets -> Machines -> STM () myActions wallets machines = do bookMachine "this machine" bookMachine "that machine" where bookMachine :: Machine -> STM () bookMachine m = do reserveMachine machines m spendCoin spendCoin :: STM () spendCoin = do decrement wallets newBalance <- getBalance wallets when (newBalance < 0) (throwSTM "Ran out of money")
- taeric 11mo agoRight, but my point is that you are still guarding a calculation, there. I suppose it is fair to say that this code just describes the paying for it side of things. My point is that I often want the code to describe everything I can actively do while the machine is in use by someone else. To that end, if I was to "script out" a trip to the laundry mat, it would not be as simple as "reserve both, when successful, pay." It would be "Confirm driers are working, find an empty washer to fill, if found fill it if not check times and plan to come back later if above a threshold start over when I'm back, otherwise pay it, come back later when it is it done, ...."
- bloppe 11mo agoI remember taking an excellent multicore class in college. We studied all sorts of non-blocking data structures and fancy locks with different properties, transactions, etc. Then toward the end, the professor mentioned in a rather offhand way one day something along the lines of "90% of the time you're going to get the best performance with a simple mutex". I forgot how to implement all those fancy patterns, but I remember the sense of paranoia that class instilled in me. I guess that was the point.
- yencabulator 11mo agoEven worse, cachelines are essentially RWLocked for you by the CPU cores. It's always mutexes underneath, no matter what you do. https://en.wikipedia.org/wiki/MESI_protocol https://en.wikipedia.org/wiki/MESI_protocol