7 ms·

> Functional programming is a reaction from the shift to the dangerous quadrant of the immutable-mutable/unshared-shared "Magic Quadrant" chart. This makes it

> Functional programming is a reaction from the shift to the dangerous quadrant of the immutable-mutable/unshared-shared "Magic Quadrant" chart. This makes it sound like you’re saying that’s why functional programming was created, which isn’t the case. I assume you mean that this is why it’s gained popularity but I don’t really agree with that - it’s certainly valuable but most functional programmers will never touch threads. I’d argue that programs without state are just easier to reason about and debug and for most software this is where the value comes from.

klipt 4y ago
> I’d argue that programs without state are just easier to reason about and debug Right, isn't the fundamental trade-off between programmer efficieny and runtime efficiency? Immutable structures are easier to reason about, but almost always run slower than their mutable counterparts. The holy grail would be immutable structures that are equally performant, but I'm not sure that's even mathematically possible in general.
- kephasp 4y ago
  Is there data supporting the notion that immutable structures are slower? There are many cases where there won't be a single difference in performance and there are a bunch of cases where immutable structures will be way faster than mutable ones.
  - philipkglass 4y ago
    The most obvious case I'm aware of is with numerical simulations in scientific computing. I worked on molecular simulations in graduate school. The core data structures are large (many-gigabytes) arrays, and almost every element of the array is updated on every iteration. Everything that requires more memory or even more memory accesses is going to be slower. In business applications you're usually not updating everything in a data structure all the time, so I can see how clever immutability may improve performance.
    - kephasp 4y ago
      But a huge mutable data structure means you can't cache the content between cores of a CPU or between systems in a cluster. So you're describing a scenario where mutability incurs a serious performance penalty. And why are you saying that requiring more memory would make a program slower? I don't see the link.
      - philipkglass 4y ago
        In one of these simulations, the logic is something like "calculate all the new positions and velocities of the molecules in a box, updated by one micro time step." It's implemented by updating a bunch of matrices in-place by mutation, often using linear algebra subroutines provided by a high performance BLAS like OpenBLAS or the one from Intel's MKL. The matrices are large enough that you'll have to page to disk if you return a new matrix from an old matrix instead of updating the matrix in-place. That's why requiring more memory makes it slower. At the hardware level, transforming a numerical array M1 into M2 by mutation in-place requires a certain number of memory reads and writes. Leaving the old matrix M1 untouched and returning M2 as a new value (in the immutable style) means that you require at least as many memory accesses as before, but cache locality is likely worse because you're not updating the same address region you are reading from. So I'd expect numerical simulations based on immutable programming techniques to run slower than current simulation tools (like NAMD, AMBER, GROMACS) that perform mutation in-place.
        kephasp 4y ago
        I wonder if the loss of locality would be compensated by the better concurrency of the overall process… I'd be interested to see benchmarks.
  - kadoban 4y ago
    > There are many cases where there won't be a single difference in performance and there are a bunch of cases where immutable structures will be way faster than mutable ones. Have you maybe written this backwards? It's literally not possible for this to be true. Mutable data structures have strictly more operations that they're allowed to do, how would they be slower? At very worst they could ignore modifications and be exactly as fast as an immutable data structure.
    - kephasp 4y ago
      When you use a mutable data structure, and your code is concurrent, you'll force the CPU to put locks everywhere in your code so that several cores won't see stale data in their internal caches. Even when you aren't writing concurrent code, mutability will prevent the CPU from using its internal concurrency to execute it faster. Also, immutable data structures can include caches that are extremely simple whereas mutable data structure would face the problem if cache invalidation if they tried. And a mutable data structure that would operate as if it's immutable? That's a nice recipe for an epic disaster.
      - agalunar 4y ago
        > When you use a mutable data structure, and your code is concurrent, you'll force the CPU to put locks everywhere in your code so that several cores won't see stale data in their internal caches. Do you mean to say the compiler will insert locks? As far as I'm aware, on AMD64/Intel64, the processor won't lock the bus for ordinary loads and stores unless an instruction has the lock prefix. The processor is otherwise perfectly happy to let different cores observe loads and stores to different addresses in different orders (except for stores being reordered past each other). > Even when you aren't writing concurrent code, mutability will prevent the CPU from using its internal concurrency to execute it faster. For an out-of-order superscalar machine, mutability has nothing to do with it; register renaming takes care of that. The things to watch out for are tight dependencies chains. If you're referring to loads and stores, store-forwarding and coalescing can spare you from having to hit the cache repeatedly for reads and writes to the same location.
- philipkglass 4y ago
  It's not possible to do always but it feels like it should be possible in special cases. If you can prove that a value V2 is ultimately derived from a modification of V1, and V1 is never referenced after creating V2, then it should be possible to invisibly convert this to an in-place mutation [1]. In the case of applying a bunch of text normalization rules to a string, for example, I care about the final string but not the intermediate states. It could be mutation underneath and I'd be none the wiser, except that the runtime performance would be better. In Scala you can add a "@tailrec" annotation to recursive functions. The annotation means that the function is guaranteed to recurse efficiently (without growing the stack) OR that the compiler will give an error telling you why it can't be guaranteed. I could imagine a similar annotation like "@withmutation" for functions where you want to guarantee efficient in-place mutation at runtime. As it is, when I run into performance pain points in Scala I redo the critical bits with (manually written) while-loops and imperative mutation. [1] Unless you later attach a debugger and expect to be able to observe V1 and V2 simultaneously. But I presume this sort of issue already comes up and is somehow dealt with regarding other compiler optimizations.
  - cassepipe 4y ago
    I think this is the idea behind Richard Feldman's Roc programming language https://www.roc-lang.org/ https://www.roc-lang.org/
  - riwsky 4y ago
    And just like that, you’ve invented Rust!
  - frostwarrior 4y ago
    AFAIK this is the idea behind ImmutableJS: https://immutable-js.com/ https://immutable-js.com/
  - lyxsus 4y ago
    Isn’t it similar to linear types in haskell?
    - eru 4y ago
- eru 4y ago
  Immutability is something that happens at the level of the programming language. Runtime efficiency is a concept that, unsurprisingly, lives at runtime. When eg a Haskell program runs, its supposedly immutable datastructures get mutated all the time. For example laziness is one way that happens. Another example is that a (pure) Scheme program will overwrite the same memory addresses over and over again while it is running, just like a C program would. Conceptually, no mutation happens, it's just that the garbage collector constantly frees up memory that will be get re-used immediately.

klipt 4y ago

> I’d argue that programs without state are just easier to reason about and debug Right, isn't the fundamental trade-off between programmer efficieny and runtime efficiency? Immutable structures are easier to reason about, but almost always run slower than their mutable counterparts. The holy grail would be immutable structures that are equally performant, but I'm not sure that's even mathematically possible in general.

kephasp 4y ago
Is there data supporting the notion that immutable structures are slower? There are many cases where there won't be a single difference in performance and there are a bunch of cases where immutable structures will be way faster than mutable ones.
- philipkglass 4y ago
  The most obvious case I'm aware of is with numerical simulations in scientific computing. I worked on molecular simulations in graduate school. The core data structures are large (many-gigabytes) arrays, and almost every element of the array is updated on every iteration. Everything that requires more memory or even more memory accesses is going to be slower. In business applications you're usually not updating everything in a data structure all the time, so I can see how clever immutability may improve performance.
  - kephasp 4y ago
    But a huge mutable data structure means you can't cache the content between cores of a CPU or between systems in a cluster. So you're describing a scenario where mutability incurs a serious performance penalty. And why are you saying that requiring more memory would make a program slower? I don't see the link.
    - philipkglass 4y ago
      In one of these simulations, the logic is something like "calculate all the new positions and velocities of the molecules in a box, updated by one micro time step." It's implemented by updating a bunch of matrices in-place by mutation, often using linear algebra subroutines provided by a high performance BLAS like OpenBLAS or the one from Intel's MKL. The matrices are large enough that you'll have to page to disk if you return a new matrix from an old matrix instead of updating the matrix in-place. That's why requiring more memory makes it slower. At the hardware level, transforming a numerical array M1 into M2 by mutation in-place requires a certain number of memory reads and writes. Leaving the old matrix M1 untouched and returning M2 as a new value (in the immutable style) means that you require at least as many memory accesses as before, but cache locality is likely worse because you're not updating the same address region you are reading from. So I'd expect numerical simulations based on immutable programming techniques to run slower than current simulation tools (like NAMD, AMBER, GROMACS) that perform mutation in-place.
      - kephasp 4y ago
        I wonder if the loss of locality would be compensated by the better concurrency of the overall process… I'd be interested to see benchmarks.
- kadoban 4y ago
  > There are many cases where there won't be a single difference in performance and there are a bunch of cases where immutable structures will be way faster than mutable ones. Have you maybe written this backwards? It's literally not possible for this to be true. Mutable data structures have strictly more operations that they're allowed to do, how would they be slower? At very worst they could ignore modifications and be exactly as fast as an immutable data structure.
  - kephasp 4y ago
    When you use a mutable data structure, and your code is concurrent, you'll force the CPU to put locks everywhere in your code so that several cores won't see stale data in their internal caches. Even when you aren't writing concurrent code, mutability will prevent the CPU from using its internal concurrency to execute it faster. Also, immutable data structures can include caches that are extremely simple whereas mutable data structure would face the problem if cache invalidation if they tried. And a mutable data structure that would operate as if it's immutable? That's a nice recipe for an epic disaster.
    - agalunar 4y ago
      > When you use a mutable data structure, and your code is concurrent, you'll force the CPU to put locks everywhere in your code so that several cores won't see stale data in their internal caches. Do you mean to say the compiler will insert locks? As far as I'm aware, on AMD64/Intel64, the processor won't lock the bus for ordinary loads and stores unless an instruction has the lock prefix. The processor is otherwise perfectly happy to let different cores observe loads and stores to different addresses in different orders (except for stores being reordered past each other). > Even when you aren't writing concurrent code, mutability will prevent the CPU from using its internal concurrency to execute it faster. For an out-of-order superscalar machine, mutability has nothing to do with it; register renaming takes care of that. The things to watch out for are tight dependencies chains. If you're referring to loads and stores, store-forwarding and coalescing can spare you from having to hit the cache repeatedly for reads and writes to the same location.
philipkglass 4y ago
It's not possible to do always but it feels like it should be possible in special cases. If you can prove that a value V2 is ultimately derived from a modification of V1, and V1 is never referenced after creating V2, then it should be possible to invisibly convert this to an in-place mutation [1]. In the case of applying a bunch of text normalization rules to a string, for example, I care about the final string but not the intermediate states. It could be mutation underneath and I'd be none the wiser, except that the runtime performance would be better. In Scala you can add a "@tailrec" annotation to recursive functions. The annotation means that the function is guaranteed to recurse efficiently (without growing the stack) OR that the compiler will give an error telling you why it can't be guaranteed. I could imagine a similar annotation like "@withmutation" for functions where you want to guarantee efficient in-place mutation at runtime. As it is, when I run into performance pain points in Scala I redo the critical bits with (manually written) while-loops and imperative mutation. [1] Unless you later attach a debugger and expect to be able to observe V1 and V2 simultaneously. But I presume this sort of issue already comes up and is somehow dealt with regarding other compiler optimizations.
- cassepipe 4y ago
  I think this is the idea behind Richard Feldman's Roc programming language https://www.roc-lang.org/ https://www.roc-lang.org/
- riwsky 4y ago
  And just like that, you’ve invented Rust!
- frostwarrior 4y ago
  AFAIK this is the idea behind ImmutableJS: https://immutable-js.com/ https://immutable-js.com/
- lyxsus 4y ago
  Isn’t it similar to linear types in haskell?
  - eru 4y ago
eru 4y ago
Immutability is something that happens at the level of the programming language. Runtime efficiency is a concept that, unsurprisingly, lives at runtime. When eg a Haskell program runs, its supposedly immutable datastructures get mutated all the time. For example laziness is one way that happens. Another example is that a (pure) Scheme program will overwrite the same memory addresses over and over again while it is running, just like a C program would. Conceptually, no mutation happens, it's just that the garbage collector constantly frees up memory that will be get re-used immediately.