6 ms·
Ruby's Proposed STM
- AaronFriel 6y agoNow what happens when you add STM to these languages? You've just created an enormous footgun by creating another color of function (https://journal.stuffwithstuff.com/2015/02/01/what-color-is-your-function/ https://journal.stuffwithstuff.com/2015/02/01/what-color-is-..., see also: https://news.ycombinator.com/item?id=8984648 https://news.ycombinator.com/item?id=8984648). 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.
- thaumasiotes 6y ago> That’s why C# has that little caveat. You can avoid the pain of async in C# by using threads. This is the first time I've seen threads referred to as a way to avoid pain.
- taffer 6y agoThreads are fine as long as they do not share mutable data structures. For example, multithreaded application servers are a rather painless experience.
- mumblemumble 6y agoThat observation doesn't really contribute to a comparison of dedicated threads and async/await, though, because the same is true of async routines.
- eyelidlessness 6y agoSince all of these concurrency approaches’ pain points are around shared mutable state, maybe it’s shared mutable state that’s the pain point.
- bglusman 6y agoYup, this is the conclusion of Joe Armstrong and why Erlang/Elixir/BEAM just doesn't allow mutable state, other than process dictionary which is inherently non-shared.
- deleted 6y ago[deleted]
- ancarda 6y agoI honestly prefer threads and mutex locks to async/async. Feel free to burn me at the stake.
- formerly_proven 6y agoWhether async or threads are preferable depends a lot on context and often the answer will be "both". 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.
- jpcooper 6y agoThere’s no guarantee that you’re not calling unsafePerformIO in Haskell, which a lot of outwardly pure libraries do. In fact, wouldn’t STM be doing this under the hood? Even the FFI in Haskell allows you to import a function without the return type being in IO as long as you pinky promise that it is pure. The idea in the end is to provide a language for working on memory concurrently. You either choose speak it or not.
- deleted 6y ago[deleted]
- kpmah 6y agoAs with Rust's 'unsafe', the fact that you can explicitly circumvent checks doesn't make those checks useless. If something goes wrong you know exactly where to look.
- jpcooper 6y agoThat may be the case for Rust. I am not sure what the implications of unsafe are for the type system. 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.
- a1369209993 6y ago> I am not sure what the implications of unsafe are for the type system. 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.
- nextaccountic 6y ago> In any case, the unsafeness of unsafePerformIO and importing an FFI function as a pure function are not reflected in the type in Haskell. 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)
- chrisseaton 6y agoIt’d be good if all writes in a transaction were automatically transactional and we had no TVars, and also if all IO automatically made a transaction irrevocable. But I’m not sure this is tractable in either implementation effort or runtime overhead.
- marcosdumay 6y agoAre you talking about the Haskell one? If so, you can't do IO inside a transaction (it won't compile), and any value not on a TVar is thread-local.
- chrisseaton 6y ago> Are you talking about the Haskell one? 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.
- cat199 6y ago> In any other language, all bets are off. 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.
- marcosdumay 6y agoWell, if you don't like the wording, translate "all bets are off" into "the programmer(s) must never make a mistake on those 10k to 10M lines on the code". That's not a reasonable thing to expect.
- rurban 6y agoNot only bets are off in non-functional language, it's the wrong solution. 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.
- rrss 6y ago> There are proven good solutions for fast and safe concurrency with ownership tracking and a good compiler/scheduler. Do you have any pointers to these solutions for the uninitiated?
- rurban 6y agoAll concurrency-safe languages. Eg pony, concurrent pascal, the parrot vm, ...
- amelius 6y agoEh, STM is often used as a solution to avoid locking. https://en.wikipedia.org/wiki/Software_transactional_memory https://en.wikipedia.org/wiki/Software_transactional_memory
- brandmeyer 6y agoIf you read into the implementation papers a little more deeply, you'll find that they are typically implemented with locks under the covers.
- orthoxerox 6y agoHaskell should just have transactional IO, then. RDBMSs have had it since god knows how long ago.
- AaronFriel 6y agoHaskell is a general purpose programming language, so I'm not sure what you mean. You can't in the general case have "transactional IO".
- a1369209993 6y agoHonestly the main feature of Haskell in this regard isn't STM-colored functions (as you note, that's a bad thing), but rather that it almost supports color-generic functions in the form of `Monad f => A -> f B -> f C`. Unfortunately, it doesn't correctly handle the identity monad `type Id a = a`, instead requiring `newtype Id a = Id a`, so it's impossible to write a function that matches both (eg) `A -> B` and `Monad f => A -> f B`.
- kccqzy 6y agoI don't understand your argument. 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?
- a1369209993 6y ago> What's wrong with [`type Id = a`]? 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 where
- kccqzy 6y agoOf course that won't work because that type synonym is far from a monad. I think you meant to write `type Id a = a` or `type Id f a = f a` instead. But 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.
- a1369209993 6y ago> I think you meant to write `type Id a = a` 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 (The last two lines can be ommitted, since GHC aborts before checking the instance body. Edit: which is why I didn't notice I had the arguments to >>= backward; fixed?) > 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.
- funcDropShadow 6y agoAnother reason why it is easier to integrate and use STM in Haskell than in most other languages, is the prevalence of immutable types. When only a tiny fraction of all memory structures needs to be tracked by STM as TVars, it becomes orders of magnitudes cheaper than in languages with predominantly mutable data structures.
- pansa2 6y agoA few years ago, the PyPy developers were working on STM for Python, as a way to mitigate the Global Interpreter Lock. Was that work ever completed? How does it compare to this work for Ruby?
- danmur 6y agoMy recollection (which could be completely wrong) was that they had a branch with it, but it really needed hardware transactional memory to memory to have decent speed for most applications.
- pansa2 6y agoMakes sense - they seem to have stopped work on STM so presumably it couldn’t be made to work well. How will STM in Ruby solve (or avoid) the problems that doomed STM in Python?
- the_mitsuhiko 6y agoIt exists, it's just quite slow. I doubt there are users of it.
- mattip 6y agoHere is the thesis paper that came out of it. https://dl.acm.org/doi/epdf/10.1145/3276479 https://dl.acm.org/doi/epdf/10.1145/3276479 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
- kimi 6y agoClojure had STM from the start, and it was one of its selling points, but the real world experience with it is that nobody uses it - atoms (i.e. global serialized write access, with non-locked reading) are 99.9% good enough.
- _pmf_ 6y agoIt was supposed to be THE killer feature of Clojure. Rich Hickey's "ants" demo is still firmly in my mind.
- MrBuddyCasino 6y agoAlso it isn’t particularly fast afaik. Hardware support was supposed to fix this, but the Intel primitives were buggy and not available on all models.
- reitzensteinm 6y agoHardware transactional memory wouldn't accelerate Clojure. The actual transactional bit is very cheap, built around compare and swap. 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.
- MrBuddyCasino 6y ago> 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). Can you expand on that? Couldn't Clojure introduce a STM-aware HashMap, why would TSX help?
- mcintyre1994 6y agoThanks for sharing this here, it was a great read and really well written. I really like the style of communication of taking a problem and existing solution, and adding requirements and workarounds one at a time until that stops working to motivate a new approach. And this was a really nice introduction for me to STM too, which seems like an interesting topic to look into more. Appreciate the references too!
- deleted 6y ago[deleted]
- im3w1l 6y agoSo I have very little knowledge here, but wont the transaction log need a global lock? Is the trick that you hold it for a very short time so that it doesn't become a problem? Also with high contention, wont the transactional threads do a lot of replaying each others work to figure out if they have conflicts or not?
- klodolph 6y agoYou use a lock-free structure for the log.
- md5person 6y ago> "lock-free" 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.
- sriram_malhar 6y agoTrue, but the key difference in the lock-free approach is that the "lock" is basically a pointer-swizzling or timestamp-swizzling operation, and so the lock duration is strictly bounded; it is determined by the application or the thread-scheduler.
- WJW 6y agoNaming is hard, but in this case lock-free is just misleading. Why oh why didn't they go with bounded-lock data structures? :)
- klodolph 6y agoBecause there is no lock. 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.
- fnord123 6y ago>Let’s say we’re a bank managing many bank accounts. Each account has a total. We get a never-ending stream of requests to move a sum of money m from an account a to account b. 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.
- the-dude 6y agoRegulators would like a word with you. Also, in theory it sounds nice, but reality is always more nuanced. I have implemented a bank-like SaaS which was regulated by our national financial regulators.
- fnord123 6y agoOf course it's more nuanced than a short HN comment. It's also more complicated than using a mutex to make changes to two values. > 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?
- the-dude 6y ago> 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 ).
- kevingadd 6y agoA string of before and after balances is still a ledger. This is distinct from just 'account, current_balance' tuples like a more typical schema would have.
- 7373737373 6y agoSeeing routing in action like this is very satisfying
- waffletower 6y agoRuby's proposed software transaction memory (STM) is Clojure.
- chrisseaton 6y agoNot sure what you mean? STM wasn't originally developed for Clojure. STM as we know it today pre-dates Clojure by over a decade.
- waffletower 6y agoMy troll was intended to say, when a Ruby developer desires to utilize STM, they would instead become a Clojurist and use a language where STM was a foundational design consideration. I am not sure why it is relevant to discuss the originality of STM. But again my post was a troll so say -- whatever -- as I did.
- cutler 6y agoJust use Clojure.