3 ms·

Hardware transactional memory wouldn't accelerate Clojure. The actual transactional bit is very cheap, built around compare and swap. You first grab the curren

Hardware 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?
- reitzensteinm 6y ago
  It could, but it just wouldn't be Clojure any more. The whole thing is built on persistent data structures, where if you modify an object you get the new version, and keep the old version unless it's garbage collected away. Further, there are guarantees that both versions perform well. 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.
  - reitzensteinm 6y ago
    I should point out that I'm fairly familiar with the literature roughly up to the level that Clojure takes advantage of (I've used it to implement custom versions of persistent maps and RRB trees that store to disk). There may be more advances since then or techniques I'm not familiar with. 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.

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?

reitzensteinm 6y ago
It could, but it just wouldn't be Clojure any more. The whole thing is built on persistent data structures, where if you modify an object you get the new version, and keep the old version unless it's garbage collected away. Further, there are guarantees that both versions perform well. 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.
- reitzensteinm 6y ago
  I should point out that I'm fairly familiar with the literature roughly up to the level that Clojure takes advantage of (I've used it to implement custom versions of persistent maps and RRB trees that store to disk). There may be more advances since then or techniques I'm not familiar with. 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.