It's always possible to decompose the final program down into one that could be based on locks. But this is often at the cost of maintainability; the code becomes one mess of spaghetti locking in order to maintain whatever invariants need to be maintained to prevent deadlock and compose code together.
Agreed, I don't need any convincing that STM is 100x more fun than locks.
You are correct that multiple-reader locks could get some of this benefit back. But those systems have serious drawbacks when a read-only lock needs to be changed into a read-write lock in the middle of an operation. There's also the same deadlock/lock-ordering problems as in any lock-based solution. STM cuts this Gordian knot by forcing all lock-taking actions to be otherwise pure, besides the mutation to the data structures protected by the locks. This way, a failing transaction can always just be killed and restarted if something goes wrong. It might be possible to enforce the same sort of purity on top of a lock-based system.
I see, so would it be safe to say that the simple but reasonable locking implementations in the paper perform poorly compared to STM because of read contention, and while read contention can be eliminated with read locks, it's too much complicated hassle and most locking data structures won't do it? It seems, naively, like relatively simple but popular structures like queues shouldn't have too much trouble taking a read lock for peekQueue but a rw lock for takeQueue.
I don't think the STM runtime has gotten a lot of love since that paper; given that TVar operations are using a linear search over the transaction log, I suspect it could go a long way if it had a capable volunteer. This is part of the motivation behind trying to port the concurrency substrate from C into Haskell [1]; getting STM out of the GHC RTS and into the hands of library writers will put a lot more eyeballs on the performance problems.
But I thought a haskell RTS was a win for correctness and ease of modification, but a lose for performance? Thanks for the paper link, I'll check it out in a bit. There's a seemingly endless supply of interesting haskell papers out there...