←back to thread

193 points ingve | 1 comments | | HN request time: 0.206s | source
Show context
FuckButtons ◴[] No.43712793[source]
I thought it was a bit odd that the author claims there’s no mutexes in sight, the TVar is effectively a mutex guard unless I’m misunderstanding this? (I’ve written exactly 0 lines of Haskel). Or is the claim that the lack of ceremony and accidental complexity around threading is the real win for concurrency here?
replies(6): >>43713040 #>>43713043 #>>43713044 #>>43713127 #>>43714265 #>>43714335 #
chongli ◴[] No.43713040[source]
No, a TVar is not a mutex guard. A TVar is a software transactional memory (STM) variable. STM works just like a database: you batch together a sequence of operations into a transaction and then execute them. During execution of a transaction, all changes made to the contents of the TVar are stored in a transaction log. If some other transaction occurs during the execution then the whole thing is aborted and re-run.

This can take any ordinary Haskell data structure and give you a lock-free concurrent data structure with easy-to-use transactional semantics. How it performs is another matter! That depends on the amount of contention and the cost of re-playing transactions.

replies(2): >>43713062 #>>43715091 #
1. whateveracct ◴[] No.43713062[source]
https://hackage.haskell.org/package/stm-containers

This library is full of STM-oriented data structures. They perform better than a simple `TVar (Map k v)`.

It's kind of a fun trick actually. The stock Map is just a tree. The STM Map is also a tree [1] but with TVars at each node. So this helps a lot with contention - you only contend along a "spine" instead of across the whole tree, which is O(log n).

[1] Technically a HAMT a la unordered-containers - trie, tree, you get the idea :)