News for hackers. Stuff that matters.
Re:Comparing Elixir and Go by jondubois on Friday January 27, 2017 @04:41AM (#13498741)
That sounds a bit better than I thought but it still doesn't change the worst-case complexity.
Re:Comparing Elixir and Go by axiomabsolute on Friday January 27, 2017 @08:47AM (#13499741)
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-Ok...) [2] http://hypirion.com/musings/understanding-persistent-vector-... [3] https://www.youtube.com/watch?v=7BFF50BHPPo

Re:Comparing Elixir and Go by jlouis on Friday January 27, 2017 @07:27AM (#13499337)
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.

Re:Comparing Elixir and Go by pdimitar on Wednesday February 01, 2017 @05:28PM (#13546029)
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.

Re:Comparing Elixir and Go by fetbaffe on Friday January 27, 2017 @05:07AM (#13498836)
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.