Ruby's Proposed STM
chrisseaton.com
chrisseaton.com
What this proposal misses is that reasoning about software transactional memory in functions all but demands being able to abort and retry code to make progress, and that therefore means having a high level separation between transactional code and IO code.
Suppose you had a banking application, you would like to use STM (as in the "ractor" example in this article) to move balances from one to another. In Haskell, you'd perform STM actions on those TVars (transactional vars) and use the default retry policy of STM to automatically construct an order of operations such that each operation appears to occur atomically. (STM doesn't impose a clock based ordering but I don't think it would be tremendously difficult to do so.)
If you don't use Haskell's "check" or "retry", you find that your code will abort and fail with near certainty. You can't perform lots of transactions on tvars and not, occasionally, read from a var another transaction is writing.
So you add "check" calls to verify your preconditions and postconditions such as balances cannot go negative, and you add "retry" calls to automatically retry transactions that fail because of concurrency.
Now imagine doing that in a modern Ruby codebase, or a modern JavaScript codebase. There's so much mutation that happens in these environments, can you guarantee within a Ruby function that it hasn't mutated another variable with ease? That it hasn't written to disk, made an API call, or changed some global state?
Haskell pioneered the use of STM. It's easier to reason about in Haskell because the world of the STM can be isolated from the world of effects due to the IO monad. It's easy to declare "this function is blue" and "this function is red" and the never the twain shall meet.
In any other language, all bets are off.
This is the first time I've seen threads referred to as a way to avoid pain.
Feel free to burn me at the stake.
E.g. GUI code -> async, because you must do everything on the UI thread. Heavy lifting in a GUI app -> threads. Traditionally you'd do this with a huge mess of callbacks, but these days it's reasonably easy to just write the GUI portion using async and have background computations run in threads signal their results through futures into the async code, which makes everything so much easier.
Parallelism and concurrency are orthogonal concerns. Multiple threads can run on the same core, while concurrent awaits can run on separate cores (depending on the language). Or the opposite!
Threads definitely solve wasted time waiting on I/O, but OS-level threads are a very limited resource in many environments, which can cause problems more quickly in programs with unbounded concurrency, and they tend to have a lot of startup cost, so they have to be created judiciously to avoid hurting performance.
Languages like Go and Elixir give the programmer access to unlimited lightweight “threads”, and that works great for concurrency, without requiring developers to re-color their functions.
One additional note is that some OSes (including Linux) have struggled to support true nonblocking File I/O for many years, so you literally have had to use multiple OS threads for I/O concurrency... one for each file operation in progress. Otherwise you would block the async executor! Languages often handle this implementation detail for the programmer, so you just don’t realize you’re using a thread-per-await sometimes.
(io_uring seems to finally solve this in a meaningful way on Linux)
I think a large part of that for me is because early in my career I got involved in Unix kernel work, first writing device drivers and later doing Unix ports, including both porting a swapping Unix to paged hardware (and rewriting pretty much all process and memory management from scratch) and porting a paging Unix to swapping hardware.
That was followed by a few years largely doing embedded stuff on systems too small to have operating systems or memory management units. For those I'd write a small kernel that supported threads and scheduling (sometimes cooperative and sometimes preemptive) and then write the embedded applications much like I would have written them on Unix, using threads instead of processes.
So for me threads are easy and things like async/wait seem overly complicated and less clear because I came at concurrency from the operating system side of things and the hardware side of things (e.g., dealing with interrupts) where thread-like thinking is natural and perhaps required.
Maybe it is conceptually harder for people who come at it from the application side of things?
On the app side, "I want to do this thing that might take a while without blocking the UI, and then do something with the result, and I have zero need to communicate with the code that's running the task beyond giving it its arguments and getting its result back," is the most common use case. Task parallelism is tailor-made for that kind of problem.
Using a dedicated thread, on the other hand, gives you some raw material you can use to solve that problem, but leaves you to handle all the messy details on your own. And doing it the easy way - one short-lived thread for every thing you need to do in the background - is expensive, while doing it the correct way and implementing a thread pool is essentially just committing to Greenspunning your own personal task parallelism library.
There are times when one might want async executors like node's event loop or rust's tokio/async-std, but in other situations one might want os threads or "green threads" with a RwLock or Mutex.
What about a few long running threads that use async internally? ;-)
The idea in the end is to provide a language for working on memory concurrently. You either choose speak it or not.
In any case, the unsafeness of unsafePerformIO and importing an FFI function as a pure function are not reflected in the type in Haskell. These are things that can and do happen.
My point was that the ability to go outside the bounds of a language does not necessarily make the language useless.
There are no implications, that's the point.
> the unsafeness of unsafePerformIO and importing an FFI function as a pure function are not reflected in the type in Haskell
Yes, that is correct behaviour; if it was reflected in the type it'd be call safePerformIO.
It's reflected in safe Haskell annotations. Unfortunately nobody cares about those. Haskell has a culture problem regarding safety, just like most other languages, both high level and low level (with the exception of Java, that don't make data races UB)
But I’m not sure this is tractable in either implementation effort or runtime overhead.
If so, you can't do IO inside a transaction (it won't compile), and any value not on a TVar is thread-local.
No?
I'm responding to the idea of the 'colour' of functions and suggesting how I think it should be in Ruby - all side effects transactional, but IO irrevocable. Drop the idea of TVar and make all mutable locations transactional.
No, in any other language, one has to have an understanding of the codebase and what is mutating and what is not instead of relying on the language to do this work for them, which, granted, can be a lot more work.
dismissing things because 'i dont want to deal with it because it is hard' is not the same as dismissing it because 'this is not possible', this argument is the former.
see also: ocaml / scheme style FP, which can be 99.9% as pure-functional and type-checked as haskell if one wants to build their system that way.
That's not a reasonable thing to expect.
STM puts the cost of locking into everything, ie slower default operations, whilst still being concurrency unsafe. Deadlocks can occur.
There are proven good solutions for fast and safe concurrency with ownership tracking and a good compiler/scheduler. No, not Rust. And not STM. We fought with this for years.
Do you have any pointers to these solutions for the uninitiated?
It is correct that the standard library provides you with a newtype-based identity monad. But as you have said, you can also write own `type Id a = a`. What's wrong with that?
The fact that it doesn't work:
> - The type synonym 'Id' should have 1 argument, but has been given none
> - In the instance declaration for 'Monad Id'
> | instance Monad Id whereBut I get your argument now. What you are saying is that we want some kind of a way to define functions that are either pure or return a monadic value. Currently that's not doable because these two have distinct types. It may be difficult to unify them via the type system. This is even more difficult for higher-order functions that take other functions.
Indeed I did, sorry, unfortunately too late to edit. The following reproduces the error:
{-# LANGUAGE TypeSynonymInstances #-}
type Id a = a
instance Monad Id where
x >>= f = f x
return = id
> It may be difficult to unify them via the type system. This is even more difficult for higher-order functions that take other functions.
IMO, the main difficulty in unifying `a ~ Monad m => m a` is inferring `m ~ \a1-> a1` in a way that allows `\a1-> a1` to inherit `Id`'s instances. It's a understandable deficiency, but it is a deficiency.
You first grab the current value of two refs, build two new values out of them through some process.
Then on commit, you lock both refs and check they're unchanged since the start of the transaction. If they are, you swap the values, if they're not, you grab the new values and rerun the computation (on and on until timeout).
The overhead comes from the lack of granularity - if two transactions change different keys in a map they'll conflict even though in theory they could run simultaneously (and indeed can with a hash table and HTM like TSX).
And also because of the speed of persistent data structures. They're not exactly slow given the flexibility they give you, but each write involves allocation.
Can you expand on that? Couldn't Clojure introduce a STM-aware HashMap, why would TSX help?
This isn't just used for Clojure's STM (although it makes the STM model trivial). It's essentially the fundamental premise of the language. Functional programming with structural sharing to allow immutable data structures to be fast enough to be useful in the real world.
Introducing a new data structure that was (I assume you mean) HTM aware would not offer the same guarantees. You'd be able to have two threads mutating it, but you couldn't (for instance) keep a history log of values by hanging on to a pointer to each one, that is still reasonably space efficient.
TSX or other HTM would allow you to build a hash map that two threads can modify simultaneously by literally just reading and writing to it as normal (with some nasty edge cases, but fundamentally it's similar to a single thread version). The hardware keeps track of which cache lines are involved in the transaction, ensures they're not written to memory, and if there's a conflict it throws them away to retry the transactions.
However in Clojure, you're not modifying the map, you're creating a new version that shares most of the structure with the old version except for your differences. If two threads modify the original hash map A, to yield B and C, all you've got now are three different trees. You might be able to invent a data structure that allow you to merge the diffs of A->B and A->C to yield D, containing both versions. But it's probably not going to be awfully fast and it's going to have corner cases that violate the transactional guarantees.
I think the problem I'm describing is fundamental, but I'm not a researcher and am not claiming any advanced knowledge beyond being an experienced Clojure developer that is familiar with the internals.
What exactly "isn't particularly fast"? :)
In any real-world application the cost of STM machinery itself is, at a first approximation, 0.
There is a cost to immutable data structures, but I don't think that's what you were talking about.
- Atoms: very popular. Usually what people reach for, perhaps overly so.
- STM / refs: Not commonly used, but I wonder if this is because we aren't used to really considering them as an option?
- Agents: I think everybody agrees that you shouldn't use these
- core.async: What many people think you should use instead
- Reducers: I've never seen these used in the wild.
Both have their place!
Having written Clojure professionally, and then moved on to Java (not intentionally, just kinda happened), I find myself using the same pattern in Java. AtomicReference + pcollections, along with Lombok's @Value is enough to get some pretty Clojurey concurrency patterns in Java.
This is why I frown when people say "Clojure STM is useless" or "nobody uses Clojure STM". Everybody uses the foundations, and the reason why the foundations are so useful is precisely because they were designed for STM.
I've been writing Clojure apps for many years now, and it is true that atoms are usually enough. I used agents in the past for their serialization capability, but these days core.async is usually a better tool. I never found a use case for refs that could not be simplified. In most applications I wrote, transactionality was needed together with persistency, which shifted the responsibility to a database.
Which is a very reasonable way to see it, in my opinion.
Players were in rooms, which were updated ten times a second. All of the rooms are largely independent, meaning the best strategy to do this is to use a threadpool to update them in parallel.
However, occasionally operations would require synchronization between rooms (eg, move one player from one to another).
It worked pretty well.
* a lot of services simply defer their state management to some other service - a database or document store. Typically have to use their concurrency/transaction management
* In apps that have state, a lot of times the only safety is required - this state only changes in one place, I can't afford a partial read, but otherwise I don't really care about concurrency. Atoms for this.
* Sometimes there is an ordering or coordination to state, but a lot of time that is producer-consumer, so core.async can be a nice fit.
* In a (relatively) small subset of cases, I actually have multiple writers whose behavior I need to coordinate. STM is perfect, and I prefer it to managing my own locks in those cases.
We all know that you should not do accounting using floating point numbers. But also, please understand that bank accounts are [append only] ledgers and the balance is a cached computation. I truly wish that we had a different example use case because this is really bad.
I have implemented a bank-like SaaS which was regulated by our national financial regulators.
> I have implemented a bank-like SaaS
Which one? What made it bank like? How was it implemented?
> which was regulated by our national financial regulators.
Which country?
> Regulators would like a word with you.
To say what?
Among other things, they require you to store the before & after balance with each transaction. As a truth value, not a cache.
And now your whole premise is out of the window ( there is a bunch of practical reasons it won't work in reality too ).
So for online casinos I would not say that the balance is cached. And I imagine traditional banking also has accounts which are never allowed to go into the negatives where a similar solution is required.
Well... that’s why the article proposes a different, better example.
Was that work ever completed? How does it compare to this work for Ruby?
How will STM in Ruby solve (or avoid) the problems that doomed STM in Python?
All the following is my opinion, and may contain errors. Take it with a grain of salt and kindly correct me where I misstated something.
If you view PyPy as a sophisticated test bed for virtual machine research it was a success. There are lots of conclusions about what works and what doesn’t, and benchmarks that show faster code when using many core. But the project ended with the conclusion the the STM model and the tracing JIT model don’t play well together, and the PyPy team preferred to stay with the tracing JIT.
Python and Ruby are very similar. The same JIT that powers PyPy powers topaz, which still performs quite well in ruby benchmarks even though it has been dormant since 2017
I never liked that term.
Lock-free algorithms will usually boil down to some combination of polling, waiting (sleep(), futex-style), or use what are essentially more fine-grained, hardware-backed locks (CAS, memory barriers, LOCK instructions, hardware-specific transactional instructions, etc). The locks are very much still there.
With a lock, you acquire the lock, you perform your operation, and then you release the lock.
Lock-free is typically done differently. You don’t acquire a lock, you start performing the operation “optimistically”, and you commit the result if no other thread has stomped on your data. If another thread has stomped on your data, you start over.
One of the important differences here is that it’s a race. Whoever commits first, wins. With a lock, you have to wait for whatever thread acquired the lock first. That thread may not even be running.
So, lock-free is fundamentally different because with a lock-free system, a thread that is running will always complete work (you just don’t know which thread). In a system with locks, threads that are running may be prevented from making progress by threads that are not running.
Systems with locks can also deadlock, lock-free systems cannot deadlock. Usually, there is some sort of guarantee that lock-free systems always make progress.
> "you commit the result if no other thread has stomped on your data"
What does "committing" mean here? If it means performing an atomic write (a-la CAS), then you're using a lock (see my next point).
> "If another thread has stomped on your data, you start over."
So you let your thread sit there in a spin-loop and CAS a condition-variable. That's a lock for all intents and purposes, and your system can still "dead-lock" (read: your thread will never get to "win the race"), if your "data gets stomped on" over and over again in-between reads (which are obviously non-atomic, otherwise you'd be locking there too).
> "Usually, there is some sort of guarantee that lock-free systems always make progress."
Getting a time-slice to continue running in a tight-loop while trying to CAS is not the same as "making progress".
"Making progress" would be - you'd get a chance to commit your changes and proceed to your next bit of business logic. But with contention, that's not guaranteed to happen at-all?
- Lock-free: at least one thread will make progress
- Wait-free: all threads will make progress
The difference between locks and lock-free is very noticeable if a thread holding a lock is suspended (which can happen on a modern system just by accessing memory that is paged out). On real-time systems it’s also possible to guarantee that high-priority tasks will make progress, regardless of how a low-priority task behaves. With locks, a low-priority task can easily prevent a high-priority task from running at all.
It can live-lock.
I think you’re possibly confusing lock-free and wait-free, which is a stronger guarantee.
Practically speaking - wouldn't the exact duration be heavily influenced by the countless layers of abstraction beneath the application itself (kernel, scheduler, hardware, speculative execution, etc)? If so, can we ever truly make the claim that the "duration is strictly bounded"?
You can still use standard kernel-provided synchronization objects (mutex/events/semaphores) in your "lock-free applications", as long as you provide timeouts to blocking wait() calls, and handle abandoned objects gracefully.
For instance, if all threads except one are stopped, the single running thread should “finish” (for whatever finish means) in a finite time (lock-free is stronger than this condition, too). An algorithm using mutex-style locks fails this guarantee, if one of the stopped threads is inside the critical section.
But, a lot of people have gone through the effort to leave explanations in this case. Isn't that good enough?
For one unaddressed example:
> You can still use standard kernel-provided synchronization objects (mutex/events/semaphores) in your "lock-free applications", as long as you provide timeouts to blocking wait() calls, and handle abandoned objects gracefully.
This might be technically true, but atomics provide significant performance benefits compared to using a mutex with a timeout, and I don't think of "lock free" as relying on busy loops as you seem to think in your comments. I'm sure a busy loop makes sense in very specific algorithms, and mutexes themselves often use a limited amount of busy waiting to avoid context switches. You can simulate atomics with mutexes, but that's not the point. Lock free is hard to do correctly. Mutexes create the possibility of a deadlock, which is incompatible with being lock-free, so you have to avoid all the footguns of lock-free and the footgun of using mutexes.
So, yes, you can use standard sync objects... but that doesn't make anything better in this case. It misses the point. "Technically correct" isn't always good enough to get an upvote.
If you don't agree, that's fine... but this is completely uncalled for and against the community guidelines:
> This community has truly deteriorated over the years.
No one is obligated to upvote things they consider incorrect, and downvotes are perfectly suitable for this purpose under HN guidelines.
If you don't see how it contributes to the conversation - why not just ignore it then? Just because you think this doesn't contribute to the conversation, doesn't make it true.
> "If you don't agree, that's fine..."
Clearly it's not "fine", otherwise you wouldn't try to silence comments you disagree with by down-voting them.
This is my last comment on HN.
Because it's misleading and/or missing the point. As stated. Why would I want more people to read something that I believe is misleading?
> Clearly it's not "fine"
Once again missing the point. The prevailing opinion on HN is what will get upvoted, and a lot of other stuff will get downvoted. I have seen that prevailing opinion be hilariously wrong before.
If you want to be heard with an unpopular opinion, you have to make a compelling argument... you can't expect to be upvoted to the top just because you're sharing an opinion. It's rare for a comment to be lukewarm enough for no one to feel strongly enough to downvote it. It's going up, going down, or it's on a thread no one is reading. Downvotes don't mean people hate the person leaving the downvoted comments; it's just a tool for disagreeing with comments.
> This is my last comment on HN.
Because people disagreed with you? People even left explanations, but that wasn't enough.
The transaction log is append only, so there are more optimal methods (including lock-free approaches to make it efficient. Also, the duration of the lock is limited to the append operation, and not determined by application (when the atomically block ends).
And yes, STM and high contention don't mix. It works well for occasional writes and predominant reads.
Tim Sweeney's presentation on this topic is hugely informative.
https://www.st.cs.uni-saarland.de//edu/seminare/2005/advance...