Software Transactional Memory (1997) | Hacker News Reader

Software Transactional Memory (1997)

dl.acm.org

24 pointsluu28 comments

No modern language I know of beats Haskell’s support for STM:

https://wiki.haskell.org/Software_transactional_memory

As I always say, Haskell is the Mercedes of programming languages.

I don't have much experience with Haskell, but Clojure also has STM out-of-the-box. I don't know if it's the approach described in paper, but it's quite fast. It's probably made faster by the fact that almost all data in Clojure is immutable.

"The Clojure STM uses multiversion concurrency control with adaptive history queues for snapshot isolation, and provides a distinct commute operation."

https://clojure.org/reference/refs, for the curious and brave

Interestingly, I’ve been using Clojure since 2009 and I’ve never once used STM (outside of playing around to learn how to use it). I’ve used agents on occasion, I’ve used atoms, I’ve used core.async a lot, but refs and STM, to me (ie YMMV) seem like one of those things that seemed like a useful great idea, that in practice just wasn’t really necessary.

Maybe others have had a different experience, of course. This is just an observation about my own code and the libraries I use.

No, your assessment is pretty accurate. I've only encountered refs once in the wild, and only because it was too much hassle to refactor working code to use an atom.

It turns out that updating a single storage point in an atom with a CAS serves 99.9% of use cases, and is much, much simpler than ref-based code.

> but refs and STM, to me (ie YMMV) seem like one of those things that seemed like a useful great idea, that in practice just wasn’t really necessary.

Haskellers (including myself) tend to default to STM to take advantage of atomicity.

Of course it's easy to make the safe choice when the shared interface between concurrency primitives make switching very low cost.

More: https://www.oreilly.com/library/view/parallel-and-concurrent...

Common Lisp has it too, via https://stmx.org/ I believe it supports the Intel TSX stuff if present and falls back to a software implementation if not present.

> Haskell is the Mercedes of programming languages.

Comfortable, packed with features, pretty fast given its weight, kind of elitist yet approachable if you invest time in it? :p

ding ding ding!

Also something about inventing/spurring mass adoption of airbags and ABS. Safe and fast.

I have a repo with six sample algorithms of increasing complexity: https://github.com/jasonincanada/stm-haskell

GCC supports code generation that will call into several different software transactional memory (STM) engines. It's not difficult to write your own engine that is called instead of a default version.

What this basically does is generate multiple versions of functions that can be called both in and not in a transaction. Functions that may be called in a transaction have to be side-effect free (i.e., no system calls, recursively). The modified functions run code for each line of memory read or written so the STM engine can decide what to do with it (e.g., reads can be redirected to other locations, writes can be used to dirty memory or redirected to a scratch location).

There are different trade-offs for efficiency, conflicts, etc. For instance, if each transaction begin just started with a global exclusive lock it would be correct, simple, and you'd never get conflicts, but just serializes everything. There are trade-offs.

Languages with more rigid semantics and a propensity towards immutability would require less annotation. The GCC version generates these invocations for engine functions on most loads and stores. As you'd imagine, it's pretty expensive as is and basically is not used as a generic method of concurrency control for this reason.

Interesting, do you have a link to the documentation for this (or even a paper describing the design)? Does Clang/LLVM have something similar? I wonder would adding STM to Rust be more practical in terms of performance (or does the question even make sense given it already guarantees data race freedom)?

There's an Intel ABI specification that GCC closely follows. The gcc implementation is called libitm and their specification is just listed as a diff of intel's specification.

Here is gcc's doc on libitm https://gcc.gnu.org/onlinedocs/libitm/ Here is intel's document (much more useful): https://gcc.gnu.org/wiki/TransactionalMemory?action=AttachFi...

I'm not sure what the support story is like on clang.

A few years ago it seemed that every cpu architecture was going to get hardware transactional memory acceleration. SPARC had it, POWER had it, even Intel added it. A transactional memory proposal for C++ made it into a Technical Report, it got implemented in GCC and it seemed to be ready to be merged into the standard.

Then I'm not sure what happened, things seem to have run out of steam, Intel never managed to make its HTM to work well and it unofficially deprecated it and generally TM went out of fashion. The TR is still there and gets minor updates, but I haven't heard about any push to merge it.

As I understand it, a bunch of people became less convinced of TM's usefulness eg. http://joeduffyblog.com/2010/01/03/a-brief-retrospective-on-...

Thanks a lot for that, very interesting perspective (particularly the challenges with unbounded transactions and nontransactional I/O). It makes me wonder (i) whether bounded transactions were also found to be too hard to use (given restrictions on transaction sizes) (ii) what has replaced STM in terms of better fine-grained concurrency control abstractions (if anything). Maybe better type system support through new languages (e.g. Rust)?

I am not familiar with any details, but the haskellians seem to still be working with STM. At least there are a bunch on talks online about it.

I had spent most of the 90s working with transactional systems and while they are useful and powerful, they aren't magic and require awareness to keep from making errors. Joe Duffy wasn't wrong when he says those problems are well known. The solutions normally are either Don't Do That Then, or managing the policy details and logic yourself, which wasn't giving them the easy concurrency they were trying for.

Edit: He has a followup post at http://joeduffyblog.com/2010/05/16/more-thoughts-on-transact...

I've been working on a JS database to support optimistic concurrency control. I did some research and arrived on 2 seemingly related concepts but from independent research lines. Software transactional memory in functional programming/Haskell land versus snapshot isolation in database research.

After reading them both, I asked this unanswered question on SO: https://stackoverflow.com/q/72084071/582917. My theory is that STM is the same as SI, but most SI database implementations don't just do value comparisons, but actually check a logical timestamp. This is probably done for performance reasons as databases handle larger pieces of data than functions would when using STM.

Along the way I also discovered SSI serializable snapshot isolation but it isn't yet available in rocksdb but cockroachdb apparently has a fork of rocksdb with it but I couldn't find it.

Anyway the db library which wraps around rocksdb is available to be used embedded in any nodejs program at https://github.com/MatrixAI/js-db.

These are apples and oranges. Snapshot isolation is a consistency guarantee, STM is a concurrency control mechanism. STM can be used to provide snapshot isolation (or stronger guarantees such as linearizability).

you are correct that snapshot isolation is a consistency guarantee. But I'm guessing the grand parent was really talking about MVCC-style database implementations, which are conceptually similar to some of the STM approaches.

MVCC implementations are indeed fundamentally about concurrency, but they also tend to make snapshot isolation easy to implement. (Far easier than implementing snapshot isolation with classic pessimistic locking!)

Yes I'm talking about snapshot isolation when implemented as a concurrency control system in databases.

But I don't think they used STM approaches to do it. So STM works nicely inside languages like Haskell, but when you work with a library database you can gain similar behaviour by using a key value database that has SI.

I think you are right about STM being roughly equivalent to snapshot isolation.

What STM offers is an easy way to invent "containers for snapshotted values" aka TVars. Using them carefully may result in better scaling: https://hackage.haskell.org/package/stm-containers

Could you explain what you are doing?

JavaScript is single threaded so I cannot see how you can implement actual concurrency control.

I implemented multiversion concurrency control in Java but I am yet to include the algorithm from the whitepaper Serializable Snapshot Isolation.

https://github.com/samsquire/multiversion-concurrency-contro...

JavaScript isn't single threaded anymore. There's workers and even at the C++ extension native add-ons are exposed to libuv threading.

But even in single threaded JS, asynchronous handlers can result in concurrent race conditions. That's why concurrency control is necessary. I also maintain https://github.com/MatrixAI/js-async-locks repo to help control all sorts of concurrent effects.

Even from a nodejs extension and libuv perspective, Javascript has one event loop.

You can create your own libuv event loops and run them on a separate pthread.

If you create a pthread in your own C++ extension then you're not really talking of Javascript.

Workers are not threads but they run in their own thread. Unfortunately you don't have shared memory. So you kind of have snapshot isolation by immutability. They can only communicate with postMessage. They're not threads, they do not share address space.

So Javascript is single threaded.

If you're getting race conditions with your multiversion concurrency control implementation, then you might need to look at how you isolate versions from one another. Write a unit test that adds numbers from 1 to 100 from 100s of concurrent transactions, you should end with 100 every time if you have no race conditions.

Without parallelism, you could introduce a bulk command API and wrap all your writes and reads in a single function.

The single threaded nature of Javascript will prevent race conditions if you do this - only one function can run at a time.

Isn't there a SharedArrayBuffer thingy in workers now?

Yes shared memory exists for webworkers. Furthermore JS land has different kinds of threading implementations, see threadsjs.

But I'm not talking about concurrency control between threads, but between asynchronous operations.

In our experience race conditions happen in JS regardless of its single threaded nature. It happens because of concurrent asynchronous operations that work on shared state that exists not necessarily in-memory but also in embedded databases. So most definitely concurrency control must be applied whenever there is any kind of shared state. The single threadedness doesn't matter if there are concurrent asynchronous operations.

YMMV but when I was writing the rocksdb native binding into nodejs, I saw that any asynchronous operations setup in the C++ would be dispatched to separate threads. Didn't explore further though. It was built into the NAPI bindings.

Reply on news.ycombinator.com