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.