Skip to main content
Software Engineering

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

2
  • Thank you! Your answer is very informative. Basically, using the example above, the object can be totally thread-safe and without any locking, if I can perform the switch in a single, atomic operation. Add, Set, and other operations will either be performed on the non-optimized version -- which means you'll get an non-optimized version back -- or on the optimized version. Gets might optimize the data structure twice, but the result will always be the same. The results will be indistinguishable. Except that if you get a non-optimized version back, it will still need to be optimized. Commented Oct 6, 2012 at 19:59
  • That's the idea, yes. It's worth noting that the optimal design for a persistent data structure depends how it's used. For example, suppose one designs a data structure so that most items hold a link to an earlier version and a list of changes that have been applied to it. If one wants to change something 1,000 times and be able to access all 1,001 versions of it, such a structure can be very efficient. On the other hand, if one won't anything older than the 100th-latest version, replacing the 100th-latest version's link to older versions with a copy of the data may save time and memory. Commented Oct 6, 2012 at 22:27