2 ms·
'I'm not sure how the periodic snapshot would "come out ahead" with the mutation free version.' A snapshot of freely mutated memory is a O(N) copy. A snapshot
by dllthomas 12y ago
'I'm not sure how the periodic snapshot would "come out ahead" with the mutation free version.'
A snapshot of freely mutated memory is a O(N) copy.
A snapshot of a immutable tree is a single O(1) pointer copy (you just need to save the root).
Doing a full copy every change would be tremendously costly (substantially more than the penalty for walking the tree on that change, and probably overwhelming the overhead ofr walking the tree on reads).
Doing a full copy every hojillion steps would of course amortize to cheap (and probably the overhead from walking a tree for reads and writes would overwhelm it).
Anything real will of course fall somewhere between. As I said, constants are tremendously context dependent.
Note that this (of course) doesn't speed up the mutation free version - but if you have the constraint of wanting regular (or otherwise cheap) snapshots then using the mutation-free version can be the cheapest way of doing that.
I don't know the details of the DLX algorithm, or adaptations to it, well enough to say much about it in particular off the top of my head. I'd love to dig into it at some point, but I've unfortunately got higher priorities presently.
- taeric 12y agoThis is assuming a very naive snapshot of a mutated memory block. I would assume that if you were doing something that needed snapshots of each instant of the program, you would come up with a much more sane algorithm for getting that done. It would probably use many of the same tricks as the immutable structures. Which is why I would assume they would be equal. (That is, I realize that immutable structures don't do a full copy on every "change." Depending on the structure and the change, they don't even do a copy at all.) Consider, we basically just described how git works, no?
- dllthomas 12y agoWell, certainly nothing stops you from using the immutable version and calling it mutable (it just happens to do no mutation!). But my point is that it's a nontrivial modification compared to other approaches to enabling snapshotting, and it's a good tool to have in your belt for that kind of situation. Particularly interesting, genuinely "persistent" data structures (as used by Okasaki in Purely Functional Data Structures - which is a fantastic read and tons of fun) can give amortized worst-case bounds even in the presence of a malicious consumer of the data structure picking which operations to run against which historical versions of the object.
- taeric 12y agoI meant more of the same strategies. Data sharing and the like. In a mutable language this can be done by simply updating the head pointer easily enough. In a non-mutable language this is tougher in some respects. This is pretty much the thing that tripped up a ton of folks back from the early days of java. "Why doesn't x.replaceAll('a', 'b') change the value of x?" was not an uncommon mistake to encounter. DLX is actually a great example of this sort of thing, as the whole point is that the operation to remove an item from a doubly linked list can be reversed to add the item back just from looking at the item that was removed. And again, consider the way that git works. Nobody would call c and the techniques they use immutable, but the underlying data structure is. More directly put, I am not calling for all data structures in a classical "mutation based program" to be mutable. I am curious about some of the more famous mutation based algorithms and if there are good comparisons to the analogous versions. There was a great post here a few weeks ago about the blind spot in functional programmers in building trees. Having just seen the "threaded trees" for what I think is my first time, I have to confess it took me longer to make than I would have thought. Mainly because I was trying to hold on to some of the "immutable" methods of programming.
- dllthomas 12y ago"I meant more of the same strategies. Data sharing and the like." Certainly it is possible to find alternative constructions that work. Occasionally these may still be faster. However, I strongly contest that it's "tougher" in a non-mutable context. Specifically: 'In a mutable language this can be done by simply updating the head pointer easily enough. In a non-mutable language this is tougher in some respects.' This is wrong. The hard part about this is making sure old things pointed at by existing snapshots don't change. If your data is immutable, you get that for free. Moreover, in terms of complexity of the system, (mutating algorithm + a bunch of stuff to capture the mutations) is likely to be messier than the nonmutating algorithm (which is sometimes cleaner than the mutating version to begin with, but certainly not always). Also, note that you've moved to talking about "mutable languages", we had been talking about algorithms. 'This is pretty much the thing that tripped up a ton of folks back from the early days of java. "Why doesn't x.replaceAll('a', 'b') change the value of x?" was not an uncommon mistake to encounter.' Which is clearly a problem with "non-mutable languages"? The problem there is that the Java paradigm had been strongly mutation oriented and then they dropped an incongruous mutation-free "method that is really more of a function" in there. Clarity and consistency are important in any setting. "DLX is actually a great example of this sort of thing, as the whole point is that the operation to remove an item from a doubly linked list can be reversed to add the item back just from looking at the item that was removed." But you can't do that if you might be sharing those lists with someone else. The point is that the constraints imposed by immutability are often the most effective means of addressing other constraints, and so study of these things is quite valuable. This thread has never been "Haskell is much better because it doesn't let you mutate anything!" - both because I've already acknowledged that in many settings the mutable versions of algorithms are preferable and because Haskell does let you mutate things (you just have to be explicit about what). "And again, consider the way that git works. Nobody would call c and the techniques they use immutable, but the underlying data structure is." As an aside, you can write C with very little mutation going on, if that's what you want to do. I've not looked at the git source, so I have no idea the degree to which they do. As I said, though, that's an aside - my main point here is that immutable data, and algorithms working with it, are valuable and there are situations where they are the best solution even where mutation is "allowed" and even where a mutation-heavy version might be preferred in a slightly different setting. "There was a great post here a few weeks ago about the blind spot in functional programmers in building trees." A cursory search isn't turning this up - it sounds interesting. Do you have the link?