4 ms·

My main gripe with immutability is that making updated data requires building a full copy of the data again with the changes. Sure, you could have zippers to ai

by gatane 2y ago

My main gripe with immutability is that making updated data requires building a full copy of the data again with the changes. Sure, you could have zippers to aid in the updating process by acting as a kind of cursor/pointer, but raw access to data beats them anytime (even if you optimize for cache). So if you had to optimize for raw speed, why not choose mutable data? https://ksvi.mff.cuni.cz/~sefl/papers/zippers.pdf https://ksvi.mff.cuni.cz/~sefl/papers/zippers.pdf

dsQTbR7Y5mRHnZv 2y ago
> My main gripe with immutability is that making updated data requires building a full copy of the data again with the changes. Conceptually yes, but the implementation doesn't always necessarily need to work that way under the hood: https://www.roc-lang.org/functional#opportunistic-mutation https://www.roc-lang.org/functional#opportunistic-mutation
- deleted 2y ago
  [deleted]
munchler 2y ago
> My main gripe with immutability is that making updated data requires building a full copy of the data again with the changes. That is not true in general. There are plenty of data structures that can be updated without forcing a full copy. Lists, trees, sets, maps, etc. All of these are common in functional programming. This is discussed in the article (e.g. "Append-Only Computing").
- sarchertech 2y ago
  If you really care about performance, iterating over all of those is going to much much slower than iterating over an array.
  - munchler 2y ago
    If you really care about multi-threading, mutating array elements is going to be much buggier than using an immutable data structure.
    - sarchertech 2y ago
      Well sure but the OP wrote >if you had to optimize for raw speed, why not choose mutable data? So in context we are talking about a case where we have to optimize for raw speed. It doesn’t matter that immutable data is easier to reason about if you don’t have the performance budget to go that route.
      - reubenmorais 2y ago
        Raw speed these days means concurrent processing, so those two are more and more often the same case. The whole "rewrite it in Rust" trend is a very clear example of the benefits of easier correctness of concurrent programming - Rust programs end up being faster than other alternatives even though on paper C has better "raw speed" (e.g. no bounds checking).
        sarchertech 2y ago
        1. Raw speed on modern CPUs means taking advantage of data locality more than anything else. Even concurrency. Cache misses will cost you a few hundred cycles, far too much to make up for with concurrency in most cases. 2. Of course given a sufficiently large array, iterating over it with 16 processors is faster than with 1. Arrays still dominate other data structures for raw performance here. 3. Concurrency doesn’t just mean multi threading. SIMD instructions can perform simultaneous operations on multiple operands in your array. Can’t do this with a linked list.
        reubenmorais 2y ago
        Yes you can write a very fast SIMD loop over densely packed data. But if that data is mutable and you need to acquire a lock before you work with it, it's very easy to lose all the performance you gained. Immutability can reduce coordination costs and improve effective parallelism. For a similar reason immutability also helps you write code with fewer data races.
cratermoon 2y ago
https://dl.acm.org/doi/10.1145/356635.356640 https://dl.acm.org/doi/10.1145/356635.356640
mrkeen 2y ago
Someone should try it with postgres. Make a raw speed branch that gets rid of the overhead of mvcc: while querying a database each transaction sees a snapshot of data (a database version) as it was some time ago, regardless of the current state of the underlying data https://www.postgresql.org/docs/7.1/mvcc.html
- ahoka 2y ago
  That’s not exactly how PostgreSQL works. This is true only at certain isolation levels.
KingMob 2y ago
> My main gripe with immutability is that making updated data requires building a full copy of the data again with the changes. That's not generally true. Many immutable languages are using "persistent" data structures, where "persist" here means that much of the original structure persists in the new one. For more, see: - Purely Functional Data Structures by Okasaki: https://www.cs.cmu.edu/~rwh/students/okasaki.pdf https://www.cs.cmu.edu/~rwh/students/okasaki.pdf - Phil Bagwell's research - e.g., https://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf https://infoscience.epfl.ch/record/64398/files/idealhashtree...

by gatane 2y ago

dsQTbR7Y5mRHnZv 2y ago

> My main gripe with immutability is that making updated data requires building a full copy of the data again with the changes. Conceptually yes, but the implementation doesn't always necessarily need to work that way under the hood: https://www.roc-lang.org/functional#opportunistic-mutation https://www.roc-lang.org/functional#opportunistic-mutation

deleted 2y ago
[deleted]

munchler 2y ago

> My main gripe with immutability is that making updated data requires building a full copy of the data again with the changes. That is not true in general. There are plenty of data structures that can be updated without forcing a full copy. Lists, trees, sets, maps, etc. All of these are common in functional programming. This is discussed in the article (e.g. "Append-Only Computing").

sarchertech 2y ago
If you really care about performance, iterating over all of those is going to much much slower than iterating over an array.
- munchler 2y ago
  If you really care about multi-threading, mutating array elements is going to be much buggier than using an immutable data structure.
  - sarchertech 2y ago
    Well sure but the OP wrote >if you had to optimize for raw speed, why not choose mutable data? So in context we are talking about a case where we have to optimize for raw speed. It doesn’t matter that immutable data is easier to reason about if you don’t have the performance budget to go that route.
    - reubenmorais 2y ago
      Raw speed these days means concurrent processing, so those two are more and more often the same case. The whole "rewrite it in Rust" trend is a very clear example of the benefits of easier correctness of concurrent programming - Rust programs end up being faster than other alternatives even though on paper C has better "raw speed" (e.g. no bounds checking).
      - sarchertech 2y ago
        1. Raw speed on modern CPUs means taking advantage of data locality more than anything else. Even concurrency. Cache misses will cost you a few hundred cycles, far too much to make up for with concurrency in most cases. 2. Of course given a sufficiently large array, iterating over it with 16 processors is faster than with 1. Arrays still dominate other data structures for raw performance here. 3. Concurrency doesn’t just mean multi threading. SIMD instructions can perform simultaneous operations on multiple operands in your array. Can’t do this with a linked list.
        reubenmorais 2y ago
        Yes you can write a very fast SIMD loop over densely packed data. But if that data is mutable and you need to acquire a lock before you work with it, it's very easy to lose all the performance you gained. Immutability can reduce coordination costs and improve effective parallelism. For a similar reason immutability also helps you write code with fewer data races.

cratermoon 2y ago

https://dl.acm.org/doi/10.1145/356635.356640 https://dl.acm.org/doi/10.1145/356635.356640

mrkeen 2y ago

Someone should try it with postgres. Make a raw speed branch that gets rid of the overhead of mvcc: while querying a database each transaction sees a snapshot of data (a database version) as it was some time ago, regardless of the current state of the underlying data https://www.postgresql.org/docs/7.1/mvcc.html

ahoka 2y ago
That’s not exactly how PostgreSQL works. This is true only at certain isolation levels.

KingMob 2y ago

> My main gripe with immutability is that making updated data requires building a full copy of the data again with the changes. That's not generally true. Many immutable languages are using "persistent" data structures, where "persist" here means that much of the original structure persists in the new one. For more, see: - Purely Functional Data Structures by Okasaki: https://www.cs.cmu.edu/~rwh/students/okasaki.pdf https://www.cs.cmu.edu/~rwh/students/okasaki.pdf - Phil Bagwell's research - e.g., https://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf https://infoscience.epfl.ch/record/64398/files/idealhashtree...