5 ms·

This is not how persistent data structures are used in practice. There is no "the" new version of a persistent structure. The best analogy I can think of is to

This is not how persistent data structures are used in practice. There is no "the" new version of a persistent structure. The best analogy I can think of is to compare it to a VCS (e.g. git). There is no need to lock any existing commit in order to create a new commit (which together with prior commits, represents a new version of the code).

majormajor 7y ago
I'm not familiar with Clojure, but you can hit conflicts in the Git world, though, which seem to be what the parent is concerned about. Two of us could be creating some new data based on the last data we had, at time T, and then the other person submits theirs at time T+5, and I submit mine at time T+10. In that case, my change hasn't taken theirs into account.
- escherize 7y ago
  If you can "submit" your change back to the original datastructure then the original datastructure is not immutable, right? Here's a nice explaination about how the persistant immutable datastructures work: https://hypirion.com/musings/understanding-persistent-vector-pt-1 https://hypirion.com/musings/understanding-persistent-vector...
  - setr 7y ago
    I believe the question is that, if two threads take the same immutable vector, and both make a change to it independently, they'll end up with two new vectors (eg two branches in git); a vector that reflects thread1's change, and a second vector that reflects thread2's change. So now you have a conflict, which requires resolution; git has a human intervene. eg x = [1,2,3] Thread1 -> x + [4] => [1,2,3,4] Thread2 -> x + [5] => [1,2,3,5] But you were expecting [1,2,3,4,5] Reality was that you wanted an order to your events, normally enforced by locking, which the immutable vector doesn't seem to help you with; they were both able to update independently, but you actually wanted them to update dependently. If you try to use immutable datastructures to avoid locking, then how is conflict resolution handled? I think the answer would be that it doesn't help you avoid locking; either you lock & share a single reference to the latest version of your immutable vector, to enforce ordered events, or you define a resolution strategy separately. The immutability aspect just stops you from not having a resolution strategy -- which would always be incorrect And if I understand correctly, the ideal scenario for immutable datastructures in concurrent scenarios is when you can define such a merge strategy (and safely give threads their own copy of the datastructure to muddle with, without actually having to copy the entire datastructure)
    - dpratt71 7y ago
      You could, as per your example, use locking as part of a resolution/merge strategy to combine the results of two separate computations running on two separate threads. Or you could use some strategy that does not involve locking. Either way, it does not support the original claim I disputed that "Immutable structures still require locking".
      - setr 7y ago
        >Either way, it does not support the original claim I disputed that "Immutable structures still require locking". It does, if you believe serialization by locking is the main strategy to handle serialization (in which case, mutable or immutable, you still need to lock), and so... you still need locking. Serialization being the main scenario GP gave. Your original answer didn't resolve the problem either -- fine, you didn't need to lock when adding elements to your immutable structure, but you still haven't reached serialization; you've just pushed the problem back another step. The answer that I believe GP would need to correct his understanding, (and much more importantly, the answer that I'm interested in :-) is what serialization strategies does immutable datastructures enable, if not locking? The other correction GP seems to require is whether serialization is actually that important in general, and whether functional programmers tend to experience otherwise... But I don't care about that answer :-)
        Scarbutt 7y ago
        the answer that I'm interested in :-) is what serialization strategies does immutable datastructures enable, if not locking? Depending on your performance goals, Compare-and-Set with retries a la clojure's atom reference construct. https://clojure.org/reference/atoms https://clojure.org/reference/atoms
        dpratt71 7y ago
        Oh goodness :) OP has conceded the point, but you're still down to argue on the basis of what a person may or may not believe is the main strategy to handle serialization. I give up. You win, I guess. Regards your other question(s), I will just add that I answered many similar questions for myself (as well as disabusing myself of a lot of misconceptions) by undertaking to get a basic understanding of Haskell.
- dpratt71 7y ago
  In brief, these sorts of conflicts simply do not arise in a fully persistent data structure. You may have a situation where you have a persistent data structure together with one or more mutable references, each to some version of the data structure. Yes, a modification to one of these mutable references would need to be synchronized, but they are separate from the persistent data structure itself. Again using git as an example, there is the persistent data structure, aka the commit graph, as well as mutable references to commits, aka branches. A change to what commit a branch references needs to be synchronized.
  - kubanczyk 7y ago
    I concede. If you have algorithm to do the `git merge` equivalent without human help, I guess no locking or STM is needed. Although that's very costly in implementation. It's great to have git as a mental model in this discussion, really useful.
    - dpratt71 7y ago
      Whether the "merge" implementation is costly or complicated very much depends on exactly what it has to do. The git example is pretty much a worst case example in this regard. An easier example could be that you have a tree structure that represents a mathematical expression. The evaluation of every node could proceed on its own lightweight thread. The merge strategy would be to simply perform the appropriate operation on the results produced by the threads evaluating the child nodes.
      - kubanczyk 7y ago
        I don't get math expressions example at all. One thread modifies one value, so there is no (mutability) problem to solve. You have customers' orders to buy items. One last item remains at your store. You accept one order and update HEAD. You accept another order in parallel and follow to merge. "Merge" here means that you need to return money to the customer and send out an apology e-mail. More cumbersome than locking, isn't it? But possible, yes.
- bjoli 7y ago
  That would be problematic using non-immutable datastructures as well as you might end up with incorrect order or even nonsensical data if you don't use locking. Having used immutable data structures and concurrency in non-clojure languages, I mostly resort to something like concurrentML for concurrency. Message passing lets you solve situations like that in more elegant ways.

majormajor 7y ago

I'm not familiar with Clojure, but you can hit conflicts in the Git world, though, which seem to be what the parent is concerned about. Two of us could be creating some new data based on the last data we had, at time T, and then the other person submits theirs at time T+5, and I submit mine at time T+10. In that case, my change hasn't taken theirs into account.

escherize 7y ago
If you can "submit" your change back to the original datastructure then the original datastructure is not immutable, right? Here's a nice explaination about how the persistant immutable datastructures work: https://hypirion.com/musings/understanding-persistent-vector-pt-1 https://hypirion.com/musings/understanding-persistent-vector...
- setr 7y ago
  I believe the question is that, if two threads take the same immutable vector, and both make a change to it independently, they'll end up with two new vectors (eg two branches in git); a vector that reflects thread1's change, and a second vector that reflects thread2's change. So now you have a conflict, which requires resolution; git has a human intervene. eg x = [1,2,3] Thread1 -> x + [4] => [1,2,3,4] Thread2 -> x + [5] => [1,2,3,5] But you were expecting [1,2,3,4,5] Reality was that you wanted an order to your events, normally enforced by locking, which the immutable vector doesn't seem to help you with; they were both able to update independently, but you actually wanted them to update dependently. If you try to use immutable datastructures to avoid locking, then how is conflict resolution handled? I think the answer would be that it doesn't help you avoid locking; either you lock & share a single reference to the latest version of your immutable vector, to enforce ordered events, or you define a resolution strategy separately. The immutability aspect just stops you from not having a resolution strategy -- which would always be incorrect And if I understand correctly, the ideal scenario for immutable datastructures in concurrent scenarios is when you can define such a merge strategy (and safely give threads their own copy of the datastructure to muddle with, without actually having to copy the entire datastructure)
  - dpratt71 7y ago
    You could, as per your example, use locking as part of a resolution/merge strategy to combine the results of two separate computations running on two separate threads. Or you could use some strategy that does not involve locking. Either way, it does not support the original claim I disputed that "Immutable structures still require locking".
    - setr 7y ago
      >Either way, it does not support the original claim I disputed that "Immutable structures still require locking". It does, if you believe serialization by locking is the main strategy to handle serialization (in which case, mutable or immutable, you still need to lock), and so... you still need locking. Serialization being the main scenario GP gave. Your original answer didn't resolve the problem either -- fine, you didn't need to lock when adding elements to your immutable structure, but you still haven't reached serialization; you've just pushed the problem back another step. The answer that I believe GP would need to correct his understanding, (and much more importantly, the answer that I'm interested in :-) is what serialization strategies does immutable datastructures enable, if not locking? The other correction GP seems to require is whether serialization is actually that important in general, and whether functional programmers tend to experience otherwise... But I don't care about that answer :-)
      - Scarbutt 7y ago
        the answer that I'm interested in :-) is what serialization strategies does immutable datastructures enable, if not locking? Depending on your performance goals, Compare-and-Set with retries a la clojure's atom reference construct. https://clojure.org/reference/atoms https://clojure.org/reference/atoms
      - dpratt71 7y ago
        Oh goodness :) OP has conceded the point, but you're still down to argue on the basis of what a person may or may not believe is the main strategy to handle serialization. I give up. You win, I guess. Regards your other question(s), I will just add that I answered many similar questions for myself (as well as disabusing myself of a lot of misconceptions) by undertaking to get a basic understanding of Haskell.
dpratt71 7y ago
In brief, these sorts of conflicts simply do not arise in a fully persistent data structure. You may have a situation where you have a persistent data structure together with one or more mutable references, each to some version of the data structure. Yes, a modification to one of these mutable references would need to be synchronized, but they are separate from the persistent data structure itself. Again using git as an example, there is the persistent data structure, aka the commit graph, as well as mutable references to commits, aka branches. A change to what commit a branch references needs to be synchronized.
- kubanczyk 7y ago
  I concede. If you have algorithm to do the `git merge` equivalent without human help, I guess no locking or STM is needed. Although that's very costly in implementation. It's great to have git as a mental model in this discussion, really useful.
  - dpratt71 7y ago
    Whether the "merge" implementation is costly or complicated very much depends on exactly what it has to do. The git example is pretty much a worst case example in this regard. An easier example could be that you have a tree structure that represents a mathematical expression. The evaluation of every node could proceed on its own lightweight thread. The merge strategy would be to simply perform the appropriate operation on the results produced by the threads evaluating the child nodes.
    - kubanczyk 7y ago
      I don't get math expressions example at all. One thread modifies one value, so there is no (mutability) problem to solve. You have customers' orders to buy items. One last item remains at your store. You accept one order and update HEAD. You accept another order in parallel and follow to merge. "Merge" here means that you need to return money to the customer and send out an apology e-mail. More cumbersome than locking, isn't it? But possible, yes.
bjoli 7y ago
That would be problematic using non-immutable datastructures as well as you might end up with incorrect order or even nonsensical data if you don't use locking. Having used immutable data structures and concurrency in non-clojure languages, I mostly resort to something like concurrentML for concurrency. Message passing lets you solve situations like that in more elegant ways.