4 ms·

> 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

> 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.
  - kephasp 4y ago
    > Do you mean to say the compiler will insert locks? I think you're right, it's the compiler that'll insert the locks according to the semantics of the language. > For an out-of-order superscalar machine, mutability has nothing to do with it; Yes it does, because it creates data dependencies. If a piece of code B loads the contents of memory where a piece of code A writes that's before B, then you can never execute B before or in parallel with A.
    - agalunar 4y ago
      > If a piece of code B loads the contents of memory where a piece of code A writes that's before B, then you can never execute B before or in parallel with A. This is a description of what a data dependency is; I'm still not sure what your point is regarding mutable data structures specifically.
      - kephasp 4y ago
        A mutable data structure will have such data dependencies all around. An immutable data structure cannot, because it will never be written in after creation.
        agalunar 4y ago
        But an immutable data structure will cause data dependencies – the only way it couldn't cause a data dependency would be if it was never read.
        kephasp 4y ago
        But once it is created, all pieces of code accessing it can be executed in any order because there will never be a write on it again.
- kadoban 4y ago
  Take your favorite immutable data structure. Fix it in your mind. Now, call it mutable, but don't change a thing. Congratulations, it's now a mutable data structure that's exactly as fast as your favorite immutable one. _But_ you now have extra opterations you can perform to optimize slow parts if you can. You have strictly more power than you started with, because you can modify data. You don't have to, but you can. Just don't make any bad optimizations. If some attempt to make it better instead makes it worse, go back to the starting point and try something else.
  - kephasp 4y ago
    Do you have examples of this idea that were implemented and weren't insanely error-prone?
    - kadoban 4y ago
      The key is that you can start with any immutable data structure you like and change it as much as you want until it stops performing as desired. If that's errors (inability to reason about it correctly) or some other issue, doesn't really matter. The point is that this procedure applies to anything. Immutable data structures are a strict subset of mutable ones. Every immutable data structure is open to moving any number of steps, in any direction, in the space of data structures. It's _purely_ extra freedom that immutable data structures don't have. If you want specific ones, first things that would come to mind for me is to start with any immutable tree impl, and start adding small mutable ~caching things on top. Batch up updates a bit to try to avoid repeated deep traversals maybe. You can do this without adding much complexity at all, and it's very flexibly for whatever operations or access patterns you want to improve.
      - kephasp 4y ago
        Look for actual examples in the wild that weren't error prone and I'd be surprised you'll find any. I get that you can imagine it. I'm saying it wouldn't work in practice.
        4y ago
- adwn 4y ago
  You seem to forget that the CPU and memory system, on which you're executing your immutable data structure implementations, provide a fundamentally mutable interface. So the compiler of your immutable language will still have to insert locks and atomic instructions (although not necessarily the same or at the same places).
  - kephasp 4y ago
    > So the compiler of your immutable language will still have to insert locks No it won't, not at the myriads of places they're needed when there are mutations all over the place. Of course there are mutations in FP, so of course sometimes we need write locks and use things like CAS. The point is not that FP doesn't use them, but that it uses them far less because they are needed only in a very limited number of places. When I write code with STM, for example, the only uses of locks or CAS are in the STM engine, not in my Haskell code, and not even in my compiled code, because my code only ever reads memory that's immutable, and immutable data structures. When I write pure code, there are no locks at all. And that makes it trivial to execute in parallel, either out of order or on several cores.
Kamq 4y ago
> It's literally not possible for this to be true. The most obvious operation that's much faster for an immutable data structure is cloning. Cloning, say, an array in a mutable system takes O(n) time. Cloning in an immutable system is just returning the pointer (or whatever pointer + length struct you're using to represent an array).
- klipt 4y ago
  Updating an element in a mutable array is O(1). With an immutable array you have to make a clone with one element changed which is O(n). Cloning a mutable array is also O(1) if you use copy-on-write.
  - Kamq 4y ago
    > Updating an element in a mutable array is O(1). Yes. Yes it is. The structures have different performance characteristics for different operations.
  - thaumasiotes 4y ago
    > Cloning a mutable array is also O(1) if you use copy-on-write. Note that this is just an example of the idea that mutable structures can achieve anything immutable structures can, by just treating them as if they're immutable. While you're using copy-on-write, your mutable array can be cloned in constant time and updated in linear time, presenting the exact characteristics of an immutable array. The mutable "equivalent" algorithm is much nastier, though, since, after you do the cloning, you'll need to create the new object (the slow, O(n) clone) as soon as you want to update either the new structure or the old one. In the functional paradigm, this is also the case -- but you're always generating a new object that you're about to use, as opposed to generating a new object because something else somewhere else in the code was watching you. For example, if you have an array, and you update it (forcing it to be realized), and then you update it a second time, you can't rely on the first time you updated it to prove that the second update will be fast. Maybe it was cloned between the updates.
kephasp 4y ago
> It's literally not possible for this to be true When you need a state that you can rollback, an immutable data structure lets you share the parts of the structure that didn't change between states. That's what ZFS does and that's also how many transactional databases store data. A mutable data structure would need an entire copy at each state change or it would need to store deltas and apply them backwards when you rollback. Both options are significantly slower than the immutable data structure (where rollback means updating a single pointer).
- adwn 4y ago
  Those immutable data structures of ZFS are implemented in C and C++, where everything is mutable. You're actually confirming kadoban's point: Mutable data structures can pretend to be immutable or partially immutable, so there can never be an immutable data structure that's faster than all possible mutable data structures. And I'm pretty sure that if ZFS creates an updated version of some immutable node, under the hood it does this via something that resembles a memcpy() followed by a mutable modification of one or more struct members.
  - kephasp 4y ago
    You're misunderstanding ZFS' persistent data structure. It's the whole point that it's not doing a copy then modifying something. Also no one claims there's one immutable data structure that's faster than all mutable data structures. That's a ridiculous strawman argument.
    - adwn 4y ago
      > You're misunderstanding ZFS' persistent data structure. It's the whole point that it's not doing a copy then modifying something. I'm talking about the internal implementation of those data structures, not about their API. Neither C nor C++ have built-in immutable data structures, so those persistent data structures with their immutable API are implemented using mutable C structs or C++ classes. > Also no one claims there's one immutable data structure that's faster than all mutable data structures. That's a ridiculous strawman argument. No, you're misunderstanding what I said: For any given abstract functionality or interface (like a key->value map, or a graph composed of vertices and edges), there exists a mutable data structure which is at least as fast as all immutable data structures that provide the same interface. That's because the set of mutable data structures is a strict superset of (i.e., contains all) the set of immutable data structures.

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.
- kephasp 4y ago
  > Do you mean to say the compiler will insert locks? I think you're right, it's the compiler that'll insert the locks according to the semantics of the language. > For an out-of-order superscalar machine, mutability has nothing to do with it; Yes it does, because it creates data dependencies. If a piece of code B loads the contents of memory where a piece of code A writes that's before B, then you can never execute B before or in parallel with A.
  - agalunar 4y ago
    > If a piece of code B loads the contents of memory where a piece of code A writes that's before B, then you can never execute B before or in parallel with A. This is a description of what a data dependency is; I'm still not sure what your point is regarding mutable data structures specifically.
    - kephasp 4y ago
      A mutable data structure will have such data dependencies all around. An immutable data structure cannot, because it will never be written in after creation.
      - agalunar 4y ago
        But an immutable data structure will cause data dependencies – the only way it couldn't cause a data dependency would be if it was never read.
        kephasp 4y ago
        But once it is created, all pieces of code accessing it can be executed in any order because there will never be a write on it again.
kadoban 4y ago
Take your favorite immutable data structure. Fix it in your mind. Now, call it mutable, but don't change a thing. Congratulations, it's now a mutable data structure that's exactly as fast as your favorite immutable one. _But_ you now have extra opterations you can perform to optimize slow parts if you can. You have strictly more power than you started with, because you can modify data. You don't have to, but you can. Just don't make any bad optimizations. If some attempt to make it better instead makes it worse, go back to the starting point and try something else.
- kephasp 4y ago
  Do you have examples of this idea that were implemented and weren't insanely error-prone?
  - kadoban 4y ago
    The key is that you can start with any immutable data structure you like and change it as much as you want until it stops performing as desired. If that's errors (inability to reason about it correctly) or some other issue, doesn't really matter. The point is that this procedure applies to anything. Immutable data structures are a strict subset of mutable ones. Every immutable data structure is open to moving any number of steps, in any direction, in the space of data structures. It's _purely_ extra freedom that immutable data structures don't have. If you want specific ones, first things that would come to mind for me is to start with any immutable tree impl, and start adding small mutable ~caching things on top. Batch up updates a bit to try to avoid repeated deep traversals maybe. You can do this without adding much complexity at all, and it's very flexibly for whatever operations or access patterns you want to improve.
    - kephasp 4y ago
      Look for actual examples in the wild that weren't error prone and I'd be surprised you'll find any. I get that you can imagine it. I'm saying it wouldn't work in practice.
      - 4y ago
adwn 4y ago
You seem to forget that the CPU and memory system, on which you're executing your immutable data structure implementations, provide a fundamentally mutable interface. So the compiler of your immutable language will still have to insert locks and atomic instructions (although not necessarily the same or at the same places).
- kephasp 4y ago
  > So the compiler of your immutable language will still have to insert locks No it won't, not at the myriads of places they're needed when there are mutations all over the place. Of course there are mutations in FP, so of course sometimes we need write locks and use things like CAS. The point is not that FP doesn't use them, but that it uses them far less because they are needed only in a very limited number of places. When I write code with STM, for example, the only uses of locks or CAS are in the STM engine, not in my Haskell code, and not even in my compiled code, because my code only ever reads memory that's immutable, and immutable data structures. When I write pure code, there are no locks at all. And that makes it trivial to execute in parallel, either out of order or on several cores.

Kamq 4y ago

> It's literally not possible for this to be true. The most obvious operation that's much faster for an immutable data structure is cloning. Cloning, say, an array in a mutable system takes O(n) time. Cloning in an immutable system is just returning the pointer (or whatever pointer + length struct you're using to represent an array).

klipt 4y ago
Updating an element in a mutable array is O(1). With an immutable array you have to make a clone with one element changed which is O(n). Cloning a mutable array is also O(1) if you use copy-on-write.
- Kamq 4y ago
  > Updating an element in a mutable array is O(1). Yes. Yes it is. The structures have different performance characteristics for different operations.
- thaumasiotes 4y ago
  > Cloning a mutable array is also O(1) if you use copy-on-write. Note that this is just an example of the idea that mutable structures can achieve anything immutable structures can, by just treating them as if they're immutable. While you're using copy-on-write, your mutable array can be cloned in constant time and updated in linear time, presenting the exact characteristics of an immutable array. The mutable "equivalent" algorithm is much nastier, though, since, after you do the cloning, you'll need to create the new object (the slow, O(n) clone) as soon as you want to update either the new structure or the old one. In the functional paradigm, this is also the case -- but you're always generating a new object that you're about to use, as opposed to generating a new object because something else somewhere else in the code was watching you. For example, if you have an array, and you update it (forcing it to be realized), and then you update it a second time, you can't rely on the first time you updated it to prove that the second update will be fast. Maybe it was cloned between the updates.

kephasp 4y ago

> It's literally not possible for this to be true When you need a state that you can rollback, an immutable data structure lets you share the parts of the structure that didn't change between states. That's what ZFS does and that's also how many transactional databases store data. A mutable data structure would need an entire copy at each state change or it would need to store deltas and apply them backwards when you rollback. Both options are significantly slower than the immutable data structure (where rollback means updating a single pointer).

adwn 4y ago
Those immutable data structures of ZFS are implemented in C and C++, where everything is mutable. You're actually confirming kadoban's point: Mutable data structures can pretend to be immutable or partially immutable, so there can never be an immutable data structure that's faster than all possible mutable data structures. And I'm pretty sure that if ZFS creates an updated version of some immutable node, under the hood it does this via something that resembles a memcpy() followed by a mutable modification of one or more struct members.
- kephasp 4y ago
  You're misunderstanding ZFS' persistent data structure. It's the whole point that it's not doing a copy then modifying something. Also no one claims there's one immutable data structure that's faster than all mutable data structures. That's a ridiculous strawman argument.
  - adwn 4y ago
    > You're misunderstanding ZFS' persistent data structure. It's the whole point that it's not doing a copy then modifying something. I'm talking about the internal implementation of those data structures, not about their API. Neither C nor C++ have built-in immutable data structures, so those persistent data structures with their immutable API are implemented using mutable C structs or C++ classes. > Also no one claims there's one immutable data structure that's faster than all mutable data structures. That's a ridiculous strawman argument. No, you're misunderstanding what I said: For any given abstract functionality or interface (like a key->value map, or a graph composed of vertices and edges), there exists a mutable data structure which is at least as fast as all immutable data structures that provide the same interface. That's because the set of mutable data structures is a strict superset of (i.e., contains all) the set of immutable data structures.