> I have timed immmutable/persistent collections against
> regular ones and found the immutable collections
> significantly slower for basic operations. However this
> isn't representative of how you would normally use the
> immutable collections. In particular it doesn't account
> for time saved by not having to copy a collection. You can
> thus only assess overall performance in the context of a
> specific real application.
>
> In my work I often make a complex set of changes to a set
> of data and then assess whether the result is acceptable
> (feasible). If it isn't feasible, then the changes have to
> be reversed. If the data set as a whole is immutable, then
> that undo is achieved by simply keeping a reference to its
> previous state. With mutable data structures you either
> make a complete copy or actually perform the undo
> operations, in either case at significant cost in CPU
> and/or code complexity.

As you say, it all depends on the application. If the data change a lot, then it makes sense to modify a copy of them. If only a small subset of the data changes, it's better for performance reasons to just keep the changes and change the original data (assuming we are talking about data sizes that can visibly affect performance).

It's really nice to see the tables documenting performance characteristics on the linked page:
http://lampwww.epfl.ch/~odersky/whatsnew/collections-api/collections_40.html

But...my application is very sensitive to memory consumption; many kinds of Maps and Map-like structures, some dense, some sparse. The Java Collection classes are extremely memory hungry. It would be really nice to see the memory-performance of the various implementations documented too.

michael