4 ms·

You only need to copy the data if the consumer of the data changes it, i.e. copy-on-write.

by fetbaffe 10y ago

jondubois 10y ago
That sounds a bit better than I thought but it still doesn't change the worst-case complexity.
- fetbaffe 10y ago
  Depends on the scenario, if you know a value never changes, you can share that between variables under the hood, as the article explains with the example about sorting arrays. Passing around complex mutable structures feels more like procedural programs.
- jlouis 10y ago
  Consider a binary tree. You don't have to copy the whole tree, which is O(n) but rather only the "spine" path from the altered element to the top, which is O(lg n). In practice, there are also many cases which ends up on the stack and never reaches the heap, so the memory allocation needs are somewhat smaller than what people think. Another point is that short-lived garbage is collected in O(1) time in the GC. So you don't pay for its collection either. Things are slower than a mutation, but the overhead is lower than people tend to think.
- axiomabsolute 10y ago
  The canonical text discussing how this is achieved refers to data structures optimized for immutability as "purely functional data structures". [1] These type of data structures are the default for Clojure as well, and there are a number of blog posts and presentations discussing their implementation. [2] [3] It's a reasonably complicated topic, but the basic idea is that since the data structures are immutable, much of their structure can be shared between versions with few changes. Most of these data structures end up using a Tree of some sort. Performance characteristics can be influenced to an extent by using bucketing to control the width/height of the tree. [1] : Purely Functional Data Structures (Amazon: https://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...) [2] http://hypirion.com/musings/understanding-persistent-vector-pt-1 http://hypirion.com/musings/understanding-persistent-vector-... [3] https://www.youtube.com/watch?v=7BFF50BHPPo https://www.youtube.com/watch?v=7BFF50BHPPo
- pdimitar 10y ago
  Both Erlang and Elixir have access to Erlang's ETS (an OS-process-local cache) and it is sparingly used in the cases when mutability is undoubtedly the more efficient approach. The FP folk aren't close-minded about this. They just use mutability only when it's provably more performant than their builtin immutable data structures.

You only need to copy the data if the consumer of the data changes it, i.e. copy-on-write.

jondubois 10y ago

That sounds a bit better than I thought but it still doesn't change the worst-case complexity.

fetbaffe 10y ago
Depends on the scenario, if you know a value never changes, you can share that between variables under the hood, as the article explains with the example about sorting arrays. Passing around complex mutable structures feels more like procedural programs.
jlouis 10y ago
Consider a binary tree. You don't have to copy the whole tree, which is O(n) but rather only the "spine" path from the altered element to the top, which is O(lg n). In practice, there are also many cases which ends up on the stack and never reaches the heap, so the memory allocation needs are somewhat smaller than what people think. Another point is that short-lived garbage is collected in O(1) time in the GC. So you don't pay for its collection either. Things are slower than a mutation, but the overhead is lower than people tend to think.
axiomabsolute 10y ago
The canonical text discussing how this is achieved refers to data structures optimized for immutability as "purely functional data structures". [1] These type of data structures are the default for Clojure as well, and there are a number of blog posts and presentations discussing their implementation. [2] [3] It's a reasonably complicated topic, but the basic idea is that since the data structures are immutable, much of their structure can be shared between versions with few changes. Most of these data structures end up using a Tree of some sort. Performance characteristics can be influenced to an extent by using bucketing to control the width/height of the tree. [1] : Purely Functional Data Structures (Amazon: https://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...) [2] http://hypirion.com/musings/understanding-persistent-vector-pt-1 http://hypirion.com/musings/understanding-persistent-vector-... [3] https://www.youtube.com/watch?v=7BFF50BHPPo https://www.youtube.com/watch?v=7BFF50BHPPo
pdimitar 10y ago
Both Erlang and Elixir have access to Erlang's ETS (an OS-process-local cache) and it is sparingly used in the cases when mutability is undoubtedly the more efficient approach. The FP folk aren't close-minded about this. They just use mutability only when it's provably more performant than their builtin immutable data structures.