5 ms·

These problems have lots of other well-known solutions. For large objects: Persistent data structures with path-copying. Batching small mutations (and using m

These problems have lots of other well-known solutions. For large objects: Persistent data structures with path-copying. Batching small mutations (and using mutation internally in a way that doesn’t leak out). Using the type system somehow to distinguish cases where copying is not necessary (experimental in certain new languages). Structuring your program around a “data store” that is mutable. For the “references” problem: Explicit references, like by ID. Or mutable “atoms” as in Clojure, which are maybe sort of like the “mediators” in the article.

UncleMeat 5y ago
Persistent data structures exist and work very well but they still remain way slower than alternatives that don't support persistence. This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks. Add in the GC overhead and you've got a meaningful problem. Yes, you aren't constructing an entirely new 30k byte array on each mutation. But you are still adding a lot of overhead to your program.
- dwohnitmok 5y ago
  > Persistent data structures exist and work very well but they still remain way slower than alternatives that don't support persistence. Depending on your definition of "way" this is true. A lot of persistent vector-like structures can have quite good performance, but if your runtime is dominated by iteration and random updating, you will still get a speed up by using raw arrays, i.e. guaranteed contiguous blocks of memory. > This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks. This is not. The whole point of immutable data structures and concurrency is that iterating over them does not require any locks because the structure won't change! So concurrent reads require absolutely no new code and certainly no locks. For concurrent writes, the usual strategy is a single CAS-like operation at the top-level to swap out the old immutable structure for a new one (e.g. Clojure atoms, Java AtomicReferences, Haskell IORefs, etc.). But that's a single thing for the whole structure, not every level. In general concurrent update in the functional programming world is handled by CAS not locks.
  - UncleMeat 5y ago
    CAS still has a lock in actual memory.
    - dwohnitmok 5y ago
      Not necessarily. Depends on the underlying hardware implementation (with different answers for e.g. x86 vs ARM) since software CAS usually is implemented as a single CPU instruction. This is also stretching the definition of "lock" quite a bit because usually CAS is used to implement lock-free and wait-free concurrency. But regardless at most, even in hardware, it's a single top-level lock, and sometimes not even that. Not one along every level of a data structure.
- tomp 5y ago
  > This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks. Um, what? Persistent data structures don't require locks at all (because they're immutable), in fact using them in a multithreaded way is 100% safe and thus much easier than their mutable (and ordinarily more efficient) counterparts.
  - UncleMeat 5y ago
    Refcounted gc means you need locking on refcounts or you can lose your tree during iteration.
    - tomp 5y ago
      Can you provide a list of reference-counted functional languages?
karmakaze 5y ago
I was thinking along the same lines. Is an "atom" in Clojure like STM where the structure/reference is changed in a highly controlled manner?
- Sinidir 5y ago
  atoms are containers that require no coordination so its a simple Compare and swap. There are Refs that require transactions and change of multiple Refs is coordinated in these transactions. WIth that Clojure has an implementation of Software Transaction Memory.
memco 5y ago
I really enjoyed this presentation on how roc-lang is being designed to handle optimization using opportunistic in-place mutation: https://yewtu.be/watch?v=vzfy4EKwG_Y&t=1328 https://yewtu.be/watch?v=vzfy4EKwG_Y&t=1328.
tomp 5y ago
Persistent data structures are very hard. It's basically impossible to cleanly combine them. E.g. if you have an immutable hashtable that contains immutable lists, and you want to modify a list - how do you know if the inner list changed or not (you don't want to be creating new hashtables if the elements don't change). They work in the small, but don't truly scale.
- mrkeen 5y ago
  > how do you know if the inner list changed or not This is a vital question that virtually every programming language overlooks. If you are using a mainstream language, you do not know if they were modified. If you use a language which has a type system to segregate mutable operations from immutable operations, then you know if they were modified. > They work in the small, but don't truly scale. Go even bigger then. Work with the kind of data that won't fit in memory. Put your data on disk - you can't insert into the middle of a 1GB+ file.
- nlitened 5y ago
  > you want to modify a list - how do you know if the inner list changed or not You know for sure that inner list did _not_ change, because it is immutable. Someone else might have a reference to an updated hashtable with an updated inner list, but the one you hold will never change—isn’t that the whole idea of immutable data structures?
  - tomp 5y ago
    No, I mean "update" in the persistent sense - create a new list, with some (or none) elements changed/added/removed. e.g. say you have a method remove_all_in_values that takes an int x and a hashmap of list of int, and returns a new hashmap of list of int, with x removed from each element of the hashmap. Obviously you'd use something like List.filter for the inner operation, but most functional programming languages give you no indication whether the result of filter is the same list (i.e. element is not present) or a new list (i.e. some elements were removed). So how do you know if you create a new hashtable or return the old one? One solution is complex, the other is wasteful.

UncleMeat 5y ago

Persistent data structures exist and work very well but they still remain way slower than alternatives that don't support persistence. This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks. Add in the GC overhead and you've got a meaningful problem. Yes, you aren't constructing an entirely new 30k byte array on each mutation. But you are still adding a lot of overhead to your program.

dwohnitmok 5y ago
> Persistent data structures exist and work very well but they still remain way slower than alternatives that don't support persistence. Depending on your definition of "way" this is true. A lot of persistent vector-like structures can have quite good performance, but if your runtime is dominated by iteration and random updating, you will still get a speed up by using raw arrays, i.e. guaranteed contiguous blocks of memory. > This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks. This is not. The whole point of immutable data structures and concurrency is that iterating over them does not require any locks because the structure won't change! So concurrent reads require absolutely no new code and certainly no locks. For concurrent writes, the usual strategy is a single CAS-like operation at the top-level to swap out the old immutable structure for a new one (e.g. Clojure atoms, Java AtomicReferences, Haskell IORefs, etc.). But that's a single thing for the whole structure, not every level. In general concurrent update in the functional programming world is handled by CAS not locks.
- UncleMeat 5y ago
  CAS still has a lock in actual memory.
  - dwohnitmok 5y ago
    Not necessarily. Depends on the underlying hardware implementation (with different answers for e.g. x86 vs ARM) since software CAS usually is implemented as a single CPU instruction. This is also stretching the definition of "lock" quite a bit because usually CAS is used to implement lock-free and wait-free concurrency. But regardless at most, even in hardware, it's a single top-level lock, and sometimes not even that. Not one along every level of a data structure.
tomp 5y ago
> This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks. Um, what? Persistent data structures don't require locks at all (because they're immutable), in fact using them in a multithreaded way is 100% safe and thus much easier than their mutable (and ordinarily more efficient) counterparts.
- UncleMeat 5y ago
  Refcounted gc means you need locking on refcounts or you can lose your tree during iteration.
  - tomp 5y ago
    Can you provide a list of reference-counted functional languages?

karmakaze 5y ago

I was thinking along the same lines. Is an "atom" in Clojure like STM where the structure/reference is changed in a highly controlled manner?

Sinidir 5y ago
atoms are containers that require no coordination so its a simple Compare and swap. There are Refs that require transactions and change of multiple Refs is coordinated in these transactions. WIth that Clojure has an implementation of Software Transaction Memory.

memco 5y ago

I really enjoyed this presentation on how roc-lang is being designed to handle optimization using opportunistic in-place mutation: https://yewtu.be/watch?v=vzfy4EKwG_Y&t=1328 https://yewtu.be/watch?v=vzfy4EKwG_Y&t=1328.

tomp 5y ago

Persistent data structures are very hard. It's basically impossible to cleanly combine them. E.g. if you have an immutable hashtable that contains immutable lists, and you want to modify a list - how do you know if the inner list changed or not (you don't want to be creating new hashtables if the elements don't change). They work in the small, but don't truly scale.

mrkeen 5y ago
> how do you know if the inner list changed or not This is a vital question that virtually every programming language overlooks. If you are using a mainstream language, you do not know if they were modified. If you use a language which has a type system to segregate mutable operations from immutable operations, then you know if they were modified. > They work in the small, but don't truly scale. Go even bigger then. Work with the kind of data that won't fit in memory. Put your data on disk - you can't insert into the middle of a 1GB+ file.
nlitened 5y ago
> you want to modify a list - how do you know if the inner list changed or not You know for sure that inner list did _not_ change, because it is immutable. Someone else might have a reference to an updated hashtable with an updated inner list, but the one you hold will never change—isn’t that the whole idea of immutable data structures?
- tomp 5y ago
  No, I mean "update" in the persistent sense - create a new list, with some (or none) elements changed/added/removed. e.g. say you have a method remove_all_in_values that takes an int x and a hashmap of list of int, and returns a new hashmap of list of int, with x removed from each element of the hashmap. Obviously you'd use something like List.filter for the inner operation, but most functional programming languages give you no indication whether the result of filter is the same list (i.e. element is not present) or a new list (i.e. some elements were removed). So how do you know if you create a new hashtable or return the old one? One solution is complex, the other is wasteful.