3 ms·

Of course there's no way to know in O(1) time if you've done two edits that just so happen to sum to no-op, regardless of if you're using Immutable.js or not.

Of course there's no way to know in O(1) time if you've done two edits that just so happen to sum to no-op, regardless of if you're using Immutable.js or not. However, depending on how to implement undo, you might be in good shape with Immutable.js. For example: you might keep a stack of the last few changed data around, and an undo could just pop off the stack in which case you can know if your oldData === newData in O(1). --- Keeping dirty bits around to determine when you need to operate on your data again is totally viable, there's nothing wrong with that approach, especially for smaller applications. Some frameworks designed for large applications even employ this technique. For larger applications, in my experience, the dirty bits tend to add up and create a lot of state management overhead, and soon you find a majority of your code cautiously stepping around mutable state instead of just making your application do what it's supposed to do. The primary thesis of Immutable.js (and persistent data structures in general) is to illuminate the option of having data which promises to never change and thus making memoization trivial. If you have an application which can take advantage of memoization for real performance improvements, then using these kinds of structures can be a big win.

taeric 12y ago
If you are doing a stack, that trick works fairly easily with a mutable stack, as well. Regardless, I was not trying to toss out immutable structures with the bathwater. They are both incredibly cool and useful. Usually fairly memory intensive, though that is less of a deal today than it was in days past. Also, fairly cache unfriendly. For many applications, this is not a main concern. (32 way branching vectors, I'm looking at you.) And yes, if you have a plethora of dirty bits, that could be difficult. If you have a plethora of immutable collections, that will lead to the same trouble. Consider, the optimization at stake here is essentially adding a single "isDirty" method to existing collections that is only set true on modifications and has a "clear" method. (There are other ways this can be done, just going for the easy way.) Far from difficult to encapsulate and get the O(1) dirty checking for cheap. And I agree that applications with many dirty bits to check are difficult. You don't exactly dodge this with immutable collections. That is, in my experience, larger applications that have a lot of immutable collections tend to create a lot of management over old/new collections. Not shockingly, the trouble seems to be when you expand the scope of what you are doing wider and wider. Not necessarily how you are keeping track of modified collections.

taeric 12y ago

If you are doing a stack, that trick works fairly easily with a mutable stack, as well. Regardless, I was not trying to toss out immutable structures with the bathwater. They are both incredibly cool and useful. Usually fairly memory intensive, though that is less of a deal today than it was in days past. Also, fairly cache unfriendly. For many applications, this is not a main concern. (32 way branching vectors, I'm looking at you.) And yes, if you have a plethora of dirty bits, that could be difficult. If you have a plethora of immutable collections, that will lead to the same trouble. Consider, the optimization at stake here is essentially adding a single "isDirty" method to existing collections that is only set true on modifications and has a "clear" method. (There are other ways this can be done, just going for the easy way.) Far from difficult to encapsulate and get the O(1) dirty checking for cheap. And I agree that applications with many dirty bits to check are difficult. You don't exactly dodge this with immutable collections. That is, in my experience, larger applications that have a lot of immutable collections tend to create a lot of management over old/new collections. Not shockingly, the trouble seems to be when you expand the scope of what you are doing wider and wider. Not necessarily how you are keeping track of modified collections.