4 ms·

Now thats a good example! First, a little correction: you don't have to make a copy of the entire state. This video explains the trick on how to get immutable

by spion 11y ago

Now thats a good example! First, a little correction: you don't have to make a copy of the entire state. This video explains the trick on how to get immutable data structures that share most of their data with their previous version https://youtu.be/SiFwRtCnxv4?t=8m39s https://youtu.be/SiFwRtCnxv4?t=8m39s - list are straightforward, and vectors and maps are based on the same HAMT tree-like structure. Of course, a system with real time constrains and hardware limitations will have different optimal solutions. And yes, reference counting is the bare minimum you'd probably like for these structures (GC is even better) However, we're talking about Go here - a language designed for writing servers that has a GC. The solution in Haskell is actually quite nice: MVars [1] plus immutable data structure. An MVar contains the current state, represented by one such structure. takeMVar "removes" the variable - a thing which can be done atomically by the updating thread when the data becomes stale. After that, subsequent attempts to readMVar from other threads would block until there is a new updated value, to ensure everything is in sync. Finally, the updating thread does a putMVar, and all readers get the new value and continue executing. The best part is they don't have to worry that the updating thread might start another update in parallel while they read: the data structures are immutable so the value being read is guaranteed to remain immutable. Even if the updating thread continues "modifying" the new structure in the background, it doesn't have an effect on the other consumer's version. But yeah, all this is pointless if you have realtime constraints and therefore need super-tight control over execution time. It might be doable in a fast reference counted language, but it will also be much harder to reason about the time it will take to release the memory for the segments that aren't in use anymore. [1]: https://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Concurrent-MVar.html https://hackage.haskell.org/package/base-4.8.1.0/docs/Contro...

AnimalMuppet 11y ago
> The best part is they don't have to worry that the updating thread might start another update in parallel while they read: the data structures are immutable so the value being read is guaranteed to remain immutable. Even if the updating thread continues "modifying" the new structure in the background, it doesn't have an effect on the other consumer's version. If I understand what you said here correctly, this doesn't work for my example. A thread cannot continue with a stale version (and function properly). It must operate on a current version all the time (or block until it can).
- spion 11y ago
  You're right. For your example thats actually an error, and it wont happen if you `takeMVar` before you start working on the new value. I'm describing a slightly different example there, where its okay to get the old data while updates are being "prepared" (e.g. every item in the dictionary is being fetched from the DB, typical for a server app). In that case, Haskell will work correctly. In Go on the other hand, reusing the data structure may result in a program crash, as Go's built in maps (which might contain that data) are not thread-safe. (You can't even make the simplest type-safe, thread-safe mutable map that uses a RWMutex automatically under the hood. Because there are no generics)

by spion 11y ago

AnimalMuppet 11y ago

> The best part is they don't have to worry that the updating thread might start another update in parallel while they read: the data structures are immutable so the value being read is guaranteed to remain immutable. Even if the updating thread continues "modifying" the new structure in the background, it doesn't have an effect on the other consumer's version. If I understand what you said here correctly, this doesn't work for my example. A thread cannot continue with a stale version (and function properly). It must operate on a current version all the time (or block until it can).

spion 11y ago
You're right. For your example thats actually an error, and it wont happen if you `takeMVar` before you start working on the new value. I'm describing a slightly different example there, where its okay to get the old data while updates are being "prepared" (e.g. every item in the dictionary is being fetched from the DB, typical for a server app). In that case, Haskell will work correctly. In Go on the other hand, reusing the data structure may result in a program crash, as Go's built in maps (which might contain that data) are not thread-safe. (You can't even make the simplest type-safe, thread-safe mutable map that uses a RWMutex automatically under the hood. Because there are no generics)