6 ms·

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 ther

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

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.