1

A critical part of my algorithm involves cloning Sets of objects. I have attempted several approaches to optimizing this operation, including:

  • Reusing the elements, so that I only need shallow copying - big performance gain.
  • Relying on the clone method of the sets, rather than manually inserting the objects - minor performance gain (see below for probable reason).
  • Making the classes containing the set maintain a copy-on-write flag, so that cloning those objects is O(1) and only upon insertion / removal are the sets cloned - some performance gain.
  • Finally I've also thought whether I can drop this approach altogether, but that's a topic for another question :)

However, profiling reveals the cloning operation still takes a significant amount of time. I can live with it, but I've been wondering if there are any tricks that will allow me to further optimize this operation - for instance, I've heard about a trick for cloning via serialization, though I'm not sure that will help.

I'm also open for switching to a different implementation of the Java's Set interface, as long as it relies on hashCode and equals. My sets are typically not very large, up to dozens of items, so I'm also willing to sacrifice some efficiency from the traditional set operators (add, contains) if it can help. I've even considered moving to a custom implementation backed by a LinkedList or some skip list, but before that I wanted to ask here if anyone has any experience or insight regarding this.

EDIT: for those asking why I need to clone these sets so many times - it's a good question! Right now the algorithm relies on initializing one group of sets to be identical to another group of sets, and later both groups may be independently updated, which is why cloning seemed like the obvious solution for me - but a better solution might definitely exist. As I've wrote in the 4th bullet above I might indeed choose a different solution, but meanwhile I'd like to focus this question on optimizing the existing one.

2
  • 2
    It would help if you said why you need to clone the set. If it's to prevent modifications, just wrap it with Collections.unmodifiableSet. If it's related to concurrent access, you may want to synchronize the accesses, or use a ConcurrentSet.
    – JB Nizet
    Jan 5, 2012 at 13:15
  • @JBNizet updated the question - hope it helps. No concurrency is involved.
    – Oak
    Jan 5, 2012 at 13:48

1 Answer 1

0

Serialization is much slower than deep cloning. I doubt it will help.

The most performant solution is to avoid needing to clone in the first place, then it won't take any time at all. Perhaps with more details as to why you are using cloning we can suggest an alternative.

One way to speed up the cloning is to have a Set which refers to an immutable set and remembers the differences in say a Map<E, Boolean> where the value is true or false depending on whether it has been added or removed. This would work best if the number of changes is relatively low.

1
  • I like this suggestion very much, but I fear it might be problematic when I have a chain of objects cloned from each other... cloning the last object will require copying not just one pointer to an immutable sets, but a lot of them.
    – Oak
    Jan 5, 2012 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.